Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Speeding up Greedy Forward Sel...

Speeding up Greedy Forward Selection for Regularized Least-Squares

Tapio Pahikkala, Antti Airola, Tapio Salakoski, Speeding up Greedy Forward Selection for Regularized Least-Squares. In: Sorin Khoshgoftaar Taghi M. Palade Vasile Pedrycz Witold Wani M. Arif Zhu Xingquan Draghici (Ed.), Proceedings of The Ninth International Conference on Machine Learning and Applications (ICMLA'10), 325-330, IEEE Computer Society, 2010.

Abstract:

We propose a novel algorithm for greedy forward feature selection for regularized least-squares (RLS) regression and classification, also known as the least-squares support vector machine or ridge regression. The algorithm, which we call greedy RLS, starts from the empty feature set, and on each iteration adds the feature whose addition provides the best leave-one-out cross-validation performance. Our method is considerably faster than the previously proposed ones, since its time complexity is linear in the number of training examples, the number of features in the original data set, and the desired size of the set of selected features. Therefore, as a side effect we obtain a new training algorithm for learning sparse linear RLS predictors which can be used for large scale learning. This speed is possible due to matrix calculus based short-cuts for leave-one-out and feature addition. We experimentally demonstrate the scalability of our algorithm compared to previously proposed implementations.

Files:

Abstract in PDF-format

Full publication in PDF-format

BibTeX entry:

@INPROCEEDINGS{inpPaAiSa10b,
  title = {Speeding up Greedy Forward Selection for Regularized Least-Squares},
  booktitle = {Proceedings of The Ninth International Conference on Machine Learning and Applications (ICMLA'10)},
  author = {Pahikkala, Tapio and Airola, Antti and Salakoski, Tapio},
  editor = {Draghici, Sorin Khoshgoftaar Taghi M. Palade Vasile Pedrycz Witold Wani M. Arif Zhu Xingquan},
  publisher = {IEEE Computer Society},
  pages = {325-330},
  year = {2010},
  keywords = {Regularized least-squares, feature selection, computational complexity, least-squares support vector machine, ridge regression, greedy algorithm},
}

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

Edit publication