Modeling the Parameter Interactions in Ranking SVM with Low-Rank Approximation

摘要

Ranking SVM, which formalizes the problem of learning a ranking model as that of learning a binary SVM on preference pairs of documents, is a state-of-the-art ranking model in information retrieval. The dual form solution of a linear Ranking SVM model can be written as a linear combination of the preference pairs, i.e., w = Sigma((i,j)) alpha(ij) (x(i) - x(j)), where alpha(ij) denotes the Lagrange parameters associated with each preference pair (i, j). It is observed that there exist obvious interactions among the document pairs because two preference pairs could share a same document as their items, e.g., preference pairs (d(1), d(2)) and (d(1), d(3)) share the document d(1). Thus it is natural to ask if there also exist interactions over the model parameters alpha(ij), which may be leveraged to construct better ranking models. This paper aims to answer the question. We empirically found that there exists a low-rank structure over the rearranged Ranking SVM model parameters alpha(ij), which indicates that the interactions do exist. Based on the discovery, we made modifications on the original Ranking SVM model by explicitly applying low-rank constraints to the Lagrange parameters, achieving two novel algorithms called Factorized Ranking SVM and Regularized Ranking SVM, respectively. Specifically, in Factorized Ranking SVM each parameter alpha(ij) is decomposed as a product of two low-dimensional vectors, i.e., alpha(ij) = < v(i), v(j)>, where vectors v(i) and v(j) correspond to document i and j, respectively; In Regularized Ranking SVM, a nuclear norm is applied to the rearranged parameters matrix for controlling its rank. Experimental results on three LETOR datasets show that both of the proposed methods can outperform state-of-the-art learning to rank models including the conventional Ranking SVM.