Efficient hold-out for subset of regressors

Tapio Pahikkala, Hanna Suominen, Jorma Boberg, Tapio I. Salakoski

Research output: A Conference proceeding or a Chapter in BookConference contributionpeer-review

5 Citations (Scopus)

Abstract

Hold-out and cross-validation are among the most useful methods for model selection and performance assessment of machine learning algorithms. In this paper, we present a computationally efficient algorithm for calculating the hold-out performance for sparse regularized least-squares (RLS) in case the method is already trained with the whole training set. The computational complexity of performing the hold-out is O(|H|3 + |H|2n), where |H| is the size of the hold-out set and n is the number of basis vectors. The algorithm can thus be used to calculate various types of cross-validation estimates effectively. For example, when m is the number of training examples, the complexities of N-fold and leave-one-out cross-validations are O(m 3/N2 + (m2n)/N) and O(mn), respectively. Further, since sparse RLS can be trained in O(mn2) time for several regularization parameter values in parallel, the fast hold-out algorithm enables efficient selection of the optimal parameter value

Original languageEnglish
Title of host publicationAdaptive and Natural Computing Algorithms - 9th International Conference, ICANNGA 2009, Revised Selected Papers
Subtitle of host publicationLecture Notes in Computer Science
Pages350-359
Number of pages10
Volume5495
DOIs
Publication statusPublished - 2009
Externally publishedYes
Event9th International Conference on Adaptive and Natural Computing Algorithms, ICANNGA 2009 - Kuopio, Finland
Duration: 23 Apr 200925 Apr 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5495 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference9th International Conference on Adaptive and Natural Computing Algorithms, ICANNGA 2009
Country/TerritoryFinland
CityKuopio
Period23/04/0925/04/09

Fingerprint

Dive into the research topics of 'Efficient hold-out for subset of regressors'. Together they form a unique fingerprint.

Cite this