A Large Deviation Bound for the Area Under the ROC Curve
Abstract
The area under the ROC curve (AUC) has been advocated as an evalu- ation criterion for the bipartite ranking problem. We study large devi- ation 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 inde- pendent test sequence. 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 ac- curacy of a ranking function with δ-confidence is larger than that required to obtain an -accurate estimate of the expected error rate of a classifi- cation 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.
Cite
Text
Agarwal et al. "A Large Deviation Bound for the Area Under the ROC Curve." Neural Information Processing Systems, 2004.Markdown
[Agarwal et al. "A Large Deviation Bound for the Area Under the ROC Curve." Neural Information Processing Systems, 2004.](https://mlanthology.org/neurips/2004/agarwal2004neurips-large/)BibTeX
@inproceedings{agarwal2004neurips-large,
title = {{A Large Deviation Bound for the Area Under the ROC Curve}},
author = {Agarwal, Shivani and Graepel, Thore and Herbrich, Ralf and Roth, Dan},
booktitle = {Neural Information Processing Systems},
year = {2004},
pages = {9-16},
url = {https://mlanthology.org/neurips/2004/agarwal2004neurips-large/}
}