Learning to Abstain from Binary Prediction
This work addresses the trade-off between accuracy and abstention in binary classification, which is incremental as it builds on existing ensemble and abstention methods.
The paper tackles the problem of binary classifiers that can abstain from predictions, aiming to minimize errors while avoiding unnecessary abstentions. It provides a minimax optimal algorithm for learning such classifiers in a semi-supervised setting, achieving efficiency comparable to linear learning and demonstrating practicality.
A binary classifier capable of abstaining from making a label prediction has two goals in tension: minimizing errors, and avoiding abstaining unnecessarily often. In this work, we exactly characterize the best achievable tradeoff between these two goals in a general semi-supervised setting, given an ensemble of predictors of varying competence as well as unlabeled data on which we wish to predict or abstain. We give an algorithm for learning a classifier in this setting which trades off its errors with abstentions in a minimax optimal manner, is as efficient as linear learning and prediction, and is demonstrably practical. Our analysis extends to a large class of loss functions and other scenarios, including ensembles comprised of specialists that can themselves abstain.