Selective Classification via One-Sided Prediction

Abstract

We propose a novel method for selective classification (SC), a problem which allows a classifier to abstain from predicting some instances, thus trading off accuracy against coverage (the fraction of instances predicted). In contrast to prior gating or confidence-set based work, our proposed method optimises a collection of class-wise decoupled one-sided empirical risks, and is in essence a method for explicitly finding the largest decision sets for each class that have few false positives. This one-sided prediction (OSP) based relaxation yields an SC scheme that attains near-optimal coverage in the practically relevant high target accuracy regime, and further admits efficient implementation, leading to a flexible and principled method for SC. We theoretically derive generalization bounds for SC and OSP, and empirically we show that our scheme strongly outperforms state of the art methods in coverage at small error levels.

arXiv commentv4: update to add relevant references

References in corpus (13)

• A tutorial on conformal prediction
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• Least Ambiguous Set-Valued Classifiers with Bounded Error Levels
• SelectiveNet: A Deep Neural Network with an Integrated Reject Option
• Adaptive Classification for Prediction Under a Budget
• Lasso type classifiers with a reject option
• Confidence sets with expected sizes for Multiclass Classification
• On the Calibration of Multiclass Classification with Rejection
• Binary Classification with Bounded Abstention Rate
• Resource Constrained Structured Prediction
• Dynamic Model Selection for Prediction Under a Budget
• Budget Learning via Bracketing
• Minimax semi-supervised confidence sets for multi-class classification