A large deviation bound for the area under the ROC curve

Shivani Agarwal, Thore Graepel, Ralf Herbrich, Dan Roth

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationAdvances in Neural Information Processing Systems 17 - Proceedings of the 2004 Conference, NIPS 2004
PublisherNeural information processing systems foundation
ISBN (Print)0262195348, 9780262195348
StatePublished - Jan 1 2005
Event18th Annual Conference on Neural Information Processing Systems, NIPS 2004 - Vancouver, BC, Canada
Duration: Dec 13 2004Dec 16 2004

Publication series

NameAdvances in Neural Information Processing Systems
ISSN (Print)1049-5258

Other

Other18th Annual Conference on Neural Information Processing Systems, NIPS 2004
CountryCanada
CityVancouver, BC
Period12/13/0412/16/04

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing

Cite this