Least Ambiguous Set-Valued Classifiers with Bounded Error Levels

Abstract

In most classification tasks there are observations that are ambiguous and therefore difficult to correctly label. Set-valued classifiers output sets of plausible labels rather than a single label, thereby giving a more appropriate and informative treatment to the labeling of ambiguous instances. We introduce a framework for multiclass set-valued classification, where the classifiers guarantee user-defined levels of coverage or confidence (the probability that the true label is contained in the set) while minimizing the ambiguity (the expected size of the output). We first derive oracle classifiers assuming the true distribution to be known. We show that the oracle classifiers are obtained from level sets of the functions that define the conditional probability of each class. Then we develop estimators with good asymptotic and finite sample properties. The proposed estimators build on existing single-label classifiers. The optimal classifier can sometimes output the empty set, but we provide two solutions to fix this issue that are suitable for various practical needs.

Final version to be published in the Journal of the American Statistical Association at https://www.tandfonline.com/doi/abs/10.1080/01621459.2017.1395341?journalCode=uasa20

References in corpus (3)

• High-dimensional generalized linear models and the lasso
• Fast learning rates for plug-in classifiers
• Consistent Algorithms for Multiclass Classification with a Reject Option

Cited by in corpus (28)

• Conformal Inference of Counterfactuals and Individual Treatment Effects
• Uncertainty Sets for Image Classifiers using Conformal Prediction
• Cautious Deep Learning
• Adaptive Conformal Inference Under Distribution Shift
• Learn then Test: Calibrating Predictive Algorithms to Achieve Risk Control
• Knowing what you know: valid and validated confidence sets in multiclass and multilabel prediction
• CD-split and HPD-split: efficient conformal regions in high dimensions
• Selective prediction-set models with coverage guarantees
• Learning Optimal Conformal Classifiers
• Fairness-aware Model-agnostic Positive and Unlabeled Learning
• Private Prediction Sets
• Distribution-free uncertainty quantification for classification under label shift
• Selective conformal inference with false coverage-statement rate control
• Non-exchangeable Conformal Prediction for Temporal Graph Neural Networks
• Interpretable hypothesis tests
• Selecting informative conformal prediction sets with false coverage rate control
• Uncertainty in Lung Cancer Stage for Outcome Estimation via Set-Valued Classification
• Distribution-free uncertainty quantification for inverse problems: application to weak lensing mass mapping
• coverforest: Conformal Predictions with Random Forest in Python
• Trustworthy scientific inference with generative models
• A Collaborative Content Moderation Framework for Toxicity Detection based on Conformalized Estimates of Annotation Disagreement
• Selective Classification via One-Sided Prediction
• T-SCI: A Two-Stage Conformal Inference Algorithm with Guaranteed Coverage for Cox-MLP
• AutoCP: Automated Pipelines for Accurate Prediction Intervals
• Localized Conformal Prediction for Image Classification with Vision-Language Models
• Conformal Predictions for Human Action Recognition with Vision-Language Models
• Temporal Graph Prototype-conditioned Conformal Prediction for Fraud Detection
• Exact Distribution-Free Hypothesis Tests for the Regression Function of Binary Classification via Conditional Kernel Mean Embeddings