基于非凸上界的ranking模型构造算法

摘要

As the existing ranking algorithms all construct models by minimizing the convex upper bound of the original objective functions, the constructed models are imprecise. In order to solve this problem, a ranking algorithm based on non-convex upper bound is proposed. In this algorithm, first, a framework based on multi-class support vector machine (SVM) is constructed and an objective function directly optimizing the NDCG (Normalized Discounted Cumulative Gain) is defined. Then, a tighter non-convex upper bound is designed to approximate the original objective function. Moreover, a concave-convex procedure is carried out and the cutting plane algorithm is used to remedy the non-convex and non-smooth characteristics of the objective function. The proposed algorithm is finally verified on the benchmark datasets. The results show that, as compared with the existing ranking algorithms based on convex upper bound, the proposed algorithm is more effective in constructing models with high accuracy and strong stability.%现有的ranking算法均通过最小化原目标函数的凸上界构造ranking模型,得到的模型不够精确.为此,文中提出一种基于非凸上界的ranking算法.该算法首先给出一个基于多类支持向量机(SVM)的框架,然后定义面向NDCG的目标函数,在此基础上设计一个比现有的凸上界更为紧凑的非凸上界逼近原目标函数；针对上界函数的非凸非光滑,提出使用凹-凸过程进行凸逼近,并采用割平面算法进行求解；最后,通过在基准数据集上的实验对该算法进行验证,并与现有算法进行对比.结果表明,相比现有的基于凸上界的ranking算法,文中算法得到的模型不但更为精确,而且更加稳定.