, , and

# Set-valued classification – overview via a unified framework

Evgenii<EMAIL_ADDRESS>[ Christophe
<EMAIL_ADDRESS>[ Mohamed
<EMAIL_ADDRESS>[ Titouan
<EMAIL_ADDRESS>[ LMO, Université Paris-Saclay, CNRS,
INRIA, .  LAMA, Université Gustave-Eiffel, .  INRIA, ZENITH, Université de
Montpellier, .

###### Abstract

Multi-class classification problem is among the most popular and well-studied
statistical frameworks. Modern multi-class datasets can be extremely ambiguous
and single-output predictions fail to deliver satisfactory performance. By
allowing predictors to predict a set of label candidates, set-valued
classification offers a natural way to deal with this ambiguity. Several
formulations of set-valued classification are available in the literature and
each of them leads to different prediction strategies. The present survey aims
to review popular formulations using a unified statistical framework. The
proposed framework encompasses previously considered and leads to new
formulations as well as it allows to understand underlying trade-offs of each
formulation. We provide infinite sample optimal set-valued classification
strategies and review a general plug-in principle to construct data-driven
algorithms. The exposition is supported by examples and pointers to both
theoretical and practical contributions. Finally, we provide experiments on
real-world datasets comparing these approaches in practice and providing
general practical guidelines.

Set-valued classification,

Multi-class classification,

survey,

Unified framework,

top-k,

###### keywords:

###### Contents

  1. 1 Introduction
  2. 2 Related classification frameworks
  3. 3 Practical motivations and applications
  4. 4 Main set-valued classification frameworks
  5. 5 Empirical comparison of the frameworks
  6. 6 Other set-valued frameworks
  7. 7 Conclusion
  8. A Omitted proofs

##  1 Introduction

Set-valued predictors, unlike single-output ones, allow to provide a set of
possible class candidates. They became popular in recent years due to their
ability to cope with class ambiguity, possibly present in multi-class
problems. This work focuses on set-valued methods for multi-class
classification problem. Unlike in single-output setup, it is not completely
clear how to define _the_ set-valued classifier of interest due to various
trade-offs that can be considered. Therefore, one of our main goals is to
provide an overview of various set-valued frameworks, previously considered in
the literature, and complement them with their natural extensions. We
highlight similarities shared by all the formulations and emphasize on their
differences. In our exposition we follow a unified statistical setting where
the description of the frameworks, methods, and underlying trade-offs become
more transparent.

###  1.1 From single-output to set-valued classifiers

(a) MNIST

(b) ImageNet

Figure 1:  Examples from MNIST and ImageNet multi-class classification tasks.

Classically, multi-class classification considers the problem of learning a
_single-output classifier_ $h:\mathcal{X}\to[L]\vcentcolon=\\{1,\ldots,L\\}$
based on data
$({\bm{X}}_{1},Y_{1}),\ldots,({\bm{X}}_{n},Y_{n})\in\mathcal{X}\times[L]$
which minimizes the error rate $\mathbb{P}(Y\neq h({\bm{X}}))$ on a new couple
$({\bm{X}},Y)$.

For problems such as MNIST (1(a)), single-output classifiers have been very
successful and we are now able to learn models with a very low error rate,
i.e., less than 1% (Ciregan, Meier and Schmidhuber, 2012). However, nowadays,
common datasets are much more complex leading to much higher errors, for
instance the error on the ImageNet dataset (1(b)) is around 20% using state-
of-the-art models (Xie et al., 2017). Such high error is not solely due to the
difficulty to construct a good classifier, but rather due to the high
ambiguity in the dataset. As shown in 1(b), some images are intrinsically
ambiguous: in some images, several objects are present; in others, due to
occlusion or noise in the image, it is not clear – even to a human expert –
what class should be predicted. Forcing a classifier to predict a single class
will thus mechanically increase its error rate as in such cases several
answers can be considered as correct.

A way to deal with this ambiguity is to allow the classifier to predict a set
of candidate classes rather than a single one (Grycko, 1993). These types of
classifiers are called _set-valued classifiers_. They are defined as mapping
from the input space $\mathcal{X}$ to the set of all subsets of $[L]$, i.e.,
the power set of $[L]$ denoted by $2^{[L]}$:

$\Gamma:\mathcal{X}\to 2^{[L]}\enspace.$

Note that by considering set-valued classifiers we do not alter the underlying
multi-class data-generating process, that is, the observed data
$({\bm{X}}_{1},Y_{1}),\ldots,({\bm{X}}_{n},Y_{n})\in\mathcal{X}\times[L]$ is
still that of multi-class – each instance ${\bm{X}}_{i}$ is tagged by a unique
class $Y_{i}$ in the sample. Instead, we change the form of prediction
functions passing from single outputs to the set-valued ones.

The easiest way to build such a classifier is to always predict a fixed number
of classes such as the top-5 most probable classes. This approach is in fact
the one chosen in the official ImageNet classification challenge (Russakovsky
et al., 2015a). However, as shown in the previous images, in general, there is
no reason to predict exactly 5 or any other a priori fixed number of classes
all the time. This observation generalizes to most of recent datasets. In such
cases, it is possible to provide a more informative prediction by relaxing
this hard constraint on the set size.

In general, it is thus necessary to develop other formulations of set-valued
classification strategies which could be more suited for the problem at hand.
Most of the known formulations can be seen as different ways to choose a
trade-off between two complementary quantities: the _error rate_ and the _set
size_ (see Section 1.2 for its formal definition). The former quantifies the
accuracy of set-valued classifier $\Gamma$ – how likely $\Gamma({\bm{X}})$
contains the underlying truth $Y$; The latter quantifies its informativeness –
informative predictions $\Gamma({\bm{X}})$ should not contain too many
candidates. For instance, top-$5$ classification strategy consists in
minimizing the average error rate $\mathbb{P}(Y\notin\Gamma({\bm{X}}))$ under
the constraint that the set size $|\Gamma({\bm{x}})|$ is less than or equals
to $5$ for every input ${\bm{x}}\in\mathcal{X}$.

We emphasize that there is no formulation which is uniformly better than the
others or one which is “incorrect”. On the contrary, each formulation is
complementary to one another: they are suited to different contexts and
applications. The goal of this work is too provide a concise overview of the
literature on set-valued classification, compare different frameworks, and
fill gaps that were not previously addressed.

###  1.2 Set-valued classification – a unified framework

First of all recall the formal statistical setup of the multi-class
classification problem. Let $({\bm{X}},Y)$ be a random couple taking values in
$\mathcal{X}\times[L]$ with joint distribution $\mathbb{P}$. Here ${\bm{X}}$
represents the vector of features (e.g., an image) and $Y$ is the unique class
(e.g., a digit present on the image). An informal goal in the set-valued
classification framework is to build a set-valued classifier
$\Gamma:\mathcal{X}\to 2^{[L]}$, which has two desired properties: its size
$|\Gamma({\bm{X}})|$ is not too large and it is likely to contain the true
class, i.e., $Y\in\Gamma({\bm{X}})$. In order to construct a set-valued
classifier with such properties, the practitioner has access to training data
$({\bm{X}}_{1},Y_{1}),\ldots,({\bm{X}}_{n},Y_{n})\overset{\text{{\rm
i.i.d.~{}}}}{\sim}\mathbb{P}$, independent from $({\bm{X}},Y)$.

Formalization of the above intuitive idea, not only requires a rigorous
definition of size and error of $\Gamma:\mathcal{X}\to 2^{[K]}$, but also, in
the spirit of decision theory, it requires a principled way to define an
“ultimate” set-valued classifier $\Gamma^{*}$. Unlike single-output
prediction, mentioned in the previous section, where it is natural to target
$g^{*}:\mathcal{X}\to[K]$ which minimizes the 0/1-loss (accuracy), such an
obviously natural choice does not exist in the set-valued classification
framework. As already mentioned, a good set-valued prediction always strikes
for a trade-off between two quantities, a measure of the accuracy of the
predicted sets and a measure of their informativeness. In this paper, we will
focus on a particular choices of such measures: respectively, error rate, and
set size, which we now define.

  * •

Error rate: this quantity can be defined point-wise or in average as

$\displaystyle\operatorname{Err}(\Gamma;{\bm{x}})\vcentcolon=\mathbb{P}(Y\notin\Gamma({\bm{X}})\mid{\bm{X}}={\bm{x}})$
$\displaystyle\textbf{(point-wise error)}\enspace,$ (1)
$\displaystyle\operatorname{Err}(\Gamma)\vcentcolon=\mathbb{P}(Y\notin\Gamma({\bm{X}})),$
$\displaystyle\textbf{(average error)}\enspace.$ (2)

Naturally, the average error is related to point-wise error by
$\operatorname{Err}(\Gamma)=\mathbb{E}_{{\bm{X}}}[\operatorname{Err}(\Gamma;{\bm{X}})]$.
The error rate is associated to the accuracy of the set-valued classifier
$\Gamma$. It is often named coverage, recall, or risk.

  * •

Set size: analogously set size can also be viewed in a point-wise manner or in
average with the following definitions

$\displaystyle\operatorname{S}(\Gamma;{\bm{x}})\vcentcolon=|\Gamma({\bm{x}})|$
$\displaystyle\textbf{(point-wise size)}\enspace,$ (3)
$\displaystyle\operatorname{S}(\Gamma)\vcentcolon=\mathbb{E}_{{\bm{X}}}|\Gamma({\bm{X}})|,$
$\displaystyle\textbf{(average size)}\enspace.$ (4)

Similarly to the error, the size admit the same relation
$\operatorname{S}(\Gamma)=\mathbb{E}_{{\bm{X}}}[\operatorname{S}(\Gamma;{\bm{X}})]$.
It is commonly accepted that the smaller the set size is the more informative
the set-valued $\Gamma$ is. In the literature, the set size can also be called
expected set size, adaptive set size or information.

The balance of the set size and the error rate can be achieved in various
ways, and, depending on the application at hand should be considered using
domain specific knowledge. Nevertheless, most of the optimal set-valued
classifiers of interest can be formalized via a minimization problem under,
possibly, distribution dependent constraints.

$\begin{aligned}
\Gamma^{*}_{(\operatorname{F_{\mathbb{P}}},\operatorname{{\mathcal{C}}_{\mathbb{P}}})}\in\operatorname*{arg\,min}_{\Gamma:\mathcal{X}\to
2^{[L]}}\;&\operatorname{F_{\mathbb{P}}}(\Gamma)\\\ \text{s.t.
}&\Gamma\in\operatorname{{\mathcal{C}}_{\mathbb{P}}}\end{aligned}\enspace,$

where $\operatorname{F_{\mathbb{P}}}(\cdot)$ is a real-valued functional on
set-valued classifiers, which depends on the distribution; and
$\operatorname{{\mathcal{C}}_{\mathbb{P}}}$ is a (distribution dependent)
family of set-valued classifiers with desired properties. Table 1 provides a
quick overview of the formulations that we describe in the paper. They
correspond to particular choices of the functional
$\operatorname{F_{\mathbb{P}}}(\cdot)$ and the family
$\operatorname{{\mathcal{C}}_{\mathbb{P}}}$. Within this unified framework,
the optimal set-valued classifier
$\Gamma^{*}_{(\operatorname{F_{\mathbb{P}}},\operatorname{{\mathcal{C}}_{\mathbb{P}}})}$
is considered as the gold standard. Consequently, the goal of the practitioner
is to build a data-driven set-valued classifier $\hat{\Gamma}$ using the
sample $({\bm{X}}_{1},Y_{1}),\ldots,({\bm{X}}_{n},Y_{n})$ which preserves, as
much as possible, all the desirable features (e.g., error rate or size) of the
optimal set-valued classifier
$\Gamma^{*}_{(\operatorname{F_{\mathbb{P}}},\operatorname{{\mathcal{C}}_{\mathbb{P}}})}$.

Despite the large variety of pairs
$(\operatorname{F_{\mathbb{P}}},\operatorname{{\mathcal{C}}_{\mathbb{P}}})$
that can be considered, most of the frameworks, previously described in the
literature, admit a general plug-in driven approach for construction of
$\hat{\Gamma}$. It consists of two principal steps: first, derive the closed-
form solution of the problem (1.2); second, estimate all the unknown
quantities in the expression for
$\Gamma^{*}_{(\operatorname{F_{\mathbb{P}}},\operatorname{{\mathcal{C}}_{\mathbb{P}}})}$.

Name |  Objective $\operatorname{F_{\mathbb{P}}}(\Gamma)$ |  Constraint $\operatorname{{\mathcal{C}}_{\mathbb{P}}}$ |  Optimal $\Gamma^{*}_{(\operatorname{F_{\mathbb{P}}},\operatorname{{\mathcal{C}}_{\mathbb{P}}})}$ | Section |
---|---|---|---|---|---
Penalized | $\operatorname{Err}(\Gamma)+\lambda\operatorname{S}(\Gamma)$ | N/A |  $\Gamma^{*}_{\lambda}$: threshold | Section 4.2 |
Point-wise size | $\operatorname{Err}(\Gamma)$ | $\operatorname{S}(\Gamma;{\bm{x}})\leq k$ |  $\Gamma^{*}_{k}$: top-$k$ | Section 4.1.1 |
Average size |  $\operatorname{Err}(\Gamma$) | $\operatorname{S}(\Gamma)\leq\bar{k}$ |  $\Gamma^{*}_{\bar{k}}$: threshold | Section 4.2.1 |
Point-wise error | $\operatorname{S}(\Gamma)$ | $\operatorname{Err}(\Gamma;{\bm{x}})\leq\epsilon$ |  $\Gamma^{*}_{\epsilon}$: top-$k({\bm{x}})$ | Section 4.1.2 |
Average error | $\operatorname{S}(\Gamma)$ | $\operatorname{Err}(\Gamma)\leq\bar{\epsilon}$ |  $\Gamma^{*}_{\bar{\epsilon}}$: threshold | Section 4.2.2 |
Fβ-score | $\frac{(1+\beta^{2})(1-\operatorname{Err}(\Gamma))}{\beta^{2}+\operatorname{S}(\Gamma)}$ | N/A |  $\Gamma^{*}_{F}$: threshold | Section 6.2 |
Hybrid size | $\operatorname{Err}(\Gamma)$ | $\begin{aligned} &\operatorname{S}(\Gamma)\leq\bar{k},\\\ &\operatorname{S}(\Gamma;{\bm{x}})\leq k\end{aligned}$ | hybrid | Section 6.1 |
Hybrid error | $\operatorname{S}(\Gamma)$ | $\begin{aligned} &\operatorname{Err}(\Gamma)\leq\bar{\epsilon},\\\ &\operatorname{Err}(\Gamma;{\bm{x}})\leq\epsilon\end{aligned}$ | hybrid | Section 6.1 |

Table 1:  Nomenclature and description. We recall the notation: average error
rate $\operatorname{Err}(\Gamma)=\mathbb{P}(Y\notin\Gamma({\bm{X}}))$; point-
wise error rate
$\operatorname{Err}(\Gamma,{\bm{x}})=\mathbb{P}(Y\notin\Gamma({\bm{X}})\,|\,{\bm{X}}={\bm{x}})$;
average set size $\operatorname{S}(\Gamma)=\mathbb{E}|\Gamma({\bm{X}})|$;
point-wise set size $\operatorname{S}(\Gamma,{\bm{x}})=|\Gamma({\bm{x}})|$.

The derivation of the explicit form of the optimal set-valued classifier
$\Gamma^{*}_{(\operatorname{F_{\mathbb{P}}},\operatorname{{\mathcal{C}}_{\mathbb{P}}})}$
assuming that the distribution $\mathbb{P}$ is known can be typically
performed in analytic way. The central objects are the marginal distribution
of the features $\mathbb{P}_{{\bm{X}}}$ and the posterior distribution111Here
$\Delta^{L-1}$ stands for the probability simplex on $L$ atoms.
${\bm{p}}=(p_{1},\ldots,p_{L})^{\top}:\mathcal{X}\to\Delta^{L-1}$ of the label
$Y$ defined component-wise for all $\ell\in[L]$ as
$p_{\ell}({\bm{x}})\vcentcolon=\mathbb{P}(Y=\ell\mid{\bm{X}}={\bm{x}})$. The
former tells us how often an observation ${\bm{x}}$ (or its neighbourhood) can
be observed, while the latter measures the relevance of label $\ell$ for the
instance ${\bm{x}}$. The explicit expression for the optimal set-valued
classifier
$\Gamma^{*}_{(\operatorname{F_{\mathbb{P}}},\operatorname{{\mathcal{C}}_{\mathbb{P}}})}$
in all the considered frameworks reduces to one of the following three cases:

  * •

Thresholding: there exists
$\theta=\theta(\mathbb{P},\operatorname{{\mathcal{C}}_{\mathbb{P}}},\operatorname{F_{\mathbb{P}}})\in[0,1]$,
such that for all ${\bm{x}}\in\mathcal{X}$ the optimal set-valued classifier
can be defined as

$\displaystyle\Gamma^{*}_{(\operatorname{F_{\mathbb{P}}},\operatorname{{\mathcal{C}}_{\mathbb{P}}})}({\bm{x}})=\left\\{\ell\in[L]\,:\,p_{\ell}({\bm{x}})\geq\theta\right\\}\enspace.$

In this case, for a given instance ${\bm{x}}$, the prediction
$\Gamma^{*}_{(\operatorname{F_{\mathbb{P}}},\operatorname{{\mathcal{C}}_{\mathbb{P}}})}({\bm{x}})$
consists of those candidates whose probability $p_{\ell}({\bm{x}})$ surpasses
a certain level $\theta$.
NB.
$\theta=\theta(\mathbb{P},\operatorname{{\mathcal{C}}_{\mathbb{P}}},\operatorname{F_{\mathbb{P}}})$
is allowed to depend on the distribution $\mathbb{P}$, which is unknown.

  * •

Point-wise top-k: for all ${\bm{x}}\in\mathcal{X}$, there exists
$k=k({\bm{x}},\mathbb{P})\in[L]$, such that the optimal set-valued classifier
can be defined as

$\displaystyle\Gamma^{*}_{(\operatorname{F_{\mathbb{P}}},\operatorname{{\mathcal{C}}_{\mathbb{P}}})}({\bm{x}})=\operatorname{top}_{{\bm{p}}}({\bm{x}},k)\enspace,$

where operator $\operatorname{top}_{{\bm{p}}}({\bm{x}},k)$ outputs
$k({\bm{x}},\mathbb{P})$ labels with largest values of
${\bm{p}}({\bm{x}})=(p_{1}({\bm{x}}),\ldots,p_{L}({\bm{x}}))^{\top}$. Note
that following this strategy implies that the point-wise size of $\Gamma$
satisfies $\operatorname{S}(\Gamma,{\bm{x}})=k({\bm{x}},\mathbb{P})$.
NB. $k=k({\bm{x}},\mathbb{P})$ is allowed to depend on a point
${\bm{x}}\in\mathcal{X}$ and the distribution $\mathbb{P}$.

  * •

Hybrid: the hybrid strategy can be obtained by a point-wise intersection of
the thresholding rule and the point-wise top-$k$ rule. We describe several
examples of such strategy in Section 6.1. See also Table 1 for some examples.
NB. we are not aware of previus contributions that consider hybrid frameworks.

We again emphasize that in case of thresholding, the value of
$\theta=\theta(\mathbb{P})$ can depend on the unknown distribution
$\mathbb{P}$ and ought to be estimated. Meanwhile, in case of point-wise
top-$k$, the parameter $k=k({\bm{x}},\mathbb{P})$ can depend on both: point
${\bm{x}}$ where prediction should be constructed as well as the unknown
distribution.

###  1.3 Organization of the paper

Section 4 presents most popular set-valued classification strategies and
illustrates them in simple examples. People that are interested only on the
numerical comparison of the different framework would directly go to Section
5. Hybrid methods, that involve sophisticate constraints or more that one
constraint are introduced in Section 6.1. In particular, we state in this
section the closed-form of the optimal hybrid set-valued classifiers.

###  1.4 Notation

Throughout this work we use the following generic notation. For every
$L\in\mathbb{N}$, we denote by $[L]\vcentcolon=\\{1,\ldots,L\\}$, the set of
first $L$ positive integers. For every finite set $A$, we denote by $|A|$ the
cardinality of $A$. The power set (the set of all subsets) of a finite set $A$
is denoted by $2^{A}$. For a monotone decreasing function $F$ we denote by
$F^{-1}$ it generalized inverse222See Embrechts and Hofert (2013) for general
definition of the generalized inverse of a monotone function. defined point-
wise as $F^{-1}(u)\vcentcolon=\inf\left\\{t\in\mathbb{R}\,:\,F(t)\leq
u\right\\}$.

##  2 Related classification frameworks

Set-valued classification has many connections with other classification
setups that may lead to confusions and the differences may not well understood
at the first sight. The purpose of this section is to clarify the relation of
set-valued classification with other frameworks and emphasize the key
differences.

###  2.1 Multi-label classification

At the first glance set-valued classification seems to be directly connected
to _multi-label classification_ (Dembczyński et al., 2012; Zhang and Zhou,
2013). This is a recurrent source of confusion for readers and practitioners
and we dedicate this section to clarify this point. Mainly, the confusion
comes from the fact that in both settings a set of label candidates is
predicted as an output. However, the crucial difference with set-valued
classification lies in the data-generating process. From purely practical
perspective, if the classes $Y_{i}$’s in a given dataset are elements of $[L]$
and not of $2^{[L]}$, then there should be no confusion between the multi-
class and the multi-label settings. In other words, it is the training sample
that dictates the setting and the underlying data generation process.

To be more precise, in multi-label classification each input
${\bm{x}}\in\mathcal{X}$ is associated with a set of labels
${\bm{y}}\in\\{0,1\\}^{L}$. During training, we are given a set of such pairs
$({\bm{X}}_{i},{\bm{Y}}_{i})_{i=1}^{n}$ and the goal is to learn a _multi-
label classifier_
${\bm{h}}=(h^{(1)},\ldots,h^{(L)})^{\top}:\mathcal{X}\to\\{0,1\\}^{L}$ from
it. A typical example of such data is the Wikipedia dataset (Zubiaga, 2012;
Bhatia et al., 2016), where ${\bm{X}}_{i}$ is a Wikipedia article and
${\bm{Y}}_{i}$ describes the categories that are intended to group similar
articles together.

Already at this level we can observe the difference between multi-labeled and
multi-class data. In the former, a given input ${\bm{x}}$ is tagged by
${\bm{y}}=(y^{(1)},\ldots,y^{(L)})^{\top}$, i.e., $L$ distinct 0/1 entries.
Meanwhile, in the latter the label is a unique integer. From the theoretical
perspective, we note that in the multi-label setting each label $Y^{(\ell)}$
has a probability
$q_{\ell}({\bm{x}})\vcentcolon=\mathbb{P}(Y^{(\ell)}=1\mid{\bm{X}}={\bm{x}})$
to be present and $1-q_{\ell}({\bm{x}})$ to be absent from the set of labels
for a given instance ${\bm{x}}$. Note that in general the
$\sum_{\ell=1}^{L}q_{\ell}({\bm{x}})$ can, and most likely does, exceed one.
In contrast, in multi-class classification, the label $Y\in[L]$ of a given
input ${\bm{x}}$ is sampled from the conditional probability
$p_{\ell}({\bm{x}})=\mathbb{P}(Y=\ell\mid{\bm{X}}={\bm{x}})$ which is a
categorical distribution, i.e., $\sum_{\ell=1}^{L}p_{\ell}({\bm{x}})=1$.

Despite the above difference, the eventual goal in both frameworks is still to
predict a set and any multi-class problem can be viewed as an instance of
multi-label problem with additional dependency structure introduced on the
classes. From this point of view, any method tailored for multi-label problems
can be used in the framework of set-valued classification. Indeed, note that
for any multi-label prediction ${\bm{h}}:\mathcal{X}\to\\{0,1\\}^{L}$ one can
build a set-valued one
$\Gamma_{{\bm{h}}}({\bm{x}})=\left\\{\ell\in[L]\,:\,{\bm{h}}^{(\ell)}({\bm{x}})=1\right\\}$.
However, since these methods are not constructed with the multi-class
generation process in mind, their applicability is limited and set-valued
minded algorithms are better suited in this case.

Of course there are other, more subtle, differences between the two
frameworks. For instance, we did not discuss the choice of the risk measure
for the multi-label classification nor we talked about possible dependencies
inside ${\bm{Y}}$. These directions are exciting and bring a lot of
interesting questions, but as it should be already clear, in a completely
different framework from what we consider in this manuscript.

###  2.2 Classification with reject option

An alternative approach to address the ambiguity in multi-class classification
problem is via the so-called classification with reject option (Chow, 1957,
1970; Herbei and Wegkamp, 2006; Ni et al., 2019; Ramaswamy et al., 2018; Wu,
Jia and Chen, 2007; Zhang, Wang and Qiao, 2018; Denis and Hebiri, 2020). In
this framework, instead of predicting a set capturing the ambiguous classes,
the classifier is allowed to abstain from prediction, that is, it informally
says _“I do not know”_. This refusal has a cost – a parameter of the problem
in this setting – depending on which lower error rate can be achieved compared
to a single class outputs.

Speaking formally, the predictor with reject option is a function of the form
$h:\mathcal{X}\to[L]\cup\\{\circledR\\}$ where $\circledR$ represents a
refusal to answer. One can view this predictor as a special form of set-valued
classifier. Indeed, whenever $h$ outputs a value in $[L]$, then the
corresponding set-valued classifier outputs a singleton. Meanwhile, the
rejection symbol $\circledR$ for $h$ corresponds to two situations for a set-
valued classifier, either the set-valued classifier outputs the empty set or
more than one label. Consequently, the classifiers with rejection are strictly
included in the set-valued predictors, since the latter allow a more flexible
quantification of “I do not know” prediction.

###  2.3 Conformal prediction

Seminal ideas of set-valued classification appear also in the works by Vovk,
Gammerman, and Shafer on conformal prediction theory (Vovk, Gammerman and
Shafer, 2005a). Given a set of supervised data
$({\bm{X}}_{1},Y_{1}),\ldots,({\bm{X}}_{n},Y_{n})$, a new instance ${\bm{X}}$,
and a confidence level $\alpha$ the goal in conformal prediction theory is to
provide a set
$\Gamma_{\alpha}({\bm{X}})=\Gamma_{\alpha}(({\bm{X}}_{1},Y_{1}),\ldots,({\bm{X}}_{n},Y_{n}),{\bm{X}})\subset
2^{[L]}$, which satisfies

$\displaystyle\mathbf{P}(Y\notin\Gamma_{\alpha}({\bm{X}}))\leq\alpha\enspace,$

where $\mathbf{P}$ stands for the joint distribution of
$({\bm{X}}_{1},Y_{1}),\ldots,({\bm{X}}_{n},Y_{n}),({\bm{X}},Y)$. To achieve
this goal, the conformal prediction theory relies on the exchangeability
assumptions, which is slightly more general than the i.i.d. assumption.
Moreover, conformal theory relies on the conformity measure which assigns a
level of similarity of each instance $({\bm{X}},Y)$ w.r.t. the data.

Though we do not focus on the conformal predictions, the reader should keep in
mind that this powerful framework should not be put against the direction that
we take here. Rather, it should be viewed as a viable alternative (and
sometimes complementary) way to build set-valued classifiers, with strong
expected error rate or expected size guarantees, having its advantages and
disadvantages over the framework described here. The major advantage is of
course the assumption free average error rate (or average size) guarantees,
while possible disadvantages include high computational complexity and
randomized nature of the constructed classifiers. The latter means that for
the same input ${\bm{X}}$ the set $\Gamma_{\alpha}({\bm{X}})$ can be different
from one experiment to another depending on the underlying randomness of
$\Gamma_{\alpha}$. For a broad review of conformal prediction theory with main
theoretical and practical advances we refer to Vovk, Gammerman and Shafer
(2005a); Vovk et al. (2017).

##  3 Practical motivations and applications

In general, set-valued classification can be applied on top of any multi-class
problem. At the same time, in certain scenarios, the set-valued approach might
be strictly preferred to the single-output paradigm. This is especially the
case in applications where the observed data $({\bm{X}}_{i},Y_{i})$ comes from
a multi-class classification problem – we observe a unique class $Y_{i}\in[L]$
associated with the observation ${\bm{X}}_{i}$ – but, the uniqueness of the
class is not actually intrinsic to the problem at hand. In this section we
describe several applications and data acquisition processes where set-valued
classification paradigm might be preferred.

###  3.1 Fault-intolerant applications

Set-valued classification framework arises naturally in fault-tolerance type
problems. The goal is to produce a prediction with (almost) null error. While
such guarantee can hardly be expected from a single output predictor, accurate
as it may be, drastically low errors can be achieved by set-valued
classifiers. This is especially the case if the error rate is added as a
desirable constraint (_cf._ Section 4.2.2). Typical examples of this problem
are connected with medical diagnosis or aeronautic purposes – areas where the
price for a wrong prediction is too high to be tolerated (Kourou et al., 2015;
Lambin et al., 2017). In these type of applications the set-valued
classification framework can serve as a replacement of a more standard
approach based on re-weighting (Turney, 1994; Elkan, 2001) of errors and
modification of score function (Ling, Huang and Zhang, 2003).

###  3.2 Highly ambiguous datasets

High ambiguity between classes emerges in numerous applications and this is
the bedrock of the use of set-valued frameworks. In practice, it is very
common that modern large-scale datasets contain a fair amount of ambiguity
among classes. It is especially the case in standard Fine-Grained Visual
Categorization (FGVC) datasets such as PlantCLEF2015 (Göeau, Joly and Bonnet,
2015a), ImageNet (Russakovsky et al., 2015a)333See
https://sites.google.com/view/fgvc7 for additional examples..

As an example, consider a classification scenario where the output $y_{i}$
lies in $[L]$. At the same time, the input ${\bm{x}}_{i}$ is a representation
of a latent object ${\bm{o}}_{i}$ which is indeed associated with a single
label $y_{i}\in[L]$. However, the observed input ${\bm{x}}_{i}$ is a blurred,
noisy, corrupted, or partial version of ${\bm{o}}_{i}$ and it may be hard to
recover the true label $y_{i}$ based solely on ${\bm{x}}_{i}$. Notably, the
noise in measurement is actually responsible for the ambiguity and set-valued
classifiers can serve as a remedy in this case.

A prominent example where such processes occur is connected to plant image
recognition (Göeau, Joly and Bonnet, 2015a; Champ et al., 2015, 2016).
Consider the case where the latent object ${\bm{o}}_{i}$ is a given plant
species and ${\bm{x}}_{i}$ is its image typically taken by a smartphone. While
a botanist expert of this flora is able to provide the exact specie $y_{i}$ of
the object ${\bm{o}}_{i}$, it is possible that even an expert may fail to
classify based on the image ${\bm{x}}_{i}$. Indeed, the latter might be too
blurred or might consist of only one organ of the plant, say the flower, which
may not provide enough information to be perfectly discriminated from other
species. On the other hand, based on the partial information provided by
${\bm{x}}_{i}$, the expert is typically able to extract a small subset of
species $\Gamma({\bm{x}}_{i})\subset[L]$ that is likely to contain the true
description $y_{i}$ of ${\bm{o}}_{i}$. In this case, the expert naturally acts
as if he is a set-valued classifier.

###  3.3 Collecting a single positive label in multi-label data

(a) banana, orange, Granny Smith

(b) sports car, convertible

(c) impala, gazelle, hartebeest

Figure 2:  Examples from ImageNet containing either multiple objects (a), or a
single object with multiple matching attributes (b), or an intrinsically
ambiguous image containing a single object associated with a single class (c).
The official annotation associated is shown in bold.

Unlike highly ambiguous datasets, positive-only data is inherently multi-
label: each observation contains several objects or attributes belonging to
different classes, see Figures 2(a) and 2(b). However, in certain cases,
annotating multi-label data can be very expensive since a positive or negative
label must be collected for every class. A common modeling assumptions was
described in (Royle et al., 2012; Hastie and Fithian, 2013; Mac Aodha, Cole
and Perona, 2019) where only a _single_ positive label $y_{i}\in[L]$ is
reported for each instance ${\bm{x}}_{i}$. The popularity of this framework
stems from the fact that it is typically easy to detect a single present
object on a picture, while it is increasingly harder and more time consuming
to detect all the present objects. Note how in this case, the inherently
multi-label problem is transformed into a multi-class one due to the data
gathering process. As an example, one might imagine the scenario where a human
expert observes an image ${\bm{x}}_{i}$ which might involve several objects,
and reports only the first one that was noticed ignoring the rest. The most
famous benchmark dataset which falls within the scope of this framework is
ImageNet (Russakovsky et al., 2015a), where each image ${\bm{x}}_{i}$ is
annotated by one and only one class $y_{i}\in[L]$.

##  4 Main set-valued classification frameworks

Several set-valued classifiers fall within the formulation (1.2). Because
there have been contributions from different fields and there is no
standardized naming for the different formulations, providing an exhaustive
overview of the literature is impossible. Therefore, in this section we made
the choice to focus on the four most popular and intuitive set-valued
classification frameworks for multi-class setting described by such unified
formulation (1.2). (We differ to Section 6 a discussion on more involved
frameworks which also fall with this formulation or on other formulations
obtained as hybrids of the four main formulations since they are not
considered in the comparison study of this work.) In these four formulations,
the set $\operatorname{{\mathcal{C}}_{\mathbb{P}}}$ in (1.2) constrains
whether the error rate or the size of the set-valued classifier.

This section is organized in four paragraphs, each of them is devoted to one
set-valued formulation. For each particular set-valued problem, we define the
set-valued classifier as a particular solution of the formulation (1.2),
exhibit a closed-form of an optimal solution, illustrate the strategy to build
a data-driven procedure, discuss its advantages and disadvantages, and provide
a brief literature review.

Before proceeding, let us comment on some general considerations (that can be
skipped by the reader without any impact): the optimal solutions that we will
provide highlight a general plug-in type approach to construct practically
relevant set-valued classification procedures for all frameworks. In
particular, all the optimal set-valued classifiers rely on the conditional
probabilities ${\bm{p}}=(p_{1},\ldots,p_{L})^{\top}$. Therefore, in order to
build a data-driven counterpart, we first need an estimator
$\hat{\bm{p}}=(\hat{p}_{1},\ldots,\hat{p}_{L})^{\top}$ of ${\bm{p}}$, and this
step requires a _labeled_ dataset. Furthermore, in order to enforce the
constraint in (1.2), it turns out that the estimation step for some set-valued
classifiers is more involved and then needs the estimation of an additional
parameter that depends on the underlying data-distribution. As a consequence,
the estimation procedures can be categorized into three types depending on
whether they require _no additional data_ , an additional _unlabeled_ data, or
an additional _labeled_ additional data. Note that in the case where
additional unlabeled data is required, if such data was already available
beforehand, i.e., in the semi-supervised setting (Vapnik, 1998), then it can
be leveraged directly by the estimation procedure. However, as we will see, in
most cases, we do not require a lot of additional data, less than for training
$\hat{\bm{p}}$, unlike most semi-supervised cases where unlabeled data is
abundant, more than training data. If, on the other hand, only labeled data is
available, then the estimation procedure might require to split this data is
two and to discard some labels.

Lastly, let us emphasize that for some of the results of this section we need
the following mild assumption.

######  Assumption 1.

Random variables $p_{\ell}({\bm{X}})$ are non-atomic for all $\ell\in[L]$.

This assumption is equivalent to assuming that the distribution of
$p_{\ell}({\bm{X}})$ is continuous for all $\ell\in[L]$. Essentially,
Assumption 1 is a sufficient condition under which several set-valued
frameworks are well defined. That is to say that the optimal set-valued
classifier
$\Gamma^{*}_{(\operatorname{F_{\mathbb{P}}},\operatorname{{\mathcal{C}}_{\mathbb{P}}})}$
exists, is unique, and is deterministic. We refer to (Chzhen, Denis and
Hebiri, 2021; Sadinle, Lei and Wasserman, 2019a) for a broad discussion on the
role of Assumption 1. In particular, (Sadinle, Lei and Wasserman, 2019a)
describe a way to bypass this assumption by considering randomized set-valued
classifiers. As it is not the main scope of this paper we resort to Assumption
1 when necessary to avoid this technicality.

###  4.1 Point-wise control – almost sure type constraints

In this part we describe those frameworks that can be formulated withing the
unified paradigm (1.2) with a set $\operatorname{{\mathcal{C}}_{\mathbb{P}}}$
defined by a point-wise type constraint on the classifier $\Gamma$.

####  4.1.1 Point-wise size control: Top-$k$ classifier.

In classification tasks, it is common to replace the top-1 error rate by a
top-k error rate. For instance, ImageNet classification task (Russakovsky et
al., 2015a) uses top-5 error rate as the main performance measure to account
for the possible presence of several objects of different classes in the
images.

This first natural approach in set-valued prediction simply consists in
predicting sets of same size $k$ for every input:

$\displaystyle|\Gamma({\bm{x}})|=k\enspace,$

which is the most straightforward generalization of the single-output
strategy. In this case, the problem can be formulated as finding the optimal
classifier $\Gamma^{*}_{k}$ solving the following problem,

$\displaystyle\Gamma^{*}_{k}\in\operatorname*{arg\,min}_{\Gamma}$
$\displaystyle\mathbb{P}(Y\notin\Gamma({\bm{X}}))$ (point-wise size control)
s.t. $\displaystyle|\Gamma({\bm{x}})|\leq k\quad\text{a.s.
}\mathbb{P}_{{\bm{X}}}$

Note that for this formulation
$\operatorname{{\mathcal{C}}_{\mathbb{P}}}=\left\\{\Gamma\,:\,|\Gamma({\bm{x}})|\leq
k\text{ a.s. }\mathbb{P}_{{\bm{X}}}\right\\}$. Though, formally this
definition depends on the marginal distribution $\mathbb{P}_{{\bm{X}}}$ one
can immediately notice that the constraint ${|\Gamma({\bm{x}})|\leq k\text{
a.s. }\mathbb{P}_{{\bm{X}}}}$ can be replaced by $|\Gamma({\bm{x}})|\leq k$
for all ${\bm{x}}\in\mathcal{X}$. The attractive feature of such a formulation
is that the optimal classifier $\Gamma^{*}_{k}$ admits a simple and intuitive
closed-form solution – at every point ${\bm{x}}$ it outputs $k$ most probable
candidates.

######  Lemma 1.

For all ${\bm{x}}\in\mathcal{X}$ the classifier $\Gamma^{*}_{k}$ can be
obtained by

$\displaystyle\Gamma^{*}_{k}({\bm{x}})=\operatorname{top}_{{\bm{p}}}({\bm{x}},k)\enspace,$

where for all ${\bm{x}}\in\mathcal{X}$, and $k\in[L]$, the operator
$\operatorname{top}_{{\bm{p}}}({\bm{x}},k)$ outputs the $k$ labels with
largest values among $p_{1}({\bm{x}}),\ldots,p_{L}({\bm{x}})$.

Top-$k$ classifier is the most straightforward approach to set-valued
classification and provides an exact control on the point-wise set size. This
simplicity is at the price of a lack of adaptation to the heterogeneity of the
problem. Indeed, top-$k$ outputs $k$ labels for every
${\bm{x}}\in{\mathcal{X}}$ independently of the level of ambiguity of the
samples. Furthermore, the exact value of $k$ to use might not always be clear
beforehand and might require a posteriori refinement. Finally, this framework
does not provide any control over the error rate.

Estimation. To estimate this set-valued classifier, a single labeled training
dataset is required, no additional data is necessary. In particular, the plug-
in top-$k$ classifier is defined element-wise by

$\displaystyle\forall{\bm{x}}\in{\mathcal{X}},\quad\hat{\Gamma}_{k}({\bm{x}})=\operatorname{top}_{\hat{{\bm{p}}}}({\bm{x}},k).$

Note that in fact this estimator does not require to estimate exactly the
conditional probability ${\bm{p}}({\bm{x}})$ as any scoring function
preserving the ranking of ${\bm{p}}({\bm{x}})$ will give exactly the same
classifier.

Bibliographic references. This formulation has long ago been used to compare
models in practice. Lapin, Hein and Schiele (2015) address the point-wise size
control formulation by providing a surrogate hinge loss. In particular, they
illustrated the superiority of their modified top-$k$ procedure as compared to
One-Versus-All SVMs. Several works followed dealing with convex surrogates for
this problem. Lapin, Hein and Schiele (2016) proposed a new hinge surrogate of
the $0/1$-loss as well as a modified cross-entropy loss, and, following the
classical results of Zhang (2004); Bartlett, Jordan and McAuliffe (2006), they
defined the notion of “top-$k$ calibration”, a property that is satisfied by
their introduced loss functions, see also Yang and Koyejo (2020). Berrada,
Zisserman and Kumar (2018) modified the loss proposed by Lapin, Hein and
Schiele (2015) in order to provide a smooth loss function better adapted for
neural networks and showed that the resulting method achieves state-of-the-art
performance on classical image datasets.

From theoretical point of view Lorieul, Joly and Shasha (2020) proved a bound
on the error rate of the top-$k$ set-valued classifier based on the
$\ell_{1}$-estimation error of the conditional probabilities.

####  4.1.2 Point-wise error control:

Another formulation consists in minimizing the average set size under a point-
wise error rate constraint

$\displaystyle\Gamma^{*}_{\epsilon}\in\operatorname*{arg\,min}_{\Gamma}$
$\displaystyle\mathbb{E}_{{\bm{X}}}|\Gamma({\bm{X}})|$ (point-wise error
control) s.t.
$\displaystyle\mathbb{P}(Y\notin\Gamma({\bm{X}})\mid{\bm{X}}={\bm{x}})\leq\epsilon,\text{
a.s. }\mathbb{P}_{{\bm{X}}}$

We remark that in this case
$\operatorname{{\mathcal{C}}_{\mathbb{P}}}=\left\\{\Gamma\,:\,\mathbb{P}(Y\notin\Gamma({\bm{X}})\mid{\bm{X}}={\bm{x}})\leq\epsilon,\text{
a.s. }\mathbb{P}_{{\bm{X}}}\right\\}$. Again, as in the previous paragraph the
dependency on $\mathbb{P}_{{\bm{X}}}$ can be dropped.

The closed-form expression of $\Gamma^{*}_{\epsilon}$ is again rather
intuitive. It is closely connected to the top-$k$ strategy, however, unlike
previous section, where $k$ was fixed beforehand, the size of the output set
can vary from one point to another in this case. The classifier
$\Gamma^{*}_{\epsilon}$ can be supported by the following intuition: “Given
point ${\bm{x}}$ the prediction $\Gamma^{*}_{\epsilon}({\bm{x}})$ consists of
$k_{\epsilon}({\bm{x}})$ most probable classes, such that the cumulative
probability of $(L-k_{\epsilon}({\bm{x}}))$ not included classes is at most
$\epsilon$”.

######  Lemma 2.

For every $\epsilon$ an optimal set-valued classifier $\Gamma^{*}_{\epsilon}$
can be obtained for all ${\bm{x}}\in\mathcal{X}$ as

$\displaystyle\Gamma^{*}_{\epsilon}({\bm{x}})=\operatorname{top}_{{\bm{p}}}({\bm{x}},k_{\epsilon})\enspace,$

where $k_{\epsilon}=k_{\epsilon}({\bm{x}})$ is such that

$\displaystyle
k_{\epsilon}({\bm{x}})=\min\left\\{k\in[L]\,:\,\sum_{\ell=1}^{k}p_{(\ell)}({\bm{x}})\geq
1-\epsilon\right\\}\enspace.$

###### Proof.

Postponed to appendix ∎

Theoretically, this formulation provides strong guarantees on the point-wise
error rate. It is thus very relevant for scenarios where the error rate must
be controlled precisely. One major drawback of this formulation is that it
does not provide any control over the set size and can thus predict large sets
which can then be uninformative. A practical limitation is that it is hard to
measure the point-wise error rate and thus the theoretical guarantees are
often violated in practice.

Estimation. To estimate this set-valued classifier, a single labeled training
dataset is required, no additional data is necessary. In particular, the plug-
in set-valued classifier is defined element-wise by

$\displaystyle\forall{\bm{x}}\in{\mathcal{X}},\quad\hat{\Gamma}_{\epsilon}({\bm{x}})=\operatorname{top}_{\hat{{\bm{p}}}}({\bm{x}},\hat{k}_{\epsilon}({\bm{x}})).$

with

$\hat{k}_{\epsilon}({\bm{x}})=\min\left\\{k\in[L]\,:\,\sum_{\ell=1}^{k}{\hat{p}}_{(\ell)}({\bm{x}})\geq
1-\epsilon\right\\}$

where ${\hat{p}}_{(\ell)}({\bm{x}})$ is a reordering of
$\hat{p}_{1}({\bm{x}}),\ldots,\hat{p}_{L}({\bm{x}})$ in decreasing order,
i.e., $\hat{p}_{(1)}({\bm{x}})\geq\ldots\geq{\hat{p}}_{(L)}({\bm{x}})$. Note
that this estimator requires to estimate exactly the conditional probability
${\bm{p}}({\bm{x}})$ as they serve to estimate the point-wise error rate on
which we set our constraint. The model must thus output calibrated
probabilities which requires additional care during training or an extra post-
processing step.

Note that due to the finite sample effects the point-wise error rate might
actually exceed the desired level $\epsilon$. If such a behaviour is
undesirable, a simple practical remedy can be provided via the off-set
strategy. This approach is exactly the same as described above, but with

$\hat{k}_{\epsilon}({\bm{x}})=\min\left\\{k\in[L]\,:\,\sum_{\ell=1}^{k}{\hat{p}}_{(\ell)}({\bm{x}})\geq
1-\epsilon+r_{n,L}\right\\}\enspace,$ (5)

where $r_{n,L}$ is some positive sequence of the size of the dataset and the
number of classes. Intuitively, this strategy requires to pick a smaller value
of $\epsilon$ for the estimator. We illustrate this strategy on Figure 3(c)
with $r_{n,L}=\sqrt{\nicefrac{{L}}{{n}}}$.

Bibliographic references. Until very recently, most references dealing with
set-valued classifiers that satisfy the point-wise error rate constraint (most
of the time referred to as conditional validity) is related to the regression
setting. For instance, (Cai, Low and Ma, 2014; Lei and Wasserman, 2014; Lei et
al., 2018) proposed an asymptotic study of predictors based on the point-wise
error rate constraint under smoothness condition on the regression function.
In addition, Barber et al. (2019) studied a relaxed version of the point-wise
error rate requirement. More recently (Gyöfi and Walk, 2020) established
finite sample distribution-free control on the tail distribution on the point-
wise error rate and on the size of the predictor. The latter reference also
provided strong consistency results under smoothness conditions on the
regression function.

One classical result when we deal with finite sample control on the point-wise
error rate is due to Lei and Wasserman (2014, Lemma 1) (extended to the
classification setting by Vovk (Vovk, 2013)) that establishes that no control
on the point-wise error rate can hold (for continuous marginal
$\mathbb{P}_{{\bm{X}}}$) in a distribution-free setting unless with trivial
set-valued predictors.

According to the classification setting, Vovk (Vovk, 2013) provided a
conformal predictor type algorithm to ensure the point-wise error rate
validity on the training sample. Recently (Gyöfi and Walk, 2020), proposed a
$k$NN based set-valued classifier and derived, under smoothness conditions on
the $p_{\ell}$’s, finite sample bounds on the conditional error rate and on
the point-wise size of the provided set. About the same time (Romano, Sesia
and Candès, 2020) developed a method that also attempt to get approximate
conditional error rate guarantee.

###  4.2 Average control – constraints in expectation

Unlike standard top-$k$ predictions, general set-valued classification
framework allows varying sizes of the set-valued classifier $\Gamma$,
depending on the ambiguity in the distribution. A natural methodological
approach to build suitable set-valued classifiers lies in the minimization of
the penalized risk that takes into account both risk and size. That is, for
$\lambda>0$, we set

$\displaystyle\Gamma^{*}_{\lambda}\in\operatorname*{arg\,min}_{\Gamma}\;$
$\displaystyle\mathbb{P}(Y\notin\Gamma({\bm{X}}))+\lambda\
{\mathbb{E}_{{\bm{X}}}}|\Gamma({\bm{X}})|\enspace.$ (penalized version)

This framework is among the first to be proposed and analyzed in the
literature by Ha (1996, 1997a, 1997b). It is also known as _class-selective
rejection_ (Ha, 1996) or _class-selection_ (Le Capitaine, 2014). It can be
seen as a generalization of classification with reject option to the multi-
class setting Herbei and Wegkamp (2006). To the best of our knowledge, from a
statistical learning perspective, this framework has not been much studied. In
particular, we have not found any study of empirical risk minimization
procedures, nor proposal of surrogate losses for this risk. Notably, the set-
valued prediction $\Gamma^{*}_{\lambda}$ admits a closed-form solution written
in a simple thresholding form.

######  Lemma 3.

For all $\lambda\geq 0$ and all ${\bm{x}}\in\mathcal{X}$ it holds that

$\displaystyle\Gamma^{*}_{\lambda}({\bm{x}})=\left\\{\ell\in[L]\,:\,p_{\ell}({\bm{x}})\geq\lambda\right\\}\enspace.$

When the cost/threshold $\lambda$ is fixed, this formulation is very simple.
However, choosing the appropriate value for $\lambda$ beforehand can be hard
in practice. In particular, the way this parameter controls the error rate and
the set size is not explicit. To overcome this difficulty, the next
formulations control these quantities explicitly.

This framework also admits a simple estimation strategy. In particular, the
plug-in set-valued classifier is defined element-wise by

$\displaystyle\forall{\bm{x}}\in{\mathcal{X}},\quad\hat{\Gamma}_{\lambda}({\bm{x}})=\left\\{\ell\in[K]\,:\,\hat{p}_{\ell}({\bm{x}})\geq\lambda\right\\}.$

Also, in general, as this formulation is expressed as an unconstrained risk
minimization problem, the decision rule can be learned directly using
empirical risk minimization approaches removing the need to estimate the
conditional probability explicitly, much alike traditional classification
methods.

####  4.2.1 Average set size control:

Instead of the above penalized version of the problem, one can consider its
constrained counterparts, for instance, minimizing the error given a
constraint on the expected set size

$\displaystyle\Gamma^{*}_{\bar{k}}\in\operatorname*{arg\,min}_{\Gamma}\mathbb{P}(Y\notin\Gamma({\bm{X}}))$
(average size control)
$\displaystyle\phantom{\Gamma^{*}_{\bar{k}}\in\operatorname*{arg\,min}_{\Gamma}}\text{s.t.
}\mathbb{E}_{{\bm{X}}}|\Gamma({\bm{X}})|\leq\bar{k}\enspace.$

For this framework the set
$\operatorname{{\mathcal{C}}_{\mathbb{P}}}=\left\\{\Gamma\,:\,\mathbb{E}_{{\bm{X}}}|\Gamma({\bm{X}})|\leq\bar{k}\right\\}$.
Note how in this case, unlike previous constrained formulations, the set
$\operatorname{{\mathcal{C}}_{\mathbb{P}}}$ unavoidably depends on the
marginal distribution $\mathbb{P}_{{\bm{X}}}$ of ${\bm{X}}$. In particular, it
is, in general, impossible to say a priori if a given set-valued classifier
$\Gamma$ belongs to this set.

It is common that the constrained versions of optimization problems are in
some sense equivalent to its penalized counterparts. This phenomena occurs
here as well following the next result of Denis and Hebiri (2017).

######  Lemma 4.

Let Assumption 1 be satisfied. Fix $\bar{k}\in(0,K)$ and define

$\displaystyle G(t)=\sum_{\ell=1}^{L}\mathbb{P}(p_{\ell}({\bm{X}})\geq
t)\enspace.$ (6)

Then, an optimal set-valued classifier $\Gamma^{*}_{\bar{k}}$ can be obtained
for all ${\bm{x}}\in\mathcal{X}$ as

$\displaystyle\Gamma_{\bar{k}}^{*}({\bm{x}})=\left\\{\ell\in[L]\,:\,p_{\ell}({\bm{x}})\geq
G^{-1}(\bar{k})\right\\}\enspace,$

where $G^{-1}(\cdot)$ is the generalized inverse of $G(\cdot)$.

Note that if we pick the penalization parameter $\lambda=G^{-1}(\bar{k})$,
then the penalized version yields the same optimal set-valued classifier as
the one resulting from the present formulation. Yet, the choice
$\lambda=G^{-1}(\bar{k})$ cannot be made without additional data.

This formulation can be seen as an adaptive version of the point-wise size
control formulation which is able handle the heterogeneity of the task
ambiguity. As a consequence, the present optimal set-valued classifier yields
a smaller error rate than that of top-$k$ classifier (since top-$k$ is
feasible for the average size control formulation with $\bar{k}=k$). On the
other hand, the threshold $G^{-1}(\bar{k})$ is distribution dependent and thus
relies on the marginal distribution ${\mathbb{P}}_{{\bm{X}}}$. It should be
noted that this formulation does not provide an explicit control over the
error rate which can be potentially large for individual samples.

Estimation. To estimate this set-valued classifier, an additional unlabeled
dataset can be used to estimate the threshold $G^{-1}(\bar{k})$. Indeed, the
constraint involved in this set-valued classifier relies on the marginal
distribution ${\mathbb{P}}_{{\bm{X}}}$, and, in principle, unlabeled data
would allow to estimate this constraint. Denote by
${\bm{X}}^{\prime}_{1},\ldots,{\bm{X}}^{\prime}_{N}$ the unlabeled dataset of
size $N$ sampled independently from ${\mathbb{P}}_{{\bm{X}}}$ and define the
following function

$\displaystyle\forall
t\in[0,1],\quad\hat{G}(t)=\frac{1}{N}\sum_{i=1}^{N}\sum_{\ell=1}^{L}\mathbb{I}{\left\\{\hat{p}_{\ell}({\bm{X}}^{\prime}_{i})\geq
t\right\\}}.$ (7)

This function is essentially the empirical counterpart of the function $G$
from Eq. (6) computed using the unlabeled dataset and for the estimator
$\hat{{\bm{p}}}$. The plug-in set-valued classifier is then defined element-
wise by

$\displaystyle\forall{\bm{x}}\in{\mathcal{X}},\quad\hat{\Gamma}_{\bar{k}}({\bm{x}})=\left\\{\ell\in[L]\,:\,\hat{p}_{\ell}({\bm{x}})\geq\hat{G}^{-1}(\bar{k})\right\\},$

where $\hat{G}^{-1}$ is the generalized inverse of $\hat{G}$.

Bibliographic references. The present framework was introduced by Denis and
Hebiri (2017), where the authors proposed a semi-supervised procedure based on
empirical risk minimization. They derived rates of convergence under
smoothness conditions on the conditional probabilities. The idea to use
unlabeled data to build set-valued classifiers was first discovered and
developed by Denis and Hebiri (2017), where the authors proposed a two step
empirical risk minimization procedure and derived rates of convergence. Later,
Chzhen, Denis and Hebiri (2019) developed a minimax analysis of this framework
and derived optimal rates of convergence for a semi-supervised approach based
on plug-in under smoothness conditions. They showed the superiority of semi-
supervised approaches over their supervised counterparts in certain
situations.

####  4.2.2 Average coverage control:

The previous approach attempt to find the best set-valued classifier among
those that have a desired average size. Yet, doing so does not actually give
any guarantees on the actual coverage, apart from being the smallest in the
set of classifiers of interest. Alternatively, we can target the minimization
of the expected set size given constraint on the error rate. This problem can
be formulated as follow

$\displaystyle\Gamma^{*}_{\bar{\epsilon}}\in\operatorname*{arg\,min}_{\Gamma}$
$\displaystyle\mathbb{E}_{{\bm{X}}}|\Gamma({\bm{X}})|$ (average error control)
s.t.
$\displaystyle\mathbb{P}(Y\notin\Gamma({\bm{X}}))\leq\bar{\epsilon}\enspace.$

For this framework the set
$\operatorname{{\mathcal{C}}_{\mathbb{P}}}=\left\\{\Gamma\,:\,\mathbb{P}(Y\notin\Gamma({\bm{X}}))\leq\bar{\epsilon}\right\\}$
and it unavoidably depends on the whole joint distribution $\mathbb{P}$ of
$({\bm{X}},Y)$.

Besides, again, this constrained formulation is closely tied to the penalized
version, thanks to the following result of Sadinle, Lei and Wasserman (2019b)
which characterizes the optimal set-valued classifier
$\Gamma^{*}_{\bar{\epsilon}}$.

######  Lemma 5.

Let Assumption 1 be satisfied. Fix $\bar{\epsilon}\in(0,1)$ and define

$\displaystyle H(t)=\mathbb{P}(p_{Y}({\bm{X}})\geq t)\enspace.$ (8)

Then, an optimal set-valued classifier $\Gamma^{*}_{\bar{\epsilon}}$ can be
obtained for all ${\bm{x}}\in\mathcal{X}$ as

$\displaystyle\Gamma_{\bar{\epsilon}}^{*}({\bm{x}})=\left\\{\ell\in[L]\,:\,p_{\ell}({\bm{x}})\geq
H^{-1}(1-{\bar{\epsilon}})\right\\}\enspace,$

where $H^{-1}(\cdot)$ is the generalized inverse of $H(\cdot)$.

Again we conclude that setting $\lambda=H^{-1}(1-{\bar{\epsilon}})$ in the
penalized version is equivalent to controlling the average error rate on the
level $\bar{\epsilon}$.

The present framework provides guarantees over the error rate. These
guarantees are weaker theoretically than those of point-wise error control and
can result in point-wise high error rates. However, this constraint is easier
to enforce and control in practice as the average error rate, unlike its
point-wise counterpart, can be measured on a labeled dataset. We additionally
emphasize that the constraint
$\mathbb{P}(Y\notin\Gamma({\bm{X}}))\leq\bar{\epsilon}$ actually depends on
the whole joint distribution $\mathbb{P}$, which stays in contrast with
average size control formulation.

Estimation. To estimate this set-valued classifier, an additional labeled
dataset (or subsampling) can be used to fit the threshold. In particular,
denote
$({\bm{X}}^{\prime}_{1},Y^{\prime}_{1}),\ldots,({\bm{X}}^{\prime}_{n^{\prime}},Y^{\prime}_{n^{\prime}})$
this labeled dataset of size $n^{\prime}$ sampled independently from
${\mathbb{P}}$ and define the following function

$\displaystyle\forall
t\in[0,1],\quad\hat{H}(t)=\frac{1}{n^{\prime}}\sum_{i=1}^{n^{\prime}}\sum_{\ell=1}^{L}\mathbb{I}{\left\\{Y^{\prime}_{i}=\ell\right\\}}\;\mathbb{I}{\left\\{\hat{p}_{\ell}({\bm{X}}^{\prime}_{i})\geq
t\right\\}}.$ (9)

This function is essentially the empirical counterpart of the function $H$ in
Eq. (8) computed using the labeled dataset and for the estimator
$\hat{{\bm{p}}}$. The plug-in set-valued classifier is then defined point-wise
by

$\displaystyle\forall{\bm{x}}\in{\mathcal{X}},\quad\hat{\Gamma}_{\bar{\epsilon}}({\bm{x}})=\left\\{\ell\in[L]\,:\,\hat{p}_{\ell}({\bm{x}})\geq\hat{H}^{-1}(1-{\bar{\epsilon}})\right\\},$

where $\hat{H}^{-1}$ is the generalized inverse of $\hat{H}$.

Bibliographic references. Lei (2014) studied a similar framework in the
context of binary classification with reject option. This framework was later
extended to the multi-class classification framework by Sadinle, Lei and
Wasserman (2019a) which provided the expression of the optimal set-valued
classifier. They also studied convergence properties of the plug-in set-valued
classifier under some smoothness assumptions on ${\mathbb{P}}$. The origin of
this framework is rooted in _conformal prediction_ literature (Vovk, Gammerman
and Shafer, 2005b) and Sadinle, Lei and Wasserman (2019a) derives a
classification procedure based on the ideas of conformal prediction theory.

##  5 Empirical comparison of the frameworks

In this section, we carry out experiments on real-world datasets to analyze
and compare the properties of the previously described formulations. We aim at
highlighting positive and negatives aspects of the frameworks described in the
previous section.

###  5.1 Constraint satisfiability in practice

In this section, we analyze if the constraints defined in each framework are
satisfied in practice. Since $\mathbb{P}$ is unknown, for all frameworks,
except point-wise size control (top-$k$), we cannot guarantee that the
constraint will be in a strict accordance with the theoretical requirement.
Our conclusions in this section will then be based on empirical evaluation of
the different constraints.

We perform our experiments on ImageNet (Russakovsky et al., 2015b) dataset
which contains 1.3 million images from 1,000 classes. We split this dataset
into a training set of 1.2 million images, a validation set of 50,000 images,
and a test set of 100,000 images. We remark that the labels of the official
test set are not publicly available and it is thus common practice to use the
official validation set as test set for experiments. This validation set
contains 50,000 images of the 1,000 classes. It is balanced and thus contains
50 images per class. Recall that the estimation procedures described in the
previous section can be performed on top of any off-the-shelf score based
classifier. For this reason, we use a pre-trained ResNet-152 neural network
(He et al., 2015) from PyTorch model
zoo444https://pytorch.org/docs/stable/torchvision/models.html. We then use the
predictions made on the validation set to carry out the experiments in this
section.

(a) Original probabilities.

(b) Calibrated probabilities.

(c) Prob. calib. + correction

Figure 3:  Plots assessing if the point-wise error rate constraint is violated
on ImageNet. The distributions of the class error rates are computed for
different values of point-wise error rate constraints. The median and the 10%,
25%, 75%, and 90% percentiles of the distribution of the class error rates are
shown. If the constraint would have been satisfied, these curves would be
below the red curve. These plots show that probability calibration is
important for the point-wise error control formulation, however, it does not
guarantee that the constraint will be satisfied.

####  5.1.1 Satisfiability of the point-wise error rate constraint

We start with the point-wise error control framework. In this case, it is
difficult to provide a good evaluation of the point-wise error
$\mathbb{P}(Y\notin\Gamma({\bm{X}})\mid{\bm{X}}={\bm{x}})$ involved in the
constraint. Indeed, for a specific ${\bm{x}}\in\mathcal{X}$ we have only
access to a binary variable
$\mathbb{I}{\left\\{Y\notin\Gamma({\bm{x}})\right\\}}$. Hence, unless we have
additional assumptions on the distribution of
$(\mathbb{I}{\left\\{Y\notin\Gamma({\bm{X}})\right\\}},{\bm{X}})$ it is
difficult to estimate the conditional expectation
$\mathbb{E}[\mathbb{I}{\left\\{Y\notin\Gamma({\bm{X}})\right\\}}\mid{\bm{X}}]=\mathbb{P}(Y\notin\Gamma({\bm{X}})\mid{\bm{X}})$.
Instead, we report a weaker quantity – the class conditional error rate
$\mathbb{P}(Y\notin\Gamma({\bm{X}})\mid Y=y)$ for all $y\in[L]$.

As shown in Figure 3-(a), the constraint is violated when we consider a neural
network based estimator of the probabilities. It is however possible to
enforce the constraint with additional steps: _i) calibration._ We apply a
probability calibration strategy that requires an additional dataset, and
which is well suited for neural networks (Guo et al., 2017). This step
consists in learning a temperature parameter $T$ which is used to scale the
predictions in the logit space before applying the softmax. As displayed in
Figure 3 (mid), this approach provides a good correction in terms of
constraint violation. However, even with this calibration step, the constraint
is still violated; _ii) correction._ We consider the correction step described
given by Equation 5. The effect of the calibration and the correction is
displayed in Figure 3 (right) where we observe that the constraint in this
case is satisfied up to $90\%$ percentile.

Apart from the recalibration, we conclude that for the particular point-wise
error control formulation, having properly calibrated probabilities is
important.

This experiment shows that point-wise error constraint is neither easy to
satisfy nor easy to measure in practice. Moreover, although theoretically, we
do not need an extra dataset to learn this constraint, in practice using this
additional data to calibrate the probabilities is very helpful and can improve
the performance. In the rest of the experiments, we will thus use temperature
scaling to calibrate probabilities when studying this formulation.

####  5.1.2 Satisfiability of average constraints

(a) Average size control with $\bar{k}=5$.

(b) Average error control with $\bar{\epsilon}=0.05$.

Figure 4:  Estimation plots depending on the size of the additional dataset of
the thresholds of the average size control and average error control
formulations on ImageNet. The mean values are shown in full line while the
shaded areas correspond to the standard deviation. The dashed line represents
the constraint to estimate. Average size control requires less additional data
than average error control to estimate a good threshold.

We now focus on constraint violation for average error control and average
size control frameworks. In both cases, we first need to compute a threshold
that we estimate thanks to an additional dataset555One can use the same
dataset to estimate the threshold and to evaluate the constraint, however,
such an approach would lead to dependency issues.. The size of this sample is
denoted by $n^{\prime}$ and $N$ for the average error control and average size
control frameworks respectively, see Equation 7 and Equation 9 respectively.
In what follows, we illustrate the effect of the sample sizes $n^{\prime}$ and
$N$ on the corresponding constraints. Secondly, we need another dataset to
measure the average error rate and the average set size according to the
considered framework. Therefore, we split the validation set into two sets of
equal sizes. One part is then used to sample the additional dataset while the
second one serves as a hold-out set to measure the average set size and
average error rate. The sampling of the additional dataset is performed $10$
times to measure standard deviations. The results are shown in Figure 4.

For average size control framework, the average size of the predicted sets
lies within an interval around the fixed constraint and the convergence is
fast w.r.t. $N$. Interestingly, even the average error rate of those sets is
very stable and converges fast as well. In contrast, for average error control
framework, both of the average error rate and the set size are highly
oscillating and converge significantly more slowly. It seems in addition that
the error rate, which is the parameter of interest here, is biased towards
higher error rates for small values of $n^{\prime}$. The main conclusion drawn
from these plots is thus that the calibration of threshold requires fewer
samples for average size control than for average error control. This is in
accordance with the general intuition since the error rate depends on the
distribution of $({\bm{X}},Y)$ while the set size relies only on the
distribution of ${\bm{X}}$. As a consequence more data are needed to ensure
good estimation of all the functions
$t\mapsto\mathbb{P}(p_{\ell}({\bm{X}})>t)$ for all $\ell\in[L]$ in the same
time.

###  5.2 Comparison on real-world datasets

We now study the different formulations on different real-world datasets and
analyze their properties. We focus on three image classification datasets:
MNIST (LeCun et al., 1998), ImageNet (Russakovsky et al., 2015b) and
PlantCLEF2015 (Göeau, Joly and Bonnet, 2015b).

(a) MNIST

(b) ImageNet

(c) PlantCLEF2015

Figure 5:  Comparison of average size control and point-wise size control
formulations, i.e., average error rate minimization under set size constraint
formulations, on different datasets. The average error rate is plotted against
the value of the constraint for both formulations, i.e., $\bar{k}$ for the
average control and $k$ for the point-wise control.

We first compare the formulations sharing the same objective but with a
different constraint. In Figure 5, we compare average size control and point-
wise size control formulations by plotting the achieved average error rate
against the value of the constraint on the set size. Note that the curve of
point-wise size control is a piece-wise constant function as the point-wise
set size can only take discrete values. The average set size does not have
this constraint and thus the curve of average size control is continuous. As
can be seen from the figure, the curve of average size control is always below
the one of point-wise size control. From left to right, the two curves are
less and less steep. This suggests that those datasets have a different amount
of ambiguity: MNIST is far less ambiguous than PlantCLEF2015. Moreover, the
wideness of the gap between the two curves depends on the dataset.

(a) MNIST

(b) ImageNet

(c) PlantCLEF2015

Figure 7:  Comparison of average error control and point-wise error control
formulations, i.e., average set size minimization under error rate constraint
formulations, on different datasets. The average set size is plotted against
the value of the constraint for both formulations, i.e., $\bar{\epsilon}$ for
the average control and $\epsilon$ for the point-wise control. The complete
plots are displayed on the left column while the right one shows a zoom on a
subpart of the plot.

Similarly, in Figure 7 , we compare average error control and point-wise error
control formulations by plotting the achieved average set size against the
value of the constraint on the error rate. As can be noticed, average error
control allows to reach average set sizes below one whereas point-wise error
control necessarily predicts sets of size larger or equal to one.
Theoretically, if the constraints were properly enforced, the curve of point-
wise error control should always be above the curve of average error control.
However, as we discussed in the previous section, the point-wise constraint is
hard to guarantee in practice and thus this property can be violated as it is
the case on PlantCLEF2015. This may suggest that the models on this dataset
are unable to accurately estimate ${\bm{p}}$. As with the previous figure,
these plots also give us insight into the amount of ambiguity in the datasets.
In particular, we can see that it is easy to achieve a very low point-wise
error rate on MNIST while keeping an average set size below two. Therefore
point-wise error control formulation is useful for MNIST if strong guarantee
on the error rate is desired. On the other hand, for ImageNet, enforcing a low
point-wise error rate implies predicting sets of size far larger than $10$ on
average which becomes not informative in most cases. Constraining the average
error rate, however, allows predicting sets far smaller. Thus, for ImageNet,
the average error control formulation might be preferred.

(a) MNIST

(b) ImageNet

(c) PlantCLEF2015

Figure 8:  Comparison of the different frameworks in terms of their average
set size / average error rate curves. In this case, all average control
frameworks share the same optimal curve. The curves of the other frameworks
are necessarily above this curve.

In Figure 8, we compare all the frameworks to each other by plotting their
achieved average error rate against their measured average set size when
varying their constraints. On this plot, the average formulations share the
same curve which is also the optimal curve (since the constraint for one
formulation is the objective of the other). Interestingly, for the different
datasets, the two point-wise control formulations behave differently. On
MNIST, the point-wise error control is very close to the optimal curve, while
on ImageNet, it is above the point-wise size control curve, and on
PlantCLEF2015, the curves of the point-wise control formulation coincide. This
is in line with our previous comment on the usefulness of point-wise error
control formulation for MNIST and its limitations for ImageNet.

(a) Point-wise set size control.

(b) Average set size control.

(c) Point-wise error rate control.

(d) Average error rate control.

Figure 9:  Comparison of the different formulations by looking at the
distribution of the error rates and set sizes per class (on ImageNet). The
plots share the same color scale.

Finally, in Figure 9, we compare the distributions of the point-wise set sizes
and point-wise error rates for the different formulations. These distributions
are measured on ImageNet in a similar fashion than in the previous subsection:
the error rates and set sizes are computed for each class and serve as proxies
for the point-wise error rate and set size. These distributions are plotted
using 2D histograms for various values of the constraints. To compare them,
all the plots share the same color scale. Compared to the other frameworks,
point-wise size control have a particular behavior: it allows a strict control
on the point-wise set size with all the samples having exactly the same set
size. The class error rates are thus always distributed along a line for this
framework. Comparing with average size control, we can see how the relaxation
of the point-wise constraint allows reducing the error rate by predicting
bigger sets for samples of higher error rate and smaller ones for samples with
lower error rate. This remark is true for all formulations (except point-wise
size control). Indeed, when transitioning from a weak to a strong constraint,
we can see that the point-wise error rates and the point-wise set size are
correlated: the higher the error rate, the more labels are predicted, and
vice-versa. To conclude, by focusing on the error control frameworks, we can
notice that the set sizes are more dispersed for point-wise error control than
for average error control at equal constraint values.

These different experiments highlight the similarities and differences between
the described set-valued classification frameworks.

##  6 Other set-valued frameworks

Previous sections were dealing with constrained formulations with the
constrains of similar nature, that is, the constraints were either point-wise
or in expectation. In principle, we can combine both point-wise and expected
constraints in one to retain positive aspects of both as well as modify the
objective function which trades-off the two adaptively. In this section we
present some natural strategies and discuss their features.

###  6.1 Hybrid frameworks

In what follows, we describe possible ways to combine constraints of different
types highlighting the issues that can arise from not a careful choice of the
tuning parameters.

####  6.1.1 Hybrid size control

Minimizing the error given constraint on the expected set size and upper bound
on point-wise: given $k\in\mathbb{N},\bar{k}\in\mathbb{R}$ such that
$0<\bar{k}<k\leq K$,

$\displaystyle\Gamma^{*}_{\bar{k},k}\in\operatorname*{arg\,min}_{\Gamma}$
$\displaystyle\mathbb{P}(Y\notin\Gamma({\bm{X}}))$ (hybrid size control) s.t.
$\displaystyle\mathbb{E}_{{\bm{X}}}|\Gamma({\bm{X}})|\leq\bar{k}$
$\displaystyle\phantom{\mathbb{E}_{{\bm{X}}}}|\Gamma({\bm{X}})|\leq k,\text{
a.s. }\mathbb{P}_{{\bm{X}}}$

######  Lemma 6.

Let Assumption 1 be satisfied. Fix $\bar{k}<k$ and define

$\displaystyle
G_{k}(t)=\sum_{\ell=1}^{k}\mathbb{P}\left(p_{(\ell)}({\bm{X}})\geq
t\right)\enspace.$

Then, an optimal set-valued classifier $\Gamma^{*}_{\bar{k},k}$ can be
obtained, for all ${\bm{x}}\in\mathcal{X}$ as

$\displaystyle\Gamma^{*}_{\bar{k},k}({\bm{x}})=\left\\{\ell\in[L]\,:\,p_{\ell}({\bm{x}})\geq
G_{k}^{-1}(\bar{k})\right\\}\bigcap\operatorname{top}_{{\bm{p}}}({\bm{x}},k)\enspace,$

where $G_{k}^{-1}$ is the generalized inverse of $G_{k}$.

Pros and Cons. Stronger set size control than for other formulations. Higher
error rate than for soft set size control.

####  6.1.2 Hybrid error control

Minimizing the expected set size given constraint on the expected error rate
and upper bound on point-wise: given $0\leq\bar{\epsilon}<\epsilon\leq 1$,

$\displaystyle\Gamma^{*}_{\bar{\epsilon},\epsilon}\in\operatorname*{arg\,min}_{\Gamma}$
$\displaystyle\mathbb{E}_{{\bm{X}}}|\Gamma({\bm{X}})|$ (hybrid error control)
s.t. $\displaystyle\mathbb{P}(Y\notin\Gamma({\bm{X}}))\leq\bar{\epsilon}$
$\displaystyle\mathbb{P}(Y\notin\Gamma({\bm{X}})|{\bm{X}})\leq\epsilon,\text{
a.s. }\mathbb{P}_{{\bm{X}}}$

######  Lemma 7.

Let Assumption 1 be satisfied. For $\bar{\epsilon}<\epsilon$ define

$\displaystyle
H_{\epsilon}(\cdot)=\mathbb{E}_{{\bm{X}}}\left[\sum_{\ell=1}^{k_{\epsilon}({\bm{X}})}p_{(\ell)}({\bm{X}})\mathbb{I}{\left\\{p_{(\ell)}({\bm{X}})\geq\cdot\right\\}}\right]\enspace,$

where $k_{\epsilon}({\bm{X}})$ is defined in Lemma 2. Then if
$H_{\epsilon}(1-\bar{\epsilon})\neq 0$, then

$\displaystyle\Gamma^{*}_{\bar{\epsilon},\epsilon}({\bm{x}})=\left\\{\ell\in[L]\,:\,p_{\ell}({\bm{x}})\geq
H^{-1}_{\epsilon}(1-\bar{\epsilon})\right\\}\enspace,$

where $H^{-1}_{\epsilon}$ is the generalized inverse of $H_{\epsilon}$.

Pros and Cons. Stronger set coverage control than for other formulations.
Higher average set size than for soft set coverage control.

####  6.1.3 Controlling error and size

$\displaystyle\Gamma^{*}_{\bar{\epsilon},k}\in\operatorname*{arg\,min}_{\Gamma}$
$\displaystyle\mathbb{E}_{{\bm{X}}}|\Gamma({\bm{X}})|$ (average error + point-
wise size) s.t.
$\displaystyle\mathbb{P}(Y\notin\Gamma({\bm{X}}))\leq\bar{\epsilon}$
$\displaystyle|\Gamma({\bm{X}})|\leq k,\text{ a.s. }\mathbb{P}_{{\bm{X}}}$

######  Lemma 8.

Define $\epsilon_{k}$ as

$\displaystyle\epsilon_{k}=\mathbb{P}(Y\notin\operatorname{top}_{{\bm{p}}}({\bm{X}},k))\enspace.$

Fix $k\in[L]$, then if $\bar{\epsilon}<\epsilon_{k}$ the feasible set of the
above problem is empty.

###### Proof.

Assume the opposite, that is, there exists $\Gamma$ such that

$\displaystyle\mathbb{P}(Y\notin\Gamma({\bm{X}}))\leq\bar{\epsilon},\quad|\Gamma({\bm{X}})|\leq
k,\text{ a.s. }\mathbb{P}_{{\bm{X}}}\enspace.$

Recall that $\operatorname{top}({\bm{X}},k)$ is an optimal set-valued
classifier with hard size constraints, but

$\displaystyle\mathbb{P}(Y\notin\Gamma({\bm{X}}))\leq\bar{\epsilon}<\epsilon_{k}=\mathbb{P}(Y\notin\operatorname{top}({\bm{X}},k))\enspace,$

which contradicts the optimality of $\operatorname{top}({\bm{X}},k)$. ∎

Pros and Cons. Requires careful parameter tuning.

$\displaystyle\Gamma^{*}_{\bar{k},\epsilon}\in\operatorname*{arg\,min}_{\Gamma}$
$\displaystyle\mathbb{P}(Y\notin\Gamma({\bm{X}}))$ (average size + point-wise
error) s.t. $\displaystyle\mathbb{E}_{{\bm{X}}}|\Gamma({\bm{X}})|\leq\bar{k}$
$\displaystyle\mathbb{P}(Y\notin\Gamma({\bm{X}})\mid{\bm{X}})\leq\epsilon,\text{
a.s. }\mathbb{P}_{{\bm{X}}}$

Pros and Cons. Requires careful parameter tuning.

###  6.2 F-score

While constraint formulations are attractive when an explicit control on the
size or coverage is required, some problems might require to optimize a
certain trade-off of the two. Given a set-valued classifier $\Gamma$ we define
its precision and recall as

$\displaystyle\text{Prec}(\Gamma)=\frac{\mathbb{P}(Y\in\Gamma({\bm{X}}))}{\mathbb{E}|\Gamma({\bm{X}})|},\quad\text{Rec}(\Gamma)=\mathbb{P}(Y\in\Gamma({\bm{X}}))\enspace,$

respectively. Relying on this notions of precision and recall we can define Fβ
score as a weighted harmonic average of the latter

$\displaystyle
F_{\beta}(\Gamma)=\left(\frac{1}{1+\beta^{2}}\text{Prec}^{-1}(\Gamma)+\frac{\beta^{2}}{1+\beta^{2}}\text{Rec}^{-1}(\Gamma)\right)^{-1}=\frac{(1+\beta)\mathbb{P}(Y\in\Gamma({\bm{X}}))}{\beta^{2}+\mathbb{E}|\Gamma({\bm{X}})|}\enspace.$

Consequently, an optimal set-valued classifier in terms of the Fβ score is
defined as

$\displaystyle\Gamma^{*}_{\text{F}}\in\operatorname*{arg\,max}_{\Gamma}\frac{(1+\beta^{2})\mathbb{P}(Y\in\Gamma({\bm{X}}))}{\beta^{2}+\mathbb{E}|\Gamma({\bm{X}})|}\enspace.$
(F-score)

######  Lemma 9.

Fix $\beta>0$, then an optimal set-valued classifier $\Gamma^{*}_{\text{F}}$
can be obtained for all ${\bm{x}}\in\mathcal{X}$ as

$\displaystyle\Gamma^{*}_{\text{F}}({\bm{x}})=\left\\{\ell\in[L]\,:\,p_{\ell}({\bm{x}})\geq\theta^{*}\right\\}\enspace,$

where $\theta^{*}$ is a unique root of

$\displaystyle\theta\mapsto\beta^{2}\theta-\sum_{\ell=1}^{L}\mathbb{E}(p_{\ell}({\bm{X}})-\theta)_{+}\enspace,$

where $(a)_{+}$ denotes the positive part of $a$, i.e., $(a)_{+}=\max(a,0)$.

Pros and Cons. Link with information retrieval metrics. The quality measured
by one score functions. Less interpretable than constrained versions.

##  7 Conclusion

In this manuscript we have provided a review of set-valued classification
literature using a unified framework of minimization under possibly
distribution dependent constraints. We highlighted two main trade-offs that
should be considered – the size and the error. Both quantities can be measured
point-wise or in average leading to various natural formulations of optimal
set-valued classifiers. We emphasized pros and cons of the described
frameworks and provided empirical studies supporting our conclusions
numerically.

##  Appendix A Omitted proofs

In this appendix, we gather the proofs omitted in Section 4.

###### Proof of Lemma 2.

First of all, notice that for all $\Gamma$ it holds that

$\displaystyle\mathbb{P}(Y\notin\Gamma(X)|X)$
$\displaystyle=1-\mathbb{P}(Y\in\Gamma(X)|X=x)$
$\displaystyle=1-\sum_{k=1}^{K}\mathbb{E}\left[\mathbb{I}{\left\\{k\in\Gamma(X)\right\\}}\mathbb{I}{\left\\{Y=k\right\\}}|X\right]$
$\displaystyle=1-\sum_{k=1}^{K}p_{k}(X)\mathbb{I}{\left\\{k\in\Gamma(X)\right\\}}\enspace.$

Thus, the constraint

$\displaystyle\mathbb{P}(Y\notin\Gamma(X)|X)\leq\epsilon,\quad\text{a.s.}\enspace,$

is equivalent to

$\displaystyle\sum_{k=1}^{K}p_{k}(X)\mathbb{I}{\left\\{k\in\Gamma(X)\right\\}}\geq
1-\epsilon\enspace.$

The above implies that $\Gamma^{*}_{\epsilon}$ can be obtained point-wise for
all $x\in\mathcal{X}$ as

$\displaystyle\Gamma^{*}_{\epsilon}(x)\in\operatorname*{arg\,min}_{\gamma\subset[K]}$
$\displaystyle\sum_{k=1}^{K}\mathbb{I}{\left\\{k\in\gamma\right\\}}$ s.t.
$\displaystyle\sum_{k\in\gamma}p_{k}(x)\geq 1-\epsilon\enspace.$

The proof is concluded by solving the above problem. ∎

###### Proof of Lemma 3.

Fix $\lambda>0$, the objective function
$U(\Gamma)=\mathbb{P}(Y\notin\Gamma({\bm{X}}))+\lambda\
{\mathbb{E}_{{\bm{X}}}}|\Gamma({\bm{X}})|$ to be minimized can be written as

$\displaystyle U(\Gamma)$
$\displaystyle=1+\mathbb{E}_{{\bm{X}}}\sum_{\ell=1}^{L}\left[(\lambda-
p_{\ell}({\bm{X}}))\mathbb{I}{\left\\{\ell\in\Gamma({\bm{X}})\right\\}}\right]\enspace.$

Clearly, minimizing the above objective can be performed point-wise, that is,
for all ${\bm{x}}\in\mathcal{X}$ it holds that

$\displaystyle\Gamma^{*}_{\lambda}({\bm{x}})=\left\\{\ell\in[L]\,:\,p_{\ell}({\bm{x}})\geq\lambda\right\\}\enspace.$

∎

###### Proof of Lemma 6.

Fix some $\bar{k}<k$. We are interested in a minimizer of the following
problem

$\displaystyle(*)=\min\left\\{\mathbb{P}(Y\notin\Gamma({\bm{X}}))\,:\,\mathbb{E}_{{\bm{X}}}|\Gamma({\bm{X}})|\leq\bar{k},\,\,|\Gamma({\bm{X}})|\leq
k,\text{ a.s. }\mathbb{P}_{{\bm{X}}}\right\\}\enspace.$

First of all notice that thanks to the weak duality we have

$\displaystyle(*)$ $\displaystyle=\min_{\Gamma}\max_{\lambda\geq
0}\left\\{\mathbb{P}(Y\notin\Gamma({\bm{X}}))+\lambda(\mathbb{E}_{{\bm{X}}}|\Gamma({\bm{X}})|-\bar{k})\,:\,|\Gamma({\bm{X}})|\leq
k,\text{ a.s. }\mathbb{P}_{{\bm{X}}}\right\\}$
$\displaystyle\geq\max_{\lambda\geq
0}\min_{\Gamma}\left\\{\mathbb{P}(Y\notin\Gamma({\bm{X}}))+\lambda(\mathbb{E}_{{\bm{X}}}|\Gamma({\bm{X}})|-\bar{k})\,:\,|\Gamma({\bm{X}})|\leq
k,\text{ a.s. }\mathbb{P}_{{\bm{X}}}\right\\}\enspace.$

The objective function of the maxmin problem can be expressed as

$\displaystyle\mathbb{P}(Y\notin\Gamma({\bm{X}}))+\lambda(\mathbb{E}_{{\bm{X}}}|\Gamma({\bm{X}})|-\bar{k})=1-\lambda\bar{k}+\mathbb{E}_{{\bm{X}}}\left[\sum_{\ell=1}^{L}(\lambda-
p_{\ell}({\bm{X}}))\mathbb{I}{\left\\{\ell\in\Gamma({\bm{X}})\right\\}}\right]\enspace.$

Solving the inner minimization problem for each fixed $\lambda\geq 0$
explicitly we derive $\Gamma_{\lambda}$ defined point-wise as

$\displaystyle\Gamma_{\lambda}({\bm{x}})=\operatorname{top}_{{\bm{p}}}({\bm{x}},k)\cap\Gamma^{*}_{\lambda}({\bm{x}})\enspace,$

where
$\operatorname{top}_{{\bm{p}}}({\bm{x}},k),\Gamma^{*}_{\lambda}({\bm{x}})$ are
the Oracles defined in Lemma 1 and 3 respectively. Substituting into the
objective function we get

$\displaystyle(*)\geq 1-\min_{\lambda\geq
0}\left\\{\lambda\bar{k}+\sum_{\ell=1}^{k}\mathbb{E}_{{\bm{X}}}\left(p_{(\ell)}({\bm{X}})-\lambda\right)_{+}\right\\}\enspace.$

We remark that the minimization problem above is convex. Besides, we observe
that under Assumption 1 it holds that the sub-differential of
$\lambda\to\mathbb{E}_{{\bm{X}}}\left(p_{(\ell)}({\bm{X}})-\lambda\right)_{+}$
is given by

$\displaystyle\partial_{\lambda}\mathbb{E}_{{\bm{X}}}\left(p_{(\ell)}({\bm{X}})-\lambda\right)_{+}=\\{\mathbb{P}(p_{(\ell)}({\bm{X}})\geq\lambda)\\}\enspace.$

Indeed, Assumption 1 guarantees that
$\mathbb{P}(p_{(\ell)}({\bm{X}})=\lambda)=0$ for all $\lambda\geq 0$. Thus,
under Assumption 1 the KKT conditions of the minimization problem above are
given by

$\displaystyle\begin{cases}\sum_{\ell=1}^{k}\mathbb{P}\left(p_{(\ell)}({\bm{X}})\geq\lambda\right)=\bar{k}-\tau\\\
\lambda,\tau\geq 0\\\ \lambda\tau=0\end{cases}\enspace.$

Let $G_{k}(\cdot)$ be defined as

$\displaystyle
G_{k}(\cdot)=\sum_{\ell=1}^{k}\mathbb{P}\left(p_{(\ell)}({\bm{X}})\geq\cdot\right)\enspace,$

and denote by $G_{k}^{-1}(\cdot)$ its generalized inverse. Continuity
assumption 1 guarantees that the function $G_{k}$ is continuous and thus we
can solve the KKT conditions for $\lambda,\tau$ as

$\displaystyle\begin{cases}\lambda=G_{k}^{-1}(\bar{k}-\tau)\enspace,\\\
\tau\geq 0\enspace,\\\ \lambda\tau=0\enspace,\end{cases}$

We claim that if $\bar{k}<k$ then $G^{-1}_{k}(\bar{k})\neq 0$. Assume the
opposite. We clearly have $G_{k}(0)=k$. Moreover, the fact that $\lambda\to
G_{k}(\lambda)$ is continuous non-increasing implies that for all
$\bar{k}\in(0,k)$ we have

$\displaystyle G_{k}(G^{-1}_{k}(\bar{k}))=\bar{k}\enspace.$

By our assumption $G^{-1}_{k}(\bar{k})=0$ and thus

$\displaystyle k=G_{k}(0)=G_{k}(G^{-1}_{k}(\bar{k}))=\bar{k}\enspace.$

The above contradicts the fact that $\bar{k}<k$, hence
$G^{-1}_{k}(\bar{k})\neq 0$.

Since $G^{-1}_{k}(\bar{k})\neq 0$, then, complementary slackness condition
implies that a solution is given by $\tau^{*}=0$ and
$\lambda^{*}=G^{-1}_{k}(\bar{k})$. Also notice that the dual solution
$\Gamma_{\lambda^{*}}({\bm{x}})=\operatorname{top}_{{\bm{p}}}({\bm{x}},k)\cap\Gamma^{*}_{\lambda^{*}}({\bm{x}})$
is feasible for the primal problem. Indeed,

$\displaystyle|\Gamma_{\lambda^{*}}({\bm{x}})|\leq|\operatorname{top}_{{\bm{p}}}({\bm{x}},k)|=k$
$\displaystyle\mathbb{E}|\Gamma_{\lambda^{*}}({\bm{X}})|=\sum_{\ell=1}^{k}\mathbb{P}\left(p_{(\ell)}({\bm{X}})\geq
G_{k}^{-1}(\bar{k})\right)=G_{k}(G^{-1}_{k}(\bar{k}))=\bar{k}\enspace.$

Thus, $\Gamma_{\lambda^{*}}({\bm{x}})$ is a solution of the primal problem. ∎

###### Proof of Lemma 7.

We start similarly to the proof of Lemma 6. Fix $\bar{\epsilon}<\epsilon$, and
set

$\displaystyle(*)=\min_{\Gamma}\left\\{\mathbb{E}_{{\bm{X}}}|\Gamma({\bm{X}})|\,:\,\mathbb{P}(Y\notin\Gamma({\bm{X}}))\leq\bar{\epsilon},\,\,\mathbb{P}(Y\notin\Gamma({\bm{X}})|{\bm{X}})\leq\epsilon,\text{
a.s. }\mathbb{P}_{{\bm{X}}}\right\\}\enspace.$

Simple algebraic manipulations lead to

$\displaystyle(*)$ $\displaystyle=\min_{\Gamma}\max_{\lambda\geq
0}\left\\{\lambda(1-\bar{\epsilon})+\mathbb{E}_{{\bm{X}}}\left[\sum_{\ell=1}^{L}(1-\lambda
p_{\ell}({\bm{X}}))\mathbb{I}{\left\\{\ell\in\Gamma({\bm{X}})\right\\}}\right]\,:\,\mathbb{P}(Y\notin\Gamma({\bm{X}})|{\bm{X}})\leq\epsilon,\text{
a.s. }\mathbb{P}_{{\bm{X}}}\right\\}$ $\displaystyle\geq\max_{\lambda\geq
0}\min_{\Gamma}\left\\{\lambda(1-\bar{\epsilon})+\mathbb{E}_{{\bm{X}}}\left[\sum_{\ell=1}^{L}(1-\lambda
p_{\ell}({\bm{X}}))\mathbb{I}{\left\\{\ell\in\Gamma({\bm{X}})\right\\}}\right]\,:\,\mathbb{P}(Y\notin\Gamma({\bm{X}})\mid{\bm{X}})\leq\epsilon,\text{
a.s. }\mathbb{P}_{{\bm{X}}}\right\\}\enspace.$

For each fixed $\lambda>0$ a solution $\Gamma_{\lambda}$ of the inner
minimization problem is given by

$\displaystyle\Gamma_{\lambda}({\bm{x}})=\Gamma^{*}_{\epsilon}({\bm{x}})\cap\bar{\Gamma}({\bm{x}})\enspace,$

where $\Gamma^{*}_{\epsilon}$ is defined in Lemma 2 and
$\bar{\Gamma}({\bm{x}})$ is defined as

$\displaystyle\bar{\Gamma}({\bm{x}})=\left\\{\ell\in[L]\,:\,p_{\ell}({\bm{x}})\geq
1/\lambda\right\\}\enspace.$

Substituting this into the objective function we get

$\displaystyle(*)$ $\displaystyle\geq\max_{\lambda\geq
0}\left\\{\lambda(1-\bar{\epsilon})-\mathbb{E}_{{\bm{X}}}\left[\sum_{\ell=1}^{k_{\epsilon}({\bm{X}})}\left(\lambda
p_{(\ell)}({\bm{X}})-1\right)_{+}\right]\right\\}$
$\displaystyle=-\min_{\lambda\geq
0}\left\\{\mathbb{E}_{{\bm{X}}}\left[\sum_{\ell=1}^{k_{\epsilon}({\bm{X}})}\left(\lambda
p_{(\ell)}({\bm{X}})-1\right)_{+}\right]-\lambda(1-\bar{\epsilon})\right\\}\enspace.$

Under Assumption 1 the KKT conditions are given by

$\displaystyle\mathbb{E}_{{\bm{X}}}\left[\sum_{\ell=1}^{k_{\epsilon}({\bm{X}})}p_{(\ell)}({\bm{X}})\mathbb{I}{\left\\{p_{(\ell)}({\bm{X}})\geq
1/\lambda\right\\}}\right]=1-\bar{\epsilon}-\tau\enspace,$
$\displaystyle\lambda,\tau\geq 0\enspace,$
$\displaystyle\lambda\tau=0\enspace.$

Introduce

$\displaystyle
H_{\epsilon}(t)=\mathbb{E}_{{\bm{X}}}\left[\sum_{k=1}^{K}\sum_{\ell=1}^{k}p_{(\ell)}({\bm{X}})\mathbb{I}{\left\\{p_{(\ell)}({\bm{X}})\geq
t\right\\}}\mathbb{I}{\left\\{k_{\epsilon}({\bm{X}})=k\right\\}}\right]\enspace.$

Then, Assumption 1 guarantees that

$\displaystyle\lambda=1/H_{\epsilon}^{-1}(1-\bar{\epsilon}-\tau)$
$\displaystyle\lambda,\tau\geq 0\enspace,$
$\displaystyle\lambda\tau=0\enspace.$

Notice that $H_{\epsilon}(0)\geq\mathbb{E}[p_{(1)}({\bm{X}})]\geq 1/K$ and
$H_{\epsilon}(1)=0$. Hence, since $t\to H_{\epsilon}(t)$ is monotone
continuous and $\mathbb{P}(p_{(1)}({\bm{X}})\geq 1-\bar{\epsilon})>0$ it holds
that $H_{\epsilon}^{-1}(1-\bar{\epsilon})>0$. ∎

## References

  * Barber et al. (2019) [author] Barber, Rina FoygelR. F., Candes, Emmanuel JE. J., Ramdas, AadityaA. and Tibshirani, Ryan JR. J. (2019). The limits of distribution-free conditional predictive inference. arXiv preprint arXiv:1903.04684.
  * Bartlett, Jordan and McAuliffe (2006) [author] Bartlett, P.P., Jordan, M.M. and McAuliffe, J.J. (2006). Convexity, classification, and risk bounds. Journal of the American Statistical Association 101 138–156.
  * Berrada, Zisserman and Kumar (2018) [author] Berrada, LeonardL., Zisserman, AndrewA. and Kumar, M PawanM. P. (2018). Smooth loss functions for deep top-k classification. ICLR.
  * Bhatia et al. (2016) [author] Bhatia, K.K., Dahiya, K.K., Jain, H.H., Mittal, A.A., Prabhu, Y.Y. and Varma, M.M. (2016). The extreme classification repository: Multi-label datasets and code.
  * Cai, Low and Ma (2014) [author] Cai, T. TonyT. T., Low, MarkM. and Ma, ZongmingZ. (2014). Adaptive Confidence Bands for Nonparametric Regression Functions. Journal of the American Statistical Association 109 1054-1070.
  * Champ et al. (2015) [author] Champ, JulienJ., Lorieul, TitouanT., Servajean, MaximilienM. and Joly, AlexisA. (2015). A comparative study of fine-grained classification methods in the context of the LifeCLEF plant identification challenge 2015. In CLEF: Conference and Labs of the Evaluation Forum 1391\.
  * Champ et al. (2016) [author] Champ, JulienJ., Lorieul, TitouanT., Bonnet, PierreP., Maghnaoui, NajateN., Sereno, ChristopheC., Dessup, ThierryT., Boursiquot, Jean-MichelJ.-M., Audeguin, LaurentL., Lacombe, ThierryT. and Joly, AlexisA. (2016). Categorizing plant images at the variety level: Did you say fine-grained? Pattern Recognition Letters 81 71–79.
  * Chow (1957) [author] Chow, C. -K. C. (1957). An optimum character recognition system using decision functions. IRE Transactions on Electronic Computers 4 247–254.
  * Chow (1970) [author] Chow, C.C. (1970). On optimum error and reject trade-off. IEEE Trans. Inform. Theory 16 41–46.
  * Chzhen, Denis and Hebiri (2019) [author] Chzhen, EvgeniiE., Denis, ChristopheC. and Hebiri, MohamedM. (2019). Minimax semi-supervised confidence sets for multi-class classification. arXiv preprint arXiv:1904.12527.
  * Chzhen, Denis and Hebiri (2021) [author] Chzhen, EvgeniiE., Denis, ChristopheC. and Hebiri, MohamedM. (2021). Minimax semi-supervised set-valued approach to multi-class classification. Bernoulli.
  * Ciregan, Meier and Schmidhuber (2012) [author] Ciregan, DanD., Meier, UeliU. and Schmidhuber, JürgenJ. (2012). Multi-column deep neural networks for image classification. In 2012 IEEE conference on computer vision and pattern recognition 3642–3649. IEEE.
  * Dembczyński et al. (2012) [author] Dembczyński, KrzysztofK., Waegeman, WillemW., Cheng, WeiweiW. and Hüllermeier, EykeE. (2012). On label dependence and loss minimization in multi-label classification. Machine Learning 88 5–45.
  * Denis and Hebiri (2017) [author] Denis, ChristopheC. and Hebiri, MohamedM. (2017). Confidence sets with expected sizes for multiclass classification. Journal of Machine Learning Research 18 1-28.
  * Denis and Hebiri (2020) [author] Denis, ChristopheC. and Hebiri, MohamedM. (2020). Consistency of plug-in confidence sets for classification in semi-supervised learning. Journal of Nonparametric Statistics 32 42–72.
  * Elkan (2001) [author] Elkan, CharlesC. (2001). The foundations of cost-sensitive learning. In Proceedings of the 17th international joint conference on Artificial intelligence-Volume 2 973–978.
  * Embrechts and Hofert (2013) [author] Embrechts, PaulP. and Hofert, MariusM. (2013). A note on generalized inverses. Mathematical Methods of Operations Research 77 423–432.
  * Göeau, Joly and Bonnet (2015a) [author] Göeau, HervéH., Joly, AlexisA. and Bonnet, PierreP. (2015a). LifeCLEF plant identification task 2015. CLEF working notes 2015\.
  * Göeau, Joly and Bonnet (2015b) [author] Göeau, HervéH., Joly, AlexisA. and Bonnet, PierreP. (2015b). LifeCLEF plant identification task 2015. CLEF working notes 2015\.
  * Grycko (1993) [author] Grycko, EugenE. (1993). Classification with Set-Valued Decision Functions. In Information and Classification (OttoO. Opitz, BertholdB. Lausen and RüdigerR. Klar, eds.) 218–224. Springer Berlin Heidelberg, Berlin, Heidelberg.
  * Guo et al. (2017) [author] Guo, ChuanC., Pleiss, GeoffG., Sun, YuY. and Weinberger, Kilian QK. Q. (2017). On Calibration of Modern Neural Networks. In International Conference on Machine Learning 1321–1330.
  * Gyöfi and Walk (2020) [author] Gyöfi, L.L. and Walk, H.H. (2020). Nearest neighbor based conformal prediction. Submitted.
  * Ha (1996) [author] Ha, Thien MT. M. (1996). An optimum class-selective rejection rule for pattern recognition. In Proceedings of 13th International Conference on Pattern Recognition 2 75–80. IEEE.
  * Ha (1997a) [author] Ha, Thien MT. M. (1997a). The optimum class-selective rejection rule. PAMI.
  * Ha (1997b) [author] Ha, Thien MT. M. (1997b). Optimum tradeoff between class-selective rejection error and average number of classes. Engineering Applications of Artificial Intelligence 10 525–529.
  * Hastie and Fithian (2013) [author] Hastie, TrevorT. and Fithian, WillW. (2013). Inference from presence-only data; the ongoing controversy. Ecography 36 864–867.
  * He et al. (2015) [author] He, KaimingK., Zhang, XiangyuX., Ren, ShaoqingS. and Sun, JianJ. (2015). Deep Residual Learning for Image Recognition. CoRR abs/1512.03385.
  * Herbei and Wegkamp (2006) [author] Herbei, R.R. and Wegkamp, M.M. (2006). Classification with reject option. Canad. J. Statist. 34 709–721.
  * Kourou et al. (2015) [author] Kourou, KonstantinaK., Exarchos, Themis PT. P., Exarchos, Konstantinos PK. P., Karamouzis, Michalis VM. V. and Fotiadis, Dimitrios ID. I. (2015). Machine learning applications in cancer prognosis and prediction. Computational and structural biotechnology journal 13 8–17.
  * Lambin et al. (2017) [author] Lambin, PhilippeP., Zindler, JaapJ., Vanneste, Ben GLB. G., Van De Voorde, LienL., Eekers, DanielleD., Compter, IngeI., Panth, Kranthi MarellaK. M., Peerlings, JurgenJ., Larue, Ruben THMR. T., Deist, Timo MT. M. et al. (2017). Decision support systems for personalized and participative radiation oncology. Advanced drug delivery reviews 109 131–153.
  * Lapin, Hein and Schiele (2015) [author] Lapin, MaksimM., Hein, MatthiasM. and Schiele, BerntB. (2015). Top-k multiclass SVM. In Advances in Neural Information Processing Systems 325–333.
  * Lapin, Hein and Schiele (2016) [author] Lapin, MaksimM., Hein, MatthiasM. and Schiele, BerntB. (2016). Loss functions for top-k error: Analysis and insights. In CVPR.
  * Le Capitaine (2014) [author] Le Capitaine, HoelH. (2014). A unified view of class-selection with probabilistic classifiers. Pattern recognition 47 843–853.
  * LeCun et al. (1998) [author] LeCun, YannY., Bottou, LéonL., Bengio, YoshuaY. and Haffner, PatrickP. (1998). Gradient-based learning applied to document recognition. Proceedings of the IEEE 86 2278–2324.
  * Lei (2014) [author] Lei, JingJ. (2014). Classification with Confidence. Biometrika.
  * Lei and Wasserman (2014) [author] Lei, JingJ. and Wasserman, LarryL. (2014). Distribution-free prediction bands for non-parametric regression. Journal of the Royal Statistical Society Series B 76 71-96.
  * Lei et al. (2018) [author] Lei, J.J., G’Sell, M.M., Rinaldo, A.A., Tibshirani, R.R. and Wasserman, L.L. (2018). Distribution-free predictive inference for regression. J. Amer. Statist. Assoc. 113 1094–1111.
  * Ling, Huang and Zhang (2003) [author] Ling, Charles XC. X., Huang, JinJ. and Zhang, HarryH. (2003). AUC: a better measure than accuracy in comparing learning algorithms. In Conference of the canadian society for computational studies of intelligence 329–341. Springer.
  * Lorieul, Joly and Shasha (2020) [author] Lorieul, TitouanT., Joly, AlexisA. and Shasha, DennisD. (2020). Average-K classification: when and how to predict adaptive confidence sets rather than top-K.
  * Mac Aodha, Cole and Perona (2019) [author] Mac Aodha, OisinO., Cole, ElijahE. and Perona, PietroP. (2019). Presence-only geographical priors for fine-grained image classification. In Proceedings of the IEEE International Conference on Computer Vision 9596–9606.
  * Ni et al. (2019) [author] Ni, C.C., Charoenphakdee, N.N., Honda, J.J. and Sugiyama, M.M. (2019). On the Calibration of Multiclass Classification with Rejection. In Advances in Neural Information Processing Systems 32 2586–2596.
  * Ramaswamy et al. (2018) [author] Ramaswamy, Harish GH. G., Tewari, AmbujA., Agarwal, ShivaniS. et al. (2018). Consistent algorithms for multiclass classification with an abstain option. Electronic Journal of Statistics 12 530–554.
  * Romano, Sesia and Candès (2020) [author] Romano, Y.Y., Sesia, MM. and Candès, E. JE. J. (2020). Classification with Valid and Adaptive Coverage. arXiv preprint arXiv:2006.02544.
  * Royle et al. (2012) [author] Royle, J AndrewJ. A., Chandler, Richard BR. B., Yackulic, CharlesC. and Nichols, James DJ. D. (2012). Likelihood analysis of species occurrence probability from presence-only data for modelling species distributions. Methods in Ecology and Evolution 3 545–554.
  * Russakovsky et al. (2015a) [author] Russakovsky, OlgaO., Deng, JiaJ., Su, HaoH., Krause, JonathanJ., Satheesh, SanjeevS., Ma, SeanS., Huang, ZhihengZ., Karpathy, AndrejA., Khosla, AdityaA., Bernstein, MichaelM. et al. (2015a). Imagenet large scale visual recognition challenge. International journal of computer vision 115 211–252.
  * Russakovsky et al. (2015b) [author] Russakovsky, OlgaO., Deng, JiaJ., Su, HaoH., Krause, JonathanJ., Satheesh, SanjeevS., Ma, SeanS., Huang, ZhihengZ., Karpathy, AndrejA., Khosla, AdityaA., Bernstein, MichaelM. et al. (2015b). ImageNet large scale visual recognition challenge. International journal of computer vision 115 211–252.
  * Sadinle, Lei and Wasserman (2019a) [author] Sadinle, MauricioM., Lei, JingJ. and Wasserman, LarryL. (2019a). Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association 114 223–234.
  * Sadinle, Lei and Wasserman (2019b) [author] Sadinle, MauricioM., Lei, JingJ. and Wasserman, LarryL. (2019b). Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association 114 223–234.
  * Turney (1994) [author] Turney, Peter DP. D. (1994). Cost-sensitive classification: Empirical evaluation of a hybrid genetic decision tree induction algorithm. Journal of artificial intelligence research 2 369–409.
  * Vapnik (1998) [author] Vapnik, V.V. (1998). Statistical learning theory. Wiley.
  * Vovk (2013) [author] Vovk, VladimirV. (2013). Conditional validity of inductive conformal predictors. Mach. Learn. 92 349–376.
  * Vovk, Gammerman and Shafer (2005a) [author] Vovk, VladimirV., Gammerman, AlexA. and Shafer, GlennG. (2005a). Algorithmic learning in a random world. Springer Science & Business Media.
  * Vovk, Gammerman and Shafer (2005b) [author] Vovk, VladimirV., Gammerman, AlexA. and Shafer, GlennG. (2005b). Algorithmic learning in a random world. Springer Science & Business Media.
  * Vovk et al. (2017) [author] Vovk, VladimirV., Nouretdinov, IliaI., Fedorova, ValentinaV., Petej, IvanI. and Gammerman, AlexA. (2017). Criteria of efficiency for set-valued classification. Annals of Mathematics and Artificial Intelligence 81 21-47.
  * Wu, Jia and Chen (2007) [author] Wu, Q.Q., Jia, C.C. and Chen, W.W. (2007). A Novel Classification-Rejection Sphere SVMs for Multi-class Classification Problems. In Third International Conference on Natural Computation (ICNC 2007) 1 34-38.
  * Xie et al. (2017) [author] Xie, SainingS., Girshick, RossR., Dollár, PiotrP., Tu, ZhuowenZ. and He, KaimingK. (2017). Aggregated residual transformations for deep neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition 1492–1500.
  * Yang and Koyejo (2020) [author] Yang, ForestF. and Koyejo, SanmiS. (2020). On the consistency of top-k surrogate losses. In International Conference on Machine Learning.
  * Zhang (2004) [author] Zhang, TongT. (2004). Statistical behavior and consistency of classification methods based on convex risk minimization. Annals of Statistics 56–85.
  * Zhang, Wang and Qiao (2018) [author] Zhang, ChongC., Wang, WenboW. and Qiao, XingyeX. (2018). On reject and refine options in multicategory classification. J. Amer. Statist. Assoc. 113 730–745.
  * Zhang and Zhou (2013) [author] Zhang, Min-LingM.-L. and Zhou, Zhi-HuaZ.-H. (2013). A review on multi-label learning algorithms. IEEE transactions on knowledge and data engineering 26 1819–1837.
  * Zubiaga (2012) [author] Zubiaga, ArkaitzA. (2012). Enhancing navigation on wikipedia with social tags. arXiv preprint arXiv:1202.5469.