Estimating the Arc Length of the Optimal ROC Curve and Lower Bounding the Maximal AUC

Song LiuNeurIPS 2022 · OpenReview

TL;DR

This paper reveals a surprising geometric connection: the arc length of an optimal Receiver Operating Characteristic (ROC) curve is actually an $f$-divergence. By leveraging this link, the author develops a variational method to estimate arc length from samples and introduces a novel two-step procedure to maximize a lower bound of the Area Under the Curve (AUC), showing competitive results on imbalanced classification tasks.

What Problem Does This Paper Address?

In binary classification, especially with imbalanced datasets, we often rely on ROC curves and the Area Under the Curve (AUC) to evaluate performance. Separately, in statistics and generative modeling, we use $f$-divergences (like KL-divergence or Total Variation distance) to measure how different two distributions are.

Examples of 1D distributions and their corresponding ROC curves.

A natural question arises: Is there a formal link between these two worlds? While previous research showed that the AUC itself is not an $f$-divergence, this paper investigates a different geometric property: the arc length of the ROC curve. The challenge lies in estimating these geometric properties and the underlying likelihood ratios directly from finite samples without knowing the true probability densities.

Methods

The author bridges the gap between ROC geometry and information theory through several key steps:

  1. Arc Length as Divergence: The paper proves that the arc length of an ROC curve (specifically, the length minus $\sqrt{2}$) is an $f$-divergence between the distributions of classification scores.
  2. The "Optimal" ROC Curve: When the classification score is a monotonic transform of the likelihood ratio, the ROC curve is "optimal" (it dominates all others). The arc length of this optimal curve—dubbed $\text{ROC}^*$—becomes a direct measure of the discrepancy between the positive and negative data distributions.
Geometric parameterization of the optimal ROC curve using tangent vectors based on the likelihood ratio.
  1. Variational Estimation: Using Fenchel duality, the author transforms the arc length estimation into a variational optimization problem. They show that the function maximizing this objective is the arctangent of the likelihood ratio. This allows for estimation using a Reproducing Kernel Hilbert Space (RKHS) framework, which is strictly convex and easier to solve than non-convex log-likelihood ratio models.
  2. AUC Lower Bounding: The author proposes a way to parameterize the area between the ROC curve and the diagonal. This leads to a two-step algorithm:
  3. Step 1: Estimate the arctangent likelihood ratio from the data.
  4. Step 2: Use these estimates as weights in a second optimization to maximize a lower bound of the maximal AUC.

Datasets

  • Synthetic Data: One-dimensional Gaussian distributions were used to illustrate the geometric concepts and compare the proposed bounds against classical Total Variation (TV) bounds.
  • CIFAR-10: A standard image classification dataset. The author converted it into ten different "one-versus-the-rest" imbalanced binary classification tasks to evaluate the AUC maximization procedure.

Key Insights and Ideas

  • Geometry is Information: The arc length of an ROC curve isn't just a visual curiosity; it's a mathematically rigorous way to define the "distance" between two populations.
  • The Arctangent Trick: Modeling the arctangent of the likelihood ratio (rather than the ratio itself or its log) provides a bounded target function $[0, \pi/2]$. This leads to a more stable, strictly convex optimization problem with a guaranteed convergence rate of $O_p(n^{-\beta/4})$.
  • Tighter TV Bounds: The paper shows that the ROC arc length provides an upper bound for Total Variation distance that is tighter than several famous classical bounds (like Pinsker’s) when the distributions are significantly different.
  • Surface Area vs. Histograms: While standard AUC maximization (Wilcoxon-Mann-Whitney) essentially sums up "histogram bars" of the ROC curve, this new approach treats the AUC as a surface integral, dividing the space into small surface elements.

Key Results

  • Competitive Performance: On the CIFAR-10 imbalanced tasks, the proposed two-step procedure achieved AUC performance comparable to state-of-the-art AUC maximizers (like SPAUC) and significantly outperformed vanilla logistic regression.
  • Theoretical Soundness: The author provides a finite sample guarantee, proving that the estimator converges to the true arctangent likelihood ratio as the number of samples increases.
  • Computational Efficiency: The objective functions are summations over individual data points ($O(n)$), though calculating the weights in the second step requires sorting the dataset ($O(n \log n)$).

Limitations and Future Work

  • Differentiability Requirement: The proposed surface integration approach requires the score distributions to be differentiable. This means it may not be directly applicable to discrete score distributions without some form of smoothing.
  • Kernel Choice: The performance in the RKHS setting depends on the choice of kernel and regularization parameters, which can be sensitive.
  • Broader Applications: The author suggests that the arctangent likelihood ratio estimator could be useful in other fields, such as outlier detection or Neyman-Pearson classification, but these applications were not explored in this specific paper.

Summary updated

Abstract

In this paper, we show the arc length of the optimal ROC curve is an $f$-divergence. By leveraging this result, we express the arc length using a variational objective and estimate it accurately using positive and negative samples. We show this estimator has a non-parametric convergence rate $O_p(n^{-\beta/4})$ ($\beta \in (0,1]$ depends on the smoothness). Using the same technique, we show the surface area sandwiched between the optimal ROC curve and the diagonal can be expressed via a similar variational objective. These new insights lead to a novel two-step classification procedure that maximizes an approximate lower bound of the maximal AUC. Experiments on CIFAR-10 datasets show the proposed two-step procedure achieves good AUC performance in imbalanced binary classification tasks.
BibTeX
@inproceedings{liu2022estimating,
  author = {Song Liu},
  title = {{Estimating the Arc Length of the Optimal ROC Curve and Lower Bounding the Maximal AUC}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=q4IG88RJiMv},
}
Figure