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) wh...
| Main Authors: | , , |
|---|---|
| Format: | Journal Article |
| Published: |
Elsevier Science Inc
2007
|
| Online Access: | http://hdl.handle.net/20.500.11937/43097 |
| _version_ | 1848756596971143168 |
|---|---|
| author | An, Senjian Liu, Wan-Quan Venkatesh, Svetha |
| author_facet | An, Senjian Liu, Wan-Quan Venkatesh, Svetha |
| author_sort | An, Senjian |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T09:14:43Z |
| format | Journal Article |
| id | curtin-20.500.11937-43097 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T09:14:43Z |
| publishDate | 2007 |
| publisher | Elsevier Science Inc |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-430972017-09-13T16:06:54Z Fast cross-validation algorithms for least squares support vector machine and kernel ridge regression An, Senjian Liu, Wan-Quan Venkatesh, Svetha 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. 2007 Journal Article http://hdl.handle.net/20.500.11937/43097 10.1016/j.patcog.2006.12.015 Elsevier Science Inc restricted |
| spellingShingle | An, Senjian Liu, Wan-Quan Venkatesh, Svetha Fast cross-validation algorithms for least squares support vector machine and kernel ridge regression |
| title | Fast cross-validation algorithms for least squares support vector machine and kernel ridge regression |
| title_full | Fast cross-validation algorithms for least squares support vector machine and kernel ridge regression |
| title_fullStr | Fast cross-validation algorithms for least squares support vector machine and kernel ridge regression |
| title_full_unstemmed | Fast cross-validation algorithms for least squares support vector machine and kernel ridge regression |
| title_short | Fast cross-validation algorithms for least squares support vector machine and kernel ridge regression |
| title_sort | fast cross-validation algorithms for least squares support vector machine and kernel ridge regression |
| url | http://hdl.handle.net/20.500.11937/43097 |