Efficient Kernel Selection via Spectral Analysis

1 Introduction

Kernel methods, such as support vector machine (SVM) and least square support vector machine (LSSVM), have been widely used in data mining, pattern recognition and machine learning. The performance of these algorithms greatly depends on the choice of kernel function. Therefore, kernel selection is foundational to kernel methods and is also a challenging problem in kernel methods.

The standard technique for kernel selection is crossvalidation (CV). It consists in using a subset of the data for training, and then testing on the remaining data in order to estimate the generalization error. However, CV requires training the learning algorithm several times, which is computationally intensive. For the sake of efficiency, some approximate CV criteria are introduced: such as generalized crossvalidation (GCV) [Golub et al., 1979], generalized approximate cross-validation (GACV) [Wahba et al., 1999], span bound [Chapelle et al., 2002], efficient leave-one-out crossvalidation (ELOO) [Cawley, 2006], influence function [Debruyne et al., 2008], Bouligand Influence Function [Liu et al., 2014; Liu and Liao, 2017], et al.

∗Corresponding author

Kernel target alignment (KTA) [Cristianini et al., 2001] is another widely used criterion that can be effectively calculated in O(n2 ) time complexity, where n is the size of data set. Based on the centered kernel matrix, an improved centered KTA (called CKTA) is proposed [Cortes et al., 2010], which gives better performance than KTA. FSM is another criterion that can be effectively calculated [Nguyen and Ho, 2008], which evaluates the goodness of a kernel function via the data distribution in the feature space. Due to their simplicity and efficiency, KTA, CKTA and FSM have been widely used. However, the connection between these measures and the generalization error of some special algorithms, such as SVM and LSSVM, has not established. Therefore, the kernels chosen by these criteria can not guarantee good performance for these specific algorithms.

Minimizing theoretical estimate bounds of generalization error is an alternative to kernel selection. To this end, some measures of complexity are introduced: such as VC dimension [Vapnik, 2000], Rademacher complexity [Bartlett and Mendelson, 2002], local Rademacher complexity [Bartlett et al., 2005], covering number [Zhang, 2002], uniform stability [Bousquet and Elisseeff, 2002], compression coefficient [Luxburg et al., 2004], eigenvalues perturbation [Liu et al., 2013], kernel stability [Liu and Liao, 2014], eigenvalues ratio [Liu and Liao, 2015], principal eigenvalue proportion [Liu et al., 2017d; 2017c], et al.

However, the focus of these measures lies on deriving theoretical generalization bounds, which are usually difficult to be used for kernel selection in practice. To address this problem, Cortes et al. [2013] used the tail eigenvalues of kernel matrix to design new algorithms for learning kernels. However, the theoretical error bound based on the tail eigenvalues of kernel matrix is lacking. Liu et al. [2015] investigate it further, and introduce a notion of eigenvalue ratio for kernel selection, which can be used to derive generalization bounds. However, the time complexity of this measure is high. Moreover, this measure brings two extra parameters that should be tuned, making this measure hard to use.

In this paper, we propose a novel measure, called spectral measure, with sound theoretical foundation and high computational efficiency. The spectral measure is defined based on the spectral decomposition of kernel matrix, and can be effectively calculated in O(n2 ). We show that the generalization error of SVM and LSSVM can be bounded with spectral measure. Furthermore, we propose a new kernel selection criterion with spectral measure by minimizing the derived upper bounds to guarantee good generalization performance, and prove that the minimum graph cut and maximum mean discrepancy are its two special cases. Theoretical analyses and experimental results show that our criterion is sound and effective. To our knowledge, the kernel selection criterion with both theoretical guarantee and O(n2 ) time complexity for kernel methods has never been given before.

2 Notations and Preliminaries

We consider supervised learning where a learning algorithm receives a sample of n labeled points S = {(xi, yi)}ni=1 ∈ (X × Y)n , where X denotes the input space and Y = {-1, +1} denotes the output space. We assume S is drawn identically and independently from a fixed, but unknown probability distribution D on X × Y.

Let K : X × X → R be a kernel function. The reproducing kernel Hilbert space (RKHS) HK associated with K is defined to be the completion of the linear span of the set of functions {K(x, ·) : x ∈ X} with the inner product denoted as 〈·, ·〉K satisfying 〈K(x, ·), f〉K = f(x), ∀f ∈ HK. We use ‖ · ‖K to denote the norm in HK. In this paper, we study the regularized algorithms:

where ℓ(·, ·) is a loss function and λ is the regularization parameter. Choosing ℓ(·, ·) to be the square loss ℓ(t, y) = (t - y)2 gives rise to LSSVM while choosing it to be the hinge loss ℓ(t, y) = max{0, 1 - yt} produces SVM.

The performance of the regularized algorithms for classification is usually measured by the generalization error or risk R(S) = Pr(x,y)∼D[yfS(x) < 0]. Unfortunately, R(S) can not be computed since the probability distribution D is unknown, hence we should estimate it from empirical data. In this paper, we will introduce a novel measure to estimate it.

K = [K(xi, xj)]ni,j=1 is the kernel matrix and N is the normal kernel matrix denoted as N = K/|K|1, where |K|1 = ∑ni,j=1 K(xi, xj). Let (λi, vi) be the spectral decomposition of N, where λi is the eigenvalue and vi is the eigenvector, i = 1, . . . , n.

In the following, we assume that |K|1 =: C, and 0 ≤ K(x, x′ ) ≤ κ, ∀x, x′ ∈ X . Let R+ = {t|t ∈ R, t ≥ 0}.

3 Spectral Measure

In this section, we will first introduce the definition of spectral measure, and then use it to derive generalization bounds for LSSVM and SVM.

3.1 Definition of Spectral Measure

It is well known that the kernel matrix contains most of the information needed by kernel methods, and its spectral decomposition plays an important role in kernel matrix. Therefore, we aim at proposing a novel measure based on the spectral decomposition of kernel matrix for kernel selection.

Definition 1 (Spectral Measure (SM)). Let (λi, vi) be the spectral decomposition of the normal kernel matrix N, i = 1, . . . , n. Assume that ϕ : R+ → R+ is a function, ϕ(λi) ≤ λi for all i ∈ {1, . . . , n}. Then the spectral measure of K with respect to ϕ is defined as

The condition of ϕ(λi) ≤ λi looks strange at first glance. Then, we will give two forms of ϕ to show that it is a very important element to remove the noise. Two special cases of ϕ are given as follows:

• Hinge form: h ≥ 0,

It is easy to verity that the Hinge form satisfies the assumption of ϕ(λi) ≤ λi. From the definition of N, one can see that 0 ≤ λi ≤ 1, so the high degree form also satisfies the assumption of ϕ(λi) ≤ λi.

From the definition of the above two forms of ϕ, one can see that ϕ(λi) = 0 (Hinge form) or ϕ(λi) → 0 quickly (High degree form) when λi is small. Note that the small value of eigenvalue usually expresses the noise [Steinwart and Christmann, 2008], thus we can use them to remove the noise.

When we use the High degree form,

The above equations shows that the SM(K, tr ) can be effectively calculated in O(n2 ).

Remark 1. The time cost of high degree form is O(n2 ), which is much faster than that of Hinge form. However, the accuracy of these two forms is similar, so in this paper, we only consider the use of high degree form for kernel selection.

3.2 SM-based Generalization Error Bounds

In this subsection, we will derive the generalization bounds for LSSVM and SVM with spectral measure.

Theorem 1. Consider the LSSVM, and assume that ‖f‖K ≤ 1, ∀f ∈ HK. Then, with probability 1 - δ over the random choice of sample S with size n ≥ 5, we have

where µ = 8 θ2 lnn ln(2n) + ln 2n δ , c0 = Cλ C+λ .

The assumption of ∀f ∈ HK, ‖f‖K ≤ 1 is a common assumption which is used in [Bartlett et al., 2005; Kloft and Blanchard, 2011; Cortes et al., 2013].

The above theorem shows that the generalization error of LSSVM can be bounded with spectral measure SM(K, ϕ). Therefore, we can choose the kernel function by maximizing SM(K, ϕ) to guarantee good generalization performance.

Theorem 2. Consider the SVM, and assume that ‖f‖K ≤ 1, ∀f ∈ HK. Then, for SVM, with probability 1 - δ over the random choice of sample S with size n ≥ 5, we have

The above theoretical analysis demonstrates the theoretical guarantee of spectral measure for kernel selection.

4 Spectral Kernel Selection

In this section, we will present a novel kernel selection criterion with spectral measure, and show the minimum graph cut and maximum mean discrepancy are its two special cases.

According to Theorem 1 and Theorem 2, to guarantee good generalization performance, we can select the kernel function by maximizing the spectral measure SM(K, ϕ). Note that we can set ϕ(t) = tr to ignore the noise, and we know that SM(K, tr ) can be calculated effectively. Thus, we consider the use of the following kernel selection criterion:

where K is a candidate set of kernel functions. Note that we can give different weights to positive and negative classes according to their sample sizes to avoid the imbalance problem of positive and negative classes. Thus, we finally consider the following weighted spectral measure criterion (SM):

where ¯ y+ = n n+ and ¯ y- = - n n- , n+ and n- are respective the sizes of positive and negative classes. One can see that the time complexity of SM criterion is O(n2 ). The time complexity of existing popular kernel selection criteria, and whether they have theoretical guarantee are reported in Table 1. We can find that our SM is the only criterion with both theoretical guarantee and O(n2 ) time complexity.

Connections to Graph Cut

In graph theory, graph cut is used to measure the degree of dissimilarity of different segmentation [Shi and Malik, 2000]. Note that K(xi, xj) can be considered as the similarity between xi and xj , thus we can use kernel matrix K as similar matrix to construct a graph. In this case, the normalized graph cut (Ncut) [Shi and Malik, 2000] can be written as

where L = D-K, K is the kernel matrix, D is the diagonal matrix with the diagonal element Dii = ∑nj=1 Kij .

If the positive and negative classes are balanced, that is n+ = n-, then yTDy = ∑ni=1 Dii = ∑ni,j=1 Kij = |K|1. Thus, we have

The above equation shows that minimizing Ncut(K) is equal to maximizing SM(K, ϕ) when setting ϕ(t) = t for kernel selection.

Connections to Mean Discrepancy

Mean discrepancy (MD) [Gretton et al., 2007] is proposed to test whether two distributions are different on the basis of samples drawn from each of them. The estimate of MD in RKHS HK [Gretton et al., 2007] can be written as

where 〈φ(xi), φ(xj )〉K = Kij .

If K has been normalized, that is K = N, it is easy to verity that

The above equation will show that MD(K) is a special case of SM(K, ϕ), which demonstrates the effectiveness of our proposed kernel selection criterion again.

Remark 2. The measure of graph cut and mean discrepancy are two special case of our SM when ϕ(t) = t, but in our analysis of the above subsection, we know that ϕ(t) = tr , r ≥ 1 can used to ignore the noise.

Remark 3. Instead of choosing a single kernel, several authors consider the use of multiple kernels by some criteria, called multiple kernel learning (MKL), see [Lanckriet et al., 2004; Kloft et al., 2011; Liu et al., 2017a; 2017b] and references therein. Our spectral measure criterion can be applied to MKL: minµMS(Kµ, tr ) s.t.‖µ‖p = 1,µ ≥ 0, where Kµ = ∑ki=1 µiKi. The above optimization problem can be efficiently solved with gradient-based algorithms. However, in this paper, we mainly want to verify the effectiveness of our spectral measure criterion. Therefore, in our experiments, we focus on comparing our criterion with other popular kernel selection criteria.

5 Experiments

In this section, we will empirically analyze the performance of our proposed spectral measure criterion SM(K, tr ) (SM).

The evaluation is made on 25 publicly available data sets from UCI, StatLib and Weka Collections seen in Table 2. For each data set, we run all methods 50 times with randomly selected 70% of all data for training and the other 30% for testing. The use of multiple training/test partitions allows an estimate of the statistical significance of differences in performance between methods. Let Ai and Bi be the test errors of methods A and B in partition i, and di = Bi - Ai, i = 1, . . . , 50. Let ¯ d and Sd be the mean and standard error of di. Then under t-test, with confidence level 95%, we claim that A is significantly better than B (or equivalently B significantly worse than A) if the t-statistic ¯ d Sd/√50 > 1.676. All statements of statistical significance in the remainder refer to a 95% level of significance. Experiments are conducted on a Dell PC with 3.1-GHz 4-core CPU and 4-GB memory. We use the popular Gaussian kernels K(x, x′ ) = exp (- ‖x-x′ ‖22 2τ ) as our candidate kernels, τ ∈ {2i , i = -15,-14, . . . , 15}. In this paper, we mainly focus on choosing the kernel selection, so we set the regularization parameter λ = 1 for all methods. The learning machine we used is LSSVM.

In the first experiment, we compare the performance of our proposed SM criterion with five popular kernel selection criteria: 5-fold cross-validation (CV), efficient leaveone-out cross-validation (ELOO) [Cawley, 2006], centered kernel target alignment (CKTA) [Cortes et al., 2010], feature space-based kernel matrix evaluation (FSM) [Nguyen and Ho, 2007] and the latest eigenvalue ratio (ER) [Liu and Liao, 2015]. For each data set, we choose the kernel parameter τ by each kernel selection criterion on the training set and then evaluate the test error for the chosen parameters on the test set. In this experiment, we set r = 3. We will explore the influence of r later. Table 2 reports the average test errors that can be summarized as follows: (a) SM is significantly better than FSM and CKTA on nearly all data sets. This can be explained by the fact that FSM and CKTA don't have theoretical guarantee for special learning algorithm, so the kernels chosen by these criteria can not guarantee good generalization performance; (b) SM is better than CV and ER on most data sets. In particular, SM is significantly better than ER (or CV) on 15 (or 11) of 25 data sets, but only 4 (or 5) sets significantly worse on the remaining data sets; (c) SM gives comparable results with ELOO. In particular, SM is significantly better than ELOO on 9 data sets (autos, breast-w, breast-cancer, hepatitis, ionosphere, labor, segment, vote and wdbc) and is significantly worse on 8 data sets (diabetes, glass, heart, pima, liver-disorders, sonar, wpbc and tic-tac-toe). The run time of SM, CV, ELOO, CKTA, FSM and ER are reported in Table 3. It turns out that SM is much faster than CV, ELOO and ER, and gives comparable results with CKTA and FSM. The above results manifest that SM can guarantee generalization performance and has high computational efficiency as well.

In the following experiment, we explore the influence of the parameter r of SM. Figure 1 plots the average test errors with different r (due to space limit, we randomly select 2 data sets). For each fixed r, we choose the kernel parameter τ by SM on the training set, and evaluate the test errors for the chosen parameters on test set. We find that the optimal r belong to [2, 5] on most data sets. And we can also find out that we can randomly set r = 2, r = 3 or r = 4 in practice without sacrificing accuracy.

6 Conclusion

In this paper, we define a new spectral measure of a kernel matrix, which can be effectively calculated in O(n2 ) time complexity. With the spectral measure, we can bound the generalization errors of LSSVM and SVM, and propose the kernel selection criterion by minimizing the derived generalization error bounds, of which the minimum graph cut and maximum mean discrepancy are two special cases. The high computational efficiency and theoretical guarantee of the spectral measure may bring a new perspective on designing kernel selection criterion using spectral analysis.

Appendix A: Proof of the Theorem 1

To prove Theorem 1, we first prove the following Lemma:

Lemma 1. If fS is the solution of LSSVM, then

Proof. Note that (fS(x1), . . . , fS(xn))T = Kα where α = [K+λI]-1y. Thus

Let (βi, ui) be the spectral decomposition of K, then we have

Since Tr(K) ≤ |K|1 = C, we know that βj C ≤ Tr(K) C ≤ 1. According to Equation (4), we have yTK[K+λI]-1y = ∑ni=1 βi/C βi/C+λ/C 〈y, ui〉2 ≥ ∑ni=1 βi/C 1+λ/C 〈y, ui〉2 . Note that λi = βi/|K|1 = βi/C, vi = ui, where (λi, vi) is the spectral decomposition of N, thus

From the assumption ϕ(λi) ≤ λi, Equations (3), (4) and (5), we have ∑ni=1 yifS(xi) ≥ ∑ni=1 ϕ(λi) 1+λ/C 〈y, vi〉2 , which completes the proof.

Theorem 3 (Theorem 8 [Gao and Zhou, 2013]). For any δ > 0, with probability at least 1 - δ over the random choice of sample S with size n ≥ 5, every f ∈ HK satisfies the following bound:

Proof of the Theorem 1. Note that PrS[yfS(x) ≤ θ] = 1n ∑ni=1 1[yifS(xi)-θ], where 1[t] = 1, if t < 0, otherwise 1[t] = 0. Thus, it is easy to verify that

From the assumption that HK ranges in [-1,1], we have 1 - yifS(xi) + θ > 0. Thus, by Equation (6), we have

According to Equation (7) and Equation (2), we have

Substituting Equation (8) to Theorem 3, we have

This completes the proof for Theorem 1.

Appendix B: Proof of the Theorem 2

Similar with the proof of the Theorem 1, we first prove the following lemma:

Lemma 2. If fS be the solution of SVM, then

where d =min{-1, 1- 1 2λ }.

Proof. Note that fS(x) = ∑ni=1 αiK(xi, x), where α is the solution of the dual form of SVM. Thus, we have

where ⊗ is the entrywise matrix product (also known as the Hadamard product). Note that

where ci = min{αi, 1} -max{αi, 1}. Note that 0 ≤ αi ≤ 1 2λ , so we can obtain that

From Equation (10), we have

Thus, we can obtain that yTK(y ⊗ α) ≥ dC + yTKy = dC + ∑i βi〈yi, ui〉2 = dC + C ∑i λi〈yi, vi〉2 ≥ dC+C ∑i ϕ(λi) · 〈yi, vi〉2 , where (βi, ui) is the spectral decomposition of K. This completes the proof.

Proof of Theorem 2. According to Lemma 2 and Equation (7), we can obtain that

Substituting Equation (11) to Theorem 3, it is easy to complete the proof.

Acknowledgments

This work is supported in part by the National Natural Science Foundation of China (No.61673293, No.61602467, No.61303056), and Excellent Talent Introduction, Institute of Information Engineering, CAS (Y7Z0111107), and Youth Innovation Promotion Association, CAS (No.2016146).