关键词: ranking 算法, 非凸上界, NDCG, 凹－凸过程, 割平面算法, 多类支持向量机

Abstract:

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.

Key words: ranking algorithm, non-convex upper bound, normalized discounted cumulative gain, concave-convex procedure, cutting plane algorithm, multi-class support vector machine