Least Ambiguous Set-Valued Classifiers With Bounded Error Levels

By Mauricio Sadinle, Jing Lei, Larry A. Wasserman. Journal of the American Statistical Association, 2016

373 citations recorded by the source corpus.

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. Supplementary materials for this article are available online.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/c949dfebccbdfa43f59c219c6bd2389dba1b2d38

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Vision and Pattern Recognition

Citations in the corpus

Knowing what you know: valid confidence sets in multiclass and multilabel prediction (2020, background): “[28] propose conformal prediction algorithms for multiclass problems that minimize the expected size of the confidence set and conformalize the scores separately for each class, providing class-wise coverage.”
Classification with Valid and Adaptive Coverage (2020, methodology): “5 Extension to label-conditional coverage Our method can be easily extended to obtain provable coverage separately for each class [19, 24]: P [ Yn+1 ∈ Ĉn,α(Xn+1) | Yn+1 = y ] ≥ 1− α, ∀y ∈ Y.”
Robots That Ask For Help: Uncertainty Alignment for Large Language Model Planners (2023, methodology): “…probabilities may be a good approximation for LLMs trained on large-scale data with a proper scoring rule [11]; one can also obtain bounds on near-optimal average set size for CP using ˆ f that approximately models conditional probabilities [12, 10], but we omit these results for brevity.”
Distribution-Free, Risk-Controlling Prediction Sets (2021, background): “See [12, 14] for further discussion of this point in that context.”
Adaptive Conformal Inference Under Distribution Shift (2021, methodology): “Perhaps the most powerful and ﬂexible tools for solving this problem come from conformal inference [see e.g. 34, 16, 32, 22, 31, 15, 3] .”
Knowing what You Know: valid and validated confidence sets in multiclass and multilabel prediction (2020, methodology): “Then the conﬁdence sets (cid:98) C σn, 1 − α satisfy Unlike other work (Sadinle et al., 2019; Romano et al., 2020) in conformal inference, validity of Theorem 6 does not rely on the scores being consistent for the log-conditional probabilities.”