Fast Factorization-free Kernel Learning for Unlabeled Chunk Data Streams

1 Introduction

One of the challenging aspects of data analytics nowadays is dealing with streaming and fast-moving input data, e.g., digital monitor images, social media feedbacks, marketing and financial data. In real applications, these data might come from several terminals without labels, simultaneously, forming chunk data streams. Particularly, a chunk of data may contain some new examples belong to the seen/known classes and/or unseen/novel classes. Therefore, we have to detect novelties first, and then incorporate all new information into the existing model. Although, novelty detection and incremental learning for data streams have received increasing attention in the past few years [Wang et al., 2016; Faria et al., 2016; Lu et al., 2017], efficient and stable solutions to simultaneously detect novelties and learn chunk data streams are still rare.

∗Corresponding Author

Recently, kernel null-space based discriminant analysis (KNDA) [Bodesheim et al., 2013] and incremental KNDA (IKNDA) [Liu et al., 2017] have been reported that their performances outperform classifiers SVDD [Tax and Duin, 2004] and GP-Mean/GP-Var [Kemmler et al., 2010], and deep approaches (e.g., Alexnet) [Krizhevsky et al., 2012] in multiclassification and novelty detection. KNDA learns a decision model by removing the intra-class variances in a reproducing kernel Hilbert null (RKHN) space, which provides elegant discrimination for highly complex and non-linear distribution data. Unfortunately, the eigen-decomposition of a large kernel matrix makes KNDA hard to scale up. IKNDA provides an updating scheme to renew the null space based on singular value decomposition (SVD). However, its incremental updating mechanism is not efficient for on-line learning tasks on large datasets. Besides, kernel methods also suffer from high memory cost of kernel matrix on large and/or high-dimensional datasets.

In this work, we put forward an efficient kernel learning method to unify the novelty detection and incremental learning for unlabeled chunk data streams in one framework. Specifically, our contributions are twofold:

• We propose an efficient factorization-free batch kernel discriminant analysis (FKDA). FKDA constructs a kdimensional RKH space from k known class centers by solving a linear system [Chu et al., 2015] in kernel space. The mapping (projection) to the feature space turns out to be the production of two small kernel matrices, thus the computational complexity of FKDA is significantly lower than other kernel DA methods, especially for large-scale scenarios. Moreover, each class is represented by a single point with a deterministic novelty threshold in RKH space, that also caters for multi-class novelty detection.

• We develop a fast and stable incremental scheme for FKDA, called IFKDA. In IFKDA, inserting a novel class to the learned model acts by appending a new orthogonal basis to the original feature space without disturbing the distribution of known classes, which makes the evolution more robust and stable. Moreover, IFKDA is very efficient in on-line learning scenarios, requiring only a small portion of the key kernel matrices to be recomputed.

2 Overview of Discriminative Analysis (DA)

In this section, we give a short overview of linear discriminative analysis and kernel discriminative analysis.

Given a data matrix with k clusters, X = {X1,X2, . . . ,Xk} ∈ Rd×n , where Xi ∈ Rd×ni and n = ∑ki=1 ni. The widely known Foley-Sammon transform [Chen et al., 2000] estimates a low-dimensional subspace to discriminative features by maximizing the following criterion:

where G ∈ Rd×l is a transformation matrix which projects data in d-dimensional space to l-dimensional subspace, Sb is between-class scatter matrix, and St is total scatter matrix ( St = Sb + Sw, where Sw is within-class scatter matrix).

A common issue of discriminative learning is the smallsize-sample (SSS) problem that n is far less than d, such that Sw is singular in general. One popular extension replaces the inverse in the classical model by pseudo-inverse, resulting in the following optimization model [Huang et al., 2002],

where (·)† denotes the pseudo-inverse of (·). And any transfer matrix G with the form

should be an optimal solution to (2) [Chu et al., 2015].

In [Chu et al., 2015], Chu et al. proposed a more efficient way for SSS problem by solving a linear system in (4) via the economic QR-factorization of X.

where G ∈ Rd×k , and E is a n-by-k matrix and the i-th column is (0, ..., ei, ..., 0)T where ei = [1...1]T ∈ Rni×1 .

Assuming that training samples are linearly independent, the solution of (4) with the minimal 2-norm is

If considering kernel tricks for DA, we should further map X into a feature space H with an implicit mapping function Φ : xij → φ(xij ), where φ(xij ) ∈ H and xij denote the j-th item of the i-th class. And we have

Accordingly, the criterion in (2) extends to

And any GΦ with the form

is an optimal solution of the optimization problem (7).

3 Factorization-free KDA (FKDA)

In this section, a fast factorization-free batch kernel DA method (FKDA) is developed. We first induce the linear system in (4) into the kernel space.

Theorem 1: Assuming XΦ are linearly independent, and the linear system in (9) is solvable, then the solution to the optimization problem (7) is given by GΦ.

Proof: See the Appendix.

Considering the advantages of using class centers as input in storage and computation as in AKDA/QR [Xiong et al., 2005], we introduce them into (9) and have

where CΦ = XΦM is a global centroid matrix in the kernel space, and M is a n-by-k matrix with the i-th column is (0, ..., ei/ni, ..., 0)T . Since

where I ∈ Rk×k is an identity matrix, then

A key observation for most widely used Gaussian kernel function: exp(-‖x-y‖2 /σ), is that for relatively large σ, the center of each class in the original space will be projected very close to the center of each class in the kernel space [Xiong et al., 2005]. So we adopt this idea to compute the centroid matrix Co in the original space first, then we approximate the kernel centroid matrix CΦ by

where ci denotes the center vector of class Xi in the original space. Therefore, we have

Assuming that class centers are linearly independent, we can resort to QR-decomposition of CΦ o = QΦRΦ to solve GΦ, where QΦ is the column orthogonal and RΦ is nonsingular. Then we have

Denote Ko = (CΦ o )T CΦ o ∈ Rk×k . Since (RΦ)T RΦ = (RΦ)T (QΦ)T QΦRΦ = (CΦ o )T CΦ o , thus

Result: Given a sample z, we can get its projection in the k-dimension RKH space by (GΦ)T φ(z) in (17).

Algorithm 1 FKDA-batch method

Require: Data matrix X, nonlinear mapping Φ and a testing sample z.

Ensure: The projected feature of z.

Stage1:

• 1: Compute the centroid matrix: Co.
• 2: Construct the kernel matrix: Ko = (CΦ o )T CΦ o . Stage2:
• 3: Construct the kernel vector: Kcz =< φ(CΦ o ), φ(z) >.
• 4: Compute (GΦ)T zΦ =K-1 o Kcz.

where Kcz ∈ Rk×1 and Kcz(i) =< φ(ci), φ(z) >.

Obviously, there is no need to really compute QRdecomposition of CΦ o .

FKDA is summarized as Algorithm 1.

Next, we compare the space and time complexities of FKDA with AKDA/QR [Xiong et al., 2005], SRKDA [Cai et al., 2007], KNDA [Bodesheim et al., 2013], KPE [Min et al., 2016], and LDA/QR [Chu et al., 2015] in Table 1. Since FKDA gives an implicit transform matrix GΦ, we add the projecting step to other methods for fairness. We also compare with a linear DA method (i.e., LDA/QR), so the space and time complexities of constructing the kernel matrix are added for all kernel methods in comparisons.

AKDA/QR and FKDA both use centroid matrix as input, so they need less space and time cost in constructing kernel matrix than other kernel DAs. The cost of constructing centroid matrix is as low as O(dn) in our implementation. Although, FKDA has to compute the inverse of Ko ∈ Rk×k with the complexity of O(k3 ), other kernel DAs also have such computation, e.g., AKDA/QR needs four times matrix inversion with the same scale, though it employs QR-decomposition, and KNDA has to compute the inversion of a matrix with the complexity of O(n3 ). In addition, the total computation cost of FKDA, including constructing kernel matrix, is no more than LDA/QR, especially when k is far less than n. Besides, LDA/QR has a demand of (d >> n) of Q matrix of X. In contrast, FKDA needs no factorization and can perform well on both (d >> n > k) and (n >> d > k) datasets, that will be demonstrated in Section 5.

4 On-line Learning for Chunk Data Streams

The on-line phase, shown in Figure 1, is composed of three operations: detect novelties, classify new samples and evolute the decision model. We will detail them in this section.

4.1 Novelty Detection and Classification

Given a chunk of unlabeled data, we assume they are clustered without noises or outliers by clustering algorithms, e.g., CluStream [Aggarwal et al., 2003], for clustering is not the focus of this work. Then we have a set of unlabeled cluster centers as input. And novelty detection and classification are performed in the learned k-RKH space.

To be noted, from the derivation of (14), we have

This means k class centers are projected to the unit positions of the k orthogonal axes, respectively, for the value of each volume of I represents the coordinate of the mapping points of known class centers in k-RKH space. For instance, given two known classes as shown in Figure 1, we have a 2-RKH space, where c1 of X1(Dog) is projected to C1(1, 0) and c2 of X2(Rabit) is projected to C2(0, 1).

Therefore, we can build a hypersphere surrounding each class center as classification boundary. New instances will be classified with respect to their distances to the previously known classes centers. The instances that being projected out of boundaries of all the known classes are classified as novel classes. Furthermore, we set the same value for the thresholds of boundaries of known classes, i.e., the half value of the Euclidean distance between two arbitrary classes. Since the positions of class centers are fixed on the axes, this value is also valid for the new inserted classes, that will be explained in the next subsection.

4.2 Updating Schemes (IFKDA)

The updating task can be easily accomplished by recomputing or appending some parts of the kernel matrices Ko and Kcz.

We suppose that a chunk of data is composed of some new samples belong to ka existing classes and some samples belongs to kb new classes. Then the new kernel matrix ˜Ko ∈ R(k+kb)×(k+kb) can be updated by (19)

where K′o ∈ Rk×k is the updated original kernel matrix Ko by recomputing the items relating to those known classes which have new samples, and Kb o ∈ Rk×kb and Kc o ∈ Rkb×kb are the new items introduced by novel classes in (20) and (21), respectively.

where αi represents φ(ci).

The time complexity for computing ˜Ko, Kb o and Kc o are O(dkka), O(dkkb), and O(dk2 b ), respectively.

Similarly, we update Kcz in two parts by

where K′cz is the updated kernel vector after inserting labeled new samples by (23), and Kb cz is the kernel vector after appending new classes by (24), where β denotes φ(z).

As we can see, the updating of known-class centers by new arriving samples does not change the rank of the kernel matrix, so as to the dimension of feature space. And the positions of known-class centers do not change under the constraint of (18). While inserting a novel class is equal to increasing one rank of the kernel matrix, resulting in appending a new basis perpendicular to the original space, see the demonstration in Figure 1. And the center of a new class is also projected into the unit position of the new axis, therefore its boundary threshold can be set to the same value as the knowns classes. Both of these features make IFKDA more stable and robust for classification, that will be verified by experiments on real datasets in Section 5.

We then compare space and time complexities for updating chunk data for IFKDA, ILDA/SSS [Kim et al., 2011], and ILDA/QR [Chu et al., 2015] in Table 2. In both respects, the updating costs of IFKDA are minimal, especially when k is far less than n (k << n) the advantages are more obvious. Besides, IKNDA only has the algorithm for learning novel classes, with O(ns + s2 ) and O(d(n + s)s + n2 s + ns2 ) in space and time complexities ( where s is the sample number in a new class), respectively, for the insertion of one novel class. In contrast, IFKDA only needs extra space of (d+k +1), and has O(dk + d) in time complexity in this case.

5 Experimental Results and Analysis

In this section, we evaluate the performances of the proposed methods on four publicly-available datasets: AR [Kim et al., 2011], AWA [Lampert et al., 2014], Caltech256 [Griffin et al., 2007] and MNIST-Fashion (MINST-F for short) [Xiao et al., 2017]. For AWA and Caltech256, we take the outputs from the 7-th full connected layer of very deep 19-layer CNN as features (4096 dims). The kernel function: exp(-‖x-y‖2 /σ) is used for all kernel DAs. Since FKDA uses approximate centers to construct kernel matrix as AKDA/QR, σ should be assigned a large value. Experiments show that choosing (σ = d) for FKDA(IFKDA) and AKDA/QR produce good overall results, we thus use this value for them in all the experiments. All methods are implemented in MATLAB and ran on an Intel (R) Core (TM) i7 PC with 3.40 GHz CPU and 8 GB RAM.

5.1 Multi-class Novelty Detection for Chunks

The settings of initial batch training stage and on-line incoming chunk data are in Table 3. Table 4 tabulates the results for FKDA and KNDA for detecting five unlabeled chunks with 20-fold cross-validation.

As we can see, although KNDA (σ = 1) produces good overall results on AWA and Caltech256, and KNDA (σ = d) performs better than KNDA (σ = 1) on AR and MNIST-F, the overall misclassification rates (denoted by Err) of FKDA (σ = d) are far less than those of KNDA on all datasets.

5.2 Incremental Learning

We first compare the performances of IFKDA and ILDA/QR with batch methods AKDA/QR, KNDA (σ = 1), and FKDA in learning chunk data streams on AWA and Caltech256.

The settings of experimental data are the same as those in Table 3. The testing data are randomly selected from the rest samples of training classes and the novel classes with the same scale of chunk data. The results of classification accuracy and CPU time on two datasets are shown in Figure 2 and Figure 3 with 20-fold-cross validation, respectively. We have the following observations:

1) IFKDA is the exact incremental version of FKDA, giving the same accuracies to FKDA in all tests. The accuracies of IFKDA and FKDA are comparable to the best algorithm. All kernel DAs are more accurate than ILDA/QR.

2) Both IFKDA and ILDA/QR are far faster than batch methods, which verifies the efficiency of incremental methods over the batch ones. IFKDA performs about 5-10 times faster than FKDA, hundreds of times faster than AKDA, and thousands of times faster than KNDA on both datasets. Although ILDA/QR runs similar as IFKDA on AWA (d = 4096 and n = 2240), but it can not work on Caltech256 (with d = 4096 and n = 7400), due to the limitation of (d >> n) for Q matrix of X in its algorithm.

3) FKDA spends less time than other batch methods in the training stage on both datasets. FKDA even has five times speed up over LDA/QR (the batch version of ILDA/QR, used in the initial training stage) on AWA. FKDA is dozens of times faster than AKDA/QR on AWA with comparable accuracy, and hundreds of times faster than AKDA/QR on Caltech256 with higher accuracy, even though they share the common on using centers as the input.

We then compare the classification accuracy and CPU time of IFKDA with IKNDA (σ = 1) in learning novel classes on Caltech256. AKDA/QR and FKDA are also taken as the baseline. The settings of batch training stage are the same as Table 3. And in on-line stage, fifteen novel classes (each has nci samples) are inserted one by one. The testing samples are randomly selected form the rest of novel classes with the same scale of inserting data. From the results in Figure 4, we have the following observations:

1) As to accuracy, all algorithms drop with the injection of new classes sequentially, but IFKDA is the most stable with the highest accuracy at the end of insertion.

2)As to CPU time, IFKDA is hundreds of times faster than IKNDA and AKDA/QR, even FKDA is faster than IKNDA.

Furthermore, we test the stability of IFKDA and IKNDA in known-class recognition after inserting fifteen novel classes on Caltech256. The testing samples are selected from the rest of initially known classes. The recognition accuracy of IFKDA is 72.35% in the batch training stage, then drops to 71.10% after the final insertion, while the accuracy of IKNDA is 75.01% in the batch training stage, then drops to 49.83% after the final insertion. This result further verifies the stability and robustness of IFKDA.

6 Conclusions

We propose a fast factorization-free kernel method (FKDA) by constructing an approximate kernel centroid matrix to solve a linear system in kernel space. Then the incremental FKDA (IFKDA) runs extremely fast by updating part of matrices. Both theoretical analysis and empirical experiments on several benchmarks validate the superiority of FKDA and IFKDA against the state-of-the-art methods. By taking advantage of our proposed algorithms, the kernel methods may be more widely applied especially when handling incremental learning problems for chunk data streams.

Acknowledgments

This research has been supported by the National Key Research and Development Program of China (Grant No. 2017YFB1103704), and the National Natural Science Foundation of China (Grant No. 61733002 and No.61572096).

A Proof of Theorem 1

The within class scatter in kernel space is

where ε = 1n eeT , εi = 1 ni ei T , e = [1...1]T ∈ Rn×1 and ei = [1...1]T ∈ Rni×1 . Thus

Since SΦ

.

And

We have the following result:

(GΦ)T SbΦGφ

Thus, rank((GΦ)T SΦ b GΦ) = k - 1, which together with (27) yields

so GΦ is a solution of (7).