On the Relationship Between Binary Classification, Bipartite Ranking, and Binary Class Probability Estimation

Harikrishna Narasimhan, Shivani AgarwalNeurIPS 2013 · OpenReview

TL;DR

This paper establishes new theoretical links between three foundational pillars of machine learning: binary classification, bipartite ranking, and class probability estimation (CPE). The authors introduce the concept of "weak regret transfer bounds," proving that a high-performing ranking model can be transformed into an effective classifier or probability estimator using only a small additional data sample for calibration.

The Problem: Connecting the Pillars of ML

In machine learning, we often treat classification (e.g., is this spam?), ranking (e.g., which email is more likely to be spam?), and probability estimation (e.g., what is the exact 87% chance this is spam?) as distinct tasks.

Mathematically, some relationships are already well-established. If you have a perfect probability model (CPE), you can easily build a perfect classifier by simply thresholding at 0.5, or a perfect ranker by sorting the probabilities. However, the reverse is not always true. Specifically, it was previously unclear if a good ranker—which only cares about the relative order of instances—could be "promoted" to a good classifier or a probability estimator.

Relationships between CPE, Ranking, and Classification (S = Strong, W = Weak)

The challenge lies in the fact that a ranker does not provide absolute scales. To turn a ranker into a classifier, you need a specific decision threshold; to turn it into a CPE model, you need to map its arbitrary scores to a strict [0, 1] probability range. This paper asks a fundamental question: Can we quantify how much "ranking quality" translates into "classification or CPE quality"?

Methods: Strong vs. Weak Regret Transfer Bounds

To bridge this gap, the authors introduce the concept of weak regret transfer bounds.

  • "Strong" bounds (which are already known for CPE to classification/ranking) allow you to transform one model to another using a fixed rule, regardless of the underlying data distribution.
  • "Weak" bounds (introduced in this paper) allow for a transformation that depends on the underlying data distribution. In practice, this means you need a small, labeled sample to "tune" the transformation.

The paper proposes two main transformation techniques to achieve this:

  1. Ranking to Classification: Finding an optimal threshold ($t$) that minimizes empirical classification error on a small validation set.
  2. Ranking to CPE: Using Isotonic Regression (specifically the Pool Adjacent Violators or PAV algorithm). This finds a monotonically increasing function that maps ranking scores to probabilities by minimizing squared error.

The core of the paper relies on a series of mathematical proofs showing that the "regret" (the gap between a model's performance and the theoretical optimum) of the resulting classifier or CPE model is strictly bounded by the regret of the original ranking model.

Key Insights and Results

To validate their theoretical bounds, the authors tested their methods on both high-dimensional synthetic datasets (where optimal "Bayes" performance could be calculated exactly) and real-world benchmarks from the UCI Machine Learning Repository (Spambase and Internet Ads).

Ranking is "Rich" Information

A good bipartite ranker (measured by AUC) actually captures a significant amount of the underlying distribution's structure. Even though it doesn't "know" absolute probabilities, it preserves the necessary ordering to reconstruct them. This provides a formal justification for why optimizing for AUC is often a good proxy for cost-sensitive classification, even when the specific costs of errors aren't known during training.

Data Efficiency and Empirical Superiority

The "weak" nature of these bounds is a feature, not a bug. The authors show that the sample size needed to calibrate a pre-existing ranker into a classifier is significantly smaller than the sample size needed to learn a classifier from scratch.

Empirical validation of regret bounds for Classification (a) and CPE (b)

In experiments on the UCI datasets, the authors demonstrated that if you have a good "legacy" ranking model and only a tiny bit of new data (e.g., 10-20% of the training set), you are much better off using that data to calibrate the ranker than you are trying to train a new Logistic Regression model from scratch. Furthermore, they proved that any algorithm that is "statistically consistent" for ranking (meaning it gets better with more data) can be turned into a consistent algorithm for classification or CPE using their transformation methods.

Limitations and Future Work

While the theoretical guarantees are strong, the authors note a few limitations:

  • Monotonicity Assumption: The transformation to CPE relies on the assumption that the true class probability is a monotonic function of the ranking scores. While often true for good rankers, it remains a strict theoretical requirement for the bounds to hold.
  • Distribution Dependence: Because the bounds are "weak," the transformation is tied to the specific distribution of the calibration data. If the data distribution shifts significantly (covariate shift), the threshold or calibration curve may become invalid.
  • Extension to Multiclass: This paper focuses strictly on binary (two-class) problems. Extending these regret transfer bounds to multiclass ranking or multi-label classification remains an open and complex challenge for future research.

Summary updated

Abstract

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).
BibTeX
@inproceedings{narasimhan2013relationship,
  author = {Harikrishna Narasimhan and Shivani Agarwal},
  title = {{On the Relationship Between Binary Classification, Bipartite Ranking, and Binary Class Probability Estimation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2013},
  url = {https://openreview.net/forum?id=BkbfnOZO-r},
}
Figure