Abstract: The discriminant model learned by traditional ranking algorithm based on Pairwise method is not accurate. Aiming at the above problem, a novel ranking algorithm based on Listwise method is proposed. The algorithm uses the discriminative model and adopts one-slack Support Vector Machine(SVM) as its framework. On this basis, the algorithm defines its objective function. In order to solve the problem of exponential size of constraints in the optimization, a cutting plane algorithm is introduced. For the sub-problem of finding the most violated constraints, the paper presents to view it as a linear assignment problem, and adopts Hungarian method to solve it. Experimental results on the benchmark datasets prove the effectiveness and stability of the algorithm.

Key words: ranking algorithm, structured learning, Listwise method, Support Vector Machine(SVM), Hungarian method

摘要： 基于Pairwise的排序算法得到的判别式模型准确率较低。为此，提出一种基于Listwise的新型排序算法。采用判别式模型，将基于1-slack的支持向量机作为算法框架，定义算法的优化目标。由于该目标的约束条件太多，难以直接优化，因此使用割平面法求解。对于算法内部寻找最违背排列的子问题，将其看作一个线性指派问题，采用匈牙利法求解。在基准数据集上的实验结果验证该算法的有效性和稳定性。

关键词: 排序算法, 结构化学习, Listwise法, 支持向量机, 匈牙利法

CLC Number: 

• TP181