快速在线增量学习混合流数据_在线学习和增量学习资源-CSDN文库

182 浏览量 2021-03-06 10:47:05 上传评论收藏 1.16MB PDF 举报

流数据的爆炸式增长为特征学习方法带来挑战，包括线性判别分析（LDA）。许多现有的LDA算法效率不高，不足以按顺序以各种方式到达的样本进行增量更新。首先，我们提出了一种新的快速批处理LDA（FLDA / QR）学习算法，该算法使用聚类中心求解下三角系统，并通过Cholesky分解对其进行了优化。为了利用矩阵的内在增量机制，我们进一步开发了一种精确的增量算法（IFLDA / QR）。与大多数现有方法的排名第一的QR更新相比，在IFLDA / QR中进行正交化的Gram-Schmidt过程显着节省了空间和时间。 IFLDA / QR能够处理流数据。包含1）现有类别中的新标记样本，2），全新（新颖）类别的样本，更重要的是，3）大量示例与1中的样本混合）和.2）。理论分析和数值实验都证明，与现有技术相比，其空间和时间成本要低得多（快2到10倍），并且具有可比的分类精度。 ### 快速在线增量学习混合流数据 #### 摘要随着移动网络、社交媒体以及视频摄像头等领域的迅速发展，流数据的增长呈现爆炸式的趋势。这些流数据的特点为连续不断且规模庞大，对传统的特征学习方法提出了巨大挑战，尤其是线性判别分析（Linear Discriminant Analysis，简称LDA）。许多现有的LDA算法在处理按顺序到来的数据时效率较低，无法有效地进行增量更新。针对这一问题，本文提出了一种新的快速批量LDA（Fast Batch LDA/QR，简称FLDA/QR）学习算法，该算法利用聚类中心来解决下三角系统，并通过Cholesky分解进行了优化。为了更好地利用矩阵的固有增量机制，还进一步开发了一种精确的增量算法（Incremental Fast LDA/QR，简称IFLDA/QR）。在IFLDA/QR中，通过Gram-Schmidt正交化过程显著地减少了空间和时间开销，与大多数现有方法的一阶QR更新相比具有明显优势。IFLDA/QR能够处理含有以下三类流数据：1）现有类别中的新标记样本；2）全新（新颖）类别的样本；3）与前两类样本混合的大量样本。理论分析和数值实验表明，与现有技术相比，IFLDA/QR在时间和空间成本上具有显著优势（快2至10倍），同时保持了可比的分类精度。 #### 引言在过去十年中，随着移动网络、社交媒体以及视频监控等领域的快速发展，流数据的产生速度呈爆炸性增长。这些流数据具有实时性强、规模大、种类繁多等特点，对传统的数据分析方法构成了巨大挑战。对于此类数据，需要一种高效且能够进行增量学习的方法。特别是当这些数据混合着已知或未知的类标签，一次一个或成块地到达时，传统方法往往难以应对。因此，本研究旨在开发一种极其快速的增量学习方法来处理混合流数据。 ### 研究背景与动机流数据通常具有以下特点： 1. **数据量大**：流数据的规模通常非常庞大。 2. **实时性强**：数据持续不断地产生并需要即时处理。 3. **多样性**：流数据可能包含多个不同的类别的数据，这些类别可能是已知的也可能是未知的。 4. **变化性**：随着时间推移，流数据的特性可能会发生变化，这要求学习模型能够适应这种变化。针对以上特点，传统的LDA算法存在不足之处： 1. **计算复杂度高**：传统的LDA算法在处理大规模数据时计算复杂度较高，尤其是在需要增量更新的情况下。 2. **内存占用大**：大量的数据存储需求增加了内存的负担。 3. **缺乏灵活性**：面对动态变化的数据流，传统的LDA算法很难做到实时调整。 ### 主要贡献本研究的主要贡献如下： 1. **提出FLDA/QR算法**：通过使用聚类中心解决下三角系统，并通过Cholesky分解进行优化，提高了算法的效率。 2. **开发IFLDA/QR算法**：进一步改进了算法，使得它能够利用矩阵的固有增量机制，通过Gram-Schmidt正交化过程减少空间和时间开销。 3. **处理混合流数据**：IFLDA/QR算法能够有效处理包含新标记样本、全新类别样本以及与这两类样本混合的大量样本。 4. **性能优越**：通过理论分析和实验验证，IFLDA/QR算法在时间和空间成本方面显著优于现有技术，同时保持了较高的分类精度。 #### 实验结果通过对不同规模和类型的流数据进行实验验证，结果显示IFLDA/QR算法在处理时间、内存占用等方面表现出色。与现有技术相比，IFLDA/QR算法可以实现2至10倍的速度提升，这对于处理大规模流数据至关重要。此外，IFLDA/QR算法还能保持与现有技术相当的分类精度，这表明该算法不仅速度快而且准确率高。 ### 结论本研究针对流数据的特点，提出了一种高效的快速在线增量学习算法IFLDA/QR。该算法在处理混合流数据方面表现出了显著的优势，能够有效地应对现有类别中的新标记样本、全新类别样本以及这些样本的混合情况。通过理论分析和实验验证，IFLDA/QR算法在时间和空间成本方面表现出色，且保持了较高的分类精度，为处理大规模流数据提供了一种有效的解决方案。

资源推荐

资源详情

资源评论

Fast Online Incremental Learning on Mixture Streaming Data

Yi Wang, Xin Fan, Zhongxuan Luo

School of Software

Dalian University of Technology

& Key Laboratory for Ubiquitous Network

and Service Software of Liaoning Province

Dalian, China

{dlutwangyi, xin.fan, zxluo}@dlut.edu.cn

Tianzhu Wang

No. 254, Deta Leisure Town

Jinzhou New District

Dalian, China

wangtz@126.com

Maomao Min

School of Software

Dalian University of Technology

Dalian, China

neilfvhv@gmail.com

Jiebo Luo

Department of Computer Science

University of Rochester

Rochester, NY 14627, USA

jluo@cs.rochester.edu

Abstract

The explosion of streaming data poses challenges to fea-

ture learning methods including linear discriminant anal-

ysis (LDA). Many existing LDA algorithms are not efﬁ-

cient enough to incrementally update with samples that se-

quentially arrive in various manners. First, we propose a

new fast batch LDA (FLDA/QR) learning algorithm that

uses the cluster centers to solve a lower triangular system

that is optimized by the Cholesky-factorization. To take ad-

vantage of the intrinsically incremental mechanism of the

matrix, we further develop an exact incremental algorithm

(IFLDA/QR). The Gram-Schmidt process with reorthogonal-

ization in IFLDA/QR signiﬁcantly saves the space and time

expenses compared with the rank-one QR-updating of most

existing methods. IFLDA/QR is able to handle streaming data

containing 1) new labeled samples in the existing classes, 2)

samples of an entirely new (novel) class, and more signiﬁ-

cantly, 3) a chunk of examples mixed with those in 1) and

2). Both theoretical analysis and numerical experiments have

demonstrated much lower space and time costs (2 ∼ 10 times

faster) than the state of the art, with comparable classiﬁcation

accuracy.

Introduction

Streaming data are explosive with the boom of mobile net-

works, social media, and video cameras in this decade.

To analyze this type of data, an efﬁcient and incremen-

tal learning strategy is necessary. Moreover, these data are

mixed with known or novel class labels, arriving one by

one or chunk by chunk. These characteristics greatly chal-

lenge the existing learning methods. We aim at developing

an extremely fast incremental learning method for mixture

streaming data.

 2017, Association for the Advancement of Artiﬁcial

Classical linear discriminant analysis (LDA) (Chen et al.

2000) and its recent variants (Sharma and Paliwal 2015;

Kong and Ding 2014; Luo, Ding, and Huang 2011) can ef-

fectively extract features for classiﬁcation. Recently, incre-

mental LDA (ILDA) methods have been emerging to address

the above challenges arisen from streaming data. Some of

these ILDA methods attempt to modify the objective func-

tion, while others use new optimization strategies to accel-

erate the calculation speed. The method of IDR/QR (Ye et

al. 2005) uses the QR-decomposition to update the within-

class scatter matrix (S

) and between-class scatter matrix

). The methods of ICLDA (Lu, Zou, and Wang 2012),

IDR/new (Lu, Jian, and Wang 2015) and ILDA/QR (Chu et

al. 2015) also follow the idea of using QR-decomposition,

and employ various techniques to reduce the matrix size for

the decomposition. However, their updating schemes, the

key to any incremental algorithms, are not space and time

efﬁcient for online learning.

Researchers also resort to the approximation of scattering

matrices for efﬁciency improvements. Liu et al. (Liu, Jiang,

and Zhou 2009) give the least-square solution of LDA (LS-

ILDA), but the incrementally update of the pseudo-inverse

of the data matrix is still time consuming. Kim et al. (Kim et

al. 2011) leverage the sufﬁcient spanning set approximation

to S

and the total scatter matrix S

by updating the princi-

pal eigenvectors and eigenvalues of these two matrices. The

time complexity signiﬁcantly decreases, but there exists an

evident gap between the accuracies of incremental and batch

versions.

In this paper, we devise an online incremental LDA al-

gorithm that requires much (2 ∼ 10 times) less computa-

tion complexity and smaller space than the state-of-the-art

for mixture streaming data. The algorithm is illustrated in

Fig. 1. Speciﬁcally, our contributions are twofold:

1. We take advantage of the QR-decomposition on a lower

triangular matrix (Chu et al. 2015), and propose a new

Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17)

2739

Figure 1: The proposed method incrementally updates the

feature space given by new information from a mixture

streaming data.

fast batch method, called FLDA/QR. This algorithm takes

the centroid of each cluster to constitute the matrix for

decomposition, requiring a smaller storage and less com-

putation. Furthermore, we greatly reduce the computation

load of the QR-decomposition in FLDA/QR by using the

Cholesky-factorization.

2. We develop an exact incremental version of FLDA/QR,

i.e, IFLDA/QR. It is possible for us to update upon the

Gram-Schmidt reorthogonalization process (Daniel et

al. 1976) thanks to the well-deﬁned intrinsic incremen-

tal mechanism of our FLDA/QR. The updating is sim-

pler and signiﬁcantly more efﬁcient than the rank-one

updating in many other ILDA algorithms based on QR-

decomposition.

The new IFLDA/QR algorithm has the ﬂexibility to han-

dle streaming data that may contain 1) new labeled sam-

ples to the existing classes, 2) samples from an entirely new

(novel) class, and more signiﬁcantly, 3) a chunk of sam-

ples mixed with those as 1) and 2). Both theoretical analysis

and numerical experiments on several benchmark data sets

validate the lowest computational costs of FLDA/QR and

IFLDA/QR compared with the state-of-the-art batch LDA

and incremental LDA algorithms, respectively. Meanwhile,

the classiﬁcation accuracies of FLDA/QR and IFLDA/QR

are close or equal to those of the existing algorithms.

Linear Discriminant Analysis

Classical LDA algorithm attempts to project data examples

into a feature space, where those from different classes are

separated as much as possible. Let linearly independent data

matrix X ∈ R

d×n

be partitioned into k clusters as X =

,...,X

}, where X

∈ R

d×n

(i =1, 2,...,k) and

n =



i=1

Deﬁne the between-class scatter S

, the within-class scat-

ter S

, and the total scatter S

, where S

= S

+ S

. The

trace of S

, Trace(S

), measures the separation between

clusters, where Trace(S

) gives the closeness within a

cluster. Therefore, the objective of LDA is to ﬁnd an optimal

transformation matrix G that maximizes Trace(S

) while

minimizing Trace(S

) in the lower dimensional space.

Equation (1) gives the objective, called the classical Fisher

criterion (Chen et al. 2000):

G =argmax

Trace((G

−1

G)), (1)

The classical LDA fails when S

is singular d  n>k.

This small sample size (SSS) problem occurs for many ap-

plications involving under sampled data such as text and

image retrieval (Chen et al. 2000). A typical solution to

the SSS problem lies in replacing the inverse in classi-

cal LDA by the pseudoinverse as (2), where A

(+)

de-

notes the pseudoinverse of A (Sharma and Paliwal 2015;

Golub, Van, and Charles 1996).

G =arg max

G=I

trace((G

(+)

G)). (2)

Furthermore, any G with

trace((G

(+)

G)=k − 1, (3)

is a solution to (2), provided that the training samples are

linearly independent (Chu et al. 2015).

Fast Batch Linear Discriminant Analysis

In this section, we present a fast batch LDA algorithm,

called FLDA/QR, from the perspective of online learning.

We aim to lower down the dimensionality of the data ma-

trix X ∈ R

d×n

for fast computation. Unlike a common

treatment using the principal component analysis (PCA) for

the reduction (Huang et al. 2002), we take cluster centers as

training examples that is handy to pick up and has a deﬁnite

dimension value in the feature space.

Denote the global center matrix C consisting of k centers

as:

C =



(1)

,...,c

(k)



= XEN

, (4)

where E =

⎡

⎢

⎣

⎤

⎥

⎦

∈ R

n×k

1 ···1

] ∈ R

1/n

··· 1/n

]

. And we let M = EN

(M ∈

n×k

), then X = CM

−1

and M

E = I. The cost of con-

structing the matrix C is as low as O(dn) in our implemen-

tation.

Subsequently, we adopt a lower triangular linear system

(5), proposed by (Chu et al. 2015), to solve (2) :

G = E, (5)

where G ∈ R

d×k

and trace((G

(+)

G)=k −1.

By replacing X with CM

−1

, we obtain a new expression

for the optimal transformation matrix, denoted by G

, in the

following:

=(CM

−1

)

−T

E = C

−T

E = C

−T

, (6)

where G

∈ R

d×k

Since the input training data is the centroid matrix, S

0. And it is easy to verify that G

= G

, and

2740

剩余6页未读，继续阅读

评论收藏

内容反馈

weixin_38729108

粉丝: 5
资源: 896

快速在线增量学习混合流数据

incremental-learning-for-SVM.rar_Svm 增量学习_online svm_svm代码matlab

Awesome-Incremental-Learning:很棒的增量学习

SVM增量式学习的自适应与优化的MATLAB代码

matlab20行代码-EndToEndIncrementalLearning:端到端增量学习

ChatGPT技术的训练数据增量学习与迁移.docx

figmn:快速增量高斯混合网络

面向分布式数据流的混合聚类算法.pdf

大规模数据处理引擎SPARK在状态评估领域中的应用.pdf

流式数据处理中的算法设计.pptx

34种数据降维方法matlab代码.zip

自组织增量神经网络matlab代码

mpcl：持续学习增量学习的理论框架

论文研究-基于支持向量机的增量学习算法.pdf

增量式极限学习机算法

自组织增量学习网络SOINN.rar

ChatGPT技术的在线学习与增量训练策略.docx

ChatGPT技术的增量学习与在线训练策略.docx

在线无监督特征提取的增量式深度学习网络

面向区块链的在线联邦增量学习算法.pdf

ChatGPT技术的增量学习与在线更新方法.docx

互联网数字营销广告数据管理平台应用.pdf

数据挖掘中聚类算法的新发展.pdf

Oracle ODI配置文档

最新资源