Finite-sample Calibration Guarantees for Binary Segmentation

Bruno Viti, Martin HollerarXiv 2026 · arXiv

TL;DR

Researchers have developed a new post-hoc calibration method for binary segmentation that provides formal, finite-sample theoretical guarantees. By deriving a novel concentration inequality that accounts for the spatial correlation between pixels, the authors ensure that a model’s confidence scores actually reflect its true accuracy, outperforming standard baselines in high-stakes settings.

What Problem Does This Paper Address?

In machine learning, calibration is the art of ensuring that a model's "confidence" matches reality. If a medical imaging model says a pixel has a 90% chance of being a tumor, it should be correct 90% of the time. Unfortunately, modern deep neural networks are notoriously overconfident.

While calibration is well-studied for simple classification, image segmentation presents a unique challenge: spatial dependence. In a classification task, samples are usually independent. In segmentation, pixels are highly correlated with their neighbors. Standard statistical tools (like Hoeffding’s inequality) assume independence (i.i.d.), making their theoretical guarantees invalid for images. This paper fills that gap by providing a mathematical framework to guarantee calibration even when pixels "talk" to each other.

Methods

The authors build upon a histogram binning approach. They partition the model's raw confidence scores into $B$ bins and calculate the actual accuracy (label frequency) within each bin on a held-out calibration set. At test time, the raw score is replaced by the bin's historical accuracy.

The core innovation lies in the theoretical guarantees:

  1. Spatial Concentration Inequality: They derived a new bound for the mean of Bernoulli random variables that explicitly accounts for spatial dependence. They use a coupling matrix $\bar{D}$ to quantify how much the distribution of one pixel is influenced by others.
  2. Empirical Estimation: Since the coupling matrix isn't analytically known for complex images, they estimate it using a lightweight autoregressive model (similar to PixelCNN). This model learns the joint distribution of labels to see how influence decays over distance.
  3. Randomized Calibrator: To satisfy "conditional" calibration (guarantees for specific confidence levels, not just the average), they introduce a tiny amount of random noise to the output, making the binning scheme mathematically recoverable.

Datasets

The authors evaluated their method across nine diverse datasets to ensure robustness across medical and general domains:

  • Medical: ISIC (skin lesions), Kvasir-SEG (polyps), TN3K (thyroid nodules), and BUSI (breast ultrasound).
  • General/Urban: Cityscapes (autonomous driving), FLAIR1 (aerial imagery), Oxford-IIIT Pet, and two subsets of MS COCO (Animals and Vehicles).

Key Insights and Ideas

  • Pixels as Data Points: A key "aha" moment is that even with only 50 calibration images, treating every pixel as a data point provides a massive effective sample size. This allows for very tight statistical guarantees that are practical for real-world use.
  • The i.i.d. Fallacy: The paper demonstrates that assuming pixels are independent leads to "guarantees" that are far too optimistic. Their spatially-aware bound is looser but actually holds true when tested against empirical data.
  • Conditional vs. Marginal: Most calibration methods only care about being right on average (marginal). This paper pushes for conditional calibration, ensuring that every confidence level (e.g., exactly 0.7) is reliable. This is much harder to achieve but vital for safety-critical applications.

Key Results

  • Superior Performance: The proposed binning strategy consistently outperformed six popular baselines, including Temperature Scaling, Isotonic Regression, and Meta-cal.
  • The Only Reliable Option for Conditional Calibration: In the difficult conditional calibration setting, the authors' method was the only one capable of attaining low calibration error ($<0.1$) with high probability ($>90\%$) across most datasets.
  • Efficiency: Despite the complex math, the calibration process is fast. The "Binning" method takes between 0.6 and 5 seconds to run, significantly faster than "Selective Scaling," which can take up to 20 minutes.
  • Validity Curves: Empirical tests showed that the actual calibration error stayed safely below the theoretically derived "guarantee" line, proving the math works in practice.

Limitations and Future Work

  • Binary Only: The current framework is strictly for binary segmentation (foreground vs. background). Extending this to multi-class problems (e.g., identifying different types of organs or road objects) is a major next step.
  • Empirical Dependence: The final guarantee relies on an empirical estimate of the spatial decay. While the authors show this estimate is stable, a purely analytical bound would be the "holy grail."
  • Supremum Looseness: To ensure the guarantee holds for any possible image, the authors have to take the "worst-case" spatial influence, which might make the bounds more conservative (looser) than necessary for typical images.
  • Region-Specific Guarantees: Currently, the guarantee is pixel-wise. Future work could explore whether we can provide guarantees for specific regions or objects within an image.

Summary updated

Abstract

Machine learning based segmentation models are frequently miscalibrated, producing for each pixel a label prediction whose associated confidence does not accurately reflect the true underlying probability. This limitation is particularly critical in high-stakes applications such as medical image segmentation. Although several calibration methods have been proposed, only a small subset of them provides theoretical guarantees on the calibration error, i.e., they do not typically ensure that, with high probability, the model exhibits a low calibration error. In this work, we develop a post-hoc calibration method for which formal calibration guarantees can be established. To achieve this, we derive from standard concentration inequalities an improved theoretical bound that explicitly accounts for the spatial dependence inherent in binary segmentation outputs. We empirically demonstrate that the proposed calibrator satisfies the derived guarantee and outperforms existing post-hoc calibration approaches.
BibTeX
@misc{viti2026finite,
  author = {Bruno Viti and Martin Holler},
  title = {{Finite-sample Calibration Guarantees for Binary Segmentation}},
  year = {2026},
  eprint = {2611.09120},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.09120},
}
Figure