2021

Learn then Test: Calibrating Predictive Algorithms to Achieve Risk Control

Angelopoulos, Anastasios N., Bates, Stephen, Candès, Emmanuel J. et al.

Understand

We introduce a framework for calibrating machine learning models so that their predictions satisfy explicit, finite-sample statistical guarantees.

Our calibration algorithms work with any underlying model and (unknown) data-generating distribution and do not require model refitting.
The framework addresses, among other examples, false discovery rate control in multi-label classification, intersection-over-union control in instance segmentation, and the simultaneous control of the type-1 error of outlier detection and confidence set coverage in classification or regression.
Our main insight is to reframe the risk-control problem as multiple hypothesis testing, enabling techniques and mathematical arguments different from those in the previous literature.

Built on

“Determination of sample sizes for setting tolerance limits”
S.. Wilks · 1941
Earlier work this paper cites.
“Statistical prediction with special reference to the problem of tolerance limits”
S.. Wilks · 1942
Earlier work this paper cites.
“An extension of Wilks’ method for setting tolerance limits”
Abraham Wald · 1943
Earlier work this paper cites.
“Non-parametric estimation II. Statistically equivalent blocks and tolerance regions–the continuous case”
John. Tukey · 1947
Earlier work this paper cites.
“Probability inequalities for sums of bounded random variables”
Wassily Hoeffding · 1963
Earlier work this paper cites.
“On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities”
VN Vapnik and A Chervonenkis · 1971
Earlier work this paper cites.
“A Simple Sequentially Rejective Multiple Test Procedure”
Sture Holm · 1979
Earlier work this paper cites.
“Analyse von Verlaufskurven”
E. Sonnemann, H. Finner and T.. Kunert · 1986
Earlier work this paper cites.
“Multiple testing in clinical trials”
P Bauer · 1991
Earlier work this paper cites.
“A result of Vapnik with applications”
Martin Anthony and John Shawe-Taylor · 1993
Earlier work this paper cites.
“Vapnik-Chervonenkis bounds for generalization”
JMR Parrondo and C Van · 1993
Earlier work this paper cites.
“Some variants on a theorem of Vapnik”
Arne Hole · 1995
Earlier work this paper cites.
“The Nature of Statistical Learning Theory”
Vladimir Vapnik · 1995
Earlier work this paper cites.
“Machine-learning applications of algorithmic randomness”
Vladimir Vovk, Alexander Gammerman and Craig Saunders · 1999
Earlier work this paper cites.
“Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods”
John Platt · 1999
Earlier work this paper cites.
“An inequality for uniform deviations of sample averages from their means”
Peter Bartlett and Gábor Lugosi · 1999
Earlier work this paper cites.
“Greedy function approximation: a gradient boosting machine”
Jerome Friedman · 2001
Earlier work this paper cites.
“Inductive confidence machines for regression”
Harris Papadopoulos, Kostas Proedrou, Vladimir Vovk and Alex Gammerman · 2002
Earlier work this paper cites.
“Concentration inequalities, large and moderate deviations for self-normalized empirical processes”
Bernard Bercu, Elisabeth Gassiat and Emmanuel Rio · 2002
Earlier work this paper cites.
“A fixed sequence Bonferroni procedure for testing multiple endpoints”
Brian Wiens · 2003
Earlier work this paper cites.
“Ratio limit theorems for empirical processes”
Evarist Giné, Vladimir Koltchinskii and Jon Wellner · 2003
Earlier work this paper cites.
“On Hoeffding’s inequalities”
Vidmantas Bentkus · 2004
Earlier work this paper cites.
“Algorithmic Learning in a Random World”
Vladimir Vovk, Alex Gammerman and Glenn Shafer · 2005
Earlier work this paper cites.
“The fallback procedure for evaluating a single family of hypotheses”
Brian Wiens and Alexei Dmitrienko · 2005
Earlier work this paper cites.
“Statistical Tolerance Regions: Theory, Applications, and Computation”
K. Krishnamoorthy and T. Mathew · 2009
Earlier work this paper cites.

Similar

“A graphical approach to sequentially rejective multiple test procedures”
Frank Bretz, Willi Maurer, Werner Brannath and Martin Posch · 2009
Cited alongside, same era.
“Imagenet: A large-scale hierarchical image database”
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li and Li Fei-Fei · 2009
Cited alongside, same era.
“The medical expenditure panel survey: a national information resource to support healthcare cost research and inform policy and practice”
Joel Cohen, Steven Cohen and Jessica Banthin · 2009
Cited alongside, same era.
“Learning multiple layers of features from tiny images” https://www.cs.toronto. edu/kriz/learning-features-2009-TR.pdf
Alex Krizhevsky and Geoffrey Hinton · 2009
Cited alongside, same era.
“An asymptotically Gaussian bound on the Rademacher tails”
Iosif Pinelis · 2012
Cited alongside, same era.
“Concentration Inequalities”
Stéphane Boucheron, Gábor Lugosi and Pascal Massart · 2013
Cited alongside, same era.
“Classification with confidence”
Jing Lei · 2014
Cited alongside, same era.
“Microsoft COCO: Common objects in context”
Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár and C Zitnick · 2014
Cited alongside, same era.
“A conformal prediction approach to explore functional data”
Jing Lei, Alessandro Rinaldo and Larry Wasserman · 2015
Cited alongside, same era.
“Cross-conformal predictors”
Vladimir Vovk · 2015
Cited alongside, same era.
“Concentration inequalities for sampling without replacement”
Rémi Bardenet and Odalric-Ambrym Maillard · 2015
Cited alongside, same era.
“A tight Gaussian bound for weighted sums of Rademacher random variables”
Vidmantas Bentkus and Dainius Dzindzalieta · 2015
Cited alongside, same era.

Then

“Detectron2”, https://github.com/facebookresearch/detectron2 , 2019
Yuxin Wu, Alexander Kirillov, Francisco Massa, Wan-Yen Lo and Ross Girshick · 2019
Later among the works it cites.
“PAC confidence sets for deep neural networks via calibrated prediction”
Sangdon Park, Osbert Bastani, Nikolai Matni and Insup Lee · 2020
Later among the works it cites.
“Flexible distribution-free conditional predictive bands using density estimators”
Rafael Izbicki, Gilson Shimizu and Rafael Stern · 2020
Later among the works it cites.
“Classification with valid and adaptive coverage”
Yaniv Romano, Matteo Sesia and Emmanuel Candès · 2020
Later among the works it cites.
“Conformal calibrators”
Vladimir Vovk, Ivan Petej, Paolo Toccaceli, Alexander Gammerman, Ernst Ahlberg and Lars Carlsson · 2020
Later among the works it cites.
“Conformal inference of counterfactuals and individual treatment effects”
Original
Lihua Lei and Emmanuel Candès · 2020
Later among the works it cites.
“Efficient conformal prediction via cascaded inference with expanded admission”
Original
Adam Fisch, Tal Schuster, Tommi Jaakkola and Regina Barzilay · 2020
Later among the works it cites.
“Distribution-Free Prediction Sets with Random Effects”
Original
Robin Dunn, Larry Wasserman and Aaditya Ramdas · 2020
Later among the works it cites.
“Robust validation: Confident predictions even when distributions shift”
Original
Maxime Cauchois, Suyash Gupta, Alnur Ali and John Duchi · 2020
Later among the works it cites.
“A distribution-free test of covariate shift using conformal prediction”
Original
Xiaoyu Hu and Jing Lei · 2020
Later among the works it cites.
“Distribution-Free, Risk-Controlling Prediction Sets”
Stephen Bates, Anastasios Angelopoulos, Lihua Lei, Jitendra Malik and Michael. Jordan · 2021
Closest in time.
“PAC Prediction Sets Under Covariate Shift”
Original
Sangdon Park, Edgar Dobriban, Insup Lee and Osbert Bastani · 2021
Closest in time.
“A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification”
Original
Anastasios Angelopoulos and Stephen Bates · 2021
Closest in time.
“Predictive inference with the jackknife+”
Rina Barber, Emmanuel Candès, Aaditya Ramdas and Ryan Tibshirani · 2021
Closest in time.
“The limits of distribution-free conditional predictive inference”
Rina Barber, Emmanuel Candès, Aaditya Ramdas and Ryan Tibshirani · 2021
Closest in time.
“Knowing what you know: Valid and validated confidence sets in multiclass and multilabel prediction”
Maxime Cauchois, Suyash Gupta and John. Duchi · 2021
Closest in time.
“Uncertainty sets for image classifiers using conformal prediction”
Anastasios Angelopoulos, Stephen Bates, Jitendra Malik and Michael Jordan · 2021
Closest in time.
“Conformalized Survival Analysis”
Original
Emmanuel Candès, Lihua Lei and Zhimei Ren · 2021
Closest in time.
“Private Prediction Sets”
Original
Anastasios Angelopoulos, Stephen Bates, Tijana Zrnic and Michael Jordan · 2021
Closest in time.
“Testing for Outliers with Conformal p-values”
Original
Stephen Bates, Emmanuel Candès, Lihua Lei, Yaniv Romano and Matteo Sesia · 2021
Closest in time.
“Consistent Accelerated Inference via Confident Adaptive Transformers”
Original
Tal Schuster, Adam Fisch, Tommi Jaakkola and Regina Barzilay · 2021
Closest in time.
“Few-shot Conformal Prediction with Auxiliary Tasks”
Original
Adam Fisch, Tal Schuster, Tommi Jaakkola and Regina Barzilay · 2021
Closest in time.
“Adaptive Conformal Inference Under Distribution Shift”
Original
Isaac Gibbs and Emmanuel Candès · 2021
Closest in time.
“Testing Randomness Online”
Vladimir Vovk · 2021
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…