Large Scale Online Kernel Classification

1 Introduction

In the fields of machine learning and artificial intelligence, online learning refers to a sequential machine learning task where a predictive model is learned incrementally from a sequence of data instances [Rosenblatt, 1958]. Unlike regular batch machine learning methods [Hoi et al., 2006] which usually suffer from a high re-training cost whenever new training data arrive, online learning algorithms are often very efficient and highly scalable, making them more suitable for largescale online applications where data usually arrive sequentially and evolute dynamically and rapidly. Online learning techniques can be applied to many real-world applications, such as online spam detection, online advertising, multimedia retrieval [Xia et al., 2013], and computational finance [Li et al., 2012]. In this paper, we restrict our discussion of online learning methodology to tackle online classification tasks.

In literature, a variety of online learning techniques have been proposed to tackle online classification tasks in recent years. One popular family of online learning algorithms is to learn a linear predictive model on the input feature space, which we refer to as "linear online learning" [Rosenblatt, 1958; Crammer et al., 2006; Dredze et al., 2008]. The key limitation of these algorithms lies in that the linear model could be restricted to make effective classification if training data are linearly non-separable in the input feature space, which can be common for some real-world classification tasks with noisy training data of relatively low dimensionality. This motivates the studies of "kernel based online learning" or referred to as "online kernel classification" [Kivinen et al., 2001; Freund and Schapire, 1999], which aims to learn kernel-based models for improving the classification of nonseparable instances in the input feature space.

One of the key challenges of conventional online kernel classification is that an online learner usually has to maintain in memory a set of support vectors for representing the kernel-based predictive model. During the online learning process, whenever a new incoming training instance is wrongly classified, it typically will be added to the support vector set, making the support vector size unbounded and potentially causing memory overflow for a large-scale online learning task. To attack this challenge, an emerging research direction is to explore "budget online kernel classification" [Crammer et al., 2003], which attempts to bound the number of support vectors with a fixed budget size using different budget maintenance strategies whenever the budget overflows. However, the key limitations of the existing budget online kernel methods lie in that some algorithms are too simple to achieve satisfactory approximation accuracy, while some other algorithms are too computationally intensive, making them harm the crucial merit of high efficiency of online learning techniques for large-scale applications.

Unlike the existing budget online kernel methods, in this paper, we present a novel framework of large-scale online kernel classification by exploring a completely different strategy. In particular, the key idea of our framework is to explore functional approximation techniques to approximate a kernel by transforming data from the input space to a new feature space, and then apply existing linear online learning algorithms on the new feature space. Specifically, we propose two different new algorithms: (i) Fourier Online Gradient Descent

(FOGD) algorithm which adopts the random Fourier features for approximating shift-invariant kernels and learns the subsequent model by online gradient descent; and (ii) Nystr¨om Online Gradient Descent (NOGD) algorithm which employs the Nystr¨om method for large kernel matrix approximation followed by online gradient descent learning. We give theoretical analysis of our proposed algorithms, and conduct an extensive set of empirical studies to examine their efficacy.

2 RelatedWork

Our work is related to two major categories of machine learning research: online learning and kernel methods.

Our work is closely related to online learning methods for classification tasks [Rosenblatt, 1958; Freund and Schapire, 1999; Crammer et al., 2006; Zhao and Hoi, 2010; Zhao et al., 2011; Wang et al., 2012; Hoi et al., 2013], particularly for budget online kernel machine learning where several algorithms have been proposed in literature [Crammer et al., 2003; Wang and Vucetic, 2010; Zhao et al., 2012]. Some well-known examples include Forgetron [Dekel et al., 2005] which basically discards old support vectors when the budget overflows for adding a new support vector, and Randomized Budget Perceptron(RBP) [Cavallanti et al., 2007] which randomly discards existing support vectors, and Projectron[Orabona et al., 2008; 2009] which uses a sophisticated projection strategy to bound the support vector size with better approximation but falls short in its high computational cost.

Moreover, our work is also related to kernel methods for large-scale classification tasks, especially for some studies on large-scale kernel methods [Williams and Seeger, 2000; Rahimi and Recht, 2007]. In particular, we employ the pioneering technique of random Fourier features, which have been successfully used in speed up batch kernelized SVMs [Rahimi and Recht, 2007], and kernel-based clustering [Chitta et al., 2012], etc. Another technique adopted in our approach is the well-known Nystr¨om method [Williams and Seeger, 2000], which has been widely applied in machine learning tasks, including Gaussian Processes [Williams and Seeger, 2000], Kernelized SVMs [Zhang et al., 2012], Kernel PCA, Spectral Clustering [Zhang and Kwok, 2009], and manifold learning [Talwalkar et al., 2008]. Although these techniques have been applied for batch machine learning tasks, to the best of our knowledge, they have never been applied to online classification tasks as our approach in this paper.

3 Large Scale Online Kernel Classification

3.1 ProblemFormulation

Consider an online binary classification task over a sequence of data instances (xt, yt),t = 1, . . . , T , where xt ∈ Rd is the observed features of the t-th data instance and yt ∈ {+1, -1} is the true class label which is only revealed from the environment at the end of each online learning round. The goal of a conventional online kernel classification task is to learn a kernel-based predictive model f(x) for classifying a new instance x ∈ Rd as follows:

where B is the number of support vectors, αi denotes the coefficient of the i-th support vector, and κ(·, ·) denotes the kernel function. The existing budget online kernel classification approach aims to bound the number of support vectors by a constant B using different budget maintenance strategies.

Unlike the existing budget online kernel classification methods using the budget maintenance strategy, we propose to explore the functional approximation strategy to tackle the challenge. In particular, our goal is to construct a new representation z(x) ∈ RD such that the inner product is able to approximate the kernel function:

By the above approximation, the model can be rewritten:

where w⊤ = ∑Bi=1 αiz(xi) denotes the weight vector to be learned in the new feature space. As a consequence, solving the regular online kernel classification task can be turned into a problem of an linear online classification task on the new feature space derived from the kernel approximation. In the following, we will present two online kernel classification algorithms by applying two different kernel approximation methods: (i) Fourier Online Gradient Descent and (ii) Nystr¨om Online gradient descent methods.

3.2 Fourier Online Gradient Descent

Random fourier features can be used in shift-invariant kernels [Rahimi and Recht, 2007]. A shift-invariant kernel is the kernel that can be written as κ(x1, x2) = k(x1 - x2), where k is some function. Examples of shift-invariant kernels include some widely used kernels, such as Gaussian and Laplace kernels. By performing an inverse Fourier transform of the shift-invariant kernel function, one can obtain:

where p(u) is a proper probability density function. Given a kernel function is continuous and positive-definite, according to the Bochner's theorem [Rudin, 1990], the kernel function can be expressed as an expectation of function with a random variable u:

The equality (4) can be obtained by only keeping the real part of the complex function. From (5), we can see any shift-invariant kernel function can be expressed by the expectation of the inner product of the new representation of original data, where the new data representation is z(x) = [cos(u⊤x), sin(u⊤x)]. As a consequence, we can sample many random Fourier components u1, ...uD independently for constructing the new representation as follows:

The online kernel learning task in the original input space can thus be approximated by solving a linear online learning task in the new feature space. More specifically, for a Gaussian kernel κ(x1, x2) = e- ‖x1-x2‖2 2σ2 , we have the corresponding random Fourier component u with the distribution p(u) = N(0, σ-2 I). For data arriving sequentially, we can construct the new representation of a data instance on-the-fly, and then perform online learning in the new feature space using the online gradient descent algorithm. We refer to the proposed algorithm as the Fourier Online Gradient Descent (FOGD), as summarized in Algorithm 1.

Algorithm 1 FOGD - Fourier Online Gradient Descent

Input: the number of Fourier components D, stepsize η;

Initialize w1 = 0. Generate random Fourier components: u1, ..., uD sampled from distribution p(u) = N (0, σ-2 I). for t = 1, 2, . . . , T do Receive xt; Construct new representation: zt(xt) = (sin(u⊤1 xt), cos(u⊤1 xt), ..., sin(u⊤Dxt), cos(u⊤Dxt)) Predict ̂ yt = sgn(w⊤ t (zt(xt))); Receive yt and suffer loss ℓ(w⊤ t (zt(xt)); yt ); if ℓ(w⊤ t (zt(xt)); yt ) > 0 then wt+1 = wt - η∇ℓ(w⊤ t (zt(xt)); yt ). end if end for

3.3 Nystr¨omOnline Gradient Descent

The above random Fourier feature based approach attempts to approximate the kernel function explicitly, which is in general data independent for the given dataset and thus may not fully exploit the potential of data distribution for kernel approximation. To address this, we propose to explore the Nystr¨om method [Williams and Seeger, 2000] to approximate a large kernel matrix by a data-dependent approach.

First we introduce some notations. We denote a kernel matrix by K ∈ RT×T with rank r. We denote the Singular Value Decomposition (SVD) of K as K = VDV⊤, where the columns of V are orthogonal and D = diag(σ1, . . . , σr, ) is diagonal. For k < r, Kk = ∑ki=1 σiViV ⊤ i = VkDkV⊤ k is the best rank-k approximation of K, where Vi is the i-th column of matrix V.

Given a large kernel matrix K ∈ RT×T , the Nystr¨om method randomly samples B ≪ T columns to form a matrix C ∈ RT×B , and then derive a much smaller kernel matrix W ∈ RB×B based on the sampled B instances. We can in turn approximate the original large kernel matrix by

Algorithm 2 NOGD - Nystr ¨om Online Gradient Descent

Input: the budget B, stepsize η, rank approximation k.

Initialize support vector set S1 = ∅, and model f1 = 0. if |St| < B then for t = 1, 2, . . . , T0 do Receive xt; Predict ̂ yt = sgn(ft(xt)); Update ft by regular Online Gradient Descent (OGD) Update St+1 = St ∪ {t} whenever loss is nonzero end for end if Construct the kernel matrix ˆKt from St. [Vt,Dt] = eigs( ˆKt, k), where Vt and Dt are Eigenvectors and Eigenvalues of ˆKt, respectively. Initialize wt = (α1, ..., αB)(D-0.5 t V⊤ t )-1 . for t = T0 + 1, . . . , T do Receive xt; Construct the new representation of xt: zt(xt) = D-0.5 t V⊤ t (κ(xt, ˆx1), ..., κ(xt, ˆxB))⊤. Predict ̂ yt = sgn((w⊤ t (zt(xt))); Update wt+1 = wt - η∇ℓ(w⊤ t (zt(xt)); yt ).

end for

where Wk is the best rank-k approximation of W, W+ denotes the pseudo inverse of matrixW.

We now apply the above Nystr¨om kernel approximation to large-scale online kernel classification task. Similar to the previous approach, the key idea is how to construct the new representation for every newly arrived data instance based on the kernel approximation principle. In particular, we propose the following scheme: (i) at the very early stage of the online classification task, we simply run any existing online kernel classification methods (e.g., kernel-based online gradient descent in our approach) whenever the number of support vectors is smaller than a predefined budget size B. Once the budget is reached, we then use the stored B instances (support vectors) to approximate the kernel value of any new instances (which is equivalent to using the first B columns to approximate the whole kernel matrix). From the approximated kernel matrix in (6), we could see the kernel value between i-th point xi and j-th point xj is approximated by

For a new instance, we construct the new representation as:

Similarly, we can then apply the existing online gradient descent algorithm to learn the linear predictive model on the new feature space induced from the kernel. We denote the proposed algorithm the Nystr¨om Online Gradient Descent (NGOD), as summarized in Algorithm 2.

4 Theoretical Analysis

This section aims to analyze the theoretical properties of the two proposed algorithms.

Theorem 1. Assume we learn with an RBF Kernel of bandwidth σ, i.e., κ(x1, x2) = exp(-‖x1 - x2‖22/2σ2 ), and the original data is contained by a ball Rd of diameter R. Let ℓ(f(x); y) : R → R be a convex loss function that is Lipschitz continuous with Lipschitz constant L. Let wt, t ∈ [T] be the sequence of classifiers generated by FOGD in Algorithm 1. Then, for any f ∗ = ∑Tt=1 αtκ(x, xt), we have the following with probability at least 1 - 28 ( dR σ2 ϵ )2 exp( -Dϵ2 4(d+1) )

where ‖f ∗‖1 = ∑Tt=1 |αt|.

Proof. Given f ∗ (x) = ∑Tt=1 αtκ(x, xt), according to the Representer Theorem [Sch¨olkopf et al., 2001], we have a corresponding linear model: w∗ = ∑Tt=1 αtz(xt), where

The first step to prove our theorems is to bound the regret of our sequence of linear model wt learned by our online learner with respect to the linear model w∗ in the new feature space. First of all, we have

Combining the above and the convexity of the loss function:

we have the following

Summing the above over t = 1, ..., T leads to:

Next we further examine the relationship between ∑Tt=1 ℓt(w∗ ) and ∑Tt=1 ℓt(f ∗ ). According to the uniform convergence of Fourier features (Claim 1 in [Rahimi and Recht, 2007]), we have the high probability bound for the difference between the approximated kernel value and the true kernel value, i.e., with probability at least 1 - 28 ( dR σ2 ϵ )2 exp( -Dϵ2 4(d+1) ), we have ∀i, j

When |z(xi)⊤z(xj) - κ(xi, xj)| < ϵ, we have

Combining (7) and (9) leads to complete the proof.

Remark. In general, the larger the dimensionality D, the higher the probability of the bound to be achieved. This means that by sampling more random Fourier components, one can approximate the kernel function more accurately and effectively. From the above theorem, it is not difficult to show that, by setting η = 1 √T and ϵ = 1 √T , we have

which leads to sub-linear regret O(√T). However, setting ϵ = 1 √T requires to sample D = O(T) random components in order to achieve a high probability, which seems unsatisfactory since we will have to solve a very high-dimensional linear online learning problem. However, even in this case, for our FOGD algorithm, the learning time cost for each instance is O(c1T), while the time cost for classifying an instance by regular online kernel classification is O(c2T), here c1 is the time for a scalar product by FOGD, while c2 is the time for computing the kernel function. Since c2 ≫ c1, our method is still much faster than the regular online kernel classification methods.

Theorem 2. Assume we learn with kernel κ(x1, x2) ≤ 1. Let ℓ(f(x); y) : R → R be a convex loss function that is Lipschitz continuous with Lipschitz constant L. Let the sequence of T instances x1, ..., xT form a kernel matrix K ∈ RT×T , and Kk is the best rank-k approximation of K, Kmax = maxi Kii, dKmax = maxij √Kii +Kjj - 2Kij. Let wt, t ∈ [T] be the sequence of classifiers generated by NOGD in Algorithm 2 with budget size B. Then, for f ∗ that minimize 12 ‖f‖H + λ T ℓt(xt), with probability at least 1 - ϵ

where ∆B = 2T √B Kmax(1 + √ T-B T -0.5 1 β(B,T) log 1ϵ dKmax K 12max ), β(B, T) = 1 - 1 2max{B,T-B} , ‖K‖2 is the spectral norm of matrix K.

Proof. We adopt similar procedure that proves the above theorem. We first bound the regret with respect the corresponding w∗ in new feature space, as (7) shows. Then we bound ∑Tt=1 ℓt(w∗ ) with respect to ∑Tt=1 ℓt(f ∗ ). As studied in

[Cortes et al., 2010](Corollary 1), we can bound the gap between suffered losses by approximation with respect to spectral norm of kernel approximation gap:

The next is to bound the spectral norm of approximated kernel gap ‖ ˆK - K‖2. As [Kumar et al., 2012](Theorem 2) shows, this can be bounded by the spectral norm of the best rank-k approximated kernel gap ‖K-Kk‖2 = σk+1:

where ∆B is as follows:

β(B, T) = 1- 1 2max{B,T-B} and ‖K‖2 is the spectral norm of K. Combining (9), (10), (11) finishes the proof.

Remark. Clearly, the larger the value of B, the smaller the value of ∆B, leading to the tighter bound. Basically ∆B = O(T) and thus √2λL(σk+1 + ∆B) 14 (1 + σk+1+∆B 4 ) 14 = O(√T). By setting η = 1 √T , we have the following:

The above sub-linear regret O(√T ) seems better than FOGD since NOGD does not require a very large value of B in order to achieve the O(√T ) bound.

5 Experimental Results

5.1 Overview and Experimental Testbed

In this section, we evaluate the empirical performance of the proposed algorithms: FOGD and NOGD, by comparing them with the state-of-the-art budget online kernel classification algorithms for large-scale online kernel classification tasks.

Table 1 shows the details of 9 publicly available datasets of diverse sizes in our experiments. All of them can be downloaded from LIBSVM website 1 , UCI machine learning repository 2 and KDDCUP competition site 3 .

1 http://www.csie.ntu.edu.tw/∼cjlin/libsvmtools/

2 http://www.ics.uci.edu/∼mlearn/

3 http://www.sigkdd.org/kddcup/

5.2 Compared Algorithms and Setup

As a yardstick for evaluation, we include the following two popular algorithms for regular online kernel classification:

• "Perceptron": the kernelized Perceptron algorithm [Freund and Schapire, 1999] without budget;
• "OGD": the kernelized online gradient descent algorithm [Kivinen et al., 2001] without budget.

Further, we compare our algorithms with the following stateof-the-art budget online kernel learning algorithms:

• "RBP": the random budget perceptron algorithm by random removal strategy [Cavallanti et al., 2007];
• "Forgetron": the Forgetron algorithm by discarding oldest support vectors [Dekel et al., 2005];
• "Projectron": the Projectron algorithm using the projection strategy[Orabona et al., 2009];
• "Projectron++": the aggressive version of Projectron algorithm[Orabona et al., 2008; 2009];
• "BPA-S": the Budget Passive-Aggressive algorithm, we adopt "BPA-S" in [Wang and Vucetic, 2010];
• "BOGD": the Budget Online Gradient Descent algorithm by uniform sampling in [Zhao et al., 2012];
• "BOGD++": the Budget Online Gradient Descent algorithm by nonuniform sampling in [Zhao et al., 2012].

To make fair comparisons, all the algorithms follow the same setups. We adopt the hinge loss as the loss function ℓ, and a Gaussian kernel with bandwidth 8. The stepsize η in the all online gradient descent based algorithms is set to 0.2. We adopt the same parameter B for NOGD and other budget algorithms. The parameter k in NOGD is set to 0.2B, and the parameter D in FOGD is set to 10B. For each data set, all the experiments were repeated 20 times using different random permutation of instances in the dataset. All the results were obtained by averaging over these 20 runs. For performance metrics, we evaluate the online classification performance by standard mistake rates and running time (seconds). Finally, all the algorithms were implemented in Matlab, and all the experiments were run in a Linux machine with 2.5GHz CPU.

5.3 Empirical Evaluations

Table 2 summarizes the empirical evaluation results on the 9 diverse data sets. We can draw several observations below.

First of all, in terms of time efficiency, we found that the budget online classification algorithms in general run much faster than the regular online kernel classification algorithms (Perceptron and OGD) especially on the large datasets, validating the importance of studying scalable online kernel methods. By further examining their results of mistake rates, we found that the budget online classification algorithms are generally worse than the two non-budget algorithms, validating the motivation of exploring effective techniques for budget online kernel classification. Among the budget online classification algorithms, no one single algorithm consistently beats all the algorithms. In general, Projectron++, BPA-S and BOGD tend to perform more accurately than RBP and Forgetron, but also take more time cost for most cases.

Second, by comparing the proposed algorithms (FOGD and NOGD) with the budget online classification algorithms, we found that they generally achieve the best or close to the best classification performance for most cases using fairly comparable or even lower time cost. Specifically, by comparing with RBP and Forgetron, our algorithms obtain much more accurate results with comparable or slightly more time cost. In comparison to Projectron++, BPA-S and BOGD++, our algorithms achieve better or at least highly comparable accuracy but with smaller or comparable time cost.

Finally, NOGD tends to perform better than FOGD (except for "spambase"). We conjecture that it may because FOGD is data-independent, while NOGD is data-dependent which approximates the kernel by sampling the given data instances. We note that our observation for the empirical advantages of Nystr¨om methods over random Fourier features is consistent to the recent comparison between Fourier random features and Nystr¨om methods [Yang et al., 2012].

6 Conclusion

This paper presented a novel framework of large-scale online kernel classification via functional approximation, going beyond conventional online kernel methods that often adopt the budget maintenance strategy to bound the support vector size. The basic idea of our framework is to approximate a kernel function or kernel matrix by exploring functional approximation techniques. We presented two new algorithms for large-scale online kernel classification: Fourier Online Gradient Descent (FOGD) and Nystr¨om Online Gradient Descent (NOGD). Our promising results on large-scale online kernel classification tasks show the state-of-the-art performance of our algorithms in both classification efficacy and efficiency. As the first attempt of exploring functional approximation for online kernel learning, our framework is generic and can be extended to other settings (e.g., regression) in future work.

Acknowledgements

This work was supported by MOE tier-1 grant (RG33/11).