A Sparse Regularized Least-Squares Preference Learning Algorithm




Tsivtsivadze E, Pahikkala T, Airola A, Boberg J, Salakoski T

Anders Holst, Per Kreuger, Peter Funk

2008

Frontiers in Artificial Intelligence and Applications

Proceedings of the Tenth Scandinavian Conference on Artificial Intelligence

TENTH SCANDINAVIAN CONFERENCE ON ARTIFICIAL INTELLIGENCE

FR ART INT

173

76

83

8

978-1-58603-867-0

0922-6389



Learning preferences between objects constitutes a challenging task that notably differs from standard classification or regression problems. The objective involves prediction of ordering of the data points. Furthermore, methods for learning preference relations usually are computationally more demanding than standard classification or regression methods. Recently, we have proposed a kernel based preference learning algorithm, called RankRLS, whose computational complexity is cubic with respect to the number of training examples. The algorithm is based on minimizing a regularized least-squares approximation of a ranking error function that counts the number of incorrectly ranked pairs of data points. When nonlinear kernel functions are used, the training of the algorithm might be infeasible if the amount of examples is large. In this paper, we propose a sparse approximation of RankRLS whose training complexity is considerably lower than that of basic RankRLS. In our experiments, we consider parse ranking, a common problem in natural language processing. We show that sparse RankRLS significantly outperforms basic RankRLS in this task. To conclude, the advantage of sparse RankRLS is the computational efficiency when dealing with large amounts of training data together with high dimensional feature representations.

Last updated on 2024-26-11 at 14:57