# Least Ambiguous Set-Valued Classifiers with Bounded Error Levels

arXiv: https://arxiv.org/abs/1609.00451 · HTML: https://mlsanity.com/paper/1609.00451/

## Key facts

- Cited by 272 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Sep 2016.

## Built on by (most cited first, 30 of 272)

- [A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification](https://mlsanity.com/paper/2107.07511/) (2021)
- [Adaptive Conformal Inference Under Distribution Shift](https://mlsanity.com/paper/2106.00170/) (2021)
- [Robots That Ask For Help: Uncertainty Alignment for Large Language Model Planners](https://mlsanity.com/paper/2307.01928/) (2023)
- [Distribution-Free, Risk-Controlling Prediction Sets](https://mlsanity.com/paper/2101.02703/) (2021)
- [Learn then Test: Calibrating Predictive Algorithms to Achieve Risk Control](https://mlsanity.com/paper/2110.01052/) (2021)
- [Conformal Prediction with Large Language Models for Multi-Choice Question Answering](https://mlsanity.com/paper/2305.18404/) (2023)
- [Conformal Inference for Online Prediction with Arbitrary Distribution Shifts](https://mlsanity.com/paper/2208.08401/) (2022)
- [Benchmarking LLMs via Uncertainty Quantification](https://mlsanity.com/paper/2401.12794/) (2024)
- [A Survey on Uncertainty Quantification of Large Language Models: Taxonomy, Open Research Challenges, and Future Directions](https://mlsanity.com/paper/2412.05563/) (2024)
- [Learning Optimal Conformal Classifiers](https://mlsanity.com/paper/2110.09192/) (2021)
- [Class-Conditional Conformal Prediction with Many Classes](https://mlsanity.com/paper/2306.09335/) (2023)
- [Image-to-Image Regression with Distribution-Free Uncertainty Quantification and Applications in Imaging](https://mlsanity.com/paper/2202.05265/) (2022)
- [Distribution-free uncertainty quantification for classification under label shift](https://mlsanity.com/paper/2103.03323/) (2021)
- [Fair Conformal Predictors for Applications in Medical Imaging](https://mlsanity.com/paper/2109.04392/) (2021)
- [API Is Enough: Conformal Prediction for Large Language Models Without Logit-Access](https://mlsanity.com/paper/2403.01216/) (2024)
- [Conformalized Survival Analysis](https://mlsanity.com/paper/2103.09763/) (2021)
- [Conformal Prediction for Deep Classifier via Label Ranking](https://mlsanity.com/paper/2310.06430/) (2023)
- [Federated Conformal Predictors for Distributed Uncertainty Quantification](https://mlsanity.com/paper/2305.17564/) (2023)
- [Decision Theoretic Foundations for Conformal Prediction: Optimal Uncertainty Quantification for Risk-Averse Agents](https://mlsanity.com/paper/2502.02561/) (2025)
- [Length Optimization in Conformal Prediction](https://mlsanity.com/paper/2406.18814/) (2024)
- [Improving Trustworthiness of AI Disease Severity Rating in Medical Imaging with Ordinal Conformal Prediction Sets](https://mlsanity.com/paper/2207.02238/) (2022)
- [On the Utility of Prediction Sets in Human-AI Teams](https://mlsanity.com/paper/2205.01411/) (2022)
- [Conformal prediction under ambiguous ground truth](https://mlsanity.com/paper/2307.09302/) (2023)
- [Uncertainty-Aware Evaluation for Vision-Language Models](https://mlsanity.com/paper/2402.14418/) (2024)
- [Conformal Prediction Sets with Limited False Positives](https://mlsanity.com/paper/2202.07650/) (2022)
- [Distribution Free Prediction Sets for Node Classification](https://mlsanity.com/paper/2211.14555/) (2022)
- [Set-valued classification -- overview via a unified framework](https://mlsanity.com/paper/2102.12318/) (2021)
- [Introspective Planning: Aligning Robots' Uncertainty with Inherent Task Ambiguity](https://mlsanity.com/paper/2402.06529/) (2024)
- [Provably Robust Conformal Prediction with Improved Efficiency](https://mlsanity.com/paper/2404.19651/) (2024)
- [Minimum Volume Conformal Sets for Multivariate Regression](https://mlsanity.com/paper/2503.19068/) (2025)

## Abstract (arXiv)

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.