We investigate the relationship between three fundamental problems in machine learning: binary classification, bipartite ranking, and binary class probability estimation (CPE). It is known that a good binary CPE model can be used to obtain a good binary classification model (by thresholding at 0.5), and also to obtain a good bipartite ranking model (by using the CPE model directly as a ranking model); it is also known that a binary classification model does not necessarily yield a CPE model. However, not much is known about other directions. Formally, these relationships involve regret transfer bounds. In this paper, we introduce the notion of weak regret transfer bounds, where the mapping needed to transform a model from one problem to another depends on the underlying probability distribution (and in practice, must be estimated from data). We then show that, in this weaker sense, a good bipartite ranking model can be used to construct a good classification model (by thresholding at a suitable point), and more surprisingly, also to construct a good binary CPE model (by calibrating the scores of the ranking model).
Author Information
Harikrishna Narasimhan (Google AI)
Shivani Agarwal (University of Pennsylvania)
More from the Same Authors

2016 Poster: Dueling Bandits: Beyond Condorcet Winners to General Tournament Solutions »
Siddartha Y. Ramamohan · Arun Rajkumar · Shivani Agarwal · Shivani Agarwal 
2014 Workshop: Analysis of Rank Data: Confluence of Social Choice, Operations Research, and Machine Learning »
Shivani Agarwal · Hossein Azari Soufiani · Guy Bresler · Sewoong Oh · David Parkes · Arun Rajkumar · Devavrat Shah 
2014 Poster: On the Statistical Consistency of Plugin Classifiers for Nondecomposable Performance Measures »
Harikrishna Narasimhan · Rohit Vaish · Shivani Agarwal 
2014 Poster: Online and Stochastic Gradient Methods for Nondecomposable Loss Functions »
Purushottam Kar · Harikrishna Narasimhan · Prateek Jain 
2014 Poster: Online DecisionMaking in General Combinatorial Spaces »
Arun Rajkumar · Shivani Agarwal 
2013 Poster: Convex Calibrated Surrogates for LowRank Loss Matrices with Applications to Subset Ranking Losses »
Harish G Ramaswamy · Shivani Agarwal · Ambuj Tewari 
2013 Spotlight: On the Relationship Between Binary Classification, Bipartite Ranking, and Binary Class Probability Estimation »
Harikrishna Narasimhan · Shivani Agarwal 
2013 Spotlight: Convex Calibrated Surrogates for LowRank Loss Matrices with Applications to Subset Ranking Losses »
Harish G Ramaswamy · Shivani Agarwal · Ambuj Tewari 
2012 Poster: Classification Calibration Dimension for General Multiclass Losses »
Harish G Ramaswamy · Shivani Agarwal 
2012 Spotlight: Classification Calibration Dimension for General Multiclass Losses »
Harish G Ramaswamy · Shivani Agarwal 
2009 Workshop: Advances in Ranking »
Shivani Agarwal · Chris J Burges · Yacov Crammer