Sparse Preference Learning
Evgeni Tsivtsivadze, Tom Heskes · Radboud Repository (Radboud University) · 2010
We propose a novel sparse preference learning/ranking algorithm.Our algorithm approximates the true utility function by a weighted sum of basis functions using the squared loss on pairs of data points, and is a generalization of the matching pursuit method.It can operate both in a supervised and a semi-supervised setting and allows efficient search for multiple, near-optimal solutions.In our experi ments we demonstrate that the proposed algorithm outperforms several state-ofthe-art learning methods when taking into account unlabeled data and performs comparably in a supervised learning scenario, while providing sparser solution.1 Introduction Learning preference relations involves prediction of ordering of the data points rather than prediction of a single numerical value as in the case of regression or a class label as in the case of a classification task.The ranking problem can be considered as a special case of preference learning when a strict order is defined over all data points.Despite notable progress in the development and application of preference learning/ranking algorithms (e.g.[5]), so far the emphasis was mainly on improving the learning performance of the method (e.g.[2,1]) and much less is known about the models that focus in addition on interpretability and sparseness of the ranking solution.Besides interpretability, sparse models also lead to notably faster prediction times (that is an absolute necessity for a wide range of applications such as e.g.search engines), compared to the non-sparse counterparts.A ranking method that can lead to sparse solutions is RankSVM [6].However, in RankSVM sparsity control is not explicit and the produced models are usually far from being interpretable.Also note, that frequently ranking algorithms are not directly applicable to more general preference learning task or can become computationally expensive.In this paper we propose a sparse preference learning/ranking algorithm.Our method is a general ization of the (kernel) matching pursuit algorithm [9] and it approximates true utility function by a weighted sum of basis functions using squared loss on pairs of data points.Unlike existing methods our algorithm allows explicit control over sparsity of the model and can be applied to ranking and preference learning problems.Furthermore, an extension of the algorithm allows us to efficiently search for several near-optimal solutions instead of a single one.We show that our algorithm can op erate in supervised or semi-supervised setting, leads to sparse solutions, and improved performance compared to several baseline methods. 2 Problem Setting Let X be a set of instances and Y be a set of labels.We consider the label ranking task [5, 3] namely, we want to predict for any instance x e X a preference relation Px C Y x Y among the set of labels Y.We assume that the true preference relation Px is transitive and asymmetric for each instance x e X .Our training set {(qi; si)}™= i contains the data points (qi; s¿) = ((xi; y¿), s¿) e (X x Y ) x R