一种新型直接优化NDCG的排序模型构造算法  

A new ranking model constructing algorithm based on direct optimization of NDCG

作　　者：程凡[1,2,3] 王煦法[2] 

机构地区：[1]安徽大学计算智能与信号处理教育部重点实验室,安徽合肥230039 [2]中国科学技术大学计算机科学与技术学院,安徽合肥230027 [3]安徽大学计算机学院,安徽合肥230039

出　　处：《中国科学技术大学学报》2013年第1期65-72,共8页JUSTC

基　　金：国家自然科学基金(60875027);安徽省自然科学基金(090412054;1104060M141);安徽省科技攻关计划重大科技专项项目(08010201002);安徽省高校优秀青年基金(2012SQRL016);安徽大学青年科学基金(KJQN1119);安徽大学计算智能与信号处理教育部重点实验室开放基金资助

摘　　要：针对现有直接优化NDCG的排序算法或基于虚梯度或基于结构化学习,其得到的模型均不够精确,提出一种新的排序算法.算法以多类SVM为框架,在此基础上设计了一个面向NDCG的目标函数.考虑到该函数的非光滑性,提出使用割平面算法进行求解,同时注意到已有割平面算法可能存在的"主问题"非单调递减,会降低算法的收敛速度,进而设计了一种高效的线性搜索算法对割平面的选择进行改进,确保了"主问题"的单调递减.基准数据集上的实验证明了所提算法的有效性.Existing ranking algorithms based on direct optimization of NDCG adopt etther the virtual gradient method or the structured learning method. However, models learned by these algorithms do not work well. To solve this problem, a new ranking algorithm was proposed, which used multi-class SVM as framework and defined an objective function related to NDCG. Faced with this non smooth function, the cutting plane algorithm was employed to overcome it. For the problem that the existing cutting plane algorithm may lead the master problem to decrease non-monotonically and converge slowly, an efficient line search algorithm was designed to improve the choices of cutting planes. Experimental results on the benchmark datasets prove the effectiveness of the proposed algorithm.

关 键 词：排序算法 NDCG 改进的割平面算法 线性搜索算法 多类SVM 

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