Verified Uncertainty Calibration

Ananya Kumar, Percy Liang, Tengyu Ma

Abstract

Uncertainty calibration ensures that a model's predicted probabilities reflect actual likelihoods, a critical requirement for safety-sensitive AI applications. This paper identifies a fundamental "measurement gap" in existing calibration techniques: parametric scaling methods (like Platt scaling) produce continuous outputs whose true error is unmeasurable with finite samples, while histogram binning is measurable but data-inefficient. We propose the scaling-binning calibrator, a hybrid approach that leverages parametric scaling for sample efficiency and binning for provable verifiability. Coupled with a new debiased estimator for Expected Calibration Error (ECE), this framework enables more accurate and verifiable uncertainty quantification.

Introduction: The Calibration Problem

When a predictive model, such as a self-driving car's vision system, assigns a 99% probability to an event, that event should occur exactly 99% of the time. This alignment is known as uncertainty calibration. Modern deep neural networks are notoriously poorly calibrated, often exhibiting extreme overconfidence. To address this, researchers typically apply post-hoc calibration methods.

Two dominant paradigms currently exist:

  1. Scaling methods (e.g., Platt or Temperature scaling) fit smooth parametric functions to model outputs. While data-efficient, they produce a continuous range of probabilities, making it impossible to calculate the true calibration error with a finite number of samples.
  2. Histogram binning discretizes predictions into buckets. This makes error measurable but requires substantial data to achieve low variance, particularly as the number of classes increases.

The Measurement Gap

A core contribution of this paper is identifying a "measurement gap." Standard evaluation practices often use binning to assess scaling methods. However, the authors prove that binning systematically underestimates the error of continuous functions. Essentially, we have been grading our models with a rubric that is too lenient; if a model outputs continuous probabilities, one can never truly know its error—only a lower bound.

Proposed Methods

To bridge this gap, the authors propose a "best of both worlds" approach.

Comparison of calibration methods: (a) Platt scaling, (b) Histogram binning, and (c) the proposed Scaling-binning calibrator.

The Scaling-Binning Calibrator

This hybrid method operates in three distinct stages:

  • Scaling: A parametric function (e.g., a sigmoid) is fitted to uncalibrated outputs to reduce variance.
  • Binning: The output space is partitioned into discrete intervals (bins).
  • Discretization: Instead of using noisy raw labels in each bin, the calibrator outputs the average of the scaling function's values within that bin.

This approach achieves a sample complexity of $O(1/\epsilon^2 + B)$, which is significantly more efficient than the $O(B/\epsilon^2)$ required by standard histogram binning.

The Debiased Estimator

Standard "plugin" estimators for Expected Calibration Error (ECE) are biased—they tend to overestimate error due to noise in the samples. Borrowing techniques from meteorology, the authors introduce a debiased estimator that can measure calibration error with $O(\sqrt{B})$ samples instead of $O(B)$. This allows for much more precise verification of how well a model is actually performing.

Experimental Results

The methods were evaluated using CIFAR-10, ImageNet, and synthetic datasets, primarily utilizing the VGG-16 architecture.

  • Lower Error: On ImageNet, the scaling-binning calibrator achieved a 5x lower calibration error than standard histogram binning (for $B=100$). On CIFAR-10, the error was 35% lower.
  • Accurate Verification: The debiased estimator was shown to be significantly closer to the "ground truth" calibration error than standard estimators, particularly when the number of bins is large or the sample size is small.
  • Efficiency Trade-offs: While binning inherently discretizes the output—which can slightly increase Mean Squared Error (Brier score)—the authors demonstrate that this penalty is small compared to the gain in provable reliability.

Conclusion

By forcing models to output a finite set of probabilities, we trade a negligible amount of precision for the ability to prove a model is calibrated. The scaling-binning calibrator offers a practical way to achieve this verifiability without sacrificing the sample efficiency of parametric methods. To support the community, the authors have released a Python library, uncertainty-calibration, to make these verified tools accessible for general use.

Summary updated

BibTeX
@inproceedings{kumar2019verified,
  author = {Ananya Kumar and Percy Liang and Tengyu Ma},
  title = {{Verified Uncertainty Calibration}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=OKrJa8PgNgv},
}
Figure