TY - GEN

T1 - A uniform convergence bound for the area under the ROC curve

AU - Agarwal, Shivani

AU - Har-Peled, Sariel

AU - Roth, Dan

PY - 2005

Y1 - 2005

N2 - The area under the ROC curve (AUC) has been advocated as an evaluation criterion for the bipartite ranking problem. We study uniform convergence properties of the AUC; in particular, we derive a distribution-free uniform convergence bound for the AUC which serves to bound the expected accuracy of a learned ranking function in terms of its empirical AUC on the training sequence from which it is learned. Our bound is expressed in terms of a new set of combinatorial parameters that we term the bipartite rank-shatter coefficients; these play the same role in our result as do the standard VC-dimension related shatter coefficients (also known as the growth function) in uniform convergence results for the classification error rate. A comparison of our result with a recent uniform convergence result derived by Freund et al. [9] for a quantity closely related to the AUC shows that the bound provided by our result can be considerably tighter.

AB - The area under the ROC curve (AUC) has been advocated as an evaluation criterion for the bipartite ranking problem. We study uniform convergence properties of the AUC; in particular, we derive a distribution-free uniform convergence bound for the AUC which serves to bound the expected accuracy of a learned ranking function in terms of its empirical AUC on the training sequence from which it is learned. Our bound is expressed in terms of a new set of combinatorial parameters that we term the bipartite rank-shatter coefficients; these play the same role in our result as do the standard VC-dimension related shatter coefficients (also known as the growth function) in uniform convergence results for the classification error rate. A comparison of our result with a recent uniform convergence result derived by Freund et al. [9] for a quantity closely related to the AUC shows that the bound provided by our result can be considerably tighter.

UR - http://www.scopus.com/inward/record.url?scp=33749019257&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33749019257&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:33749019257

SN - 097273581X

SN - 9780972735810

T3 - AISTATS 2005 - Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics

SP - 1

EP - 8

BT - AISTATS 2005 - Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics

T2 - 10th International Workshop on Artificial Intelligence and Statistics, AISTATS 2005

Y2 - 6 January 2005 through 8 January 2005

ER -