Analysis of k-partite ranking algorithm in area under the receiver operating characteristic curve criterion

The k-partite ranking, as an extension of bipartite ranking, is widely used in information retrieval and other computer applications. Such implement aims to obtain an optimal ranking function which assigns a score to each instance. The AUC (Area Under the ROC Curve) measure is a criterion which can be used to judge the superiority of the given k-partite ranking function. In this paper, we study the k-partite ranking algorithm in AUC criterion from a theoretical perspective. The generalization bounds for the k-partite ranking algorithm are presented, and the deviation bounds for a ranking function chosen from a finite function class are also considered. The uniform convergence bound is expressed in terms of a new set of combinatorial parameters which we define specially for the k-partite ranking setting. Finally, the generally margin-based bound for k-partite ranking algorithm is derived.