Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Efficient Hold-Out for Subset ...

Efficient Hold-Out for Subset of Regressors

Tapio Pahikkala, Hanna Suominen, Jorma Boberg, Tapio Salakoski, Efficient Hold-Out for Subset of Regressors. In: Mikko Kolehmainen, Pekka Toivanen, Bartlomiej Beliczynski (Eds.), Proceedings of the 9th International Conference on Adaptive and Natural Computing Algorithms (ICANNGA'09), 5495, 350-359, Springer, 2009.

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+nH^2), 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/N^2+(nm^2)/N) and O(mn), respectively. Further, since sparse RLS can be trained in O(mn^2) time for several regularization parameter values in parallel, the fast hold-out algorithm enables efficient selection of the optimal parameter value.

Files:

Full publication in PDF-format

BibTeX entry:

@INPROCEEDINGS{inpPaSuBoSa09a,
  title = {Efficient Hold-Out for Subset of Regressors},
  booktitle = {Proceedings of the 9th International Conference on Adaptive and Natural Computing Algorithms (ICANNGA'09)},
  author = {Pahikkala, Tapio and Suominen, Hanna and Boberg, Jorma and Salakoski, Tapio},
  volume = {5495},
  editor = {Kolehmainen, Mikko and Toivanen, Pekka and Beliczynski, Bartlomiej},
  publisher = {Springer},
  pages = {350-359},
  year = {2009},
  keywords = {hold out, cross-validation, regularized least-squares, subset of regressors},
}

Belongs to TUCS Research Unit(s): Turku BioNLP Group

Edit publication