A Large Deviation Bound for the Area Under the ROC Curve
Shivani Agarwal, Thore Graepel, Ralf Herbrich, Dan Roth · 2004
The area under an ROC curve (AUC) has been advocated as an evaluation criterion for bipartite ranking problems. In this paper, we study large deviation properties of the AUC; in particular, we derive a distribution-free large deviation bound for the AUC which serves to bound the expected accuracy of a ranking function in terms of its empirical AUC on an independent test sequence. 1 A comparison of our result with a corresponding large deviation result for the classification error rate suggests that the test sample size required to obtain an ɛ-accurate estimate of the expected accuracy of a ranking function with δ-confidence is larger than that required to obtain an ɛ-accurate estimate of the expected error rate of a classification function with the same confidence. A simple application of the union bound allows the large deviation bound to be extended to learned ranking functions chosen from finite function classes. 1