Fast cross-validation algorithms for least squares support vector machine and kernel ridge regression
MetadataShow full item record
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) wherein a subset of m examples are used for validation and the other subset of (n-m) examples are used for training the classifier. In this case l linear systems of dimension (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 l linear systems of dimension (n-m), we compute the inverse of an n dimensional square matrix and solve l linear systems of dimension m, thereby reducing the complexity when l 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 n. 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.
The link to the journal’s home page is: http://www.elsevier.com/wps/find/journaldescription.cws_home/328/description#description
Copyright © 2007 Elsevier Ltd. All rights reserved
Showing items related by title, author, creator and subject.
An, Senjian; Liu, Wan-Quan; Venkatesh, Svetha; Hong, Y. (2011)In the last decade, many variants of classical linear discriminant analysis (LDA) have been developed to tackle the under-sampled problem in face recognition. However, choosing the variants is not easy since these methods ...
On-Line dynamic security assessment of wind farm connected power systems using a class of intelligent algorithmsTiako, Remy (2012)Recently large-scale wind farms are integrated quite commonly into power systems. The stochastic operation of wind plants due to intermittency and intra-interval effects of the wind is a problematic issue to determine the ...
Gao, Jason (2002)Carrierless amplitude and phase (CAP) modulation is generally regarded as a bandwidth efficient two-dimensional (2-D) passband line code. It is closely related to the pulse amplitude modulation (PAM) and quadrature amplitude ...