TY - GEN

T1 - Efficient hold-out for subset of regressors

AU - Pahikkala, Tapio

AU - Suominen, Hanna

AU - Boberg, Jorma

AU - Salakoski, Tapio

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

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

U2 - 10.1007/978-3-642-04921-7_36

DO - 10.1007/978-3-642-04921-7_36

M3 - Conference contribution

AN - SCOPUS:78650747993

SN - 3642049206

SN - 9783642049200

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 350

EP - 359

BT - Adaptive and Natural Computing Algorithms - 9th International Conference, ICANNGA 2009, Revised Selected Papers

T2 - 9th International Conference on Adaptive and Natural Computing Algorithms, ICANNGA 2009

Y2 - 23 April 2009 through 25 April 2009

ER -