# Hierarchical Selective Classification

Shani Goren*
Technion
<EMAIL_ADDRESS>
&Ido Galil*
Technion, Deci.AI
<EMAIL_ADDRESS>
Ran El-Yaniv
Technion, Deci.AI
<EMAIL_ADDRESS>

###### Abstract

††footnotetext: *The first two authors have equal contribution.

Deploying deep neural networks for risk-sensitive tasks necessitates an
uncertainty estimation mechanism. This paper introduces _hierarchical
selective classification_ , extending selective classification to a
hierarchical setting. Our approach leverages the inherent structure of class
relationships, enabling models to reduce the specificity of their predictions
when faced with uncertainty. In this paper, we first formalize hierarchical
risk and coverage, and introduce hierarchical risk-coverage curves. Next, we
develop algorithms for hierarchical selective classification (which we refer
to as “inference rules”), and propose an efficient algorithm that guarantees a
target accuracy constraint with high probability. Lastly, we conduct extensive
empirical studies on over a thousand ImageNet classifiers, revealing that
training regimes such as CLIP, pretraining on ImageNet21k and knowledge
distillation boost hierarchical selective performance.

##  1 Introduction

Deep neural networks (DNNs) have achieved incredible success across various
domains, including computer vision and natural language processing. To ensure
the reliability of models intended for real-world applications we must
incorporate an uncertainty estimation mechanism, such as _selective
classification_ [17], which allows a model to abstain from classifying samples
when it is uncertain about their predictions. Standard selective
classification, however, has a shortcoming: for any given sample, it is
limited to either generating a prediction or rejecting it, thereby ignoring
potentially useful information about the sample, in case of rejection.
To illustrate the potential consequences of this limitation, consider a model
trained for classifying different types of brain tumors from MRI scans,
including both benign and malignant tumors. If a malignant tumor is identified
with high confidence, immediate action is needed. For a particular
hypothetical scan, suppose the model struggles to distinguish between 3
subtypes of malignant tumors, assigning a confidence score of 0.33 to each of
them (assuming those estimates are well-calibrated and sum to 1). In the
traditional selective classification framework, if the preset confidence
threshold is higher than 0.33, the model will reject the sample, failing to
provide valuable information to alert healthcare professionals about the
patient’s condition, even though the model has enough information to conclude
that the tumor is malignant with high certainty. This could potentially result
in delayed diagnosis and treatment, posing a significant risk to the patient’s
life. However, a hierarchically-aware selective model with an identical
confidence threshold would classify the tumor as malignant with 99%
confidence. Although this prediction is less specific, it remains highly
valuable as it can promptly notify healthcare professionals, leading to early
diagnosis and life-saving treatment for the patient.
This motivates us to propose _hierarchical selective classification_ (HSC), an
extension of selective classification to a setting where the classes are
organized in a hierarchical structure. Such hierarchies are typically
represented by a tree-like structure, where each node represents a class, and
the edges reflect a semantic relationship between the classes, most commonly
an ’is-a’ relationship. Datasets with an existing hierarchy are fairly common,
for instance, the ImageNet dataset [10], which is widely used in computer
vision tasks, is organized according to the WordNet hierarchy [29]. A
visualization of a small portion of the ImageNet hierarchy is shown in Figure
1.

Figure 1: A detailed example of HSC for the output of ViT-L/16-384 on a
specific sample. The base classifier outputs leaf softmax scores, with
internal node scores being the sum of their descendant leaves’ scores,
displayed in parentheses next to each node. The base classifier incorrectly
classifies the image as a ’Golden Retriever’ with low confidence. A selective
classifier can either make the same incorrect leaf prediction if the
confidence threshold is below 0.29, or reject the sample. A hierarchical
selective classifier with the _Climbing_ inference rule (see Section 3) climbs
the path from the predicted leaf to the root until the confidence threshold
$\theta$ is met. Setting $\theta$ above 0.29 yields a hierarchically correct
prediction, with smaller $\theta$ values increasing the coverage. An Algorithm
for determining the optimal threshold is introduced in Section 4.

The key contributions of this paper are as follows:
(1) We extend selective classification to a hierarchical setting. We define
_hierarchical selective risk_ and _hierarchical coverage_ , leading us to
introduce _hierarchical risk-coverage curves_.
(2) We introduce _hierarchical selective inference rules_ , i.e., algorithms
used to hierarchically reduce the information in predictions based on their
uncertainty estimates, improving hierarchical selective performance compared
to existing baselines. We also identify and define useful properties of
inference rules.
(3) We propose a novel algorithm to find the optimal confidence threshold
compatible with any base classifier without requiring any fine-tuning, that
achieves a user-defined target accuracy with high probability, which can also
be set by the user, greatly improving over the existing baseline.
(4) We conduct a comprehensive empirical study evaluating HSC on more than
1,000 ImageNet classifiers. We present numerous previously unknown
observations, most notably that training approaches such as pretraining on
larger datasets, contrastive language-image pretraining (CLIP) [31], and
knowledge distillation significantly boosts selective hierarchical
performance.

##  2 Problem Setup

Selective Classification Let $\mathcal{X}$ be the input space, and
$\mathcal{Y}$ be the label space. Samples are drawn from an unknown joint
distribution $P(\mathcal{X}\times\mathcal{Y})$ over
$\mathcal{X}\times\mathcal{Y}$. A classifier $f$ is a prediction function
$f:\mathcal{X}\rightarrow\mathcal{Y}$, and $\hat{y}=f(x)$ is the model’s
prediction for $x$. The _true risk_ of a classifier $f$ w.r.t. $P$ is defined
as: $R(f|P)=\mathbb{E}_{P}[\ell(f(X),Y)]$, where
$\ell:\mathcal{Y}\times\mathcal{Y}\rightarrow\mathbb{R}^{+}$ is a given loss
function, for instance, the 0/1 loss. Given a set of labeled samples
$S_{m}=\\{(x_{i},y_{i})\\}_{i=1}^{m}$, the _empirical risk_ of $f$ is:
$\hat{R}(f|S_{m})=\frac{1}{m}\sum_{i=1}^{m}\ell(f(x_{i}),y_{i}).$ Following
the notation of [19], we use a _confidence score_ function
$\kappa(x,\hat{y}|f)$ to quantify prediction confidence. We require $\kappa$
to induce a partial order over instances in $\mathcal{X}$. In this work, we
focus on the most common and well-known $\kappa$ function, _softmax response_
[9, 35]. For a classifier $f$ with softmax as its last layer:
$\kappa(x,\hat{y}|f)=f_{\hat{y}}(x)$. Softmax response has been shown to be a
reliable confidence score in the context of selective classification [16, 17]
as well as in hierarchical classification [40], consistently achieving good
performance.
A _selective model_ [8, 12] is a pair $(f,g)$ where $f$ is a classifier and
$g:\mathcal{X}\rightarrow\\{0,1\\}$ is a _selection function_ , which serves
as a binary selector for $f$. The selective model abstains from predicting
instance $x$ if and only if $g(x)=0$. The selection function $g$ can be
defined by a confidence threshold $\theta$:
$g_{\theta}(x|\kappa,f)$$=\mathds{1}[\kappa(x,\hat{y}|f)>\theta].$ The
performance of a selective model is measured using selective risk and
coverage. _Coverage_ is defined as the probability mass of the non-rejected
instances in $\mathcal{X}$: $\phi(f,g)=\mathds{E}_{P}[g(X)].$ The _selective
risk_ of $(f,g)$ is:
$R(f,g)=\frac{\mathbb{E}_{P}[\ell(f(X),Y)g(X)]}{\phi(f,g)}.$
Risk and coverage can be evaluated over a labeled set $S_{m}$, with the
_empirical coverage_ defined as:
$\hat{\phi}(f,g|S_{m})=\frac{1}{m}\sum_{i=1}^{m}g(x_{i})$, and the _empirical
selective risk_ :
$\hat{R}(f,g|S_{m})=\frac{\frac{1}{m}\sum_{i=1}^{m}\ell(f(x_{i}),y_{i})g(x_{i})}{\hat{\phi}(f,g|S_{m})}.$
The performance profile of a selective classifier can be visualized by a
_risk-coverage curve_ (RC curve) [12], a curve showing the risk as a function
of coverage, measured on a set of samples. The area under the RC curve, namely
_AURC_ , was defined by [19] for quantifying selective performance via a
single scalar. See Figure 2(a) for an example of an RC Curve.

Hierarchical Classification Following the notations of [11] and [40], a
hierarchy $H=(V,E)$ is defined by a tree, with nodes $V$ and edges $E$, the
root of the tree is denoted $r\in V$. Each node $v\in V$ represents a semantic
class: the leaf nodes $\mathcal{L}\subseteq V$ are mutually exclusive ground-
truth classes, and the internal nodes are unions of leaf nodes determined by
the hierarchy. The root represents the semantic class containing all other
objects. A sample $x$ that belongs to class $y$ also belongs to the ancestors
of $y$. Each node has exactly one parent and one unique path to it from the
root node. The set of leaf descendants of node $v$ is denoted by
$\mathcal{L}(v)$, and the set of ancestors of node $v$, including $v$ itself,
is denoted by $\mathcal{A}(v)$. A hierarchical classifier
$f:\mathcal{X}\rightarrow V$ labels a sample $x\in\mathcal{X}$ as a node $v\in
V$, at any level of the hierarchy, as opposed to a flat classifier, that only
predicts leaves.
Given the hierarchy, it is correct to label an image as either its ground
truth leaf node or any of its ancestors. For instance, a Labrador is also a
dog, a canine, a mammal, and an animal. While any of these labels is
technically correct for classifying a Labrador, the most specific label is
clearly preferable as it contains the most information. Thus, it is crucial to
observe that the definition of hierarchical correctness is incomplete without
considering the amount of information held by the predictions. The correctness
of a hierarchical classifier $f$ on a set of samples $S_{m}$ is defined by:
$\frac{1}{m}\sum_{i=1}^{m}\mathds{1}[{f(x_{i})\in\mathcal{A}(y_{i})}]$. Note
that when $H$ is flat and does not contain internal nodes, the hierarchical
accuracy reduces to the accuracy of a standard leaf classifier. In the context
of classification tasks, the goal is usually to maximize accuracy. However, a
trivial way to achieve 100% hierarchical accuracy would be to simply classify
all samples as the root node. For this reason, a mechanism that penalizes the
model for predicting less specific nodes must be present as well. In section 3
we define _coverage_ , which quantifies prediction specificity. We aim for a
trade-off between the accuracy and information gained by the prediction, which
can be controlled according to a user’s requirements. A review of related work
involving hierarchical classification can be found in section 6.

Hierarchical Selective Classification Selective classification offers a binary
choice: either to predict or completely reject a sample. We propose
hierarchical selective classification (HSC), a hierarchical extension of
selective classification, which allows the model to retreat to less specific
nodes in the hierarchy in case of uncertainty. Instead of rejecting the whole
prediction, the model can now partially reject a sample, and the degree of the
rejection is determined by the model’s confidence. For example, if the model
is uncertain about the specific dog breed of an image of a Labrador but is
confident enough to determine that it is a dog, the safest choice by a classic
selective framework would be to reject it. In our setting, however, the model
can still provide useful information that the object in the image is a dog
(see Figure 1).
A _hierarchical selective classifier_ $f^{H}\triangleq(f,g_{\theta}^{H})$
consists of $f$, a base classifier, and $g_{\theta}^{H}:\mathcal{X}\rightarrow
V$, a hierarchical selection function with a confidence threshold $\theta$.
$g_{\theta}^{H}$ determines the degree of partial rejection by selecting a
node in the hierarchy with confidence higher than $\theta$. Defining
$g_{\theta}^{H}$ now becomes non-trivial. For instance, $g_{\theta}^{H}$ can
traverse the hierarchy tree, directly choose a single node, or follow any
other algorithm, as long as the predicted node has sufficient confidence. For
this reason, we refer to $g_{\theta}^{H}$ as a _hierarchical inference rule_.
In section 3 we introduce several inference rules and discuss their
properties.
Hierarchical selective classifiers differ from the previously discussed
hierarchical classifiers by requiring a hierarchical selection function. In
contrast to non-selective hierarchical classifiers, which may produce
predictions at internal nodes without a selection function, a hierarchical
selective classifier can handle uncertainty by gradually trading off risk and
coverage, controlled by $g_{\theta}^{H}$. This distinction is crucial because
hierarchical selective classifiers provide control over the full trade-off
between risk and coverage, which is not always attainable with non-selective
hierarchical classifiers.
To our knowledge, controlling the trade-off between accuracy and specificity
was only previously explored by [11]. They proposed the _Dual Accuracy Reward
Trade-off Search_ (DARTS) algorithm, which attempted to obtain the most
specific classifier for a user-specified accuracy constraint. They used
information gain and hierarchical accuracy as two competing factors,
integrating them into a generalized Lagrange function. Our approach differs
from theirs in that we guarantee control over the full trade-off, while some
coverages cannot be achieved by DARTS.
As mentioned in section 2, it is considered correct to label an image as
either its ground truth leaf node or any of its ancestors. Thus, we employ a
natural extension of the 0/1 loss to define the true risk of a hierarchical
classifier $f^{H}$ with regard to $P$:
$R^{H}(f^{H}|P)=\mathds{E}_{P}[f^{H}(X)\notin\mathcal{A}(Y)],$ and the
empirical risk over a labeled set of samples $S_{m}$:
$\hat{R^{H}}(f^{H}|S_{m})=\frac{1}{m}\sum_{i=1}^{m}\mathds{1}[f^{H}(x_{i})\notin\mathcal{A}(y_{i})].$
To ensure that specific labels are preferred, it is necessary to consider the
specificity of predictions. _Hierarchical selective coverage_ , which we
propose as a hierarchical extension of selective coverage, measures the amount
of information present in the model’s predictions. A natural quantity for that
is entropy, which measures the uncertainty associated with the classes beneath
a given node. Assuming a uniform prior on the leaf nodes, the entropy of a
node $v\in V$ is
$H(v)=-\sum_{{v^{\prime}\in\mathcal{L}(v)}}\frac{1}{|\mathcal{L}(v)|}\log(\frac{1}{|\mathcal{L}(v)|})=\log(|\mathcal{L}(v)|).$
At the root, the entropy reaches its maximum value,
$H(r)=\log(|\mathcal{L}|)$, while at the leaves the entropy is minimized, with
$H(y)=0$ for any leaf node $y\in\mathcal{L}$. This allows us to define
coverage for a single node $v$, regardless of $g_{\theta}^{H}$. We define
hierarchical coverage (from now on referred to as coverage) as the entropy of
$v$ relative to the entropy of the root node:
${\phi}^{H}(v)=1-\frac{H(v)}{H(r)}.$ The root node has zero coverage, as it
does not contain any information. The coverage gradually increases until it
reaches 1 at the leaves. We can also define true coverage for a selective
model: $\phi^{H}(f^{H})=\mathds{E}_{P}[\phi(f^{H}(X)].$ The empirical coverage
of a classifier over a labeled set of samples $S_{m}$ is defined as the mean
coverage over its predictions:
$\hat{\phi^{H}}(f^{H}|S_{m})=\frac{1}{m}\sum_{i=1}^{m}\phi(f^{H}(x_{i})).$ For
a hierarchy comprised of leaves and a root node, hierarchical coverage reduces
to selective coverage, where classifying a sample as the root corresponds with
rejection.
The hierarchical selective performance of a model can be visualized with a
hierarchical RC curve. The area under the hierarchical RC curve, which we term
_hAURC_ , extends the non-hierarchical AURC, by using the hierarchical
extensions of selective risk and coverage. For examples of hierarchical RC
curves see Figure 2(a) and Figure 2(b).

##  3 Hierarchical Selective Inference Rules

Algorithm 1 Climbing Inference Rule

Classifier $f$, class hierarchy $H=(V,E)$, sample $x_{i}\in\mathcal{X}$,
confidence threshold $\theta$.

Predicted node $\hat{v}$.

Perform temperature scaling [21]

Obtain $f_{v}(x_{i})$ $\forall v\in V$

$\hat{v}\leftarrow\underset{y\in L}{\arg\max}f_{y}(x_{i})$

while $f_{\hat{v}}(x_{i})<\theta$ do

$\hat{v}\leftarrow\text{parent}(\hat{v})$

end while

To define a hierarchical selective model $f^{H}=(f,g_{\theta}^{H})$ given a
base classifier $f$, an explicit definition of $g_{\theta}^{H}$ is required.
$g_{\theta}^{H}$ determines the internal node in the hierarchy $f^{H}$
retreats to when the leaf prediction of $f$ is uncertain. $g_{\theta}^{H}$
requires obtaining confidence for internal nodes in the hierarchy. Since most
modern classification models only assign probabilities to leaf nodes, we
follow [11] by setting the probability of an internal node to be the sum of
its leaf descendant probabilities:
$f^{H}_{v}(x)=\sum_{y\in\mathcal{L}(v)}f_{y}(x).$ Unlike other works that
assign the sum of leaf descendant probabilities to internal nodes, our
algorithm first calibrate the leaf probabilities through _temperature
scaling_. Since the probabilities of internal nodes heavily rely on the leaf
probabilities supplied by $f$, calibration is beneficial for obtaining more
reliable leaf probabilities, and since the internal nodes probabilities are
sums of leaf probabilities, this cumulative effect is even more pronounced.
Further, [16] found that applying temperature scaling also improves ranking
and selective performance, which is beneficial to our objective. In this
section, we introduce several inference rules, along with useful theoretical
properties. We propose the _Climbing_ inference rule (Algorithm 1), which
starts at the most likely leaf and climbs the path to the root, until reaching
an ancestor with confidence above the threshold. A visualization of the
Climbing inference rule is shown in Figure 1.
We compare our proposed inference rules to the following baselines: The first
is the _selective inference rule_ , which predicts ’root’ for every uncertain
sample (this approach is identical to standard “hierarchically-ignorant”
selective classification). The second hierarchical baseline, proposed by [40],
selects the node with the highest coverage among those with confidence above
the threshold. We refer to this rule as “ _Max-Coverage_ ” (MC), and its
algorithm is detailed in Appendix A.

Certain tasks might require guarantees on inference rules. For example, it can
be useful to ensure that an inference rule does not turn a correct prediction
into an incorrect one. Therefore, for an inference rule $g_{\theta}^{H}$ we
define:
1\. Monotonicity in Correctness: For any $\theta_{1}\leq\theta_{2}$, base
classifier $f$ and labeled sample $(x,y)$:
$(f,g_{\theta_{1}}^{H})(x)\in\mathcal{A}(y)\Rightarrow(f,g_{\theta_{2}}^{H})(x)\in\mathcal{A}(y)$.
Increasing the threshold will never cause a correct prediction to become
incorrect.
2\. Monotonicity in Coverage: For any $\theta_{1}\leq\theta_{2}$, base
classifier $f$ and labeled sample $(x,y)$:
${\phi^{H}}[(f,g_{\theta_{1}}^{H})(x)]\geq{\phi^{H}}[(f,g_{\theta_{2}}^{H})(x)]$.
Increasing the threshold will never increase the coverage.

The Climbing inference rule outlined in Algorithm 1 satisfies both
monotonicity properties. MC satisfies monotonicity in coverage, but not in
correctness. An additional algorithm that does not satisfy neither of the
properties is discussed in Appendix B.

(a)

(b)

Figure 2: (2(a)) hierarchical RC curve of a ViT-L/16-384 model trained on
ImageNet1k, evaluated with the 0/1 loss as the risk and softmax response as
its confidence function $\kappa$. The purple shaded area represents the area
under the RC curve (hAURC). Full coverage occurs when the model accepts all
leaf predictions, for which the risk is 0.13. Increasing the confidence
threshold leads to the rejection of more samples. For example, when the
threshold is 0.77 the the risk is 0.04, with coverage 0.8.
(2(b)) hierarchical RC curves of different inference rules with EVA-L/14-196
[13] as the base classifier. When the coverage is 1.0, all inference rules
predict leaves. Each inference rule achieves a different trade-off, resulting
in distinct curves. This example represents the prevalent case, where the
“hierarchically-ignorant” selective inference rule performs the worst and
Climbing outperforms MC.

When comparing hierarchical selective models, we find it useful to measure the
performance improvement gained by using hierarchical selective inference. We
propose a new metric: _hierarchical gain_ , defined as the improvement in
hAURC between $(f,g_{\theta})$, a “hierarchically-ignorant” selective model,
and $(f,g_{\theta}^{\textbf{H}})$, the same base classifier with a
hierarchical inference rule. This metric might also point to which models have
a better hierarchical understanding, as it directly measures the improvement
gained by allowing models to leverage hierarchical knowledge. Note that if the
selective inference rule is better than the hierarchical inference rule being
assessed, the hierarchical gain will be negative. An illustrative individual
example of RC curves comparison for one model is shown in Figure 2(b).

##  4 Optimal Selective Threshold Algorithm

In Section 3, we defined several inference rules that, given a confidence
threshold, return a predicted node in the hierarchy. In this section, we
propose an algorithm that efficiently finds the optimal threshold for a user-
defined target accuracy and confidence level. The algorithm, outlined in
Algorithm 2, receives as input a hierarchical selective classifier $f^{H}$, an
accuracy target $1-\alpha$, a confidence level $1-\delta$ (which refers to the
interval around $1-\alpha$, not to be confused with the model’s confidence),
and a calibration set. It outputs the optimal threshold $\hat{\theta}$ that
ensures the classifier’s accuracy on an unseen test set falls within a
$1-\delta$ confidence interval around $1-\alpha$, with a resulting error
margin of $\epsilon$. The threshold is calculated once on the calibration set
and then used statically during inference. The algorithm does not require any
retraining or fine-tuning of the model’s weights. For each sample
$(x_{i},y_{i})$ in the calibration set, the algorithm first calculates
$\theta_{i}$, the minimal threshold that would have made the prediction
$f^{H}(x_{i})$ hierarchically correct. Then $\hat{\theta}$, the optimal
threshold, is calculated in a method inspired by split conformal prediction
[42].

Algorithm 2 Optimal Hierarchical Selective Threshold

1:Hierarchical selective classifier $f^{H}=(f,g^{H})$, hierarchy $H=(V,E)$,
calibration set $S_{n}=\\{(x_{i},y_{i})\\}_{i=1}^{n}$, target accuracy
$1-\alpha\in(0,1)$, confidence level $1-\delta$.

2:Optimal threshold $\hat{\theta}$, and $\epsilon$ s.t.
$P(|C(n,\alpha)-(1-\alpha)|\leq\epsilon)\geq 1-\delta$, where
$C(n,\alpha)=P(\theta_{n+1}\leq\hat{\theta}|S_{n})$

3:Based on $\alpha,n,\delta$, calculate $\epsilon$ $\triangleright$ See
Appendix D

4:for $(x_{i},y_{i})$ in $S_{n}$ do

5: Obtain $f^{H}_{v}(x_{i})$, $\forall v\in V$

6: $\theta_{i}\leftarrow(g_{\theta}^{H})^{-1}(x_{i}|\kappa,f)$
$\triangleright$ See Algorithm 5 in Appendix C

7:end for

8:Sort $\\{\theta_{i}\\}_{i=1}^{n}$ in ascending order

9:$\hat{\theta}\leftarrow\theta_{{\lceil(n+1)(1-\alpha)\rceil}}$

Theorem 1 Suppose the calibration set $S_{n}=\\{(x_{i},y_{i})\\}_{i=1}^{n}$
and a given test sample $(x_{n+1},y_{n+1})$ are exchangeable. For any target
accuracy $\alpha\in(0,1)$ and $\delta$, define $\theta_{n+1}$, $\hat{\theta}$
and $\epsilon$ as in Algorithm 2, and
$C(n,\alpha)=P(\theta_{n+1}\leq\hat{\theta}|S_{n})$.
Then:$P(|C(n,\alpha)-(1-\alpha)|\leq\epsilon)\geq 1-\delta.$
Proof: See Appendix D.
Note: our algorithm can provide an even greater degree of flexibility: the
user may choose to set the values of any three parameters out of
$\alpha,n,\epsilon,\delta$. With the three parameters fixed, we can compute
the remaining parameter. In the algorithm we implicitly assumed $n$ is fixed,
but increasing $n$ yields more stable results. For a detailed discussion of
this topic, see Appendix D.

##  5 Experiments

In this section we evaluate the methods introduced in Section 3 and Section 4.
The evaluation was performed on 1115 vision models pretrained on ImageNet1k
[10], and 6 models pretrained on iNat-21 [22] (available in timm 0.9.16 [43]
and torchvision 0.15.1 [28]). The reported results were obtained on the
corresponding validation sets (ImageNet1k and iNat-21). The complete results
and source code necessary for reproducing the experiments are provided in the
Supplementary Material.

Inference Rules: Table 1 compares the mean results of the Climbing inference
rule to both hierarchical and non-hierarchical baselines. The evaluation is
based on RC curves generated for 1115 models pretrained on ImageNet1k and 6
models pretrained on iNat21 with each inference rule applied to their output.
These aggregated results show the effect of different hierarchical selective
inference rules, independent of the properties or output of a specific model.
Compared to the non-hierarchical selective baseline, hierarchical inference
has a clear benefit. Allowing models to handle uncertainty by partially
rejecting a prediction instead of rejecting it as a whole, proves to be
advantageous. The average model is capable of leveraging the hierarchy to
predict internal nodes that reduce risk while preserving coverage.
Nonetheless, the differences remain stark when comparing the hierarchical
inference rules. Climbing, achieving almost 15% hierarchical gain, outperforms
MC, with more than double the gain of the latter. These results highlight the
fact that the approach taken by inference rules to leverage the hierarchy can
significantly impact outcomes. A possible explanation for Climbing’s superior
performance could stem from the fact that most models are trained to optimize
leaf classification. By starting from the most likely leaf, Climbing utilizes
the prior knowledge embedded in models for leaf classification, while MC
ignores it. Interestingly, our analysis also shows that HSC improves
confidence calibration. Appendix F discusses the calibration of HSC in more
detail.

Table 1: Comparison of mean hAURC and hierarchical gain results for the selective, Max-Coverage (MC) and Climbing inference rules applied to 1115 models trained on ImageNet1k, and 6 models trained on iNat21. | ImageNet-1k (1115 models) | iNat21 (6 models)
---|---|---
Inference Rule | hAURC | Hier. Gain | hAURC | Hier. Gain
($\times$ 1000) | (%) | ($\times$ 1000) | (%)
Selective | 42.27$\pm$0.46 | - | 13.35$\pm$0.50 | -
MC | 39.99$\pm$0.53 | 6.92$\pm$0.26 | 11.96$\pm$0.45 | 10.45$\pm$0.46
Climbing | 36.51$\pm$0.47 | 14.94$\pm$0.22 | 10.15$\pm$0.41 | 23.94$\pm$1.24

Optimal Threshold Algorithm: We compare our algorithm to DARTS [11]. We
evaluate the performance of both algorithms on 1115 vision models trained on
ImageNet1k, for a set of target accuracies. For each model and target accuracy
the algorithm was run 1000 times, each with a randomly drawn calibration set.
We also evaluate both algorithms on 6 models trained on the iNat21 dataset. We
compare the algorithms based on two metrics: (1) _target accuracy error_ ,
i.e., the mean distance between the target accuracy and the accuracy measured
on the test set; (2) coverage achieved by using the algorithms’ output on the
test set. The results presented in Table 2, and Table 4 in Appendix G, show
that our algorithm consistently achieves substantially lower target accuracy
error, indicating that our algorithm succeeds in nearing the target accuracy
more precisely. This property allows the model to provide a better balance
between risk and coverage. Our algorithm is more inclined towards this trade-
off, as it almost always achieves higher coverage than DARTS. This is
particularly noteworthy when the desired target is high: while DARTS loses
coverage quickly, our algorithm manages to maintain coverage that is up to
twice as high. Importantly, DARTS does not capture the whole risk-coverage
trade-off. Specifically, at the extreme point in the trade-off when it aims to
maximize specificity, it still falls short of providing full coverage, and its
predictions do not reduce to a flat classifier’s predictions, i.e. it may
still predict internal nodes.
Our algorithm offers additional flexibility to the user by allowing the tuning
of the confidence interval ($1-\delta$), while DARTS does not offer such
control. Figure 3 illustrates the superiority of our technique over DARTS in
detail. Appendix H compares the results of an additional baseline, conformal
risk control [3]. The results show that the conformal risk control algorithm
exhibits a significantly higher mean accuracy error than both our algorithm
and DARTS.

Table 2: Results (mean scores) comparing the hierarchical selective threshold algorithm (Algorithm 2) with DARTS, repeated 1000 times for each model and target accuracy with a randomly drawn calibration set of 5,000 samples, applied to 1115 models trained on ImageNet1k (meaning we evaluated each algorithm 1,115,000 times). $1-\delta$ is set at 0.9. Target Accuracy (%) | Target Accuracy Error (%) | Coverage
---|---|---
| DARTS | Ours | DARTS | Ours
70 | 14.52$\pm$1.3e-03 | 10.79$\pm$3.1e-03 | 0.97$\pm$1.4e-05 | 1.00$\pm$5.0e-05
80 | 4.86$\pm$5.2e-03 | 2.19$\pm$7.0e-03 | 0.96$\pm$5.8e-05 | 0.98$\pm$1.0e-04
90 | 0.73$\pm$9.6e-03 | 0.02$\pm$4.0e-04 | 0.88$\pm$9.9e-04 | 0.87$\pm$2.9e-05
95 | 0.69$\pm$1.4e-02 | 0.02$\pm$2.2e-04 | 0.74$\pm$2.6e-03 | 0.76$\pm$7.4e-05
99 | 0.63$\pm$4.2e-03 | 0.02$\pm$1.1e-04 | 0.22$\pm$2.0e-03 | 0.40$\pm$3.2e-04
99.5 | 0.40$\pm$1.9e-03 | 0.02$\pm$7.5e-05 | 0.13$\pm$9.8e-04 | 0.26$\pm$2.5e-04
Figure 3: Individual model examples comparing the hierarchical selective
threshold algorithm against DARTS, with each algorithm repeated 1000 times.
The mean and median results are shown in dark green. The light green area
shows the $\epsilon$ interval around the target accuracy, and the remaining
area is marked in red (i.e., each repetition has a $1-\delta$ probability of
being in the green area and a $\delta$ probability of being in the red area).
The target accuracy is 95% and $1-\delta=0.9$. In both examples, the target
accuracy error of DARTS is high, and the entirety of its accuracy distribution
lies outside of the confidence interval. Left: EVA-Giant/14 [13]. DARTS fails
to meet the constraint, whereas our algorithm’s mean accuracy is very close to
the target. Right: ResNet-152 [44]. While our algorithm has a near-perfect
mean accuracy, DARTS rejects all samples, resulting in zero coverage. Figure
4: Comparison of different methods by their improvement in hAURC, relative to
the same model’s performance without the method. The number of models
evaluated for each method: knowledge distillation: 42, pretraining: 61, CLIP:
16, semi-supervised learning: 11, adversarial training: 8.

Empirical Study of Training Regimes: Inspired by [16], which demonstrated that
training methods such as knowledge distillation significantly impact selective
performance, we aimed to investigate whether training regimes could also
contribute to hierarchical selective performance. The goal of this
experimental section is to provide practitioners with valuable insights for
selecting effective training regimes or pretrained models for HSC.
We evaluated the hAURC of models trained with several training regimes: (a)
Knowledge Distillation (KD) [37, 1, 33]; (b) Pretraining: models pretrained
either on ImageNet21k [36, 38, 50, 25, 33] or on ImageNet12k, a 11,821 class
subset of the full ImageNet21k [43]; (c) Contrastive Language-Image
pretraining (CLIP) [31]: CLIP models equipped with linear-probes, pretrained
on WIT-400M image-text pairs by OpenAI, as well as models pretrained with
OpenCLIP on LAION-2B [34, 7], fine-tuned either on ImageNet1k or on
ImageNet12k and then ImageNet1k. Note that _zero-shot_ CLIP models (i.e., CLIP
models without linear-probes) were not included in this evaluation, and are
discussed later in this section. (d) Adversarial Training [47, 39]; (e)
various forms of Weakly-Supervised [26] or Semi-Supervised Learning [49, 48].
To ensure a fair comparison, we only compare pairs of models that share
identical architectures, except for the method being assessed (e.g., a model
trained with KD is compared to its vanilla counterpart without KD). Sample
sizes vary according to the number of available models for each method. The
hAURC results of all models were obtained by using the Climbing inference
rule.

(1) CLIP exceptionally improves hierarchical selective performance, compared
to other training regimes. Out of the methods mentioned above, CLIP (orange
box), when equipped with a “linear-probe”, improves hierarchical performance
the most by a large margin. As seen in Figure 4, the improvement is measured
by the relative improvement in hAURC between the vanilla version of the model
and the model itself. CLIP achieves an exceptional improvement surpassing 40%.
Further, its median improvement is almost double the next best methods,
pretraining (purple box) and semi-supervised learning (light blue box). One
possible explanation for this improvement is that the rich representations
learned by CLIP lead to improved hierarchical understanding. The image-text
alignment of CLIP can express semantic concepts that may not be present when
learning exclusively from images. Alternatively, it could be the result of the
vast amount of pertaining data.
(2) Pretraining on larger ImageNet datasets benefits hierarchical selective
performance, with certain models achieving up to a 40% improvement. However,
the improvement rates vary significantly: not all models experience the same
benefit from pretraining, and some may experience minimal or no improvement.
While semi-supervised learning also shows improvement in hierarchical
selective performance, the relatively low number of models tested (only 11)
makes it challenging to draw firm conclusions.
(3) Knowledge Distillation achieves a notable improvement, with a median
improvement of around 10%. Although not as substantial as the dramatic
increase seen with CLIP, it still offers a solid improvement. This observation
aligns with [16], who found that knowledge distillation improves selective
prediction performance as well as ranking and calibration.
(4) Linear-probe CLIP significantly outperforms zero-shot CLIP in HSC: We
compared pairs of models with identical backbones, where one is the original
zero-shot model, and the other was equipped with a linear-probe, that is, it
uses the same frozen feature extractor but has an added head trained to
classify ImageNet1k. The zero-shot models evaluated are the publicly available
models released by OpenAI. The mean relative improvement from zero-shot CLIP
to linear-probe CLIP is 45%, with improvement rates ranging from 32% to 53%.
We hypothesize that the hierarchical selective performance boost may be
related to better calibration or ranking abilities. Specifically, we observe
that all CLIP models equipped with linear-probes had significantly higher
AUROC than their zero-shot counterparts, indicating superior ranking. Figure 7
in Appendix I shows these results in more detail.

##  6 Related Work

In selective classification, several alternative methods for confidence
thresholding have been developed [5, 27]. However, these methods generally
necessitate some form of training. This work is focused on post-hoc methods
that are compatible with any pretrained classifier, which is particularly
advantageous for practitioners. Furthermore, despite the availability of other
options, threshold-based rejection even with the popular Softmax confidence
score continues to be widely used [16, 19], and can be readily enhanced with
temperature scaling or other techniques [6, 14, 16].
Various works leverage a hierarchy of classes to improve leaf predictions of
flat classifiers [45, 4, 24] but comparatively fewer works explore
hierarchical classifiers. [45] optimized a “win” metric comprising a weighted
combination of likelihoods on the path from the root to the leaf. [4] focused
on reducing leaf mistake severity, measured by graph distance. They introduced
a hierarchical cross-entropy loss, as well as a soft label loss that
generalizes label smoothing. [24] claimed that both methods in [4] result in
poorly calibrated models, and proposed an alternative inference method. [11]
proposed the Dual Accuracy Reward Trade-off Search (DARTS) algorithm, which
attempted to obtain the most specific classifier for a user-specified accuracy
constraint. They used information gain and hierarchical accuracy as two
competing factors, which are integrated into a generalized Lagrange function
to effectively obtain multi-granularity decisions. Additional approaches
include the Level Selector network, trained by self-supervision to predict the
appropriate level in the hierarchy [23]. [40] proposed a loss based on [46]
and performed inference using a threshold-based inference rule. Other works
allow non-mandatory leaf node prediction, although not directly addressing the
accuracy-specificity trade-off [32, 46]. The evaluation of hierarchical
classifiers has received relatively little attention previous to our research.
The performance profile of a classifier could be inferred from either the
average value of a metric across the operating range or by observing operating
curves that compare correctness and exactness or information precision and
recall [40], or measuring information gain [11, 46]. Set-valued prediction
[20] tackles a similar problem to hierarchical classification by allowing a
classifier to predict a set of classes. Although both approaches handle
uncertainty by predicting a set of classes, the HSC framework hard-codes the
sets as nodes in the hierarchy. This way, HSC injects additional world
knowledge contained in the hierarchical relations between the classes,
yielding a more interpretable prediction. Conformal risk control [3] is of
particular interest because it constrains the prediction sets to be
hierarchical. Appendix H shows a comparison of this baseline to our method.

##  7 Concluding Remarks

This paper presents HSC, an extension of selective classification to a
hierarchical setting, allowing models to reduce the information in predictions
by retreating to internal nodes in the hierarchy when faced with uncertainty.
The key contributions of this work include the formalization of hierarchical
risk and coverage, the introduction of hierarchical risk-coverage curves, the
development of hierarchical selective inference rules, and an efficient
algorithm to find the optimal confidence threshold for a given target
accuracy. Extensive empirical studies on over a thousand ImageNet classifiers
demonstrate the advantages of the proposed algorithms over existing baselines
and reveal new findings on training methods that boost hierarchical selective
performance.
However, there are a few aspects of this work that present opportunities for
further investigation and improvement: (1) Our approach utilizes softmax-based
confidence scores. exploring alternative confidence functions and their impact
on hierarchical selective classification could provide further insights; (2)
While we have identified certain training methods that boost hierarchical
selective performance, the training regimes were not optimized for
hierarchical selective classification. Future research could focus on
optimizing selective hierarchical performance. (3) Although our threshold
algorithm is effective, it could be beneficial to train models to guarantee
specific risk or coverage constraints supplied by users, in essence
constructing a hierarchical “SelectiveNet” [18];

## References

## References

  * Aflalo et al. [2020] Yonathan Aflalo, Asaf Noy, Ming Lin, Itamar Friedman, and Lihi Zelnik-Manor.  Knapsack pruning with inner distillation.  _CoRR_ , abs/2002.08258, 2020.  URL https://arxiv.org/abs/2002.08258.
  * Angelopoulos and Bates [2021] Anastasios N. Angelopoulos and Stephen Bates.  A gentle introduction to conformal prediction and distribution-free uncertainty quantification.  _CoRR_ , abs/2107.07511, 2021.  URL https://arxiv.org/abs/2107.07511.
  * Angelopoulos et al. [2022] Anastasios N. Angelopoulos, Stephen Bates, Adam Fisch, Lihua Lei, and Tal Schuster.  Conformal risk control.  _CoRR_ , abs/2208.02814, 2022.
  * Bertinetto et al. [2020] Luca Bertinetto, Romain Müller, Konstantinos Tertikas, Sina Samangooei, and Nicholas A. Lord.  Making better mistakes: Leveraging class hierarchies with deep networks.  In _2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020_ , pages 12503–12512. Computer Vision Foundation / IEEE, 2020.  doi: 10.1109/CVPR42600.2020.01252.  URL https://openaccess.thecvf.com/content_CVPR_2020/html/Bertinetto_Making_Better_Mistakes_Leveraging_Class_Hierarchies_With_Deep_Networks_CVPR_2020_paper.html.
  * Cao et al. [2022] Yuzhou Cao, Tianchi Cai, Lei Feng, Lihong Gu, Jinjie Gu, Bo An, Gang Niu, and Masashi Sugiyama.  Generalizing consistent multi-class classification with rejection to be compatible with arbitrary losses.  In _NeurIPS_ , 2022.
  * Cattelan and Silva [2024] Luís Felipe P. Cattelan and Danilo Silva.  How to fix a broken confidence estimator: Evaluating post-hoc methods for selective classification with deep neural networks, 2024.
  * Cherti et al. [2023] Mehdi Cherti, Romain Beaumont, Ross Wightman, Mitchell Wortsman, Gabriel Ilharco, Cade Gordon, Christoph Schuhmann, Ludwig Schmidt, and Jenia Jitsev.  Reproducible scaling laws for contrastive language-image learning.  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2023, Vancouver, BC, Canada, June 17-24, 2023_ , pages 2818–2829. IEEE, 2023.  doi: 10.1109/CVPR52729.2023.00276.  URL https://doi.org/10.1109/CVPR52729.2023.00276.
  * Chow [1957] C. K. Chow.  An optimum character recognition system using decision functions.  _IRE Trans. Electron. Comput._ , 6(4):247–254, 1957.  doi: 10.1109/TEC.1957.5222035.  URL https://doi.org/10.1109/TEC.1957.5222035.
  * Cordella et al. [1995] Luigi P. Cordella, Claudio De Stefano, Francesco Tortorella, and Mario Vento.  A method for improving classification reliability of multilayer perceptrons.  _IEEE Trans. Neural Networks_ , 6(5):1140–1147, 1995.  doi: 10.1109/72.410358.  URL https://doi.org/10.1109/72.410358.
  * Deng et al. [2009] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2009), 20-25 June 2009, Miami, Florida, USA_ , pages 248–255. IEEE Computer Society, 2009.  doi: 10.1109/CVPR.2009.5206848.  URL https://doi.org/10.1109/CVPR.2009.5206848.
  * Deng et al. [2012] Jia Deng, Jonathan Krause, Alexander C. Berg, and Li Fei-Fei.  Hedging your bets: Optimizing accuracy-specificity trade-offs in large scale visual recognition.  In _2012 IEEE Conference on Computer Vision and Pattern Recognition, Providence, RI, USA, June 16-21, 2012_ , pages 3450–3457. IEEE Computer Society, 2012.  doi: 10.1109/CVPR.2012.6248086.  URL https://doi.org/10.1109/CVPR.2012.6248086.
  * El-Yaniv and Wiener [2010] Ran El-Yaniv and Yair Wiener.  On the foundations of noise-free selective classification.  _J. Mach. Learn. Res._ , 11:1605–1641, 2010.  doi: 10.5555/1756006.1859904.  URL https://dl.acm.org/doi/10.5555/1756006.1859904.
  * Fang et al. [2023] Yuxin Fang, Wen Wang, Binhui Xie, Quan Sun, Ledell Wu, Xinggang Wang, Tiejun Huang, Xinlong Wang, and Yue Cao.  EVA: exploring the limits of masked visual representation learning at scale.  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2023, Vancouver, BC, Canada, June 17-24, 2023_ , pages 19358–19369. IEEE, 2023.  doi: 10.1109/CVPR52729.2023.01855.  URL https://doi.org/10.1109/CVPR52729.2023.01855.
  * Feng et al. [2023] Leo Feng, Mohamed Osama Ahmed, Hossein Hajimirsadeghi, and Amir H. Abdi.  Towards better selective classification.  In _ICLR_. OpenReview.net, 2023.
  * Fisch et al. [2022] Adam Fisch, Tommi S. Jaakkola, and Regina Barzilay.  Calibrated selective classification.  _Trans. Mach. Learn. Res._ , 2022, 2022.
  * Galil et al. [2023] Ido Galil, Mohammed Dabbah, and Ran El-Yaniv.  What can we learn from the selective prediction and uncertainty estimation performance of 523 imagenet classifiers?  In _The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023_. OpenReview.net, 2023.  URL https://openreview.net/pdf?id=p66AzKi6Xim.
  * Geifman and El-Yaniv [2017] Yonatan Geifman and Ran El-Yaniv.  Selective classification for deep neural networks.  In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, _Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA_ , pages 4878–4887, 2017.  URL https://proceedings.neurips.cc/paper/2017/hash/4a8423d5e91fda00bb7e46540e2b0cf1-Abstract.html.
  * Geifman and El-Yaniv [2019] Yonatan Geifman and Ran El-Yaniv.  Selectivenet: A deep neural network with an integrated reject option.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 2151–2159. PMLR, 2019.  URL http://proceedings.mlr.press/v97/geifman19a.html.
  * Geifman et al. [2019] Yonatan Geifman, Guy Uziel, and Ran El-Yaniv.  Bias-reduced uncertainty estimation for deep neural classifiers.  In _7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019_. OpenReview.net, 2019.  URL https://openreview.net/forum?id=SJfb5jCqKm.
  * Grycko [1993] Eugen Grycko.  Classification with set-valued decision functions.  In Otto Opitz, Berthold Lausen, and Rüdiger Klar, editors, _Information and Classification_ , pages 218–224, Berlin, Heidelberg, 1993. Springer Berlin Heidelberg.  ISBN 978-3-642-50974-2.
  * Guo et al. [2017] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger.  On calibration of modern neural networks.  In Doina Precup and Yee Whye Teh, editors, _Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017_ , volume 70 of _Proceedings of Machine Learning Research_ , pages 1321–1330. PMLR, 2017.  URL http://proceedings.mlr.press/v70/guo17a.html.
  * Horn et al. [2021] Grant Van Horn, Elijah Cole, Sara Beery, Kimberly Wilber, Serge J. Belongie, and Oisin Mac Aodha.  Benchmarking representation learning for natural world image collections.  In _CVPR_ , pages 12884–12893. Computer Vision Foundation / IEEE, 2021.
  * Iqbal and Gall [2019] Ahsan Iqbal and Juergen Gall.  Level selector network for optimizing accuracy-specificity trade-offs.  In _2019 IEEE/CVF International Conference on Computer Vision Workshops, ICCV Workshops 2019, Seoul, Korea (South), October 27-28, 2019_ , pages 1466–1473. IEEE, 2019.  doi: 10.1109/ICCVW.2019.00184.  URL https://doi.org/10.1109/ICCVW.2019.00184.
  * Karthik et al. [2021] Shyamgopal Karthik, Ameya Prabhu, Puneet K. Dokania, and Vineet Gandhi.  No cost likelihood manipulation at test time for making better mistakes in deep networks.  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net, 2021.  URL https://openreview.net/forum?id=193sEnKY1ij.
  * Liu et al. [2021] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  In _2021 IEEE/CVF International Conference on Computer Vision, ICCV 2021, Montreal, QC, Canada, October 10-17, 2021_ , pages 9992–10002. IEEE, 2021.  doi: 10.1109/ICCV48922.2021.00986.  URL https://doi.org/10.1109/ICCV48922.2021.00986.
  * Mahajan et al. [2018] Dhruv Mahajan, Ross B. Girshick, Vignesh Ramanathan, Kaiming He, Manohar Paluri, Yixuan Li, Ashwin Bharambe, and Laurens van der Maaten.  Exploring the limits of weakly supervised pretraining.  In Vittorio Ferrari, Martial Hebert, Cristian Sminchisescu, and Yair Weiss, editors, _Computer Vision - ECCV 2018 - 15th European Conference, Munich, Germany, September 8-14, 2018, Proceedings, Part II_ , volume 11206 of _Lecture Notes in Computer Science_ , pages 185–201. Springer, 2018.  doi: 10.1007/978-3-030-01216-8\\_12.  URL https://doi.org/10.1007/978-3-030-01216-8_12.
  * Mao et al. [2023] Anqi Mao, Mehryar Mohri, and Yutao Zhong.  Theoretically grounded loss functions and algorithms for score-based multi-class abstention.  _CoRR_ , abs/2310.14770, 2023.
  * Marcel and Rodriguez [2010] Sébastien Marcel and Yann Rodriguez.  Torchvision the machine-vision package of torch.  In _ACM Multimedia_ , pages 1485–1488. ACM, 2010.
  * Miller [1995] George A. Miller.  Wordnet: A lexical database for english.  _Commun. ACM_ , 38(11):39–41, 1995.  doi: 10.1145/219717.219748.  URL https://doi.org/10.1145/219717.219748.
  * Naeini et al. [2015] Mahdi Pakdaman Naeini, Gregory F. Cooper, and Milos Hauskrecht.  Obtaining well calibrated probabilities using bayesian binning.  In _AAAI_ , pages 2901–2907. AAAI Press, 2015.
  * Radford et al. [2021] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever.  Learning transferable visual models from natural language supervision.  In Marina Meila and Tong Zhang, editors, _Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event_ , volume 139 of _Proceedings of Machine Learning Research_ , pages 8748–8763. PMLR, 2021.  URL http://proceedings.mlr.press/v139/radford21a.html.
  * Redmon and Farhadi [2017] Joseph Redmon and Ali Farhadi.  YOLO9000: better, faster, stronger.  In _2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, Honolulu, HI, USA, July 21-26, 2017_ , pages 6517–6525. IEEE Computer Society, 2017.  doi: 10.1109/CVPR.2017.690.  URL https://doi.org/10.1109/CVPR.2017.690.
  * Ridnik et al. [2021] Tal Ridnik, Emanuel Ben Baruch, Asaf Noy, and Lihi Zelnik.  Imagenet-21k pretraining for the masses.  In Joaquin Vanschoren and Sai-Kit Yeung, editors, _Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks 1, NeurIPS Datasets and Benchmarks 2021, December 2021, virtual_ , 2021.  URL https://datasets-benchmarks-proceedings.neurips.cc/paper/2021/hash/98f13708210194c475687be6106a3b84-Abstract-round1.html.
  * Schuhmann et al. [2022] Christoph Schuhmann, Romain Beaumont, Richard Vencu, Cade Gordon, Ross Wightman, Mehdi Cherti, Theo Coombes, Aarush Katta, Clayton Mullis, Mitchell Wortsman, Patrick Schramowski, Srivatsa Kundurthy, Katherine Crowson, Ludwig Schmidt, Robert Kaczmarczyk, and Jenia Jitsev.  LAION-5B: an open large-scale dataset for training next generation image-text models.  In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, _Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022_ , 2022.  URL http://papers.nips.cc/paper_files/paper/2022/hash/a1859debfb3b59d094f3504d5ebb6c25-Abstract-Datasets_and_Benchmarks.html.
  * Stefano et al. [2000] Claudio De Stefano, Carlo Sansone, and Mario Vento.  To reject or not to reject: that is the question-an answer in case of neural classifiers.  _IEEE Trans. Syst. Man Cybern. Part C_ , 30(1):84–94, 2000.  doi: 10.1109/5326.827457.  URL https://doi.org/10.1109/5326.827457.
  * Tan and Le [2021] Mingxing Tan and Quoc V. Le.  Efficientnetv2: Smaller models and faster training.  In Marina Meila and Tong Zhang, editors, _Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event_ , volume 139 of _Proceedings of Machine Learning Research_ , pages 10096–10106. PMLR, 2021.  URL http://proceedings.mlr.press/v139/tan21a.html.
  * Touvron et al. [2021] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou.  Training data-efficient image transformers & distillation through attention.  In Marina Meila and Tong Zhang, editors, _Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event_ , volume 139 of _Proceedings of Machine Learning Research_ , pages 10347–10357. PMLR, 2021.  URL http://proceedings.mlr.press/v139/touvron21a.html.
  * Touvron et al. [2022] Hugo Touvron, Matthieu Cord, and Hervé Jégou.  Deit III: revenge of the vit.  In Shai Avidan, Gabriel J. Brostow, Moustapha Cissé, Giovanni Maria Farinella, and Tal Hassner, editors, _Computer Vision - ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23-27, 2022, Proceedings, Part XXIV_ , volume 13684 of _Lecture Notes in Computer Science_ , pages 516–533. Springer, 2022.  doi: 10.1007/978-3-031-20053-3\\_30.  URL https://doi.org/10.1007/978-3-031-20053-3_30.
  * Tramèr et al. [2018] Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian J. Goodfellow, Dan Boneh, and Patrick D. McDaniel.  Ensemble adversarial training: Attacks and defenses.  In _6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings_. OpenReview.net, 2018.  URL https://openreview.net/forum?id=rkZvSe-RZ.
  * Valmadre [2022] Jack Valmadre.  Hierarchical classification at multiple operating points.  In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, _Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022_ , 2022.  URL http://papers.nips.cc/paper_files/paper/2022/hash/727855c31df8821fd18d41c23daebf10-Abstract-Conference.html.
  * Vovk [2012] Vladimir Vovk.  Conditional validity of inductive conformal predictors.  _CoRR_ , abs/1209.2673, 2012.
  * Vovk et al. [1999] Volodya Vovk, Alexander Gammerman, and Craig Saunders.  Machine-learning applications of algorithmic randomness.  In Ivan Bratko and Saso Dzeroski, editors, _Proceedings of the Sixteenth International Conference on Machine Learning (ICML 1999), Bled, Slovenia, June 27 - 30, 1999_ , pages 444–453. Morgan Kaufmann, 1999.
  * Wightman [2019] Ross Wightman.  Pytorch image models.  https://github.com/huggingface/pytorch-image-models, 2019.
  * Wightman et al. [2021] Ross Wightman, Hugo Touvron, and Hervé Jégou.  Resnet strikes back: An improved training procedure in timm.  _CoRR_ , abs/2110.00476, 2021.  URL https://arxiv.org/abs/2110.00476.
  * Wu et al. [2017] Cinna Wu, Mark Tygert, and Yann LeCun.  Hierarchical loss for classification.  _CoRR_ , abs/1709.01062, 2017.  URL http://arxiv.org/abs/1709.01062.
  * Wu et al. [2020] Tz-Ying Wu, Pedro Morgado, Pei Wang, Chih-Hui Ho, and Nuno Vasconcelos.  Solving long-tailed recognition with deep realistic taxonomic classifier.  In Andrea Vedaldi, Horst Bischof, Thomas Brox, and Jan-Michael Frahm, editors, _Computer Vision - ECCV 2020 - 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part VIII_ , volume 12353 of _Lecture Notes in Computer Science_ , pages 171–189. Springer, 2020.  doi: 10.1007/978-3-030-58598-3\\_11.  URL https://doi.org/10.1007/978-3-030-58598-3_11.
  * Xie et al. [2020a] Cihang Xie, Mingxing Tan, Boqing Gong, Jiang Wang, Alan L. Yuille, and Quoc V. Le.  Adversarial examples improve image recognition.  In _2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020_ , pages 816–825. Computer Vision Foundation / IEEE, 2020a.  doi: 10.1109/CVPR42600.2020.00090.  URL https://openaccess.thecvf.com/content_CVPR_2020/html/Xie_Adversarial_Examples_Improve_Image_Recognition_CVPR_2020_paper.html.
  * Xie et al. [2020b] Qizhe Xie, Minh-Thang Luong, Eduard H. Hovy, and Quoc V. Le.  Self-training with noisy student improves imagenet classification.  In _2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020_ , pages 10684–10695. Computer Vision Foundation / IEEE, 2020b.  doi: 10.1109/CVPR42600.2020.01070.  URL https://openaccess.thecvf.com/content_CVPR_2020/html/Xie_Self-Training_With_Noisy_Student_Improves_ImageNet_Classification_CVPR_2020_paper.html.
  * Yalniz et al. [2019] I. Zeki Yalniz, Hervé Jégou, Kan Chen, Manohar Paluri, and Dhruv Mahajan.  Billion-scale semi-supervised learning for image classification.  _CoRR_ , abs/1905.00546, 2019.  URL http://arxiv.org/abs/1905.00546.
  * Yu et al. [2024] Weihao Yu, Chenyang Si, Pan Zhou, Mi Luo, Yichen Zhou, Jiashi Feng, Shuicheng Yan, and Xinchao Wang.  Metaformer baselines for vision.  _IEEE Trans. Pattern Anal. Mach. Intell._ , 46(2):896–912, 2024.  doi: 10.1109/TPAMI.2023.3329173.  URL https://doi.org/10.1109/TPAMI.2023.3329173.

Supplementary Material

##  Appendix A Max-Coverage Inference Rule Algorithm

Algorithm 3 Max-Coverage Inference Rule [40]

Classifier $f$, class hierarchy $H=(V,E)$, sample $x_{i}\in\mathcal{X}$,
confidence threshold $\theta$.

Predicted node $\hat{v}$.

Obtain $f_{v}(x_{i})$ $\forall v\in V$

$\hat{v}\leftarrow\underset{v}{\arg\max}\;{\\{\phi(v)|\;f_{v}(x_{i})\geq\theta,v\in
V\\}}$ $\triangleright$ Break ties by confidence rate

##  Appendix B Jumping Inference Rule

The Jumping inference rule (Algorithm 4) traverses the most likely nodes at
each level of the hierarchy, until reaching $\theta$. Unlike Climbing, jumping
is not confined to a single path from the root to a leaf. Although it
performed better than a “hierarchically-ignorant” selective inference, it
still underperformed by the other algorithms.

Algorithm 4 Jumping Inference Rule

Classifier $f$, class hierarchy $H=(V,E)$, sample $x_{i}\in\mathcal{X}$,
confidence threshold $\theta$.

Predicted node $\hat{v}$.

Perform temperature scaling

Obtain $f_{v}(x_{i})$ $\forall v\in V$

$\hat{v}\leftarrow\underset{y\in L}{\arg\max}f_{y}(x_{i})$

while $f_{\hat{v}}(x_{i})<\theta$ do

$\hat{v}\leftarrow\underset{v}{\arg\max}\\{f_{v}(x_{i})|v\in
V,\;height(v)=h\\}$

$h\leftarrow h+1$

end while

(*) If the leaves in $H$ are not all at the same depth, pad the hierarchy with
dummy nodes

##  Appendix C Hierarchy Traversal for Threshold Finding

We demonstrate an example algorithm for the Climbing inference rule that
obtains $\theta_{i}$ for a single instance $(x_{i},y_{i})$.

Algorithm 5 Hierarchy Traversal - Climbing

1:Calibration sample $(x_{i},y_{i})$, classifier $f$, class hierarchy
$H=(V,E)$, tightness coefficient $\epsilon$.

2:$\theta_{i}$ \- the minimal threshold that would have made the prediction
correct.

3:$\theta_{i}\leftarrow 0$

4:$v_{i}\leftarrow\underset{y\in L}{\arg\max}f_{y}(x_{i})$

5:while $v_{i}\notin\mathcal{A}(y_{i})$ do

6: $\theta_{i}\leftarrow f_{v_{i}}(x_{i})+\epsilon\cdot
f_{\text{parent}(v_{i})}(x_{i})$

7: $v_{i}\leftarrow\text{parent}(v_{i})$

8:end while

##  Appendix D Proof of Theorem 1

Recall that for each sample $(x_{i},y_{i})$, $\theta_{i}$ is the minimal
threshold that would have made the prediction $f^{H}(x_{i})$ hierarchically
correct.

The following is based on [2]:
To avoid handling ties, we assume $\\{\theta_{i}\\}_{i}^{n}$ are distinct, and
without loss of generality that the calibration thresholds are sorted:
$0\leq\theta_{1}<...<\theta_{n}\leq 1$.

To keep indexing inside the array limits:
$\hat{\theta}\overset{\Delta}{=}\begin{cases}\theta_{\lceil(n+1)(1-\alpha)},&\alpha\geq\frac{1}{n+1}\\\
1,&otherwise\end{cases}.$

We also assume the samples $(x_{1},y_{1}),...,(x_{n+1},y_{n+1})$ are
exchangeable. Therefore, for any integer $k\in[1,n]$, we have:

$P(\theta_{n+1}\leq\theta_{k})=\frac{k}{n+1}.$

That is, $\theta_{n+1}$ is equally likely to fall in anywhere between the
calibration points. By setting $k=\lceil(n+1)(1-\alpha)\rceil$:

$P(\theta_{n+1}\leq\theta_{\lceil(n+1)(1-\alpha)\rceil})=\frac{\lceil(n+1)(1-\alpha)\rceil}{n+1}\geq
1-\alpha.$

In conformal prediction, the probability $P(\theta_{n+1}\leq\hat{\theta})$ is
called “marginal coverage” (not to be confused with the hierarchical selective
definition of coverage in section LABEL:sec:hsc). The analytic form of
marginal coverage given a fixed calibration set, for a sufficiently large test
set, is shown by [41] to be

$C(n,\alpha)=P(\theta_{n+1}\leq\hat{\theta}|\\{(X_{i},Y_{i})\\}_{i=1}^{n})\sim
Beta(n+1-l,l),$

where $l=\lfloor(n+1)\alpha\rfloor$

From here, the CDF of the $Beta$ distribution paves the way to calculating the
size $n$ of the calibration set needed in order to achieve coverage of
$1-\alpha\pm\epsilon$ with probability $1-\delta$:

$P(|C(n,\alpha)-(1-\alpha)|\leq\epsilon)\geq 1-\delta.$

Remarks on theorem 1:

  1. 1.

To simplify, we made an implicit assumption that users can usually allocate a
limited number of samples to the calibration set, and thus would prefer the
threshold’s optimality guarantee to hold without imposing additional
requirements on the data. However, our algorithm can provide an even greater
degree of flexibility: the user may choose to set the values of any three
parameters out of: $\alpha,n,\epsilon,\delta$. With the three parameters
fixed, the CDF of the Beta distribution can be used to compute the remaining
parameter. For instance, a certain user may have an unlimited budget of
calibration samples, while they require a specific error margin. In that case,
the using the Beta distribution, the algorithm computes the calibration set
size required for Theorem 1 to hold.

  2. 2.

The output of the algorithm holds for a calibration set of any size $n$.
Following the previous point, increasing $n$ does yield more stable results.

  3. 3.

In the context of conformal prediction, the property stated in Theorem 1 is
referred to as marginal coverage, not to be confused with the previous
definition of coverage in section 2. This property is called marginal
coverage, since the probability is marginal (averaged) over the randomness in
the calibration and test points.

##  Appendix E Comparison of Inference Rules Without Temperature Scaling

Table 3: hAURC and gain results for each inference rule. Mean results of 1115 pretrained ImageNet1k models. | Inference Rule | hAURC ($\times 1000$) | Hierarchical Gain (%)
---|---|---|---
No Temp. Scaling | Selective | 42.27$\pm$0.46 | -
Max-Coverage [40] | 39.99$\pm$0.53 | 6.92$\pm$0.26
Climbing (Ours) | 39.24$\pm$0.49 | 8.26$\pm$0.19
Temp. Scaling | Selective | 41.16$\pm$0.46 | -
Max-Coverage | 37.21$\pm$0.52 | 11.09$\pm$0.47
Climbing (Ours) | 36.51$\pm$0.47 | 12.51$\pm$0.16

##  Appendix F Hierarchical Selective Classification improves Confidence
Calibration

Confidence calibration refers to the problem of predicting probability
estimates representative of the true correctness likelihood. The calibration
of both hierarchical and non-hierarchical versions of selective classification
is a highly intriguing topic that has not been thoroughly explored in previous
research. Fisch et al. [15] suggested that often, but not always, more
confident predictions can also be more calibrated.

We measure calibration using the Expected Calibration Error (ECE) [30], a
commonly used metric for calibration. For each model, we computed the ECE for
each hierarchical coverage. We then computed the area under the ECE-Coverage
curve. Subsequently, we calculated the area under the ECE-Coverage curve, and
compared these areas similarly to the hAURC metric described in section 5.

Our analysis, which includes results from 1,115 models, reveals that selective
classification not only improves risk, but also improves calibration.
Additionally, the choice of hierarchical inference rule significantly impacts
whether calibration improves or degrades. On average, across the 1,115 models,
the mean area under the ECE-Coverage curve when applying the selective
inference rule was 36.58. For Max-Coverage [40], the mean area was 55.89,
while for the climbing inference rule, the mean area was the lowest at 12.44
(a smaller area indicates better calibration, areas were multiplied by 1000).
Interestingly, unlike hAURC, hierarchical inference rules do not necessarily
show improvement over the selective baseline: the area for Max-Coverage is
significantly higher than that for the selective rule. Figure 5 compares two
ECE-Coverage curves for the same model, demonstrating that the climbing
inference rule achieves a better curve compared to the selective baseline.

Figure 5: Comparison of selective and climbing hierarchical ECE-Coverage
curves rules with ViT-L/16-384 as the base classifier. This example represents
the prevalent case, in which climbing outperforms the “hierarchically-
ignorant” selective inference rule.

##  Appendix G Threshold Algorithm Results on iNat21

Table 4: Comparison of hierarchical selective threshold algorithm (Algorithm 2) with DARTS, repeated 100 times for each model and target accuracy with a randomly drawn calibration set of 10,000 samples, applied to 6 models trained on iNat21. $1-\delta$ is set at 0.9. Target Accuracy (%) | Target Accuracy Error (%) | Coverage
---|---|---
| DARTS | Ours | DARTS | Ours
70 | 24.64 $\pm$ 7.9e-04 | 21.22 $\pm$ 7.3e-04 | 0.98 $\pm$ 5.73e-06 | 1.000 $\pm$ 0.00e+00
80 | 14.64 $\pm$ 8.5e-04 | 11.22 $\pm$ 1.2e-03 | 0.98 $\pm$ 1.87e-06 | 1.000 $\pm$ 0.00e+00
90 | 4.64 $\pm$ 2.4e-04 | 1.22 $\pm$ 2.9e-03 | 0.98 $\pm$ 3.46e-06 | 1.000 $\pm$ 6.57e-05
95 | 0.32 $\pm$ 2.9e-02 | 0.02 $\pm$ 8.7e-03 | 0.97 $\pm$ 4.75e-04 | 0.951 $\pm$ 2.41e-04
99 | 0.49 $\pm$ 3.0e-02 | 0.01 $\pm$ 1.3e-03 | 0.39 $\pm$ 2.20e-02 | 0.687 $\pm$ 2.49e-03
99.5 | 0.42 $\pm$ 2.9e-02 | 0.01 $\pm$ 2.5e-03 | 0.06 $\pm$ 2.42e-02 | 0.413 $\pm$ 2.02e-03

##  Appendix H Conformal Risk Control Results

Figure 6 shows the mean accuracy error of the threshold algorithms introduced
in section 4 compared to the additional conformal risk control (CRC) algorithm
[3]. The mean accuracy error of CRC is strikingly higher than the other
algorithms, reaching a climax when the target accuracy is set to 95%.

Figure 6: Mean accuracy error comparison between the hierarchical selective
threshold algorithm (Algorithm 2), conformal risk control (CRC) and DARTS,
repeated 1000 times for each model and target accuracy with a randomly drawn
calibration set of 5,000 samples, applied to 1115 models trained on ImageNet1k
(meaning we evaluated each algorithm 1,115,000 times). $1-\delta$ is set at
0.9.

##  Appendix I CLIP Zero Shot VS Linear Probe

Figure 7 compares the improvement in hAURC and AUROC between zero-shot CLIP
models and their linear-probe counterparts. It can be easily observed that for
all the tested backbones the linear-probe models have significantly better
hAURC and AUROC. We encourage follow-up research to explore further the
possible connection between ranking and HSC.

Figure 7: Comparison between zero-shot and linear-probe CLIP models sharing
the same backbone. The round markers represent the zero-shot models, and the
star markers represent their respective linear-probes.

##  Appendix J Technical Details

Most experiments consider image classification on the ImageNet1k [10]
validation set, containing 50 examples each for 1,000 classes. Additional
evaluations were performed on the iNat21-Mini dataset [22], containing 50
examples each for 10,000 biological species in a seven-level taxonomy. For
experiments requiring calibration set, it was sampled randomly from the
validation set.

The evaluation was performed on 1115 vision models pretrained on ImageNet1k
[10], and 6 models pretrained on iNat-21 [22] (available in timm 0.9.16 [43]
and torchvision 0.15.1 [28]).

All experiments were conducted on a single machine with one Nvidia A4000 GPU.
The evaluation of all experiments on a single GPU took approximately one week.