On Theoretically Optimal Ranking Functions in Bipartite Ranking

• 成果类型: Article
• 署名作者: Uematsu, Kazuki; Lee, Yoonkyung
• 署名单位: University System of Ohio; Ohio State University
• 刊物名称: JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION
• ISSN/ISSBN: 0162-1459
• DOI: 10.1080/01621459.2016.1215988
• 发表日期: 2017
• 页码: 1311-1322
• 关键词: Classification; AREA

摘要

This article investigates the theoretical relation between loss criteria and the optimal ranking functions driven by the criteria in bipartite ranking. In particular, the relation between area under the ROC curve (AUC) maximization and minimization of ranking risk under a convex loss is examined. We characterize general conditions for ranking-calibrated loss functions in a pairwise approach, and show that the best ranking functions under convex ranking-calibrated loss criteria produce the same ordering as the likelihood ratio of the positive category to the negative category over the instance space. The result illuminates the parallel between ranking and classification in general, and suggests the notion of consistency in ranking when convex ranking risk is minimized as in the RankBoost algorithm for instance. For a certain class of loss functions including the exponential loss and the binomial deviance, we specify the optimal ranking function explicitly in relation to the underlying probability distribution. In addition, we present an in-depth analysis of hinge loss optimization for ranking and point out that the RankSVM may produce potentially many ties or granularity in ranking scores due to the singularity of the hinge loss, which could result in ranking inconsistency. The theoretical findings are illustrated with numerical examples. Supplementary materials for this article are available online.