Journal of South China University of Technology(Natural Science Edition) ›› 2012, Vol. 40 ›› Issue (4): 57-63.

• Computer Science & Technology • Previous Articles     Next Articles

Construction Algorithm of ranking Model Based on Non-Convex Upper Bound

Cheng Fan1,2  Wang Xu-fa1  Li Long-shu2   

  1. 1．School of Computer Science and Technology,University of Science and Technology of China,Hefei 230027,Anhui,China; 2．School of Computer Science and Technology,Anhui University,Hefei 230039,Anhui,China
  • Received:2011-06-27 Revised:2011-11-28 Online:2012-04-25 Published:2012-03-01
  • Contact: 程凡(1979-) ，男，博士生，讲师，主要从事信息检索、机器学习研究． E-mail:chengfan@mail.ustc.edu.cn
  • About author:程凡(1979-) ，男，博士生，讲师，主要从事信息检索、机器学习研究．
  • Supported by:

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

PDF

618

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

CLC Number: