Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Greedy RankRLS: a Linear Time ...

Greedy RankRLS: a Linear Time Algorithm for Learning Sparse Ranking Models

Tapio Pahikkala, Antti Airola, Pekka Naula, Tapio Salakoski, Greedy RankRLS: a Linear Time Algorithm for Learning Sparse Ranking Models. In: Evgeniy Gabrilovich, Alexander J. Smola, Naftali Tishby (Eds.), SIGIR 2010 Workshop on Feature Generation and Selection for Information Retrieval, 11-18, ACM, 2010.

Abstract:

Ranking is a central problem in information retrieval. Much work has been done in the recent years to automate the development of ranking models by means of supervised machine learning. Feature selection aims to provide sparse models which are computationally efficient to evaluate, and have good ranking performance. We propose integrating the feature selection as part of the training process for the rank- ing algorithm, by means of a wrapper method which performs greedy forward selection, using leave-query-out cross-validation estimate of performance as the selection criterion. We introduce a linear time training algorithm we call greedy RankRLS, which combines the aforementioned procedure, together with regularized risk minimization based on pairwise least-squares loss. The training complexity of the method is O(kmn), where k is the number of features to be selected, m is the number of training examples, and n is the overall number of features. Experiments on the LETOR benchmark data set demonstrate that the approach works in practice.

Files:

Full publication in PDF-format

BibTeX entry:

@INPROCEEDINGS{inpPaAiNaSa10a,
  title = {Greedy RankRLS: a Linear Time Algorithm for Learning Sparse Ranking Models},
  booktitle = {SIGIR 2010 Workshop on Feature Generation and Selection for Information Retrieval},
  author = {Pahikkala, Tapio and Airola, Antti and Naula, Pekka and Salakoski, Tapio},
  editor = {Gabrilovich, Evgeniy and Smola, Alexander J. and Tishby, Naftali},
  publisher = {ACM},
  pages = {11-18},
  year = {2010},
  keywords = {feature selection, learning to rank, ranking, RankRLS, regularized least-squares, variable selection},
}

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

Edit publication