Fast Cross-Validation

1 Introduction

Kernel methods, such as SVM, least square SVM and kernel ridge regression (KRR), have been successfully solving various problems in machine learning community. The performance of these algorithms greatly depends on the selection of the hyper-parameters. Therefore, model selection is foundational to kernel methods and is also a challenging problem in kernel methods.

There have been many interesting attempts to derive the theoretical bounds of the generalization error or other techniques to select the hyper-parameters [Liu and Liao, 2015; Ding and Liao, 2014a; 2017; 2014b; Liu et al., 2013; 2017; Li et al., 2017; Liu and Liao, 2014], but the most widely accepted model selection method is still the t-fold crossvalidation (t-CV). Unfortunately, t-CV requires training t times, making it disabled for large scale model selection.

∗Corresponding author.

In this paper, we present an approach to approximating the CV based on the notion of Bouligand influence function (BIF) [Christmann and Messem, 2008] and Nystr¨om method [Ding and Liao, 2012] for a variety of kernel methods, including LSSVM, KRR and SVM. Specifically, we first show how to approximating the CV via the Taylor expansion of BIF. Then, we provide a method to calculate the BIF for general distribution, and further evaluate BIF for sample distribution. Finally, we use the Nystr¨om method to improve the efficiency of the computation of the BIF matrix, and give an approximate CV criterion for model selection of kernel methods. The proposed approximate CV requires training on the full data only once, hence can significantly improve the efficiency. Experimental results on 18 datasets show that our proposed CV can not only give the comparable results as the state-of-the-art methods, but also significantly improve the efficiency.

Related Work

In this subsection, we will introduce the related work about the approximate CV methods of kernel methods and Bouligand influence function.

Approximate CV of Kernel Methods

The extreme form of t-CV, where t equals the sample size, is known as leave-one-out CV. For the sake of efficiency, much work has been done to reduce the time complexity of leave-one-out CV for some specific kernel-based learning algorithms, see [Chapelle et al., 2002; Vapnik and Chapelle, 2000] for SVM, [Cawley and Talbot, 2007; Ding and Liao, 2011; Ding et al., 2018] for LSSVM, [Cawley and Talbot, 2004] for sparse LSSVM, [Cawley and Talbot, 2008] for kernel logistic regression, and [Debruyne et al., 2008] for kernel-based regression. There is much work on improving the efficiency of the leave-one-out CV, but little work focuses on the general t-CV. In our previous [Liu et al., 2014], we present a strategy for approximating the general CV based on the notion of Bouligand influence function (BIF) for some kernel-based algorithms. However, there are two limitations of this approximate method: 1) the loss function used in kernel-based algorithms must be differentiable, hence it can not be used for the non-differentiable case, such as the popular SVM; 2) we need to compute the inversion of the BIF matrix of time complexity O(n3 ), which is not suitable for large scale problem. To overcome these limitations, we propose a novel method to smooth the non-differentiable loss based on the Huber function, and we use the Nystr¨om method to improve the efficiency of the computation of the BIF matrix,

Bouligand Influence Function

In the field of robust statistics, the notion of influence function (IF) [Hampel et al., 1986] is introduced in order to analyze the effects of outliers on the algorithm. Steinwart and Christmann [2008] showed that SVMs for classification and regression have a bounded influence function under some assumption on the loss function. Koh and Liang [2017] used the notion of influence functions to trace a model's prediction through the learning algorithm and back to its training data. Christmann and Messem [2008] generalized the notion of influence function, and introduced a new notion from Bouligand-derivatives [Robinson, 1991] called Bouligand influence function (BIF), which measures the impact of an infinitesimal small amount of contamination of the original distribution. They also showed that SVMs have a bounded BIF with some assumptions on loss function. The focus of the above work lies in deriving theoretical analysis of robust statistics for some kernel methods, but little work aims at developing practical procedures for model assessment.

The rest of the paper is organized as follows. We introduce some notations and preliminaries in Section 2. In Section 3, we present an approximate CV method via BIF. In Section 4, we use the Nystr¨om method to accelerate the computation of the BIF matrix, and give the final model section criterion. In Section 5, we analyze the performance of our proposed criterion compared with other state-of-the-art model selection criteria. We end in Section 6 with conclusion.

2 Notations and Preliminaries

We consider the supervised learning where a learning algorithm receives a sample of n labeled points

where X denotes the input space and Y denotes the output space, Y ⊂ R in the regression case and Y = {-1,+1} in classification case. We assume S is drawn identically and independently from a fixed, but unknown probability distribution P on Z = X × Y.

Let κ : X × X → R be a kernel, that is, κ is symmetric and for any finite set of points {xi}ni=1 , the kernel matrix

is positive semidefinite. The reproducing kernel Hilbert space (RKHS) Hκ associated with the kernel κ is defined to be the completion of the linear span of the set of functions {Φ(x) = κ(x, ·) : x ∈ X} with the inner product satisfying

The operator fκ : P → fκ(P) =: fκ,P is defined by

where V : Y × Y → R+ ∪ {0} is a loss function, λ is the regularization parameter and ‖ · ‖κ is the norm in RKHS.

Let PS be the sample distribution associated with S, that is PS(z) = 1 |S| if z ∈ S, otherwise 0, where |S| is the size of S. When PS is used,

KRR, LSSVM and SVM are the special cases of such regularized algorithms. For KRR and LSSVM, V is the square loss:

For SVM, V is the hinge loss:

Let S1, . . . , St be a random equipartition of S into t parts, called folds. For simplicity, assume that n mod t, and hence,

Let PS\Si be the empirical distribution of the sample S without the observations Si, that is PS\Si (z) = 1 n-m if z ∈ S\Si, otherwise 0. Let fκ,PS\Si be the hypothesis learned on all of the data excluding Si. Then, the t-fold cross-validation (tCV) can be written as

3 Approximate CVwith BIF

In this section, we will introduce the notion of BIF, and show how to use BIF to approximate the CV.

3.1 Bouligand Influence Function (BIF)

Definition 1 ([Christmann and Messem, 2008]). Let P be a distribution and fκ be an operator fκ : P → fκ,P, then the Bouligand influence function (BIF) of fκ at P in the direction of a distribution Q ̸= P is defined as

Denote

One can see that BIF(Q; fκ, P) is the first order derivative of fκ,Pϵ,Q at ϵ = 0. If BIF exist, the following first Taylor expansion holds:

Note that

where PSi is the sample distribution corresponding to Si, that is, PSi (x) = 1m if x ∈ Si, otherwise 0. Thus, if taking

Equation (2) gives

Thus, the approximation of t-CV can be written as t-BIF :=

Note that t-BIF only depends on the calculation of fκ,PS and BIF(PSi ; fκ, PS). Thus, if given the BIF(PSi ; fκ, PS), we need to train the algorithm only once on the full data set S to obtain fκ,PS for approximating the fκ,PS\Si , i = 1, . . . , t.

The calculation of BIF at the continuous distribution P are given as follows:

Theorem 1 ([Liu et al., 2014]). Let Hκ be the RKHS of a bounded continuous kernel κ on X, and V (·, ·) a loss function and P be a distribution on Z, then the BIF of fκ in the direction of a distribution Q ̸= P is

where the operator L : Hκ → Hκ is defined by

In the next, we will evaluate the BIF of the sample distribution to approximate CV for square loss (KRR and LSSVM) and Hinge loss (SVM).

3.2 Approximate CV of Square Loss

In the next, we will give an approximate CV for square loss. From Theorem 1, we know that the operator L at sample distribution PS maps fκ,PS ∈ Hκ to

Thus, one can see that

where In = (1, . . . , n)T. Equation (5) indicates that the matrix

is the finite sample version of the operator L at PS.

From Theorem 1, it is now clear that where Ci is an n × n matrix with [Ci]j,k = 1 if xk ∈ Si, otherwise 0, ◦ is the entrywise matrix product.

Let B be the n × t matrix with

Therefore, according to Equation (3), we can obtain that

So, the t-CV for square loss can be approximated by

3.3 Approximate CV of Hinge Loss

Note that the hinge loss V (y, f(x)) = max(0, 1 - yf(x)) is not differentiable, but according to Theorem 1, we know that to obtain BIF we should compute the derivative of loss function. Thus, we propose to use a differentiable approximation of it, inspired by the Huber loss:

Note that if h → 0, the Huber loss converges to the hinge loss. From the Huber loss, we know that

We say that xi is a support vector if

Let us reorder the training points such that the first nsv points are support vectors. Let I0 be the n×n diagonal matrix with the first nsv entries being 1 and the others 0. Similar with the square loss, it is easy to verity that

is the finite sample version of the operator L at PS, and the following equation holds:

Let B be the n × t matrix with

Therefore, the t-CV for hinge loss can be approximated by

Remark 1. In this subsection, we only give an approximate CV for Hinge loss. In fact, we can use this strategy to approximate CV of other kernel-based algorithms of nondifferentiable, such as support vector regression (SVR) and L1-SVM [Steinwart and Christmann, 2008].

4 Model Selection

According to the above discussion, we know that

is an efficient approximation of CV, which only need to training once. However, to obtain t-BIF, we need O(n3 ) to calculate the inversion of L to obtain the BIF matrix B.

To accelerate the computation of the inversion of L, we consider the use of the popular Nystr¨om method . Suppose we randomly sample c columns of the matrix K uniformly without replacement. Let C denote the n × c martix formed by theses columns. Let W be the c × c matrix consisting of the intersection of these c columns with the corresponding c rows of K. Without loss of generality, we can rearrange the columns and rows of K based on this sampling such that:

The Nystr ¨om method uses W and C to construct an approximation ˜K of K defined by:

where W+ is the Moore-Penrose generalized inverse of W. If we write the SVD of W = UWΣWUTW, then

where UW and ΣW is the singular values and singular vectors of W.

Pluging Equation (10) into Equation (9), we can obtain that

where we let V := CUW√Σ+W ∈ Rn×c .

Note that we need to solve the inverse of L:

To reduce the computational cost, we intend to use the inverse of ˜L,

as an approximation of the inverse of L.

According to the Woodbury formula:

where A ∈ Rn×n , X ∈ Rc×c , Y ∈ Rc×c and Z ∈ Rc×n , it is easy to verity that

Note that VTV ∈ Rc×c , so only need O (c3 + nc2 ) to compute the ˜L-1 .

Therefore, in this paper, we consider the use of the following criterion for model selection:

where ˜B is the approximation of B with ˜L replace of L.

Time Complexity Analysis

To compute t-FBIF, we need O(c3 + nc2 ) to calculate the inversion of ˜L, and O(n2 + tnc) to calculate the B. Since fκ,PS has been obtained in the training process. Thus, the overall time complexity t-FBIF is

For the traditional t-CV method, the algorithm under consideration need to be executed t times, hence the time complexities are O(tn3 ), which is much larger than O(c3 + n2 + nc2 + tnc).

5 Experiments

In this section, we will compare our proposed approximate t-CV (t-FBIF) with the popular t-CV (t-CV), the efficient leave-one-out CV (ELOO) [Cawley, 2006] and eigenvalue ratio (ER) [Liu and Liao, 2015], t = 5, 10. The data sets are 18 publicly available data sets from LIBSVM Data 1 : 9 data sets for classification and 9 data sets for regression. Experiments are performed on a PC of 3.1GHz CPU with 4GB memory. We use the Gaussian kernel

as our candidate kernel σ ∈ {2i , i = -15, -14, . . . , 14, 15}. The regularization parameter

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

The learning algorithm used in our experiments for regression is KRR (square loss) and for classification is SVM (hinge loss). 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

All statements of statistical significance in the remainder refer to a 95% level of significance.

5.1 Accuracy

The test errors for classification and test mean square errors for regression are reported in Table 1. For our methods, we set h = 0.05 and c = 0.1n. The parameters (if have) for the compared algorithms follow the same experimental setting in their papers. The elements are obtained as follows: For each training set, we select the kernel parameter σ and the regularization parameter λ by each criterion on the training set, and evaluate the test error for the chosen parameters on the test set. The results in Table 1 can be summarized as follows:

• (a) Neither of t-CV and t-FBIF is statistically superior at the 95% level of significance, t=5, 10. Thus, the quality of our approximation is quite good;
• (b) t-FBIF is better than ELOO. In particular, t-FBIF is significantly better than ELOO on Heart, Breast, Liver, Bodyfat, Triazines and Cpusmall, but only significantly worse on Sonar.
• (c) t-FBIF is better than ER. In particular, t-FBIF is significantly better than ER on Ionosphere, Liver, Bodyfat, Triazines and Abalone, but only significantly worse on Sonar.

5.2 Efficiency

The running time is reported in Table 2 that can be summarized as follows:

• (a) The time cost of t-FBIF are much lower than that of tCV. In particular, 5-FBIF and 10-FBIF are 5 (or more) and 10 (or more) times faster than 5CV and 10CV on all datasets, respectively. For large dataset, such as Abalone and Cpusmall, 10-FBIF is 20 times faster than 10-CV. Thus, t-FBIF significantly improves the efficiency of tCV for model selection;
• (b) t-FBIF is 2 (or more) faster than ELOO and ER on all datasets. For large dataset, t-FBIF is nearly 5 times than ELOO and ER.

6 Conclusion

In this paper, we present an approximate CV method based on the theoretical notion of BIF and Nystr¨om method for a variety of kernel methods. The proposed approximate CV requires training on the full data only once, hence can significantly improve the efficiency. Experimental results on 18 data sets show that our approximate CV is 20 times more efficiency (for large scale datasets) and has no statistical discrepancy when compared to the original one. This is an interesting attempt to apply the theoretical notion of BIF for practical model selection.

Future work includes extending our criterion to other kernel-based algorithms, such as support vector regression, L1-SVM and kernel logistic regression.

Appendix: Proof of Theorem 1

Proof. From Theorem 2 in [Vito et al., 2004], we have

Let fϵ = fκ,Pϵ,Q . Note that Pϵ,Q = (1 - ϵ)P + ϵQ, hence we can obtain that

Taking the first derivative on both sides of (13) with respect to ϵ yields

Setting ϵ = 0 and according to Equation (12), we have

By the definition of the operator L, we can obtain that

Acknowledgments

This work is supported in part by the National Key Research and Development Program of China (2016YFB1000604), the National Natural Science Foundation of China (No.6173396, No.61673293, No.61602467) and the Excellent Talent Introduction of Institute of Information Engineering of CAS (Y7Z0111107).