TY - GEN
T1 - Adaptive estimation of the optimal ROC curve and a bipartite ranking algorithm
AU - Clémençon, Stéphan
AU - Vayatis, Nicolas
PY - 2009/12/1
Y1 - 2009/12/1
N2 - In this paper, we propose an adaptive algorithm for bipartite ranking and prove its statistical performance in a stronger sense than the AUC criterion. Our procedure builds on and significantly improves the RankOver algorithm proposed in [1]. The algorithm outputs a piecewise constant scoring rule which is obtained by overlaying a finite collection of classifiers. Here, each of these classifiers is the empirical solution of a specific minimum-volume set (MV-set) estimation problem. The major novelty arises from the fact that the levels of the MV-sets to recover are chosen adaptively from the data to adjust to the variability of the target curve. The ROC curve of the estimated scoring rule may be interpreted as an adaptive spline approximant of the optimal ROC curve. Error bounds for the estimate of the optimal ROC curve in terms of the L∞-distance are also provided.
AB - In this paper, we propose an adaptive algorithm for bipartite ranking and prove its statistical performance in a stronger sense than the AUC criterion. Our procedure builds on and significantly improves the RankOver algorithm proposed in [1]. The algorithm outputs a piecewise constant scoring rule which is obtained by overlaying a finite collection of classifiers. Here, each of these classifiers is the empirical solution of a specific minimum-volume set (MV-set) estimation problem. The major novelty arises from the fact that the levels of the MV-sets to recover are chosen adaptively from the data to adjust to the variability of the target curve. The ROC curve of the estimated scoring rule may be interpreted as an adaptive spline approximant of the optimal ROC curve. Error bounds for the estimate of the optimal ROC curve in terms of the L∞-distance are also provided.
U2 - 10.1007/978-3-642-04414-4_20
DO - 10.1007/978-3-642-04414-4_20
M3 - Conference contribution
AN - SCOPUS:77952075199
SN - 3642044131
SN - 9783642044137
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 216
EP - 231
BT - Algorithmic Learning Theory - 20th International Conference, ALT 2009, Proceedings
T2 - 20th International Conference on Algorithmic Learning Theory, ALT 2009
Y2 - 3 October 2009 through 5 October 2009
ER -