Confident Prediction

Methods for conformal/probabilistic prediction (Conformal Predictors, Venn-Predictors) are wrappers around Machine Learning algorithms, that provide guarantees about their predictions; generally, their sole assumption is exchangeability on data (weaker than standard i.i.d.). They were first proposed in the book “Algorithmic Learning in a Random World” (Vovk, Gammerman, Shafer; 2005).

Conformal Predictors (CP) allow limiting the errors committed by a learning algorithm (“underlying algorithm”), in a multi-label classification setting, to a desired significance level \(\varepsilon\): their accuracy is guaranteed to be at least \(1-\varepsilon\).

Venn-Predictors (VP) output a set of probability distributions on the labels, as a prediction for a new object \(x\); one of these distributions is guaranteed to be perfectly calibrated.

Conformal Prediction for Hidden Markov Models (CPHMM) are an alternative to HMM and the Viterbi algorithm for supervised sequence learning problems (Cherubin, Nouretdinov, 2016), giving error guarantees (validity) under the sole exangeability assumption. They are more robust than the standard maximum likelihood approach when facing arbitrary distributions.

Code

• Python implementation of Conformal Prediction with scikit-learn integration: https://github.com/donlnz/nonconformist
• My Rust implementation of Conformal Prediction-related methods, aiming for correctness and performance: https://github.com/gchers/random-world
• My implementation of CPHMM https://github.com/gchers/cphmm
• (Unmaintained) My old Python implementation of Conformal Prediction: https://github.com/gchers/cpy

Projects

A list of works on CP.

1. Approximating full conformal prediction at scale via influence functions Martinez, Javier Abad, Bhatt, Umang, Weller, Adrian, and Cherubin, Giovanni In Proceedings of the AAAI Conference on Artificial Intelligence 2023 [Paper]
2. How do the performance of a Conformal Predictor and its underlying algorithm relate? Cherubin, Giovanni In Conformal and Probabilistic Prediction with Applications 2023 [Paper]
3. Exact Optimization of Conformal Predictors via Incremental and Decremental Learning Cherubin, Giovanni, Chatzikokolakis, Konstantinos, and Jaggi, Martin In Proceedings of the 38th International Conference on Machine Learning 2021 [Abs] [Paper] [Url]

   Conformal Predictors (CP) are wrappers around ML models, providing error guarantees under weak assumptions on the data distribution. They are suitable for a wide range of problems, from classification and regression to anomaly detection. Unfortunately, their very high computational complexity limits their applicability to large datasets. In this work, we show that it is possible to speed up a CP classifier considerably, by studying it in conjunction with the underlying ML method, and by exploiting incremental&decremental learning. For methods such as k-NN, KDE, and kernel LS-SVM, our approach reduces the running time by one order of magnitude, whilst producing exact solutions. With similar ideas, we also achieve a linear speed up for the harder case of bootstrapping. Finally, we extend these techniques to improve upon an optimization of k-NN CP for regression. We evaluate our findings empirically, and discuss when methods are suitable for CP optimization.

4. (Poster) Fast conformal classification using influence functions Bhatt, Umang, Weller, Adrian, and Cherubin, Giovanni In Proceedings of the Tenth Symposium on Conformal and Probabilistic Prediction and Applications 2021 [Abs] [Paper] [Url]

   We use influence functions from robust statistics to speed up full conformal prediction. Traditionally, conformal prediction requires retraining multiple leave-one-out classifiers to calculate p-values for each test point. By using influence functions, we are able to approximate this procedure and to speed up considerably the time complexity.

5. Exchangeability martingales for selecting features in anomaly detection Cherubin, Giovanni, Baldwin, Adrian, and Griffin, Jonathan In Proceedings of the Seventh Workshop on Conformal and Probabilistic Prediction and Applications 2018 [Url] [PDF] [Code]
6. Majority vote ensembles of conformal predictors Cherubin, Giovanni Machine Learning 2018 [Url] [PDF]
7. Hidden Markov Models with Confidence Cherubin, Giovanni, and Nouretdinov, Ilia In Conformal and Probabilistic Prediction with Applications - 5th International Symposium, COPA 2016, Madrid, Spain, April 20-22, 2016, Proceedings 2016 [Slides] [Code]
8. Conformal Clustering and Its Application to Botnet Traffic Cherubin, Giovanni, Nouretdinov, Ilia, Gammerman, Alexander, Jordaney, Roberto, Wang, Zhi, Papini, Davide, and Cavallaro, Lorenzo In Statistical Learning and Data Sciences - Third International Symposium, SLDS 2015, Egham, UK, April 20-23, 2015, Proceedings 2015 [Slides]