Distribution-free binary classification: prediction sets, confidence intervals and calibration

Abstract

We study three notions of uncertainty quantification -- calibration, confidence intervals and prediction sets -- for binary classification in the distribution-free setting, that is without making any distributional assumptions on the data. With a focus towards calibration, we establish a 'tripod' of theorems that connect these three notions for score-based classifiers. A direct implication is that distribution-free calibration is only possible, even asymptotically, using a scoring function whose level sets partition the feature space into at most countably many sets. Parametric calibration schemes such as variants of Platt scaling do not satisfy this requirement, while nonparametric schemes based on binning do. To close the loop, we derive distribution-free confidence intervals for binned probabilities for both fixed-width and uniform-mass binning. As a consequence of our 'tripod' theorems, these confidence intervals for binned probabilities lead to distribution-free calibration. We also derive extensions to settings with streaming data and covariate shift.

arXiv comment34 pages; significant updates from previous version (unambiguous notation, better exposition, and cleaner results); originally appeared as a spotlight at Neural Information Processing Systems (NeurIPS) '20

References in corpus (10)

• What Uncertainties Do We Need in Bayesian Deep Learning for Computer Vision?
• On Calibration of Modern Neural Networks
• Deep Anomaly Detection with Outlier Exposure
• Accurate Uncertainties for Deep Learning Using Calibrated Regression
• Evaluating model calibration in classification
• Time-uniform Chernoff bounds via nonnegative supermartingales
• Mix-n-Match: Ensemble and Compositional Methods for Uncertainty Calibration in Deep Learning
• Dirichlet-based Gaussian Processes for Large-scale Calibrated Classification
• Calibration tests in multi-class classification: A unifying framework
• Large-scale probabilistic predictors with and without guarantees of validity

Cited by in corpus (2)

• Regression Diagnostics meets Forecast Evaluation: Conditional Calibration, Reliability Diagrams, and Coefficient of Determination
• Don't Just Blame Over-parametrization for Over-confidence: Theoretical Analysis of Calibration in Binary Classification