[工程科技]Generalization bounds for the area under the ROC curve.pdf

Journal of Machine Learning Research 6 (2005) 393–425 Submitted 6/04; Published 4/05 Generalization Bounds for the Area Under the ROC Curve∗ Shivani Agarwal SAGARWAL@CS .UIUC .EDU Department of Computer Science University of Illinois at Urbana-Champaign 201 North Goodwin Avenue Urbana, IL 61801, USA Thore Graepel THOREG @MICROSOFT.COM Ralf Herbrich RHERB @MICROSOFT.COM Microsoft Research 7 JJ Thomson Avenue Cambridge CB3 0FB, UK Sariel Har-Peled SARIEL@CS .UIUC .EDU Dan Roth DANR @CS .UIUC .EDU Department of Computer Science University of Illinois at Urbana-Champaign 201 North Goodwin Avenue Urbana, IL 61801, USA Editor: Michael I. Jordan Abstract We study generalization properties of the area under the ROC curve (AUC), a quantity that has been advocated as an evaluation criterion for the bipartite ranking problem. The AUC is a different term than the error rate used for evaluation in classification problems; consequently, existing generaliza- tion bounds for the classification error rate cannot be used to draw conclusions about the AUC. In this paper, we define the expected accuracy of a ranking function (analogous to the expected error rate of a classification function), and derive distribution-free probabilistic bounds on the deviation of the empirical AUC of a ranking function (observed on a finite data sequence) from its expected accuracy. We derive both a large deviation bound, which serves to bound the