Efficient cross-validation for kernelized least-squares regression with sparse basis expansions

Tapio Pahikkala, Hanna Suominen, Jorma Boberg

Research output: Contribution to journalArticle

10 Citations (Scopus)

Abstract

We propose an efficient algorithm for calculating hold-out and cross-validation (CV) type of estimates for sparse regularized least-squares predictors. Holding out H data points with our method requires O(min(H 2 n,Hn 2)) time provided that a predictor with n basis vectors is already trained. In addition to holding out training examples, also some of the basis vectors used to train the sparse regularized least-squares predictor with the whole training set can be removed from the basis vector set used in the hold-out computation. In our experiments, we demonstrate the speed improvements provided by our algorithm in practice, and we empirically show the benefits of removing some of the basis vectors during the CV rounds.

Original languageEnglish
Pages (from-to)381-407
Number of pages27
JournalMachine Learning
Volume87
Issue number3
DOIs
Publication statusPublished - Jun 2012
Externally publishedYes

Fingerprint

Experiments

Cite this

Pahikkala, Tapio ; Suominen, Hanna ; Boberg, Jorma. / Efficient cross-validation for kernelized least-squares regression with sparse basis expansions. In: Machine Learning. 2012 ; Vol. 87, No. 3. pp. 381-407.
@article{05fc54c214f34ff8bd9b83a014423133,
title = "Efficient cross-validation for kernelized least-squares regression with sparse basis expansions",
abstract = "We propose an efficient algorithm for calculating hold-out and cross-validation (CV) type of estimates for sparse regularized least-squares predictors. Holding out H data points with our method requires O(min(H 2 n,Hn 2)) time provided that a predictor with n basis vectors is already trained. In addition to holding out training examples, also some of the basis vectors used to train the sparse regularized least-squares predictor with the whole training set can be removed from the basis vector set used in the hold-out computation. In our experiments, we demonstrate the speed improvements provided by our algorithm in practice, and we empirically show the benefits of removing some of the basis vectors during the CV rounds.",
keywords = "Cross-validation, Hold-out, Kernel methods, Least-squares support vector machine, Regularized least-squares, Sparse basis expansions",
author = "Tapio Pahikkala and Hanna Suominen and Jorma Boberg",
year = "2012",
month = "6",
doi = "10.1007/s10994-012-5287-6",
language = "English",
volume = "87",
pages = "381--407",
journal = "Machine Learning",
issn = "0885-6125",
publisher = "Springer",
number = "3",

}

Efficient cross-validation for kernelized least-squares regression with sparse basis expansions. / Pahikkala, Tapio; Suominen, Hanna; Boberg, Jorma.

In: Machine Learning, Vol. 87, No. 3, 06.2012, p. 381-407.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Efficient cross-validation for kernelized least-squares regression with sparse basis expansions

AU - Pahikkala, Tapio

AU - Suominen, Hanna

AU - Boberg, Jorma

PY - 2012/6

Y1 - 2012/6

N2 - We propose an efficient algorithm for calculating hold-out and cross-validation (CV) type of estimates for sparse regularized least-squares predictors. Holding out H data points with our method requires O(min(H 2 n,Hn 2)) time provided that a predictor with n basis vectors is already trained. In addition to holding out training examples, also some of the basis vectors used to train the sparse regularized least-squares predictor with the whole training set can be removed from the basis vector set used in the hold-out computation. In our experiments, we demonstrate the speed improvements provided by our algorithm in practice, and we empirically show the benefits of removing some of the basis vectors during the CV rounds.

AB - We propose an efficient algorithm for calculating hold-out and cross-validation (CV) type of estimates for sparse regularized least-squares predictors. Holding out H data points with our method requires O(min(H 2 n,Hn 2)) time provided that a predictor with n basis vectors is already trained. In addition to holding out training examples, also some of the basis vectors used to train the sparse regularized least-squares predictor with the whole training set can be removed from the basis vector set used in the hold-out computation. In our experiments, we demonstrate the speed improvements provided by our algorithm in practice, and we empirically show the benefits of removing some of the basis vectors during the CV rounds.

KW - Cross-validation

KW - Hold-out

KW - Kernel methods

KW - Least-squares support vector machine

KW - Regularized least-squares

KW - Sparse basis expansions

UR - http://www.scopus.com/inward/record.url?scp=84862027224&partnerID=8YFLogxK

U2 - 10.1007/s10994-012-5287-6

DO - 10.1007/s10994-012-5287-6

M3 - Article

VL - 87

SP - 381

EP - 407

JO - Machine Learning

JF - Machine Learning

SN - 0885-6125

IS - 3

ER -