Abstract
We reduce ranking, as measured by the Area Under the Receiver Operating Characteristic Curve (AUC), to binary classification. The core theorem shows that a binary classification regret of r on the induced binary problem implies an AUC regret of at most 2r. This is a large improvement over approaches such as ordering according to regressed scores, which have a regret transform of r ↦ nr where n is the number of elements.
Article PDF
Similar content being viewed by others
References
Agarwal, S., & Niyogi, P. (2005). Stability and generalization of bipartite ranking algorithms. In Proceedings of the eighteenth annual conference on computational learning theory (COLT) (pp. 32–47).
Agarwal, S., Har-Peled, S., & Roth, D. (2005). A uniform convergence bound for the area under the ROC curve. In Proceedings of the 10th international workshop on artificial intelligence and statistics.
Ailon, N., & Mohri, M. (2007). An efficient reduction of ranking to classification (Technical Report TR-2007-903). New York University.
Alon, N. (2006). Ranking tournaments. SIAM Journal on Discrete Mathematics, 20, 137–142.
Bansal, N., Coppersmith, D., & Sorkin, G. B. (2006). A winner–loser labeled tournament has at most twice as many outdegree misrankings as pair misrankings (IBM Research Report RC24107). November 2006.
Clémençon, S., Lugosi, G., & Vayatis, N. (2005). Ranking and scoring using empirical risk minimization. In Proceedings of the eighteenth annual conference on computational learning theory (COLT) (pp. 1–15).
Cohen, W., Schapire, R., & Singer, Y. (1999). Learning to order things. Journal of Artificial Intelligence Research, 10, 243–270.
Coppersmith, D., Fleischer, L., & Rudra, A. (2006). Ordering by weighted number of wins gives a good ranking for weighted tournaments. In Proceeding of the 17th annual symposium on discrete algorithms (SODA) (pp. 776–782).
Cortes, C., & Mohri, M. (2004). AUC optimization versus error rate minimization. In Advances in neural information processing systems (NIPS).
Freund, Y., Iyer, R., Schapire, R., & Singer, Y. (2003). An efficient boosting algorithm for combining preferences. Journal of Machine Learning Research, 4, 933–969.
Landau, H. (1953). On dominance relations and the structure of animal societies, III: the condition for a score structure. Bulletin of Mathematical Biophysics, 15, 143–148.
Langford, J., & Zadrozny, B. (2005). Estimating class membership probabilities using classifier learners. In Proceedings of the 10th international workshop on artificial intelligence and statistics.
Marshall, A., & Olkin, I. (1979). Mathematics in science and engineering: Vol. 143. Inequalities: theory of majorization and its applications. New York.
Rudin, C., Cortes, C., Mohri, M., & Schapire, R. (2005). Margin-based ranking meets boosting in the middle. In Proceedings of the eighteenth annual conference on computational learning theory (COLT).
Slater, P. (1961). Inconsistencies in a schedule of paired comparisons. Biometrika, 48, 303–312.
Author information
Authors and Affiliations
Corresponding author
Additional information
Editors: Claudio Gentile, Nader H. Bshouty.
Rights and permissions
About this article
Cite this article
Balcan, MF., Bansal, N., Beygelzimer, A. et al. Robust reductions from ranking to classification. Mach Learn 72, 139–153 (2008). https://doi.org/10.1007/s10994-008-5058-6
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10994-008-5058-6