@inproceedings{2b55c97a0ab94ec5bb664b6fa8f002dd,

title = "A large deviation bound for the area under the ROC curve",

abstract = "The area under the ROC curve (AUC) has been advocated as an evaluation criterion for the bipartite ranking problem. 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. 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.",

author = "Shivani Agarwal and Thore Graepel and Ralf Herbrich and Dan Roth",

year = "2005",

month = jan,

day = "1",

language = "English (US)",

isbn = "0262195348",

series = "Advances in Neural Information Processing Systems",

publisher = "Neural information processing systems foundation",

booktitle = "Advances in Neural Information Processing Systems 17 - Proceedings of the 2004 Conference, NIPS 2004",

note = "18th Annual Conference on Neural Information Processing Systems, NIPS 2004 ; Conference date: 13-12-2004 Through 16-12-2004",

}