---

---

Tapio Pahikkala, Evgeni Tsivtsivadze, Antti Airola, Jorma Boberg, Tapio Salakoski:
Learning to Rank with Pairwise Regularized Least-Squares

Inproceeding
Year: 2007
Month: Jul
Booktitle: SIGIR 2007 Workshop on Learning to Rank for Information Retrieval
Editor: Joachims, Thorsten and Li, Hang and Liu, Tie-Yan and Zhai, ChengXiang
Pages: 27-33
Keywords: Information retrieval, Ranking, Regularized least-squares, Machine learning
Laboratory: Bioinformatics

Abstract

Learning preference relations between objects of interest is one of the key
problems in machine learning. Our approach for addressing this task is based on
pairwise comparisons for estimation of overall ranking. In this paper, we
propose a simple preference learning algorithm based on regularized least
squares and describe it within the kernel methods framework. Our algorithm, that
we call RankRLS, minimizes a regularized least-squares approximation of a
ranking error function that counts the number of incorrectly ranked pairs of
data points. We consider both primal and dual versions of the algorithm. The
primal version is preferable when the dimensionality of the feature space is
smaller than the number of training data points and the dual one is preferable
in the opposite case. We show that both versions of RankRLS can be trained as
efficiently as the corresponding versions of standard regularized least-squares
regression, despite the fact that the number of training data point pairs under
consideration grows quadratically with respect to the number of individual
points. As a representative example of a case where the data points outnumber
features we choose the Letor dataset. For the opposite case, we choose the parse
ranking task. We show that on the Letor dataset the primal RankRLS performs
comparably to RankSVM and RankBoost algorithms that are used as baselines.
Moreover, we show that the dual RankRLS notably outperforms the standard
regularized least-squares regression in parse ranking. We suggest that the main
advantage of RankRLS is the computational efficiency both in the primal and the
dual versions, especially since the efficient implementation of the latter is
not straightforward, for example, for the support vector machines.

Download abstract