Seminar: Yoonkyung Lee

This talk examines the theoretical relation between loss criteria used in ranking and the optimal ranking functions driven by the criteria. We investigate the relation between AUC maximization and minimization of ranking risk under a convex loss in bipartite ranking, and characterize general conditions for ranking-calibration akin to classification-calibration. The best ranking functions under convex ranking-calibrated loss criteria are shown to produce the same ordering of instances 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 bipartite ranking. The optimality of ranking algorithms is further considered in multipartite ranking through minimization of the theoretical risk which combines pairwise ranking errors of ordinal categories with differential ranking costs. The extension shows that for a certain class of convex loss functions, the optimal ranking function can be represented as a ratio of weighted conditional probability of the upper categories to the lower categories, where the weights are given by the pairwise ranking costs. The theoretical findings are illustrated with numerical examples.

 

This is joint work with Kazuki Uematsu.