# Classification Under Ambiguity: When Is Average-K Better Than Top-K?

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 48 references that are in the map.
- First posted on arXiv 16 Dec 2021.

## Builds on (most cited first, 18 of 18)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [On Calibration of Modern Neural Networks](https://mlsanity.com/paper/1706.04599/) (2017)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [What Uncertainties Do We Need in Bayesian Deep Learning for Computer Vision?](https://mlsanity.com/paper/1703.04977/) (2017)
- [Aleatoric and Epistemic Uncertainty in Machine Learning: An Introduction to Concepts and Methods](https://mlsanity.com/paper/1910.09457/) (2019)
- [Uncertainty Sets for Image Classifiers using Conformal Prediction](https://mlsanity.com/paper/2009.14193/) (2020)
- [Least Ambiguous Set-Valued Classifiers with Bounded Error Levels](https://mlsanity.com/paper/1609.00451/) (2016)
- [Human uncertainty makes classification more robust](https://mlsanity.com/paper/1908.07086/) (2019)
- [Fast Differentiable Sorting and Ranking](https://mlsanity.com/paper/2002.08871/) (2020)
- [Machine Learning with a Reject Option: A survey](https://mlsanity.com/paper/2107.11277/) (2021)
- [Smooth Loss Functions for Deep Top-k Classification](https://mlsanity.com/paper/1802.07595/) (2018)
- [Loss Functions for Top-k Error: Analysis and Insights](https://mlsanity.com/paper/1512.00486/) (2015)
- [On the Consistency of Top-k Surrogate Losses](https://mlsanity.com/paper/1901.11141/) (2019)
- [Analysis and Optimization of Loss Functions for Multiclass, Top-k, and Multilabel Classification](https://mlsanity.com/paper/1612.03663/) (2016)
- [SafePredict: A Meta-Algorithm for Machine Learning That Uses Refusals to Guarantee Correctness](https://mlsanity.com/paper/1708.06425/) (2017)
- [Learning Confidence Sets using Support Vector Machines](https://mlsanity.com/paper/1809.10818/) (2018)

## Built on by (most cited first, 1 of 1)

- [Conformal Prediction Sets Can Cause Disparate Impact](https://mlsanity.com/paper/2410.01888/) (2024)

## Abstract (arXiv)

When many labels are possible, choosing a single one can lead to low precision. A common alternative, referred to as top-K classification, is to choose some number K (commonly around 5) and to return the K labels with the highest scores. Unfortunately, for unambiguous cases, K>1 is too many and, for very ambiguous cases, K ≤ 5 (for example) can be too small. An alternative sensible strategy is to use an adaptive approach in which the number of labels returned varies as a function of the computed ambiguity, but must average to some particular K over all the samples. We denote this alternative average-K classification. This paper formally characterizes the ambiguity profile when average-K classification can achieve a lower error rate than a fixed top-K classification. Moreover, it provides natural estimation procedures for both the fixed-size and the adaptive classifier and proves their consistency. Finally, it reports experiments on real-world image data sets revealing the benefit of average-K classification over top-K in practice. Overall, when the ambiguity is known precisely, average-K is never worse than top-K, and, in our experiments, when it is estimated, this also holds.