Consistent Binary Classification with Generalized Performance Metrics

Oluwasanmi Koyejo, Nagarajan Natarajan, Pradeep Ravikumar, Inderjit S. DhillonNeurIPS 2014 · OpenReview

Introduction

In many real-world machine learning applications, standard classification accuracy is an inadequate metric. In domains like medical diagnosis or fraud detection, the cost of a "false negative" often far outweighs a "false positive," and datasets frequently suffer from severe class imbalance. To address this, practitioners rely on specialized metrics such as the F1-score, Jaccard similarity coefficient, or the AM measure.

Despite the widespread use of these metrics, two major theoretical gaps have persisted:

  1. The "Optimal" Classifier: For many of these complex metrics, it was not theoretically clear what the Bayes optimal decision rule actually looked like.
  2. Statistical Consistency: There was a lack of algorithms guaranteed to converge to this optimal performance as more data becomes available, particularly for metrics defined as ratios of linear combinations of the confusion matrix.

This paper provides a unified theoretical framework for a wide range of binary classification metrics, proving that the optimal classifier for any metric in this family is a thresholded version of the conditional class probability. Furthermore, it introduces two simple, statistically consistent algorithms to find that optimal threshold.

Theoretical Framework: Generalized Performance Metrics

The authors define a "Generalized Performance Metric" as any ratio of linear combinations of the four fundamental population quantities: True Positives (TP), False Positives (FP), True Negatives (TN), and False Negatives (FN).

The Universal Form of Optimal Classifiers

The most striking insight of the paper is that almost all popular binary metrics share the same optimal functional form. The authors prove that for any metric in this family, the optimal classifier always takes the form:

$$\theta^*(x) = \text{sign}(P(Y=1|x) - \delta^*)$$

Where $P(Y=1|x)$ is the probability of the positive class given the input (often denoted as $\eta(x)$), and $\delta^*$ is a metric-dependent threshold.

Optimal thresholds for various metrics

Unlike standard accuracy, where the optimal threshold is always 0.5, the optimal threshold for generalized metrics depends on both the metric's specific constants and the underlying data distribution. Whether optimizing for Accuracy, F-measure, or Precision, the strategy remains to threshold the class probability; only the location of the threshold changes.

Proposed Algorithms

To estimate this optimal classifier in practice, the paper proposes two statistically consistent approaches:

  1. Two-Step Expected Utility Maximization (Algorithm 1):
  2. Step 1: Estimate the conditional probability $P(Y=1|x)$ using a standard method like logistic regression.
  3. Step 2: Perform a one-dimensional search on a validation set to find the threshold $\delta$ that maximizes the target metric.
  4. Weighted Empirical Risk Minimization (Algorithm 2):
  5. This approach utilizes cost-sensitive surrogate losses (such as weighted hinge or logistic loss). It searches for the optimal "weight" (which corresponds to a threshold) that maximizes the performance metric.

These algorithms provide a theoretical "blessing" to common practitioner heuristics—such as searching for the best threshold on a validation set—proving that these methods are asymptotically consistent when implemented correctly.

Empirical Results

The authors evaluated their algorithms on several benchmark datasets, focusing on those with class imbalances, including REUTERS-21578, LETTERS, SCENE, and WEB PAGE.

F-measure performance across datasets

The empirical gains are substantial. For instance, on the SCENE dataset (a 6-class image categorization task evaluated for binary F-measure), Algorithm 1 achieved an F1-score of 0.6891. This vastly outperformed standard Empirical Risk Minimization (ERM)—which relies on a default 0.5 threshold—which only achieved 0.3953.

Furthermore, on the REUTERS dataset, as the number of positive instances ($C$) increased, the proposed algorithms consistently matched or exceeded the performance of existing state-of-the-art methods specifically tuned for F-measures, demonstrating robust handling of class imbalance.

Limitations and Future Work

While the paper establishes a strong foundation, it notes a few limitations:

  • Binary Limitation: The current framework is strictly limited to binary classification. Extending these consistency results to multi-class and multi-label domains remains a significant next step.
  • Convergence Rates: The authors provide rigorous proofs that both algorithms are $\mathcal{L}$-consistent (they converge to the optimal possible metric value as $n \to \infty$). However, the paper does not provide specific convergence rates detailing exactly how much data is needed to get within $\epsilon$ of the optimum.
  • Threshold Search: Both algorithms require a one-dimensional search for the optimal threshold or weight. While computationally efficient, this adds a layer of complexity compared to simple "plug-and-play" classifiers.

Summary updated

Abstract

Performance metrics for binary classification are designed to capture tradeoffs between four fundamental population quantities: true positives, false positives, true negatives and false negatives. Despite significant interest from theoretical and applied communities, little is known about either optimal classifiers or consistent algorithms for optimizing binary classification performance metrics beyond a few special cases. We consider a fairly large family of performance metrics given by ratios of linear combinations of the four fundamental population quantities. This family includes many well known binary classification metrics such as classification accuracy, AM measure, F-measure and the Jaccard similarity coefficient as special cases. Our analysis identifies the optimal classifiers as the sign of the thresholded conditional probability of the positive class, with a performance metric-dependent threshold. The optimal threshold can be constructed using simple plug-in estimators when the performance metric is a linear combination of the population quantities, but alternative techniques are required for the general case. We propose two algorithms for estimating the optimal classifiers, and prove their statistical consistency. Both algorithms are straightforward modifications of standard approaches to address the key challenge of optimal threshold selection, thus are simple to implement in practice. The first algorithm combines a plug-in estimate of the conditional probability of the positive class with optimal threshold selection. The second algorithm leverages recent work on calibrated asymmetric surrogate losses to construct candidate classifiers. We present empirical comparisons between these algorithms on benchmark datasets.
BibTeX
@inproceedings{koyejo2014consistent,
  author = {Oluwasanmi Koyejo and Nagarajan Natarajan and Pradeep Ravikumar and Inderjit S. Dhillon},
  title = {{Consistent Binary Classification with Generalized Performance Metrics}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=SkZmMtb_-B},
}
Figure