Fast cross-validation algorithms for least squares support vector machine and kernel ridge regression

Given n training examples, the training of a least squares support vector machine (LS-SVM) or kernel ridge regression (KRR) corresponds to solving a linear system of dimension n  . In cross-validating LS-SVM or KRR, the training examples are split into two distinct subsets for a number of times (l)(l) wherein a subset of mm examples are used for validation and the other subset of (n-m)(n-m) examples are used for training the classifier. In this case ll linear systems of dimension (n-m)(n-m) need to be solved. We propose a novel method for cross-validation (CV) of LS-SVM or KRR in which instead of solving ll linear systems of dimension (n-m)(n-m), we compute the inverse of an n   dimensional square matrix and solve ll linear systems of dimension m  , thereby reducing the complexity when ll is large and/or m   is small. Typical multi-fold, leave-one-out cross-validation (LOO-CV) and leave-many-out cross-validations are considered. For five-fold CV used in practice with five repetitions over randomly drawn slices, the proposed algorithm is approximately four times as efficient as the naive implementation. For large data sets, we propose to evaluate the CV approximately by applying the well-known incomplete Cholesky decomposition technique and the complexity of these approximate algorithms will scale linearly on the data size if the rank of the associated kernel matrix is much smaller than nn. Simulations are provided to demonstrate the performance of LS-SVM and the efficiency of the proposed algorithm with comparisons to the naive and some existent implementations of multi-fold and LOO-CV.