Modeling the Parameter Interactions in Ranking SVM with Low-Rank Approximation
Jun Xu, Wei Zeng, Yanyan Lan, Jiafeng Guo, Xueqi Cheng · IEEE Transactions on Knowledge and Data Engineering · 2018
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 = Σ(i,j)αijxi-xj), where αijdenotes 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 (d1,d2) and (d1,d3) share the document d1. Thus it is natural to ask if there also exist interactions over the model parameters α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 α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 αijis decomposed as a product of two low-dimensional vectors, i.e., αij=〈vi,vj〉, where vectors viand vjcorrespond 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.