基于Listwise的新型排序算法  

Novel Ranking Algorithm Based on Listwise

作　　者：程凡[1] 李龙澍[1] 

机构地区：[1]安徽大学计算机科学与技术学院,合肥230039

出　　处：《计算机工程》2011年第23期165-167,共3页Computer Engineering

基　　金：教育部人文社科青年基金资助项目(10YJC630398);安徽省自然科学基金资助项目(090412054);安徽省科技攻关计划重大科技专项基金资助项目(08010201002)

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

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

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]