Conjugate Conformal Prediction for Online Binary Classification

Mustafa Kocak NYU Tandon SoE, Dennis Shasha Courant Institute of Mathematical Sciences New York University, Elza Erkip NYU Tandon School of Engineering
Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, PMLR R14:592-601, 2016.

Abstract

Binary classification (rain or shine, disease or not, increase or decrease) is a fundamental problem in machine learning. We present an algorithm that can take any standard online binary classification algorithm and provably improve its performance under very weak assumptions, given the right to refuse to make predictions in certain cases. The extent of improvement will depend on the data size, stability of the algorithm, and room for improvement in the algorithms performance. Our experiments on standard machine learning data sets and standard algorithms (k-nearest neighbors and random forests) show the effectiveness of our approach, even beyond what is possible using previous work on conformal predictors upon which our approach is based. Though we focus on binary classification, our theory could be extended to multiway classification. Our code and data are available upon request.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR14-soe16a, title = {Conjugate Conformal Prediction for Online Binary Classification}, author = {SoE, Mustafa Kocak NYU Tandon and University, Dennis Shasha Courant Institute of Mathematical Sciences New York and Engineering, Elza Erkip NYU Tandon School of}, booktitle = {Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence}, pages = {592--601}, year = {2016}, editor = {Ihler, Alexander and Janzing, Dominik}, volume = {R14}, series = {Proceedings of Machine Learning Research}, month = {25--29 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r14/main/assets/soe16a/soe16a.pdf}, url = {https://proceedings.mlr.press/r14/soe16a.html}, abstract = {Binary classification (rain or shine, disease or not, increase or decrease) is a fundamental problem in machine learning. We present an algorithm that can take any standard online binary classification algorithm and provably improve its performance under very weak assumptions, given the right to refuse to make predictions in certain cases. The extent of improvement will depend on the data size, stability of the algorithm, and room for improvement in the algorithms performance. Our experiments on standard machine learning data sets and standard algorithms (k-nearest neighbors and random forests) show the effectiveness of our approach, even beyond what is possible using previous work on conformal predictors upon which our approach is based. Though we focus on binary classification, our theory could be extended to multiway classification. Our code and data are available upon request.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Conjugate Conformal Prediction for Online Binary Classification %A Mustafa Kocak NYU Tandon SoE %A Dennis Shasha Courant Institute of Mathematical Sciences New York University %A Elza Erkip NYU Tandon School of Engineering %B Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2016 %E Alexander Ihler %E Dominik Janzing %F pmlr-vR14-soe16a %I PMLR %P 592--601 %U https://proceedings.mlr.press/r14/soe16a.html %V R14 %X Binary classification (rain or shine, disease or not, increase or decrease) is a fundamental problem in machine learning. We present an algorithm that can take any standard online binary classification algorithm and provably improve its performance under very weak assumptions, given the right to refuse to make predictions in certain cases. The extent of improvement will depend on the data size, stability of the algorithm, and room for improvement in the algorithms performance. Our experiments on standard machine learning data sets and standard algorithms (k-nearest neighbors and random forests) show the effectiveness of our approach, even beyond what is possible using previous work on conformal predictors upon which our approach is based. Though we focus on binary classification, our theory could be extended to multiway classification. Our code and data are available upon request. %Z Reissued by PMLR on 04 October 2026.
APA
SoE, M.K.N.T., University, D.S.C.I.o.M.S.N.Y. & Engineering, E.E.N.T.S.o.. (2016). Conjugate Conformal Prediction for Online Binary Classification. Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R14:592-601 Available from https://proceedings.mlr.press/r14/soe16a.html. Reissued by PMLR on 04 October 2026.

Related Material