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

ABSTRACT

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.

KEYWORDS:

• Statistical learning theory
• k-partite ranking
• AUC criterion
• shatter coefficient
• margin

CLASSIFICATION:

• 60J20
• 68Q32

Acknowledgments

We thank the reviewers for their constructive comments and detailed suggestions in improving the quality of this paper.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported in part by the National Natural Science Foundation of China (11401519) and PhD initial funding of the first author.