To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hierarchical Classifiers
Authors: Roman Plaud
Alexandre Perez-Lebel
Matthieu Labeau
Antoine Saillenfest
Thomas Bonald
Venue: ICML 2025 poster (2025)
Keywords: Hierarchical Classification
Optimal Decoding
Primary area: general_machine_learning->evaluation
TL;DR: We propose an optimal decoding framework for hierarchical classification, deriving decision rules that optimize hierarchical metrics.

Abstract: Hierarchical classification offers an approach to incorporate the concept of mistake severity by leveraging a structured, labeled hierarchy. However, decoding in such settings frequently relies on heuristic decision rules, which may not align with task-specific evaluation metrics. In this work, we propose a framework for the optimal decoding of an output probability distribution with respect
to a target metric. We derive optimal decision rules for increasingly complex prediction settings, providing universal algorithms when candidates are limited to the set of nodes. In the most general case of predicting a *subset of nodes*, we focus on rules dedicated to the hierarchical $\mathrm{hF}_{\beta}$ scores, tailored to hierarchical settings. To demonstrate the practical utility of our approach, we conduct
extensive empirical evaluations, showcasing the superiority of our proposed optimal strategies, particularly in underdetermined scenarios. These results highlight the potential of our methods to enhance the performance and reliability of hierarchical classifiers in real-world applications.

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hierarchical Classifiers
Roman Plaud 12 Alexandre Perez-L.cbel Matthieu Labeau
Antoine Saillenfest
Thomas Bonald
Abstract
Blur level u-a
Blur level om3
Blur level gm6
Blur level om9
Hierarchical classification offers an approach to incorporate the concept of mistake severity by leveraging a structured, labeled hierarchy. However, decoding in such settings frequently relies on heuristic decision rules, which may not align with task-specific evaluation metrics. In this work, we propose framework for the optimal decoding of an output probability distribution with respect to a target metric. We derive optimal decision rules for increasingly complex prediction settings, providing universal algorithms when candidates are limited to the set of nodes. In the most general case of predicting a subset of nodes. we focus on rules dedicated to the hierarchical hF3s scores, tailored to hierarchical settings. To demonstrate the practical utility of our approach, we conduct extensive empirical evaluations, showcasing the superiority of our proposed opti- mal strategies, particularly in underdetermined scenarios. These results highlight the potential of our methods to enhance the performance and reliability hierarchical classifiers in real-world applications. The code available at
1P1 opt. (oundopolden, retravvrr Majority-ssle retrieve
golden rut sver goldan retr lever
hanting dog hunting dog win-hwiee
hanting dog Camirore persian,
Argmacgollen,
Figure Underdetermination amplifies decision-making dis- parities between decoding strategies. Predictions of three decod- ing strategies hased the probability estimates of a pretrained VGG11 model, for images with blur levels {0, 3, 6,9) 9). Cor- rect predictions are highlighted in green, incorrect red.
broader superclasses (Deng et al., 2009; Chang et al., 2021). The severity a misclassificattio error is then related to the distance between predicted class and the true class in this hierarchy: the larger the distance, the more severe the error. For any given hierarchy, one can define misclassifica- tion costs not only between the leaf nodes (corresponding to the initial classes), but across all nodes of the tree, includ- ing internal nodes. It may then be interesting to allow the prediction of internal nodes of the hierarchy. For example, it can be difficult to distinguish between two specific types of cancer that require different treatments. In such a case, the best decision would probably be predict more gen- eral category such as simply indicating that the patient has cancer allowing for a general treatment, effective for different types of cancer.
cww.a.aacoo///aaPPPapaaa laud/ hierarchical ca www.eeiissiiieleeeeeeeeeeeeeeeee
Given a conditional probability distribution over the hierar- chy, the optimal prediction can be theoretically defined as the one minimizing the expected misclassification cost. This principle has long been established: the optimal decision corresponds to minimizing the conditional risk (Duda & Hart, 1973; Berger, 1985; Smith, 2005). In the context of hierarchical classification, misclassification costs are often embedded in evaluation metrics that inherently reflect the hierarchical structure and therefore encode the severity of errors. Numerous works in the literature propose such hi- erarchical evaluation measures (Kosmopoulos al., 2014; Amigo & Delgado, 2022). However, the task of optimally decoding from posterior probability distribution, given target hierarchical metric, has received comparatively little attention. Some optimal strategies exist for specific met- rics (Bi & Kwok, 2012; Ramaswamy et al., 2015) but, in
1. Introduction
In many real-world classification tasks, the costs associated with misclassification are not uniform (Domingos, 1999; Elkan, 2001). autonomous driving for instance, mistak- ing lamppost for tree is less eritical than mistaking pedestrian for tree. One way to model the severity of mis- classifications is by organizing classes into a hierarchical tree structure, where classes are grouped into progressively
'Institut Polytechnique de Paris "Onepoint. 29 rue des Sablons, 75016. Paris, France "Soda, Inria Saclay, France "Fundamental Technologies, USA. Correspondence Roman Plaud <plaud. @ @gmail.com...
Proceedings of the nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
practice, the decoding strategy often relies on straightfor- ward heuristies, such as selecting the leaf class with the highest posterior probability (by applying argmax over the leaf nodes) or applying threshold on the probability dis- tribution (e.g.. by summing probabilities bottom-up until a threshold is met).
acle probability distribution. For example, in multi-label classification, the exponential number of possible predic- tions makes exhaustive search impractical. Consequently, significant body of work has emerged that aims to design optimal decoding strategies tailored to specific metrics-i.e. specific definitions of misclassification costs (Lewis, 1995; Dembezynski et al., 2010; Quevedo et al., 2011) and in par- ticular for F-scores (Jansche, 2007: del Coz et al., 2009;
As pre-trained models are ubiquitous in classification tasks, and misclassification costs are not necessarily known during training. our work solely focuses on post-hoc decoding, independently of the task of estimating a predictive model.
Waegeman et al., 2014).
This topic has attracted reasonable interest in the context of hierarchical classification. As the candidate prediction set grows in cardinality, optimal decision-making becomes gradually more difficult. In practice, the literature often considers a specific hierarchical metric and proposes opti- mal strategies to decode probabilities: for example, Bi & Kwok (2012) develop decoding strategies for family of eval- uation measures called HMC-loss, while Ramaswamy et al. (2015) and Cao et al. (2024) address the tree distance loss and its generalized version. Similarly, Karthik et al. (2021) introduce an optimal-decoding framework, restricting to Icaf decoding only. However, most of the time, no clear connection is made between the decision- maaiin process from trained classifiers and the actual evaluation measure aim to optimize. Instead, heuristics strategies are widely used, Selecting the maximum probability over leaf nodes is common practice but various rules exist, listed in Valmadre (2022). Also, Wang et al. (2017) propose a top-down stop- ping algorithm, Deng et al. (2012) find a trade-off between specificity and correctness while Jain et al. (2023) propose strategy that reweigh each Ieaf probability based on its parent's. While some works advocate for more systematic evaluation methodology, through bypasssing the decoding step (Plaud et al., 2024), efforts have largely focused on op- timizing common metrics (Wu & Palmer, 1994; Zhao et al., 2017) coupled with a generic heuristic strategy. Therefore, our work bridges the gap between decoding and evaluation, two interdependent concepts, by proposing strategies to identify optimal predictions for a given hierarchical metric.
Contributions. We propose a framework for deriving op- timal decoding strategies in hierarchical classification by adapting the cost-sensitive decoding framework, originally designed for flat classification (Section 3). Building on this characterization, and assuming access to the true oracle probability distribution, we develop tractable algorithms that yield the optimal prediction for a given hierarchical metric, including metrics such as the hl's 3 scores, which general- ize the well-known F scores to hierarchical classification (Section 4). Finally, we validate our theoretical findings in practical situations (Section 5) by demonstrating the superi- ority of our decoding strategies on probability distributions estimated by a diverse set of models, across wide range of metrics. We further demonstrate that the more underdeter- mined a classification task is is..,e, the more stochastic the relationship between features and labels-thh more crucial it becomes to use our newly introduced decoding algorithms: principle which we illustrate in Figure 1.
2. Related work
Determining the action that minimizes the expected cost given a probability distribution over classes has been stud- ied extensively since its introduction in early works (Duda & Hart, 1973; Berger, 1985; Smith, 2005). In practice, and even when misclassification costs are not uniform, this prob- lem is often straightforward to address. For example, in the binary classification case, the optimal decision rule re- duces to simple threshold (Elkan, 2001). In the multiclass setting, a straightforward brute-force approach that com- putes the expected cost for each possible action remains practical as long as the number of classes is moderate. As a result, cost-sensitive classification (Petrides & Verbeke, 2022) has primarily focused on designing learning algo- rithms that account for cost non-uniformity during training, either through resampling techniques (Elkan, 2001; Chawla et al., 2002) or developing reweighted losses (Viola & Jones, 2001; Zadrozny & Elkan, 2001; Lin et al., 2017). This is because the challenge often lies in learning a model that produces accurate probability estimates, which can then be used for optimal decision-making. However, there are classification problems where identifying the optimal action is computationally prohibitive, even with access to the or-
3. Problem formulation
Consider a standard single-label classification problem, with x E X' the input and y E {41,..., , the label, out of K distinct classes. We denote TP the probability measure gov- erning the joint distribution of the input-label pairs (x, y). Hierarchy. Additionally, directed tree T, referred to as the hierarchy, defined as a set of nodes A and edges E, such that the leaf nodes of T correspond to the set of classes L = [/,, in our single-label classification problem. An edge e E defines a parent-child relation. The unique root node of the tree is denoted by and P(N) is the power set of AV
assume that there exists
Remark. This design implicitly assumes exhaustive hi- erarchy i.e. every instance's 's most specific class is leaf in
2

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
T. However, by adding beforehand "stopping" children node at any internal position, we could also accommodate datasets whose instance's s most specific label lies at in- ternal node, thereby preserving the full generality of our framework.
of E for a given metric C' and model can then be defined as follows:
Definition 3.3. Decoding cost. Given a model f. the cost of a decision rule for the metric C is:
Model. When designing a hierarchical classifier, one typ- ically uses a probabilistic model / X - ((C where (CC) is the set of probability distributions over L and for each E X, f(x) Pa is estimate of the posterior distribution |P(y|x x I) over the leaf nodes L. Remark. This model formulation may seem restrictive, but it includes the more general hierarchy-awarr models capable of predicting probabilities over internal nodes of the hierarchy-not just the leaves- since the leaf distribution can be derived from them.
B(C(E(f(x)),
where the expectation is taken with respect to the joint distribution of (x. y) with probability P.
In practice, the decoding cost is estimated by computing the empirical mean N Σi= C(E(Pa,), ye) on a test set of N samples. Our focus this work is on the performance analysis of decision rules with respect to specific evalua- tion measures. In particular, we examine Bayes-optimal decodings that minimize the decoding cost by design.
In this work, we assume that f is given (e.g., trained neu- ral network), and we have access to the predicted distribu- tions Pay..... . P over some test samples .......: -N E X. From these estimations, our objective is to make predictions hy....,hy hx that are as close as possible to the ground-trune labels yı..... yN. in the sense that it minimizes the misclas- sification cost for each sample. This cost is defined through an evaluation metric (Definition 3.1). Before introducing it formally, clarify the nature of the prediction set, denoted H. which play central role in our framework:
3.1. Bayes-optimal decoding
Unless stated otherwise, we now assume that we know the true posterior probability distribution: (x) = Pyy x= x) == (px (1))EC E A(C), Va X
We formalize the task of deriving optimal predictions from an oracle posterior probability distribution for a given evalu- ation metric e. The goal is to identify a decoding function E A(C - H that minimizes the decoding cost:
Leaf node prediction: The metric is simply able to compare a leaf E L to the ground-trute lcaf label. Internal node prediction The metric can compare any node of the hierarchy h E N the ground-trutt leaf label.
EC E argmin E[C(E(f((x))
(-(())+
For any x E X, this objective can be reformulated point- wise as:
Set of nodes prediction: The metric can compare set of nodes h E P(N) to the ground-truth leaf label.
(px)) E arrgmin B(C(h,y) | x = x] hEH
Definition 3.1. Evaluation metric. An evaluation metric for a set H of candidate predictions is function that quantifies the misclassification costs:
Then, using the definition of expectation, we can define the optimal decision rule as follows:
Definition 3.4. Optimal decision rule. An optimal de- cision rule for metric : H x L - R is given by
C: H x - IR
<c. A(C) + H where
(h. + v)
where h is the prediction and y the ground-truth leaf label.
(p) = arrgmin hEH
p(1)C(h.1)
(1)
IEC
We list in Appendix C. examples of metrics with differ- ent candidate sets. To perform the evaluation, decision rule & (Definition 3.2) is required. A decision rule maps a probability distribution to a prediction h, as defined below.
We assume that the optimization problem has a unique so- lution; further details on this assumption are provided in Appendix C.2. This decision rule minimizes the expected evaluation metric C, ensuring that any alternative decoding is suboptimal and results a higher expected cost. However, even if the misclassification cost matrix (C(h, !)) (1.))xx is precomputed and can be accessed in constant time, com- puting the risk Σ p(I)C(h, 1) for all h E H via brute- force search has a time complexity of O(7)) [C). As a result, when |7|] grows exponentially (for instance, when H. = P(N)), brute-force search quickly becomes infeasi- ble. Even when restricting predictions to internal nodes (i.e.,
Definition 3.2. Decision rule. A decision rule for a set H. of candidate predictions is a function & ACC + H.
Importantly, we highlight that even if probabilities are es- timated for leaf nodes only, one may want to make a pre- diction that is not necessarily a leaf. Equipped with the decision rule, the cost of a prediction for the labut-label pair (xr, y) can be computed as C(((px), y). The decoding cost
3

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
H M). the computational cost can still be prohibitive for large hierarchies. Alternative strategies are hence necessary.
4.2. Node candidate set
When H. = -W, a brute-force algorithm remains feasible: assuming that the cost matrix (C(h, ()) (t.))xxx is pre- computed, the overall complexity of the brute-force ap- proach is O(L |C]). However, hierarchies can often contain more than 10, 000 nodes (Ashburner et al., 2000; He & McAuley, 2016), and this algorithm must be applied for each individual data point, significantly impacting time efficiency.
4. Optimal decoding strategies for hierarchical evaluation measures
For certain metrics C, it is possible derive a closed-form solution for (px(,,), which can be analytically defined us- ing only Pz. In other cases, an algorithm is needed that computes the optimal prediction (px)) with better time complexity than brute-force search. To derive closed-form solutions or algorithms, it is often necessary to compute (n),,, defined as the bottom-up sum of the probabilities of the leaf descendants of n.
To reduce the time complexity of a standard brute-force search, we focus a category of metrics that are hierar- chically reasonable' (Definition 4.2). For n & r, let (n) denote the unique parent of n in the hierarchy tree T, and recall that [(n) represents the set of leaf-node descendants of n. We then aim to derive constraints on p(n) to determine when a node n or its parent ((n) can be ruled out as sub- optimal, Specifically, the intuition is that if n is sufficiently unlikely, it cannot be the optimal prediction. Conversely, if is too likely, its parent (n) cannot be the optimal pre- diction either. Using these constraints, we efficiently filter out large portion of nodes and apply a simple brute-force algorithm to the remaining candidate set, which overall, drastically reduces time complexity.
Definition 4.1. Let C(n) be the leaf descendants of node n ni n E L. (() = {n.)). Then we define
(n) == P(y E [(n)(x = x)
Σ (1) IEC(M)
We refer to this quantity simply as the probability of n. For the sake of readability, we omit the pa notation and use p instead.
We organize our approach by distinguishing between differ- ent types of candidate sets H. proposing adapted strategies for each type of frameworks and metrics.
Definition 4.2. Let n E (r) and / E L. We call a metric C N x L + R hierarchically reasonable a metric satisfying the following properties:
4.1. Leaf candidate set
C(n, C(=(m), ifl ((C())
(2)
When H L. the evaluation metric compares only the predicted lcaf h with the ground-truth leaf y. This setup closely resembles a standard cost-sensitive classification problem, with the key difference being that hierarchical information is incorporated into the metric's definition. In this case, the optimal decision rule from Definition 1 is expressed as:
C(n, < C(T(n), if E C(n)
(3)
Equation (2) encodes the intuition that when the ground truth is Guitar, predicting Musical Instrument is better than predicting Piano. Similarly, Equation (3) implies that when the ground truth is Guitar, predicting Musical Instrument is better than predicting Object. Given p E A(C) and a metrie L. satisfying Equations (2) and (3), our objective is to find (p) E N, the optimal decoding strategy for p. As explained, for n E N, we derive conditions on p(n)) for or T()) to be sub-optimal:
(p(P)= = argmin
Σ (())C(h,I). IEC
KEC
Karthik et al. (2021) introduced this exact framework for the metric C 7LCA where VLCAA (h, 1) is the height in T of the lowest common ancestor (LCA) between h and 1. They proved that, if maxiec p()) > 0.5, then the opti- mal decision rule is the argmax over leaf nodes. In other cases, they perform a brute-force algorithm which results in O((C()) time complexity, assuming that the cost matrix (mLA (h, (a.eee c is computed beforehand.
Lemma 4.3. Let C NXL + R be hierarchically reasonable. For n E N (r), define 8% = C(n, C(T(n), the node-parent loss difference for label l and
M, max Ent > 0
mn = max dnt > 0 (E((n)
(EL(L(n)
M₁ min End >> 0
mn min 5nt > 0 (E2)C(m)
(E((n)
Then, for p A(C), have:
Additionally, for the Topl error metric defined Topl(h,w) wh, 1(h- * y). the optimal decision rule is the argmax over leaf nodes. We highlight this seemingly triv- ial result because this decoding strategy is frequently used to evaluate models with metrics beyond Topl, despite not being the optimal decision rule.
p(n) > M +ma G (n) = (p) # π (n)
M.
p(n) < m, M G (n) = (p) + n
in
We name these conditions after the concept of reasonableness introduced hy Elkan (2001)
4

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
Proofs are provided in Appendix E.1.1. It naturally follows that Vn E N, Emin (n) I (n). Here, gmin (n) and Imase (n) act as thresholds for p(n), allowing to remove portions of the hierarchy from the search space. Hence, Lemma 4.3 will be at the core of our general algorithm. However, it also allows us to derive closed-form solutions for specific metries: we recover two known results, which we detail below.
Algorithm 1 Theorem 4.4
1: function FINDOPTIMAL (leavess Imax Iwin
2:
p < PROBANODES (Plavee) D Definition 4.1
3:
S + FINDCANDSET(2, 9maxx Imin) D Leemma 4.3
4: Toopt f BRUTEFORCEES.
D (*)
5: return Rops
end function
This leads to an overall complexity of O(dmax - |C| + (I). The detailed proof provided in Appendix E.I.I.
4.2.1. 1. APPLICATIONS TO SPECIFIC METRICS
Tree distance loss. This metric denoted (h, y) is defined as the length of the shortest path between h and y in T. Here, Lemma 4.3 gives that the optimal decoding corresponds to the deepest node with p(n) > 0.5 (Ramaswamy et al., 2015), referred to as Majority decoding (Valmadre, 2022). Generalized tree distance loss. This metric is defined as (h, y) = (h, y) + c d(h), where d(h) denotes the depth of node h and с 2 0. Here, Lemma 4.3 shows that the optimal decoding corresponds to the deepest node with ++s (Cao et al., 2024).
There exist certain metrics that do not fully satisfy Equa- tion (2): it in fact implies that when the ground truth label is Piano, predicting a Cat is less severe than predicting a Persian Cat; however, some metrics treat these two incorrect predictions as equally severe. As a result, the condition (2) can be transformed to:
C(n.1) (((()..)) ifl ((((() and LCA(I, + r, C(n.l)= - C(+(n),
if ((A(m) and LCA(1, n) =r. (4)
p(n) > ?
Proofs are detailed in Appendix E.1.2.
We recall that LCA(n,,) 1) denotes the lowest common ances- tor of nodes n and l. Under constraints (3) and (4), Theo- rem 4.4 is still valid. The proof is detailed in Appendix 1.1.
4.2.2. GENERAL ALGORITHM
In the general case, where C' is defined via cost matrix ((th,,)) that is hierarchically reasonable, we propose an algorithm that improves upon the ((VV (C) brute-force search. The algorithm filters nodes using Lemma 4.3, followed by a brute-force search on the re- maining candidates. The size of the candidate set is (dmaa)) (x), where dmax is the depth Tf and in practice, dmax Fe log(LW)). This leads to the following theorem:
This transformation accommodates metries commonly used in practice, such as the Wu-Palmer metric (Wu & Palmer, 1994) and its information-theoortii extension (Zhao et al., 2017).
4.3. Subset of nodes decoding
The most general candidate prediction set, P(N), includes all subsets of nodes in N, with cardinality 2|M1 represent- ing a flexible framework, where one is allowed to decode one or more nodes. This particularly useful in scenarios involving hesitation between two or more nodes. However, this generality comes significant computational cost: the exponential growth of the space makes brute-force ap- proach infeasible, with a time complexity of O(2)A1. [C]). From a decoding strategy perspective, one might argue that P(V) contains redundancy. For example, both {Piano} and (Piano, Musical Instrument) belong to P(V),, yet they represent inherently the same prediction because Piano is included in Musical Instrument and therefore more specific. To address this, predictions can be restricted to those that contain mutually exclusive nodes. That is, predictions h C N such that:
Theorem 4.4. Let C be hierarchically reasonable and p E (f)), then the optimul decision rule (p((p) can be computed with an algorithm of O (dmax [C] + (VI) time complexity.
Sketch of the proof.
Key elements of the decoding strategy are displayed in Al- gorithm 1. We give here some general insights on how the algorithm is derived.
1. We begin with computing the probability distribution over the whole hierarchy, by bottom-up summation of leaf probabilities as in Definition 4.1. This can be performed by single tree traversal whose complexity is O(IN)).
2. We compute candidate set by pruning nodes that do not fulfill conditions enunciated in Lemma 4.3, This results in a candidate set whose cardinality is (dmaa).
V(n,, n2) E h, ni + n2 + ni $ A(n2) and na $ A(n1)
3. We perform brute-force search on the remaining can- didate set, whose complexity (ddmax O((4))
Here, A(n) denotes the set of ancestors of n in T (it is defined inclusively, with n E A(n)). We denote this re- stricted set as My(N). However, despite this restriction, the cardinality of (WW remains exponential:
FFor a complete binary tree. dmen = log, (IA1 | + 1) -
5

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
Proposition 4.5. For T = EN, where each non-leaf node has at least two children, the cardinality of (T(N)
We denote 2(p) {n N,, p(n) I+ (T) This condition alone is not sufficient to exhibit a polynomial- time algorithm. Following the approach in Waegeman et al. (2014), we decompose the problem into an outer and inner maximization based on the cardinality of he Combined with Lemma 4.6, this decomposition enables the formulation of a tractable algorithm for computing Shr, o (p).
satisfies [MT(N)] 2 2 - 1.
The proof is detailed in Appendix E.2.1.
Remark. As shown in Aho & Sloane (1973), for a complete binary tree of depth d, the cardinality of MM (AV is given by
[MT(NV] |g] 2 2 [1 W1+1, where q = 1.502873.
Theorem 4.7. Let dmaa = maxieg d(l) be the leaf nodes maximum depth. Let p E A(C), then the optimal deci- sion rule Sby, (p) can be computed with an algorithm of O ( (WI) time complexity.
We hence focus on designing algorithms that address this issue without relying on brute-force approaches. In such scenarios, it becomes notably harder to design general al- gorithms that are agnostic to the choice of the metric. For example, Bi& & Kwok (2012) derived optimal decoding al- gorithms for a family of losses called HMC-loss. Here, we focus on the 3-core, family of metries that bal- ances precision and recall through the parameter B, which controls the level of emphasis on either metric. It is natu- ral extension of the Fg-score in the context of hierarchical classification (Kiritchenko et al., 2006; Kosmopoulos et al., 2014), and it has been shown to exhibit desirable proper- ties (Amigo & Delgado, 2022). This set-based metric is computed by considering the cardinalities of overlap be- tween the predicted set and the ground truth label. Specifi- cally, the predictions and ground truth are augmented with their ancestors as follows:
Sketch of the proof.
The algorithm is based on the following result:
Sür, (p) = argmax 1 ((()) (EM nEA | k(p())
argmax
Σ
1(n E (n)
where:
[2()) = (d
p(1) 1-3ا (d)+))
The idea is straightforward: for each k E {l...., [Q())
select the k nodes belonging to Q(p) with the highest (n). The algorithm is thus a for-loop with most (flmaax) iterations. Each iteration involves:
Computing (A)(m) Te)(P) which can be done via a single tree traversal, i.e., in ((VV))
hraug U A(n) and yo = A(v)
neh
Then, the hF, 1 s-score is defined follows:
Selecting the top-k nodes with highest (2()) which is also ((W7)..
hPr(h, = 1 O y
use n y
hRo(h, y)
h
Hence, the total complexity is Oddrax -WI. Detailed proofs are given in Appendix E.2.4.
1 + g2
hF (h v)
kRe(h.yj + hPE(h.))
12
Summary of Contributions. In the case where the can- didate set is H. = N, we derived an O'dmax - [2] + IWT) algorithm, significantly faster than the O(N CI brute- force search, applicable to any hierarchically reasonable metric (a condition generally met practice). In the most general case, where H = P(N), the brute-force search becomes exponential, and we derived an algorithm with time complexity O [ddxx IW(),, finding the optimal predic- tion with respect to the hF's scores. Equipped with these algorithms, we now evaluate their practical efficiency.
As hF, only uses hame, we get the intuition that various predictions may be redundant; in fact, the search space can be restricted to (M) (see Appendix E.2.3 for full explanations). The task, therefore, is to find the optimal decision rule for the metric hFg. which is given by fiF," A(C)- + MMT(N,, where:
Ehr argmax E(()) (h0 (h,
(EM IEc
Remark. This time, our objective is to maximize expected utility, whereas we previously focused on minimizing ex- pected cost.
5. Experiments
Similarly to Lemma 4.3 we first derive a condition on node probability. The intuition is the same: if p(n) is too small, cannot be an element of Shr a (p).
5.1. Evaluation methodology
Although our proposed decoding strategies are proven to be optimal for the oracle probability distribution, trained models only approximate it. We therefore empirically assess the performance of our strategies against cxisting decodings. To evaluate the effectiveness of our approach, we first select hierarchical datasets, and define the evalua- tion metrics to optimize. Using trained models, we infer
Lemma 4.6. Let P A(C) and n M and dmaa (n) max)e((m) d(l) the leaf nodes maximum depth among leaf descendants of n. Then, hF's
p(n) < (+,82(dmm(()) (n)+1) := 4min (n) = n & Shp, (p)
6

---

To Each Metric Its Decoding: Post-Hocc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
Pretrained on Imagenet
Finetured on Imagenet-Hf
Finetured on Inat19-H
score
hF2 score
hF0.5 score
Optimal (ours)
Deng (2012)
Expected
Pluraiity
Jain al. (2023)
Argmax
Top Down
Majonity
4%
2%
0%
2%
4%
Wu-Palmer Similarity
Zhao Similarity
Tree Distance Loss
Optimal (ours)
Deng (2012)
Expected Info.
Pluraiit
Jain (2023)
Argnax
Top Down
Majonit
Majority is the Inptinal Decoding
-10% 0%
20% -00%
-10%
10% 20%
20%
-10%
10%
20%
Figure 2: Relative Gain (in %) of Decoding Strategies. Each dot represents the relative gain of the optimal strategy the average over all other strategies for a specific metric and model on the set of given dataset, with symbols indicating dataset: for models pretrained ImageNet, * for models fine-tuned on ImageNet-H, and models fine-tuned on iNat19. Boxplots summarize the distribution of relative gains for each decoding strategy. The higher the gain, the better the decoding strategy. Results are reported for six metrics across various model architectures trained on three datasets.
probability distributions for each input instance the test set. We then apply our optimal decoding strategy alongside commonly used heuristic strategies for comparison. Finally, assess and compare the average performance of all decoding strategies across the test set. We list below the datasets, models, metrics and heuristics used. The detailed experimental setup can be found in Appendix D.1.
Table 1: Key statistics of the selected datasets.
Dataset
Nb. leaves
Nb. of nodes
dmax
Test set size
TieredImageNet-H
608
843
12
15,200
Inat-19-H
1010
1190
40,737
tions of Bertinetto et al. (2020), also fine-tune ResNet- 18 architecture on both datasets using different loss func- tions. Specifically, we employ the hierarchical cross-entropy loss and soft label methods proposed by Bertinetto et al. (2020), a YOLO-v2 conditional softmax cross-entropy loss (Redmon Farhadi, 2017), embedding methods from Barz & Denzler (2019), and standard cross-entropy loss. Metrics. We use several widely adopted metrics in hierarchi- cal contexts. These include Tree Distance Loss, for which an optimal decoding is available in closed form (Ramaswamy et al., 2015), the Wu-Palmer metric (Wu & Palmer, 1994) and its cnermatiiontheoretie extension (Zhao et al., 2017), for which we apply Theorem 4.4, and hF for 3 E 0.5, 1, 2, for which we leverage Theorem 4.7. All definitions of met- ries are available Appendix C.I.
Datasets. While our approach can be applied any kind of data, we solely rely this work on computer vision datasets, due the complexity of their label hierarchy and the availability of appropriate models. Specifically, we utilize TieredImageNet-H and iNat19. Introduced by Bertinetto et al. (2020) together with properly defined hi- erarchy trees, these datasets, summarized in Table 1, are respectively subsets of ImageNet-14 1k (Deng et al., 2009) and iNaturalist-19 19 (Van Horn al., 2018).
Models. Given that TieredlmageNet-H is subset of ImageNet-16 K, existing pre-trained models can be directly used. We select 10 models from the PyTorch library, which are listed in Appendix 1.1.2. Following the recommenda-
Decoding Heuristics. A variety of decoding heuristics have been proposed, often using the node information

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
hF1 score
hF2 score
hF0.5 score
pd
0%
M
-5%
P2
p4 0.57
Relative gain
-10%
-15%
03 0.30
20%
0.50
-2%
Optinal
Paralit
Agrrax
p2
p3
-30%
Deng st 2002)
Karthk all (2001)
Tea-foown
Espected Info.
Jain et (2023)
Majority
Figure 3: Agreement map on the simplex of R for two decoding strategies. For hierarchy with three leaf nodes displayed the top-left corner, this tigure shows the agreement map between 1t'; and Majority decoding: each point in the simplex is color-coded, green dot indicates equality of the two predictions, while red dot indicates disagreement.
-35%
0
10
5 Blur level
10
10
Figure 4: Impact of blurring on the sub-optimality of heuristic decodings. This figure shows the relative performance decrease (in %) of heuristics compared to the optimal decoding for the hF 3-core,, with 8 E {1, 0.5, 2,2,, as a function of the blur level. Results are averaged across multiple models and datasets, with 95% confidence interval displayed for each decoding strategy.
((n) = log( [(m]]] be categorized into leaf-node decoding and any-node decod- ing strategies. Leaf-node decoding strategies include:
[C]
to define these strategies. These can
that, regardless of the dataset, model, or training algorithm used, applying the optimal decoding strategy is always ad- vantageous. Appendix D.2. demonstrates the univeuniversal superiority of optimal decoding algorithms. Moreover, our decoding algorithms exhibit reasonable time complexity (a few μa8 per sample). More details can be found on this topic in Appendix D.3. For the selected hierarchies, when H = NV, our algorithms are, on average, 60x faster than a brute-force approach. Furthermore, when H = P(N), our algorithms efficiently solve problems that are intractable using brute-force methods.
1. a argmax i.e. {()) = argmax(ez p()), which selects the leaf node with the highest probability
2. Leaf optimal decoding for TLCA (Karthik et al., 2021)
3. HiE-self, E(p) argmaX p(T(()))pp)) -p(),, combining parent probabilities p(T(()) with leaf probabilities p(l) (Jain et al., 2023)
4. top- top-down, which selects a leaf node by performing a top-down traversal of the hierarchy, choosing the most likely nodes from the root to the leaf level.
Any-node decoding strategies include:
Another noteworthy aspect is the behavior of the non- optimal heuristics. We differentiate between leaf-node heuristics, which always predict a leaf node, and node heuris- tics, which can predict both internal and leaf nodes. Leaf- node heuristics are more -oiil-orreeted,, i.e. they predict leaves which increases their ability to capture the correct leaf label but also leads more errors. In contrast, node heuristics more conservative and mrecision-oriented cap- turing the most specific class less often but with fewer errors. This trade-off is quantified by the f-score, where 3 = 2 gives twice as much importance to recall as to precision. As a result, leaf-node heuristics, such as argmax, top-down, Karthik et al. (2021), and Jain et al. (2023), are more com- petitive among non-optimal decoding strategies under this setting. However, when precision becomes more impor- tant (8 = 0.5), node heuristics, such as Deng et al. (2012), Expected Information, and Majority, perform better.
5. Majority Rule: (p) = argmax,eeN' I(n) p(n) >
0.5, selecting the most informative node with p(n) 0.5 (Valmadre, 2022)
6. Plurality Rule, {(p) = argmax,EN [(n) s.t. V2 E A(n),, p(n) > p(z), selecting the most informative label more likely than any non-ancestor (Valmadre, 2022)
7. Darts Algorithm, (x( argmax, (I(n) + X)p(n). balancing information (()) and confidence p(n) with a parameter X (Deng et al., 2012)
8. Expected Information, maximizing expected infor- mation by setting À= = 0 in the Darts Algorithm
Heuristic (7.) requires an held-out set to tune its parameter. Currently, no heuristic explicitly addresses decoding sets of nodes, and our attempt based on Lemma 4.6 yielded poor results.
Nonetheless, the relative gains of the optimal strategy re- main modest: from 1% to 5% for all metrics except Mistake Severity, which achieves relative gain of 10%. In practice, we observe that, for a given data point, optimal predictions often align with heuristic predictions. This is expected: when the model is nearly 100% confident that the label is Piano, any reasonably designed heuristic will predict Piano.
5.2. Analysis
Each plot in Figure 2 illustrates the performance of various decoding algorithms across different datasets and models. A clear takeaway is the consistent superiority of optimal decoding algorithms across all evaluation metrics. It means
8

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
Disagreements arise when the entropy of the predicted prob- ability distribution increases.
6. Conclusion
In this work, we addressed the challenge of optimal decod- ing in hierarchical classification tasks. Given a predefined hierarchical evaluation metric and a posterior probability distribution over leaf nodes, our goal was to identify the best possible prediction. To this end, we developed universal algorithms for hierarchically reasonable metrics when the prediction set is restricted to the nodes of the hierarchy. Ad- ditionally, we introduced a decoding algorithm specifically tailored hF hhF---som g-scores Our empirical results demonstrated the effectiveness of these optimal decoding strategies, specif- ically in underdetermined classification tasks.
We provide an intuition for this phenomenon in Figure 3. For simple hierarchy with five nodes, including three leaf nodes, the figure displays the agreement map between the optimal decoding strategy and the Majority Rule heuristic. We observe that when the probability distribution is skewed towards one of the leaf nodes, both strategies tend to agree. However, as the distribution approaches the center of the simplex, disagreements become more frequent. This sug- gests that the more underdetermined the problem becomes, the greater the overall relative performance gain from using optimal decoding strategies. While some domains exhibit greater intrinsic randomness (e.g., medicine), we propose an experiment in which we artificially introduce randomness into a computer vision task by progressively blurring the in- put images. As the images become increasingly blurred, the image features become less predictive, causing the posterior probability distribution to approach the center of the sim- plex. We expect to find more disagreements, thus increasing performance gap between optimal decoding and heuristics.
Future work could explore extending framework to non- tree hierarchies. Additionally, this study does not tackle the challenge of accurately predicting the posterior probability distribution. A promising direction would be to incorpo- rate cost-sensitive learning during training, as suggested in prior work (Ramaswamy et al., 2015; Cao et al., 2024), or to develop post-hoc recalibration methods that provide guarantees on the estimated probability estimation.
5.3. Blurring the images
Impact Statement
We propose an experimental setting in which we keep the exact same models introduced in Section 5.1, trained on the same datasets. However, these models are evaluated on modified test sets in which imputs images are progressively blurred. In Figure 1, we illustrate the effect of gradually blurring an input image on the decision-making process. The model used is VGG11 (Simonyan & Zisserman, 2014), and the input image is labeled as a golden retriever. Under the hF -ccore optimal decision rule, the prediction transi- tions from golden retriever to hunting dog, which remains correct but less specific. A similar pattern is observed for majority decoding; however, the highest level of blurring, the prediction becomes carnivore reflecting an even coarser classification. In contrast, argmax decoding consistently produces highly specific predictions but fails on the last two levels of blurring, yielding incorrect results. As decodings tend to disagree more, we expect that relative performance of heuristic decodings will gradually decrease with the level of blur, relatively to optimal one. Figure illustrates the relative drop in performance compared to the optimal de- coding strategies for hF g-soress, averaged across datasets and models. As expected, the blurrier the image, the greater the relative decrease in performance. This confirms our intu- ition: for an underdetermined problem, it is important to use appropriate decoding strategies when aiming at optimizing target hierarchical metric.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
A Acknowledgments
The authors would like to thank Clémence Grislain and Nathanaäl Beau for their thorough review of an earlier ver- sion of this paper and their valuable feedback. They also thank Jean Vassoyan and Pirmin Lemberger for insightful discussions during the development of this work.
References
Aho, A. V. and Sloane, N. J. A. Some doubly exponen- tial sequences. Fibonacci Quarterly, (1(4):499433) 1973. URL https::////// http:///ww....t..cc.... htt.mmathh../aaanneddd 11-4/ 1144//ho-aapp a.pdf.
Amigo, E. and Delgado, A. Evaluating extreme hierarchical multi-label classification. In Muresan, S., Nakov, P., and Villavicencio, A. (eds.), Proceedings the the 60th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp. 5809-5819 Dublin, Ireland, May 2022. Association for Computational Linguistics. doi: 10. 100118633/110022.ccccccoo 399. URL https: // acl.anttollooy..rg22222...---
Ashburner, M., Ball, C. A., Blake, J. A., Botstein, D., Butler, H., Cherry, J. M., Davis, A. P., Dolinski, K., Dwight, S. S.,
9

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hierarchical Classifiers
Eppig, J. T., et al. Gene ontology: tool for the unification of biology. Nature Genetics, 25(1):25-29, 2000.
Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., and Fei-Fei, L. Imagenet: A large-scale hierarchical image database.
In 2009 IEEE Conference Computer Vision and Pat- tem Recognition (CVPR), pp. 248 118-255. IEEE, 2009.
Barz, B. and Denzler, J. Hierarchy-bast based image embeddings for semantic image retrieval. 01 2019. doi: 10. 109/ WACV 2EEV.201900007.
Deng, J., Krause, J., Berg, A. C., and Fei-Fei, L. Hedging your bets: Optimizing accuracy sppeiiiccitpciiiiitty trade-offs in large scale visual recognition. In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pp. 3450- 3457, 2012. doi: 10. 10.1109/CRR..2022.22
Berger, J. O. Statistical Decision Theory and Bayesian Analysis. Springer Series in Statistics. Springer, New York, 2nd edition, 1985, ISBN 978-0387960982. doi:
Domingos, P. Metacost: A general method for making classifiers cost-sensitive. In Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 155-164 ACM, 1999. doi: (0.1145/312129.3122
Bertinetto, L., Mueller, R., Tertikas, K. Samangooei, S., and Lord, N. A. Making better mistakes: Leveraging class hierarchies with deep networks. In The IEEE/CVF Conference on Computer Vision and Puttern Recognition (CVPR), June 2020.
Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer,
Bi, W. and Kwok, J. T-Y. Hierarchical multilabel classifica- tion with minimum bayes risk. 2012 IEEE 12th Interna- tional Conference on Data Mining, pp. 101-110, 2012. URL https: / //tpp//smmmmmicccccc....r.r
M., Heigold, G., Gelly, S., Uszkoreit, J., and Houlsby, N. An image is worth 16x16 words: Transformers for image recognition scale. International Conference Learning Representations (ICLR), 2021.
CorpusTD:108599::
Duda, R. and Hart, P. Pattern Classification and Scene Analysis. Wiley, New York, 1973.
Cao, Y., Feng, L.,, and An, B. Consistent hierarchical clas- sification with a generalized metric. In Dasgupta, S., Mandt, S., and Li, Y. (eds.), Proceedings of The 27th International Conference Artificial Intelligence and Staristics, volume 238 of Proceedings of Machine Learn- ing Research, pp. 4833. PMIR, 02-04 May 2024. URL http::://pprcceeenns.lspp.ppppo //333 cao24a.html.
Elkan, C. The foundations of cost-sensitive learning. In Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI), pp. 973-978. Mor- gan Kaufmann Publishers Inc., 2001. URL https: // //caeeeb.usdd.edu//el.....
Garg, A., Sani, D., and Anand, S. Learning hierarchy aware features for reducing mistake severity. In European Con- ference on Computer Vision, pp. 252-267. Springe, 2022.
Chang, D., Pang, K., Zheng, Y., Ma, Z., Song, Y.-Z., and Guo, J. Your "flamingo" is my "bird": Fine-grained, or not. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 11476-11485, June June 2021.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
Chawla, N. V., Bowyer, K. W., Hall, L. O., and Kegelmeyer, W. P. Smote: Synthetic minority over-sampling technique. In Journal of Artificial Intelligence Research (JAIR), vol- ume 16, pp. 321-357, 2012.
He, R. and McAuley, J. Ups and downs: Modeling the visual evolution of fashion trends with one-class collabo- rative filtering. In Proceedings of the 25th International Conference on World Wide Web, pp. 507-517. Interna- tional World Wide Web Conferences Steering Committee, 2016.
del Coz, J. J.. Diez, J., and Bahamonde, A. Learning nondeterministic classifiers. Journal of Machine Learn ing Research, 10(79):2733-2293, 2009. URL http: //
Huang, G., Liu, Z., Van Der Maaten, L., and Weinberger, K. Q. Densely connected convolutional networks. Pro- ceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
http:///wwwo/ccc1000//ttm coz09a.html
Dembezynski, K., Cheng, W., and Hüllermeier, E. Bayes optimal multilabel classification via proba- bilistic classifier chains. In International Confer- ence on Machine Learning, 2010. URL https:
Jain, K., Karthik, S., and Gandhi, V. Test-time amend- ment with a coarse classifier for fine-grained classifi- cation. In Thirty-seentth Conference on Neural In- formation Processing Systems, 2023. URL https: / //openreviee..o wwtp://e..eee//rrrooeo d= QG8qGxso.
6418797.
10

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
Jansche, M. A maximum expected urility framework for binary sequence labeling. In Zaenen, A. and van den Bosch, A. (eds.), Proceedings of the 45th Annual Meet- ing of the Association of Computational Linguistics. pp. 736-743, Prague, Czech Republic, June 2007. Asso- ciation for Computational Linguistics. URL https: aaacllancholoog.org/eeeee 1093//
Plaud, R., Labeau, M., Saillenfest, A., and Bonald, T. Re- visiting hierarchical text classification: Inference and metrics. In Barak, L. and Alikhani, M. (eds.), Proceed- ings of the 28th Conference on Computational Natu- ral Language Learning, pp. 231-242, Miami, FI., USA, November 2024, Association for Computational Linguis- tics. doi: 10. 10.186653/1/22044coolll 1.18. URL https: / //aclaatthollog..rr//2222..o0
Karthik, S., Prabhu, A., Dokania, P. K., and Gandhi, V. No cost likelihood manipulation at test time for making better mistakes in deep networks. In International Conference on Learning Representations, 2021. URL https: openreview.net/ forum? id=1d1111 93sEnkY11j.
Quevedo, J., Luaces, O., and Bahamonde, A. Multilabel classifiers with a probabilistic thresholding strategy, Pat- tern Recogn., 45:876-888 01 2011.
Ramaswamy, H.. Tewari, A., and Agarwal, Convex calibrated surrogates for hierarchical classification. In Bach, F. and Blei, D. (eds.), Proceedings of the 32nd International Conference on Machine Learning, vol- ume 37 of Proceedings of Machine Learning Research, pp. 1852-1860, Lille, France, 07-09 Jul 2015. PMLR. URL https: : httess///ppopdeeee wag.ccedding.mi..pree..... r rama swamy 5.html.
Kiritchenko, S., Nock, R., and Famili, F. Learning and eval- uation the presence of class hierarchies: Application to text categorization. volume 4013, pp. 395-406, 06 2006. ISBN 978- 77778---440-22004- doi: 10.1007/11766244 34.
Kosmopoulos, A., Partalas, I., Gaussier, E., Paliouras, G., and Androutsopoulos, I. Evaluation measures for hi- erarchical classification: a unified view and novel ap- proaches. Data Mining and Knowledge Discovery, 29 (3):820-865, sep 2014. doi: 10. 10.10077/110118-014-0033 URL https:/ /ttp//iiiogg./o///// (as.oogg/10.100722222222.2. 014-0382-x.
Redmon, J. and Farhadi, A. Yolo9000: Better, faster, stronger. In 2017 IEEE Conference on Computer Vi- sion and Pattern Recognition (CVPR), pp. 6517-6525, 2017. doi: 10. 10.1109/CVPR.2017..
Ren, M., Triantafillou, E., Ravi, S., Snell, J., Swersky, K., Tenenbaum, J. B., Larochelle, H., and Zemel, R. S. Meta-learning for semi-supervised few-shot classifica- tion. In International Conference on Learning Repre- sentations, 2018. URL https: //s:://arxaa http://wwx..rrr/////////////.o.t abs/ 1 1803.00676.
Krizhevsky, A., Sutskever, I., and Hinton, G. E. Imagenet classification with deep convolutional neural networks. 2012.
Lewis, D. D. Evaluating and optimizing autonomous text classification systems. In Proceedings of the Interna- tional ACM Conference on Research and Development in Information Retrieval (SIGIR), pp. 246-254, 1995.
Simonyan, K. and Zisserman, A. tional networks for large-scale image recognition. arXiv preprint 1rXiv:1409.1556 2014.
Very deep convolu-
Lin, T.-Y., Goyal, P., Girshick, R., He, K., and Dollár, P. Focal loss for dense object detection. 2017 IEEE International Conference on Computer Vision (ICCV), pp. 2999-3007, 2017. doi: Nt.1109/CCC.22017.00
Smith, J. Decision Analysis: Principles and Practice. Cam- bridge University Press, 2005.
Szegedy, C., Vanhoucke, V., loffe, S., Shlens, J., and Wojna, Z. Rethinking the inception architecture for computer vision. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
Liu, Z., Hu, H., Lin, Y., Yao, Z., Xie, Z., Wei, Y., Ning, J., Cao, Y., Zhang, Z., Dong, L., Wei, Y., and Guo, B. Swin transformer v2: Scaling up capacity and resolution. arXiv preprint xxXv:2111.09883 2022a.
Tan, M. and Le, Q V. Efficientnetv2: Smaller models and faster training. arXiv preprint arXiv:2104.00298 2021.
Liu, Z., Mao, H., Wu, C.-Y,, Feichtenhofer, C., Darrell, T., and Xie, S. A convnet for the 2020s. Proceedings of the JEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2022b.
Valmadre,
Hierarchical classification at multiple operating points. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 18034-18045 Curran Associates, Inc., 2022. URL https://prooeeedigg..eeez. eaper_filees/paper/2222//11 72 2275cc1dfBB2211dB841122aaalllll Paper-Conferenceepd.
Petrides, G. and Verbeke, W. Cost-sensitive ensemble learn- ing: a unifying framework. Data Mining and Knowledge Discovery, 36, 01 2022. doi: 10. 10.1007/s10611 --011-00790-

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
Van Horn, G., Branson, S., Farrell, R., Haber, S., Barry, J., Ipeirotis, P., Belongie, S., and Perona, P. The inaturalist species classification and detection dataset. In Proceed- ings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 8769-8778, 2018.
Viola, P. and Jones, M. Fast and robust classification using asymmetric adaboost and a detector cascade. In Advances in Neural Information Processing Systems (NIPS), vol- ume 14, pp. 1311-, 2001.
Waegeman, W., Dembezyíski, K., Jachnik, A., Cheng, W., and Hüllermeier, E. On the bayes-optimality of f-measure maximizers. Journal of Machine Learning Research, 15(103))3513-3568, 2014. URL http://t/////. /mlr..rrg httpa/s//v/wwwaeeene.ee Aaaaegeman44.hhm... 4a.html.
Wang, Y., Hu, Q.. Zhou, Y., Zhao, H., Qian, Y., and Liang, J. Local bayes risk minimization based stopping strategy for hierarchical classification. In 2017 IEEE International Conference on Data Mining (ICDM), pp. 515-524, 2017. doi: 10.1 2009/IDM.2017..66
Wu, Z. and Palmer, M. Verb semantics and lexical selec- tion. In Proceedings of the 32nd Annual Meeting of the Association for Computational Linguistics, pp. 133-138, Las Cruces, New Mexico, USA, 1994. Association for Computational Linguistics. doi: 10.31155/98113329988711
URL https::ttt.. http://acaaanncoooooooo///////// 19199
Zadrozny, B. and Elkan, C. Learning and making deci- sions when costs and probabilities are both unknown. In Proceedings of the Seventh ACM SIGKDD Interna- tional Conference on Knowledge Discovery and Data Mining, KDD '01, pp. 204-20 213, New York, NY, USA, 2001. Association for Computing Machinery. ISBN 1581 13311X https: doi: 10. 10.1145/552512.502544..
URL
Zhao, H., Torralba, A., Torresani, L.,, and Yan, Z. Open vocabulary scene parsing. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), pp. 2002-2010. IEEE, 2017, doi: AL110//CCV.2211.222 URL https:// httppss//ppnnccess.eeee...c wtt.tttcccc..211pppppce. Zhao Owwo..pee.... Vocabulary Scene ICCV 2017 p...ppppr...f.
12

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
Appendices
A. Notations
We display in Table A. the list of notations we use throughout the manuscript.
Math Symbol
Domain
Description
N
Set of nodes in the hierarchy Set of leaf nodes in the hierarchy
C
E
N X N
Set of edges
T (N.E)
Hierarchy Tree
P(N)
Power set N
X
Input domain
X
Random variable representing the input features
C
Random variable representing the label
P
X x L +
[0.
Joint probability distribution.
N
A node
1
C
A leaf node
N
The root node
(n)
.V
unique parent of in T Set of children of n in T Set of ancestors of in T (defined inclusively) Set of leaf descendants of n
C(n)
P(N)
A(n)
P(N)
[(n)
P(N)
1(n)
=log( C(n)
Information node n
Depth of node n in T
d(nz)
N
Defined as the length of the shortest path between n and r in T
dma (n))
N
max d(l). Max depth of leaf descendants of
IE((m)
dmax
=max d(l). Max depth of leaf nodes lEC
deai
N
=mim d(l). Min depth of leaf nodes IEL
LCA
N² + N
Lowest common ancestor of two nodes.
(CC)
Simplex over C Set of candidate prediction
H
[C,N, P(N))
H
A prediction.
C
H. x L + R
An evaluation metric that compare a prediction / to a ground truth I.
A(C) + *H
A decision rule
=argmin > pp(()C(h,1) hCh lEC Optimal decision rule for metric C' and proba
A(C) + H.
P(| = x)
(1)
[0.1]
Posterior probability of class for input x
Eiec(,) P(||x xx =x)
(n)
[0.1]
Posterior probability of class for input
hang
P(N)
U A(n)
nEh
MT(N)
P(P(N))
(h P(N), n1. 12
LCA(n1, n2) =
Uy (N)
P(P(N))
thTE h M
Table A.I: Notations used in the manuscript
13

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
B. Limitations
While our algorithms demonstrate significant improvements over straightforward heuristics specific contexts, it is natural ask whether these empirical findings extend to other types of data. In this work, we focus on image datasets due the abundance of pretrained models and well-established benchmarks in the vision domain. Exploring other modalities -such as text data- remains important direction for future work, but falls outside the scope of this work.
Another important aspect we did not address is the accurate estimation of the posterior probability distribution. As discussed in the conclusion, promising direction for future work is to incorporate hierarchical cost-sensitive learning during training or to develop post-hoc hierarchical recalibration methods that could offer theoretical guarantees on the quality of the estimated probabilities.
C. Additional Content
C.1. Metrie Defintion
We recall that evaluation measure for set 7 of candidate predictions is function that quantifies the misclassification costs as follows.
Definition C.1. Evaluation Measure. An evaluation metric for set of candidate predictions function that quantifies the misclassification costs:
C: C: C (h, 3) C(h
where the prediction and y the ground-truc leaf label.
C.1.1. =
Here, we provide examples of metrics for the case when He
Lowest Common Ancestor (LCA) Height:
TLCA (h, y) = Height of the lowest common ancestor between h and y in T.
Top-1 Error:
Top1(h, v) = 1(h + v).
where 1(:) the indicator function.
C.1.2. H N
For H = N. we list example of used metrics:
Tree Distance Loss (Ramaswamy et al., 2015):
DL y) Length of the shortest path between h and y in T.
Generalized Tree Distance Loss (Cao et al., 2024):
DI, v) DL(h,y) + c. d(hh)
where d(h) is the depth of node in T.
Wu-Palmer Similarity (Wu Palmer, 1994):
Ded(LCA(,, v))
wP(h,y) = d(h) + d(y)
Zhao Similarity (Zhao et al., 2017):
2 I(LCA(h, v)) ZS(h, v)
1(h) + 1(y)
where I(-) represents the information content node.
14

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
C.1.3. - For H. = P(V), we list below example of such metrics:
Hierarchical F-score ghF
1 + B3
hF (h,
A2
hRe(h.y)
hPr(h.y))
where
m n y hnan
m n y
hPr(h,
hRe(h,
gog
Hamming Loss:
(1 U yu \ (hang O y your
HL(,,
Jaccard Similarity:
1h n y Jaco(h,y)
hhawg U your
C.2. On the Uniqueness of (p)
In the main manuscript, defined the optimal decision rule for A(C) and evaluation measure C follows:
Definition C.2. Optimal Decision Rule. The optimal decision rule for the metric C H C R is given by
E (ff) H. where
(p) = argmin Σ (()))((,.).. NEH IEC
(6)
First, note that the argmin is well-defined, as is non-empty and finite, ensuring the existence at least one minimizer. However, we have no theoretical guarantee that (2-(p) uniquely defined, since multiple elements H may attain the minimum. In practice, this ambiguity is not problematic. multiple optimal predictions exist, one can simply select one at random, they all yield the same expected risk. When dealing with expected probabilities this random influence the estimation of the performance, however, such cases rare in real-world scenarios. When working with estimated probabilities, ties between optimal predictions never occur.
15

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
D. Detailed Experiments
D.I. Experiment setup
D.1.1. DATASETS
We give here additional details on how datasets were constructed.
tigred Original magee was introduced by Ren et al. (2018) for few-shot classification. Original version features disjoint class splits based on the WordNet hierarchy and was designed to assess few-shot classifiers Then Bertinetto et al. (2020) adapted it for standard image classification, resampling it to include all classes across train, validation, and test splits. They chose this dataset because it covered large part of the 1, 0,000 classes of ImageNet. Additionally, they slightly modified the WordNet graph to turn it into tree. This resulted in tree of 843 nodes, including 608 leaf nodes and a depth of 12. This version is referred to as tieredImagNNe--I..
1Nat19. NNtturalist-99 19 (Van Horn et al., 2018) is a dataset of organism images primarily used for evaluating fine-grained visual categorization methods. It was introduced with hierarchical species relationships, providing an 8-level complete tree spanning 1010 leaf node classes which was directly usable. Since test set labels are not public, Bertinetto et al. (2020) re-sampled it into three splits (70% training, 15% validation, 15% test) from the original train and validation sets.
D.1.2. MODELS
Pretrained Models. We leverage 10 pretrained models from the PyTorch library, including Swin Transformer V2 (Liu et al., 2022a), VGG-11 (Simonyan & Zisserman, 2014), AlexNet (Krizhevsky et al., 2012), EfficientNet V2-S (Tan & Le, 2021), ConvNeXt-Tiny (Liu et al., 2022b), Re (He et al., 2016), DenseNet-121 (Huang et al., 2017), Vision Transformer (ViT-B/16) (Dosovitskiy et al., 2021), and Inception V3 (Szegedy et al., 2016). While these models could be directly evaluated on ImageNer-Ik using the original WordNer hierarchy, we opted to evaluate them on tieredlmageNet-Ii the aformentionned subset of ImageNet-1k, 1k. Unlike ImageNet-Ik, Ik,, tieredImageNeetHH spans 608 classes instead of the original 1, 0000 To generate probability distributions over the 608 leaf nodes of the fieredImageNet-H hierarchy, we adopted a straightforward approach: for each model and input, we extracted the logits corresponding to the 608 leaf nodes and applied a softmax function. This process yields a valid probability distribution over the Ieaf nodes.
Finetuned Models. As explained in the core of the manuscript we follow the recommendations of Bertinetto et al. (2020) and follow-up works (Karthik et al., 2021: Jain et al., 2023; Garg et al., 2022: Valmadre, 2022) by finetuning a Resnet- 18 architecture with various learning strategies. We detail them here. Bertinetto et al. (2020) propose two hierarchy-aware loss modifications: Hierarchical Cross-Entropp weights misclassifications based on their distance in the class hierarchy (it has an hyperparameter a > 0), while Hierarchical Smoothing assigns non non-zero probabilities to related classes to smooth the target distribution. We also use the YOLO-v2 conditional softmax cross-entropy loss (Redmon & Farhadi, 2017), which computes localized softmax. Additionally, we utilize embedding methods from Barz & Denzler (2019), which map class labels into a embedding space to capture semantic relationships between classes. Finally, we use also a standard cross-entropy loss.
1.3. METRICS
As briefly explained in the core of the text. We use 6 different widely used metrics. We list them below together with their optimal decoding strategy.
Tree Distance Loss:
DL u) = Length of the shortest path between h and y in T.
Optimal Decoding Strategy: Majority Decoding: :
{D)(p) argmax I I(n) s.t p(n) 2 0.5 (Ramaswamy et al., 2015)
neN
Wu-Palmer Similarity (WP):
wP(h,)) 2 2-d(LAA(h.u)) v)) d(h) +d(y)
Optimal Decoding Strategy: Use Theorem 4.4. Zhao Similarity (7S)):
ZS(h, v) = 2 I(LCA(h,,))) 8))
I(h) (vv)
16

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
Optimal Decoding Strategy: Use Theorem 4.4.
Hierarchical F-Score for B {0.5, 1,2)
1 _
(h)(h,
8a hRe(h.y)
hPP(h.y)
Optimal Decoding Strategy: Use Theorem 4.7.
1.1.4. DECODING HEURISTICS
A variety of decoding heuristics have been proposed to leverage class hierarchy information during decoding. These heuristics can be categorized into strategies for decoding leaf nodes and those for decoding any node.
Leaf-Node Decoding Strategies:
These heuristics focus on selecting leaf node from the hierarchy:
Leaf Argmax:
E(p) = argmax p()),
iEC
Karthik al. (2021). This method optimally decode for the 7LCA metric.
HiE-self (Jain et al., 2023):
E(p) arginax p(T(1) p()).
lEC
Any-Node Decoding Strategies: These heuristics allow for selecting nodes at any level of the hierarchy:
Confidence Threshold (Valmadre, 2022):
E (p) = argmax [(n) s.t. p(n) > T
neN
Majority Rule:
Confidence Threshold with T 0.5
Plurality Rule (Valmadre, 2022):
(p)) argmax I(n) s.t. V2 e e A(n), p(n) > p(2),
neN
Darts Algorithm (Deng et al., 2012):
Ex(p) argmax (L(n) + -m)),,
neN
Expected Information:
Darts Algorithm with 0
D.2. Detailed results of decoding performance
In this section we provide detailed results about the performance of all decoding strategies for all models, datasets and metrics. We display it Table D.I the performance of each decoding and for each model and dataset for the Mistake Severity metric, in Table D.2 for the Wu-Palmer similarity metric, in Table D.3 for the Zhao similarity metric and in Tables D.4, D.5 and D.6 the results for 3-sore for 3 E {0.5,1,2)
D.3. Time Computation Analysis
In Table D.7, we provide insights into the time taken by different decoding strategies, with particular focus the time required for optimal decoding strategies introduced by our newly proposed algorithms. As mentioned in the main text, all optimal decoding strategies exhibit reasonable inference times. The worst-case scenario is observed for the optimal decoding of the Zhao similarity metric on the iNat19 dataset, with an average decoding time of approximately 13 milliseconds per sample. Beyond this, we note that for all hF scores, the inference time is around millisecond per input sample.
17

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
Optimal (ours)
Expected Info Valmadre
Plurality Valmadre
Deng
Karthik al.
Jain
Argmax
Top-Down
Barz & Denzler
4.18
4.54
5.13
4.23
4.S4
5.65
5.66
6.47
ticredimageNeet
Cross-entropy
1.74
1.77
Hxe (a = 0.1)
1.62
1.71
1.73
1.71
1.78
1.82
1.85
1.89
Hxe (a: = 0.6)
1.96
2.14
2.14
2.04
2.22
2.26
2.3
2.42
Soft-labels
1.59
1.71
1.73
1.68
1.75
1.82
1.84
1.86
Yolo-
1.79
1.86
1.92
1.99
1.99
1.98
Cross eross-entropy
1.63
1.84
1.85
1.79
1.91
1.92
1.95
1.93
Hxe (a 0.1)
1.58
1.80
1.81
1.74
1.87
1.87
1.88
1.88
1N
Hxe 0.6)
1.96
2.33
2.42
Soft-labels
1.68
1.99
1.99
1.8
1.95
1.94
1.94
1.95
Yolo-V2 V2
1.68
1.86
1.86
1.86
1.99
1.97
1.96
2.02
Alexnet
2.12
2.29
2.34
2.26
2.4
2.51
2.54
2.59
Convnext Tiny
0.80
0.81
0.86
Densenet121
1.19
1.27
1.28
1.24
1.27
1.32
1.32
1,34
bieredlnngeeeet
Efficientmet_y2..s
0.74
0.72
0.72
0.72
0.76
0.73
0.73
0.78
Inception_v3
1.05
1.07
1.09
1.07
1.12
1.13
1.13
1.18
Resnet18
1.41
1.52
1.53
1.49
1.54
1.58
1.59
1.63
Swin_v2 v2_1
0.83
0.88
Vgg11
1.41
1.50
1.51
1.47
1.53
1.57
1.60
1.62
Vit.b16
0.87
0.88
0.89
0.88
0.92
0.92
0.92
0.94
Table D.1: Performance on Mistake Severity metric of different decoding strategy for various models trained on various datasets
Optimal
Expected Info
Plurality Valmadre
Deng et
Karthik et al.
Jain et
Argmax
Top-Down
Majority
(ours)
Valmadre
Barz & Denzler
33.71
33.15
34,09
35.17
33.19
34,85
34,83
37.7
37.39
INa19 nesodinngeeest
Cross-entropy
11.77
12.30
12.30
12.07
12.45
12.27
12.29
12.43
12.36
Hxe (a = 0.1)
11.96
12.27
12.27
12.15
12.49
12.21
12.39
12.5
12.42
Hxe (a = 0.6)
13.88
15.07
15.07
14.06
14.89
14.62
14.77
15.14
14.52
Soft-labels
11.70
12.28
12.28
11.92
12.27
12.27
12.32
12.27
12.27
Yolo-V2
13.27
13.48
13.48
13.67
13.90
13.43
13.31
14.16
13.82
Cross-entropy
13.14
14.47
14.47
13.59
13.68
13.72
13.9
13.79
13.70
Hxe (a 0.1)
12.74
14.21
14.21
13.17
13.37
13.45
13.40
13.11
1ixe (ax 0.6)
16.17
19.18
19.18
16.72
17.21
17.21
17.31
17.31
16.42
Soft-labels
16.0
13.72
13.87
13.89
Yoln-V2
13.54
14.87
14.87
14,09
14.06
13.98
14.42
13.91
Alexnet
15.81
16.59
16.59
16.2
16.72
16.84
16.58
Convnext Tiny
5.57
5.67
5.67
5.79
5,93
5,48
5.46
6.64
Densenet121 21
8.59
9.04
9.04
8.76
8.87
8.91
8.9
8.93
8.93
Efficientnet v2
5.10
5.18
5.15
5.29
5,43
4.99
4.96
5.28
5.96
Inception_v3
7.56
7.74
7.74
7.71
8.0
7.69
7.64
7.87
8.16
Resnet18
10.35
10.79
10.79
10.6
10.79
10.65
10.69
10.86
10.77
Swin v2.t
5.77
5.83
5.83
5.86
6.04
5.72
5.72
5.91
6.32
Vggll
10.77
10.77
10.45
10.73
10.59
10.75
10.74
10.87
Vit.b.16
6.25
6.25
6.26
6.23
6.21
Table D.2: Performance Wu-Palmer Similarity metric of different decoding strategy for various models trained
various datasets
18

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
Optimal
Expected Info
Plurality Valmadre
Deng et al.
Karthik et al.
Jain et al.
Argmax
Top-Down
Majority
(ours)
Valmadre
Barz Denzler
48.32
47.92
47.92
54.08
52.92
47.42
47.40
50,27
60.32
INar tereellmgeeNeet
Cross-entropy
18.94
19.55
19.55
19.69
20.57
19.29
19.19
19.49
21.34
Hxe (a 0.1)
19.04
19.68
19.68
19.89
20.74
19.29
19.33
19.64
21.54
Hxe (a 0.6)
24.27
26.76
26.76
25.02
27.09
25.25
24.80
25.54
27.43
Soft-labels
18.81
19.45
19.45
19.43
20.29
19.2
19.23
21.20
Yolo- V2
21.14
21.72
21.72
22.17
22.83
21.18
20.8
22.07
23.76
Cross-entropy
22.71
23.3
23.3
23.52
23.4
23.39
23.53
23.57
24.92
Hxxe (a 0.1)
22.46
23.03
23.03
23.14
23.18
23.13
23.18
23.26
24.17
Hixe (a 0.6)
29.67
31.59
31.59
31.02
31.43
31.34
31.4
31.6
32.65
Soft-labels
23.58
25.96
25.96
24.05
23.95
23.79
23.71
24.05
27.06
Yolo-V2
23.51
24.17
24.17
24.44
24.39
24.15
23.99
24.67
25.41
Alexnet
25.5
26.28
26.28
26.58
28.38
26.08
26.04
26.36
28.99
Convnext Tiny
8.60
9.04
9,04
9.42
9.86
8.70
8.60
9.03
11.67
tieredlnage Nor.1
Densenet121
13.69
14.23
14.23
14.09
14.35
13.89
13.81
13.97
15.08
Efficientnet_ye v___s_22
7.89
8.18
8.18
8.63
8.99
7.87
7.81
8.23
10.4
Inception v3
11.88
12.22
12,22
12.54
13.23
12.07
11.97
12.29
14.04
Resnet18
16.61
17.12
17.10
17.29
17.72
16.77
16.74
17.11
Swin v2 t
9.02
9.30
9.30
9.64
10.06
9.06
9.05
9.32
11.05
Vggll
16.46
17.07
17.07
17.11
17.75
16.63
16.74
16.86
18.81
Vit.-16
9.69
9.92
9.92
10.15
10.54
9.78
9.69
9.84
11.36
Table D.3: Performance Zhao Similarity metric of different decoding strategy for various models trained various datasets
Optimal
Expected Info
Plurality Valmadre
Deng et
Karthik et al.
Jain et al.
Argmax
Top-Down Majority
(ours)
Valmadre
Barz Denzler
79.0
74.75
71.25
75.81
74.26
68,92
68.92
65.49
78.21
Heredllaggeee...
Cross-entropy
92.32
90.93
90.54
90.3
89.68
89.37
89.29
89.03
91.6
Hxe (a 0.1)
92.27
91.08
90.71
90.22
89.65
89.42
89.2
88.95
91.6
Hxe (a 0.6)
91.29
90.38
90.09
89.13
87.76
87.43
87 87.08
86.42
90.90
lobt-labels
92.30
90.99
90.63
90.43
89.87
89,39
89.25
89.15
91.72
Yolo-V2
91.35
90.37
90.04
88.95
88.43
88.38
88.39
87.48
90.56
Cross eoosryy
91.76
89.97
89.73
88,88
88,03
87,99
87.84
87.94
90,93
Hxe (a 0.1)
92.03
90.34
90.09
89.17
88.31
88.30
88.23
88,27
91.24
Hxe (a 0.6)
90.67
88.82
88.63
86.49
84.94
84,94
84.85
84.85
90.24
loft-labels
91.40
89.96
89,82
88.85
87,82
87,87
87.84
87.78
91.22
Yolo-V2
91.48
90.09
89.88
88.42
87.57
87,70
87.77
87.38
90.66
Alexnet
89.98
88.00)
87.3
87.23
86.19
85,48
85.28
84,99
89.21
Convnext Tiny
95.63
95.76
95.67
95.38
95.11
95.26
95.24
94.90
95.82
tiered Ner
Densenet121
94.14
93.2
92.97
92.79
92.51
92.26
92.23
92.12
93.56
Eflicientnet.22.s
96.16
96.13
96.04
95.8
95.54
95.68
95.69
95.33
96.16
Inception_v3
94.71
94.19
93.92
93.77
93.38
93.32
93.32
93.04
94.46
Resnet18
93.16
91.94
91.67
91.4
90.99
90.76
90.67
90.42
92.53
Swin_v2.5
95.92
95.58
95,45
95.26
95.00
95.05
95.03
94.79
95.77
Vggl1
93.15
92.10
91.83
91.59
91.09
90.81
90.60
90.5
92,61
Vit_b16
95.63
95.21
95.07
94.92
94.64
94.60
94.60
94.46
95.40
Table D.4: Performance on hFFo.5 metric of different decoding strategy for various models trained various datasets
19

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
Optimal
Expected Info
Plurality Valmadre
Deng
Karthik et al.
Jain et
Argmax
Top-Down
Majority
(ours)
Valmadre
Barz Denzler
73.98
71.28
70.03
70.01
71.13
69.04
69.04
66.29
68.36
fieradlmugeeet
Cross-entropy
89.88
89.32
89.3
89.51
89.15
89. 99.24
89.21
89.08
89.39
Hxe (a 0.1)
89.82
89.32
89,32
89.43
89.1
89.29
89.13
89.01
89,33
Hxe (a 0.6)
87.97
86.86
86.86
87.72
86.95
87.11
86.98
86.61
87.45
Soft-labels
89,91
89.33
89.33
89.64
89.3
89.24
89.19
89.21
89,47
Yolo V2
88.59
88.32
88.32
88.11
87,88
88.22
88.32
87.55
88.13
Cross-entropy
88.83
87.51
87.51
88.22
88.03
87.99
87.84
87.94
88.3
Hxe (a 0.1)
89.18
87.73
87.73
88.58
88.31
88.3
88.23
88.27
88.79
Hxe (a = 0.6)
86.48
83.55
83.55
85.5
84.94
84,94
84.85
84.85
85.96
Soft-lahels
88.56
86.23
86.23
88.11
87.82
87.87
87.84
87.78
87.88
Yolo-V2
88.49
87.19
87.19
87.78
87.57
87.7
87.77
87.38
88.1
Alexnet
86.41
85.57
85.57
85.92
85,25
85.31
85.2
85.13
85.78
Convnext Tiny
95.13
95.07
95.07
95.01
94.84
95.2
95.22
94.93
94.34
Densenet121
92.62
92.13
92.13
92.38
92.26
92.19
92.2
92.16
92.31
tieredlnageaat
Efficientnet v2
95.57
95.51
95.53
95.44
95.29
95.63
95.66
95.37
94.93
Inception v3
93.49
93.27
93.27
93.32
93.03
93.26
93.3
93.09
93.01
Resnet18
91.08
90.61
90.61
90.78
90.59
90.66
90.62
90.46
90.74
Swin_v2.t
95.03
94.93
94.93
94.92
94.74
94.99
94.99
94.81
94.59
Vggl1
91.07
90.64
90.64
90.92
90.64
90.71
90.57
90.56
90.66
Vit.b_16 94.64
94.55
94.55
94.56
94.39
94.54
94.56
94.48
94.31
Table D.5: Performance on hF' metric of different decoding strategy for various models trained various datasets
Optimal
Expected Info
Plurality Valmadre
Deng et
Karthik et al.
Jain et al.
Argmax
Top-Down
Majority
(ours)
Valmadre
Barz Denzler
74.72
69.26
69.2
66.05
68.71
69.31
69.32
67.37
62.14
VeredInngeNe..
Cross-entropy
90.81
88.31
88.31
88.96
88.76
89.2
89.22
89.2
87.76
Hxe (a = 0.1)
90.93
88.21
88.21
88.88
88.71
89.24
89.14
89.15
87.
Hxe (a 0.6)
88.67
84.18
84.18
86.6
86.32
86.9
86.97
86.9
84.71
Soft-labels
90.92
88.3
88.3
89.08
88.9
89.19
89.2
89.35
87.81
Yolo-
89.75
86.94
86.94
87.5
87.49
88.15
88.34
87.71
86.3
Cross-entropy
89.52
85.67
85.67
87.72
88,03
87.99
87.84
87.94
86.35
Hxe (a 0.1)
89.7
85.78
85.78
88.12
88.31
88.3
88.23
88.27
86.91
Hxe (a = 0.6)
86.53
79.32
79,32
84.67
84,94
84,94
84.85
84.85
82.5
Soft-labels
89.27
83,22
83.22
87.52
87.82
87.87
87.84
87.78
85,25
Yolo-V2
89.15
84.96
84.96
87.27
87.57
87.7
87.77
87.38
86.12
Alexnet
87.5
84,21
84,21
84,98
84,56
85.26
85,24
85.37
83,27
Convnext Tiny
95.79
94.58
94.58
94.75
94.65
95.18
95.23
95.01
93.26
fierddlaage Ner.H
Densenet121
93.51
91.45
91.45
92.1
92.09
92.19
92.23
92.25
91.38
Efficientnet. v2
96.21
95.12
95.12
95.19
95.1
95.62
95.67
95.44
94.01
Inception v3
94.22
92.76
92.76
93.01
92.79
93.26
93.33
93.2
91.98
Resnet18
92.08
89.77
89.77
90.35
90.31
90.63
90.64
90.57
89,43
Swin_v__t
95.79
94.5
94.5
94.69
94.55
94,97
95.0
94.88
93.73
Vgg11
92.06
89.7
89.7
90.44
90.33
90.68
90.6
90.7
89,22
Vit_h_16 95.37
94.14
94.14
94.33
94.22
94.52
94.57
94.54
93.52
Table D.6: Performance on hF, metric of different decoding strategy for various models trained various datasets
20

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
Metric
Group
Optimal (Brute-force) Optimal (ours)
Deng (2012)
Expected Info.
Plurality Karthik (2021) Jain et al. (2023)
Argmax Tup-Down Majority
Wo-Palmer
(fnetuned
INat19
289.5
2.786
0.312
0.211
0.033
0,033
0.036
0.018
0.021
0,004
(Inctuned models)
seredlmageNee
(x:
125.7
1.641
0.157
0.166
0.043
0.031
0.024
0.010
0.021
0,000
veredlningeNes- H
models)
125.7
1.199
0.159
0.168
0.045
0.031
0.024
0.010
0.022
0,000
INat19
259.88
Than
(inetuned mudels)
[x 22)
15:119
0.212
0,210
0,33
0,33
0.036
0.088
0.000
0.004
BeredllaggeNe
125.7
3,008
0.156
0.022
0.014
(fuctuned
(pectinined models)
ugredlmageNes
125.7
36)
3.196
0.158
0.168
0.047
0.031
0.024
0.010
0.022
0,000
1Nar19
Soverity
(finatuned madels)
0.034
0.034
vireedlmageNer II
(finetuned models)
0.16
0.156
0.158
0.045
0,032
0.034
0.010
0.022
0,003
derellmageNes
(preéraized models)
0.016
0.158
0.160
0.045
0,032
0.004
0.010
0.022
0,000
1Na119 (finctuncd
lntraetable
0302
0,035
0,034
0.086
0.121
0.004
DireelimagNNe- (finetnned models)
Intraesable
1.012
0.157
0.164
0.046
0,030
0.022
0.010
0.021
0.001
GeredllmageNe (pretrained models)
Intracsable
0.63
0.157
0.012
MP.
19 (fiettnne modets)
Intrassable
1.033
0.213
0,220
0.032
0.034
0.006
0.018
0.000
0.004
rireellmgpNNe-tt
(fnstuned
1.91
0,030
0.011
deredlmageeer II (pretminedd models)
Intractable
1.387
0.158
0.163
0.045
0,631
0.023
0.008
0,021
0,002
MF,
(fnectuned models)
Intractable
0.13
0.032
0.034
0.016
0.018
0.020
0.004
(finctuned modets)
Intracsable
2921
0.156
0.168
0.044
0,031
0.024
0.010
0.021
0,000
siredllmaeNee-I (protiiieed models)
Intruetable
2.881
0.159
0.170
0,050
0.032
0.004
0.010
0.025
0.003
Table D.7: Decoding time for each strategy, reported in milliseconds per sample and averaged across all models within each group.
D.4. Additional Information for the Blurring Motivation
In Section 5.1, provide the motivation for introducing image blurring. We illustrate this motivation with single example based on Figure 3, which visualizes the agreement map for -score and Majority decoding strategies. An agreement map is constructed as follows:
A simplex mesh in 3 created, where each point corresponds to a single probability distribution over leaf nodes. For each point the mesh, the probability is decoded using both the optimal decoding strategy and the heuristic decoding strategy.
The agreement map is constructed by coloring areas in green where the two decoding strategies agree, and in red where they disagree.
In the following, we display agreement maps for all heuristic strategies selected in the main text versus the optimal strategy, evaluated across all six metrics.
Argmax
Top-Down
Plurality
Expected Info.
Karthik et al. (2021) Jain al. (2023)
Figure D.I: Agreements maps heuristic decoding strategies vs. Mistake Severity optimal decoding strategy.
Overall, it is evident that the more central the probability is within the simplex, the greater the disagreement between the optimal decoding strategy and the heuristic strategy. This observation motivates the introduction of the blurring effect. Specifically, blurring an image increases label uncertainty and randomness, causing the oracle probability distribution to shift towards the center of the simplex. Similarly, the estimated oracle probability distribution follows this shift.
21

---

To Each Metric Its Decoding: Post-Hooc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
Argmax
Top-Down
Majority
Plurality
Expected Info.
Karthik et al. (2021)
Jain et al. (2023)
Figure D.2: Agreements maps heuristic decoding strategies vs. Wu-Palmer similarity optimal decoding strategy.
Argmax
Top-Down
Majority
Plurality
Expected Info.
Karthik et al. (2021) Jain et al. (2023)
Figure D.3: Agreements maps heuristic decoding strategies vs. Zhao similarity optimal decoding strategy.
Argmax
Top-Down
Majority
Plurality
Expected Info.
Karthik al. (2021)
Jain et al. (2023)
Figure D.4: Agreements maps heuristic decoding strategics vs. hF u.s optimal decoding strategy.
Argmax
Top-Down
Majority
Plurality
Expected Info.
Karthik al. (2021)
Jain et al. (2023)
Figure D.5: Agreements maps of heuristic decoding strategies vs. hF,, optimal decoding strategy.
Argmax
Top-Down
Majority
Plurality
Expected Info.
Karthik al. (2021)
Jain et al. (2023)
Figure D.6: Agreements maps of heuristic decoding strategics vs. hF2 optimal decoding strategy.
D.5. Additional Experiments for the blurring experiment
We begin by describing the experimental setup used for these evaluations. The models from previous experiments of Appendix D.2, trained on various datasets, remain unchanged. However, modify the test set images by applying increasing levels of blur, parameterized by the standard deviation This blur is applied to resized images, typically of size 224 x 224, using a Gaussian Blur transformation with a kernel size of 61 and standard deviation of a.
We recall also the intuition of this blurring experiment. As the images become progressively more blurred, their features become less informative, causing the posterior probability distribution to converge toward the center the simplex. As illustrated in Figure even human expert would find challenging to confidently predict the class label for the image on the far right. This experimental setup is designed to amplify the frequency of disagreements between heuristic strategies and optimal decoding.
D. MORE VISUAL EXAMPLES
22

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
Blur level o=0
Blur level o=3
Blur level o=6
Blur level o=9
hF1 opt: valley
valley
whole
valley
animal whole
valley
Majority: valley
valley
whole
Argmax: valley
valley
valley
valley
Exp. Info.: valley
valley
valley
valley
Khartik: valley
valley
valley
valley
Jain valley
valley
valley
valley
Top-Downvalley
valley
norfolk_terries
lakeland_ -errier
Plurality: valley
valley
whole
animal
Figure D.7: Influence of blurring to the decision-makinn of various decoding strategies. Image displayed is labeled valley
Blur level o=0
Blur level o=2
Blur level o=4
Blur level g=7
hF1 opt:
rhinoceros beetle
Siinoceros_beetle
thinoceros_beett insect
Majority: rhinoceros_beete rhinoceros_beetle
Sohnoceros_beette rhinoceros rhinoceros_beetle rhinoceros beette rhinoceros_beett
animal
Argmax:
thinoceros_beetee phinoceros_beette
rhinoceros_beetle
banded _ecko
Exp. Info.:
thinoceros_beetee
banded_ fly banded _ecko
Khartik:
rhinoceros_beetle rhinoceros beetle
rhinoceros_beetle
Jain
thinoceros_beetle beetle
rhinoceros beetle
Top-
beeetee thinoceros_beetl
rhinoceros_beett thinoceros_beette
banded_gecke diapsid
Plurality:
thinoceros_beete
Figure D.8: Influence of blurring to the decision-making of various decoding strategies. Image displayed is labeled rhinoceros beetle
23

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
Blur level o=0
Blur level o=3
Blur level o=6
Blur level o=8
hF1 opt:
magpie
magpie
goose
vertebrategolf ball
Majority:
magpie
magpie
goose
instrumentality golf golf_ball ball
Argmax:
magpie
magpie
goose
Exp. Info.: magpie
magpie
goose
ball golf ball
Khartik: magpie
magpie
goose
golf golf_ball ball
Jain magpie
magpie
goose
golf ball
Top-Down:magple
magpie
goose
golf ball
Plurality: magpie
magpie
goose
golf ball
Figure D.9: Influence of blurring to the decision-making of various decoding strategies. Image displayed is labeled magpie
Blur level o=0
Blur level o=3
Blur level o=6
Blur level a=9
hF1 opt:
cello
device
placental device
instrumentality primate
Majority: cello
instrumentality
artifact
placental
Argmax:
cello
binoculars
binoculars
chimpanzee
Exp. Info.:
cello
device
device
anthropoid_ _pp
Khartik: cello
face_powder
face_powder
face face_powder
Jain
cello
binoculars
tobacco_ shop
chimpanzee
cornet
binoculars
chimpanzee
Plurality: cello
musical_instrument
device
placental
Figure D.10: Influence of blurring to the decision-making various decoding strategies. Image displayed is labeled cello
24

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
Blur level o=0
Blur level o=3
Blur level a=6
Blur level a=8
hF1 opt:
chime
chime
chime
artifact old_
Majority:
chime
chime
muuscal_instrunee
placental
Argmax:
chime
chime
chime
patas
Exp. Info.:
chime
chime
chime
wt__wolld_mookk.
Khartik: chime
chime
chime
patas
Jain SoppDown:chime
chime
chime
chime
patas
chime
chime
patas
Plurality:
chime
chime
chime
old_ @id_word__ng workd_mookeyy
Figure D. 1: Influence of blurring to the decision-making of various decoding strategies. Image displayed is labeled chime
Blur level o=0
Blur level o=3
Blur level g=5
Blur level σ=9
hF1 opt:
swing
instrumentality artifact
artifact whole
artifact
Majority: instrumentality
artifact
Argmax:
swing
bannister
sandbar
worm_
Exp. Info.: swing
shore
sandbar
worm_fence
Khartik: swing
face_powder
sandbar
face_powder
Jain
swing
bannister
sandbar
worm_fence
Top-Down:swing
sunglasses
worm_fence
hourglass
Plurality: swing
instrumentality
artifact
instrumentality
Figure D.12: Influence blurring to the decision decision-making of various decoding strategies. Image displayed is labeled swing
25

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
Blur level o=0
Blur level o=3
Blur level o=5
Blur level o=7
hF1 opt:
standard_schnauze
terrier terrier
terrier
Majority:
Seandard_schnaurr
Haandard_schnauzer
terrier
Argmax:
standard_schnauzer
standard_schnauzer
standard_schnauzer
standard_schnauze
Exp. Info.: Lunndard_schnuzer
Landard_schhauzer
Hlandard_schnazzer
terrier
Khartik: haandaddsschnuzer
standard_schnauzer
kerry_blue_terme serreer
Jain
wire-haired_ foo___o________ee_
terrier
bluu-eeereeerrerr
Hop-Down:standarr scchaazzr
standard_schnauzer standard scchauzer
standard standard_schnauzer schnnazer
standard_schnauzer scchnazzrr
standard
Plurality: Slandard_schnauze
saanaard_schnuzer
standard_schnauzer
Figure D.13: Influence of blurring the decision-maan making of various decoding strategies. Image displayed is labeled standard schnauzer
Blur level o=0
Blur level o=3
Blur level o=6
Blur level o=9
hF1 opt: OX
ox
placental placental
placental
Majority:
ox
placental
placental
Argmax:
ox
OX
OX
patas
Exp. Info.:
primate
Khartik:
OX
0X
OX
patas
Jain OX
OX
OX
patas
DownDox
OX
OX
Plurality:
OX
bovid
carnivore
Figure D.14: Influence of blurring the decision-making of various decoding strategies. Image displayed labeled
26

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
D.5.2. FULL QUANTITATIVE RESULTS
Figure D.15 illustrates the relative gain in performance compared optimal decoding strategies for the six selected metrics, averaged across datasets and models. For the hF a scores and the Mistake Severity metric, observe the expected trend: image blurriness increases, the relative loss in performance of heuristic strategies becomes more pronouneed. This aligns with our intuition that the problem becomes more uncertain, the choice of an appropriate decoding strategy becomes increasingly important for optimizing hierarchical target metric.
Interestingly, the results differ for the Zhao Similarity and Wu-Palmer metries. While the optimal decoding strategy consistently remains the best, the relative performance of heuristics exhibits an unexpected trend. Specifically, the relative loss decreases significantly the blur level increases up 3, after which it begins to increase again. Despite this variability, the optimal decoding strategy maintains statistically significant advantage over the heuristics in all cases.
hF1 score
hF2 score
hF0.5 score
Mistake Severity
Zhao
Wu-Palmer
0%
55%
-00%
Relative gain
-15%
20%
-25%
Optimal (ours)
Puraity
Argrox
Deng at (2012)
Karthicnt et a 12001)
Tap- Down
12023)
Majorily
0
10
10 Blur level
10
5
10
Figure D.15: Impact of blurring on the sub-optimality of heuristic decodings. This figure shows the relative performance gain (in heuristic decodings compared to the optimal decoding for the selected metrics, as function blur level. Results are averaged across multiple models and datasets, with a 95% confidence interval displayed for each decoding strategy.
27

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
E. Proofs.
This section provides the detailed proofs of the theoretical results.
E.1. Nodes decoding (H = W)
In this section
on the Definition E.1. Let (CC) and h N then define the conditional risk of h for metric C follows:
we
will
rely
conditional risk
defined
as
follows:
Re(hlp) = Σ
p(0) I(h,t)
LEC
E. HIBRARCHICALLY REASONABLE METRICS CASE IN WHICH EQUATIONS (2) AND (3) ARE VERIFIED.
Lemma F.2. Let C: : + R be hierarchically reasonable. For EN (r), define of C(n, C(a(n), the node-parent loss difference for label and:
M max 8nd LEL)((N)
My max 5nd (E((m)
Mn
min dnt >> 0 m, min 5 LE2(m)
1(()
The, for p (L)), have:
1. p(n) > M +mn
Mr
= C ( = (p) + *(n)
2. p(n) m. Mm
Imin (n) (d(p) #
Proof.
Let L:N: :N + R satisfy Equations (2) and (3). We now proceed to prove statement 1.
Assume p(n) >
M.
Then, we have:
M. m.
M
p(n) >
M n
+ mm
11k
p(n)
Mg
(1 -1- p(n))
Licc(()) p(1)
Eecorc()) P(I)
This implies
Σ p()) (E((m)
Σ p(l) M
man
-C((().)-Ccm.)))
(EC)C(n)
-0tm,)-C(((o)))
Rewriting:
Σ -())(((())))) Σ p())((n,1>> Σ p(1)C(n,1) - Σ p())((((M).)
(E((n)
IEC(A)
(EC)C(()
(ECTC(n)
Thus:
Σ [p(()((()))1)>> Σp(1)((n))
IEC
lEC
And finally:
Re(T(n)lp) > Re(1lp)
Therefore, has a strictly lower conditional risk than x (n), which shows that (n) is not the optimal decoding.
28

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
Statement 2 follows this exact same proof.
Let us also prove that
m mn + Mn
Inin (n) S (n)
M,
Mn mn
The function x + x+C
where a constant an increasing function on R+ and as min S M, we have,
M,
M
imin (n) S M + Mn.
-maxx (n)
M, + mn
2mn
Theorem F.3. Let L be a hierarchically reasonable metric and (CC), then the optimal decision rule Eo (p) can be computed with algorithm of (dmax [ (V]) time complexity.
Algorithm 2 g (n) and q (n) computation.
[tb]
function GETCST((,, L)
M, max C(n, 1) C(T(n),1)
IeL),n
m, + min ((nn(()( - C(n,1) >0
IEC.,
Mn. maxC((((n).)) C(n,l)> >0
IEL,
mA min C(n, l) ((T()))))
LEC
return
m.
M.
m. +M M. +m
end function
function @COMP(n, Pnin Grraee L)
if n E L then
91,92 + GETCST((n), L) C (n) + 91
mmax (n) +-
return {n}
else
((n) - U @COMP(e, sminr d L)
cEC(N)
91,92 t GETCST(C(R), L)
Loin (n) +- Q11
q (n)) t-
return L(n)
end end function
C L t 1 Dpvi PROBANODES(T, quiuu C L)
29

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
Algorithm 3 Probability Computation
1: function PROBANODESREC'y, P. Pleaves)
2: if 12 L then
3: p(n) t (n.)
4: return p(n)
5: else
6: p(n)
PROBANODESKECIe, p. Piewes) eEC(m)
Σ
7: end if
8: end function
9: function PROBANODESS(Lcvee)
10: p P LM1o
PROBANODESREC(T; p. Pleaves)
return p
13: end function
Algorithm 4 Candidate Selection
1: function FINDCANDSETREC(n. S, Imax, 9min)
2: if p(n) > 9max (n) then
3: S S (T(n)
4: else if p(n) qmin then
5:
S-S S {n}
6: else if L p(n) < min Juin (n) then nEN
7:
return
8: end if
9: for E C(n) do
10:
FINDCANDSETRECIG, p, S, 9maxx Imin)
11: end for
end function
function FINDCANDSET(p, Amax, Amin)
14:
S <
15:
FINDCANDSETRFCCC, S, fmax Iminn
16: return
17:
end function
Algorithm Brute-force search
function BRUTEFORCE(S,, p)
2: nope
3: Tops
4: for S do
5:
r r Σ p(I)C(n,1) 1)
IEC
6:
if < Topt then
7:
Topt +-
8:
Nopt f- n1
9: end
end for
11: return Nopt
12: end function
30

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
Algorithm 6 General Algorithm
1: function FINDOPTIMALI (Peaaves Imaxs 9mnin)
2: f- PROBANODES( (Pcavos)
3: S < FiNDCANDSET(2,, Quaxx Quin)
4: Nopp < BRUTEFORCE(S. p)
5: return Ropt
6: end function
Proof. The general algorithm is summarized in Algorithm 6. It consists in
1. Computing probability distribution over nodes, given probability distribution over leaves. (Algorithm 3)
2. Filtering each node based on condition of Lemma E.2. It outputs a candidate set S which can all be the optimal prediction (Algorithm 4)
3. A brute-force algorithm performed on this remaining candidate set (Algorithm 5)
Algorithm 2 correspond the computation of (Amin (n)))ee and (1max(n)))ess (n)))ev. This is independant of the input probability distribution p and can be performed beforehand. To this extent, the time complexity of Algorithm 1 is not added to the overall complexity of the optimal decoding. However this algorithm has (( [C) complexity. In fact, function QCOMP consists in a tree traversal in which each node is visited exactly once. For each visit, constants Mn.ma, Mp, Mn, TT,, are computed in a ((1)) time complexity. Therefore, the overall complexity of Algorithm is ( [C]).
Algorithm correspond the computation the whole probability distribution over all nodes given probability distribu- tion over leaf nodes. This seemingly trivial computation is tree traversal which necessitates the visit of exactly each node. Therefore the overall complexity of Algorithm 3 is ((IV)) This has to be done for each probability distribution, and therefore contributes to Theorem E.3 time complexity.
Algorithm 7 correspond to the candidate selection step. It performs once again tree traversal, which also necessitates to visit each node exactly once. Therefore the overall complexity of Algorithm 3 is (((W)) For convenience, we separate Algorithm and Algorithm 4, but this can be done simultancously.
Algorithm is basic brute-force algorithm. For each node n E S, the computation of the risk r necessite [C] operation. Therefore the overall complexity of Algorithm is O([S) [C). Let us now prove that |S] = O(dmxx)
Proof of |S| (clmax)
We recall condition 2 of Theorem E.3:
p(n) < C (n) = (p) +
Then, the contrapositive writes
n nES S p(n) 2 miin (n) 2
min f (n) == q
EEN
Therefore,
Σ p(n) 2 |S| d
RES n
Inequality holds also for n = because p(r) = 1 2 d
This can be rewritten:
| <
Σ p(n)
Amnn
RES
p(n)
NEN
We recall. p(n) E() p(l). Then, on given level of the hierarchy ie on set {n E N, ddd(m) = d}. there is no common leaf descendant between two elements of the set. We therefore have
Σ p(n) S p()) = 1
BEN
IEC
d(n)=d
31

---

To Each Metric Its Decoding: Post-Hocc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
Eventually,
duaa
Σ p(n) = Σ Σ p(n)= S dmax + 1
7
nEN
d=0 nEN d(n)=d
Which finally give,
|S|
(dmax + 1) O (dmax)
Amin
Wrapping up everything obtain time Complexity for Algorithm 6 of (d |C| + (V
1.1. APPLICATION TO SPECIFIC METRICS
In this section, we detailed the proof of statements made in Section 4.2.1. We aim to retrieve the two following propositions.
Proposition E.4. Tree distance Loss Optimal Decision Rule (Ramaswamy el al., 2015). Let DL be the Tree distance Loss whose definition is DL(h, y) = Length of the shortest path between h and y in T. Let E (LC then optimal decision rule EDL (p) is given by:
(pL = argmax d(n)) s.t p(n) 2 0.5
nEN
Proposition E.5. Generalized Tree distance Loss Optimal Decision Rule (Cao al., 2024). Let DL be the Generalized Tree distance Loss whose definition is (h, y) (L(h, y) + e d(h). Where d(h) is the depth of node h. Let p E A(C) then optimal decision rule EDI. (p) is given by:
1
SDL (p) = argmax d(n) s.t p(n) 2
neN
2
Proof.
We prove the second Proposition, the first one is included in the second. Let E (Nrr and / E LV((()) then
gDLc (n, (T.(()(
+ - (d(nn) 1))
( d(n)+1]
(because Cl))(m))
+
Then,
M. max (EL(L(n)
&DL 1+c
Similarly,
mn = - Mn = 1 m, =1
Therefore, DLe Dis 1+c Lemma E.2 gives:
if p(n) > Itc then π (n) is not the optimal prediction
p() < Life ? then n is not the optimal prediction
Then, as there can be at most node per level whose probability is greater than deepest node whose probability is greater than 1tc This concludes the proof.
1tc
2 2 we retrieve that ÉDL (p) is the
2
32

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
1.3. HIERARCHICALLY REASONABLE METRICS CASE IN WHICH EQUATIONS (3) AND (4) VERIFIED.
In such case, we have the following result:
Proposition E.6. Let N x + R be a metric that satisfy Equations (3) and (4). For n E N \ (r), define
Sh -((n,)) - ((T(n), 1) the node-parent loss difference for label and
M = max C(n, 1) (()()), >0 ma min C(r(n),1) ((, 1 >0
(EC)C(n)
lEC(m)
LC
Ma max C(+(n),)) C(n,1)
Tin
min teC(L(n)
C(n,1) C(T(n))))
(EC(M)
LCA(n.))#r
Let On be the shallowest non-root ancestor (an C(r)) the set of children of For p E A(L), have:
1. p(n)= >
M. p(aa) = (1) p(an) = (p( # x(n)
M. 4min
2. p(n) < ma
p(an) = Gmin (ni) p(an) = (p(p) #
Rn Mr
Proof.
Let L N L > R be hierarchical metric that satisfy Equations (3) and (4), We now proceed to prove statement 2.
Assume p(n) i, Ma
p(an). Then, we have:
p(n) < mn
p(an)
mn + Mn
Mn
((n)
in (p(an) p((1))
Lice(n) p()
E (ER)E()) p(t)
This implies
C(C(() - C(T(n).
(E2)2()) =CA(n.))=F
Σ v())
Ma
Σ p(1)
lE2(n)
-Ca(m)
(EC(C())
LOA(H.)ET
Rewriting:
Σ -) - Σ p())C(n,1) Σ p())C(n,1) - E p())C(((m).)
(E)(
lE((n)
(EC(C())
(EC)C(n)
Thus:
[x(()(((())))) Σp(1)((n))
LEC
leC
And finally:
Ro(T(n)lp) < Ro(alp)
Therefore, T (n) has a strictly lower risk than n, which shows that n is not the optimal decoding. Statement 1 follows this exact same proof.
33

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hierarchical Classifiers
Proposition E.7. be an evaluation measure that verifies and 4. Let p E A(C), then the optimal decision rule (p( can be obtained through an algorithm of (Odmmxx [C] (N() time complexity.
Algorithm 7 Candidate Selection
1: function FINDCANDSETRR:CISST,, 5, Quaxx quinu)
2: if p(n) > 9max (n) p((0)) then
3: S 5 S {*(n)}
4: else if p(n) < 4min p(a,) then
5:
5 5-S1 ( {n}
6: else if L p(n)
min (min p(an) then NEN
7: return
8: end if
9: for E C(n) do
FINDCANDSETRECCISIC S, fmax. (min) 11: end for
10:
end function
function FINDCANDSETBIS(p. Imax 9min
14:
S S
15:
Call: FINDCANDSETRECDISC,, S, 9max. 9min)
16: return S
17: end function
Algorithm 8 General Algorithm Bis
function FINDOPTIMAL AT (Pheavsss Tmax. qmin)
2: p f PROBANODES(Picae))
3: S FINDCANDSETBIS(p. Gmaxx Qmin)
4: Hoppt <- BRUTEFORCE(S, p)
5: return Ropt
6: end function
The general algorithm is summarized Algorithm 8. It follows the exact same intuition of Algorithm 56. consists
1. Compute probability distribution nodes, given probability distribution leaves. (Algorithm 3)
2. Filtering each node based condition of Theorem E.6. It outputs candidate set S which can all be the optimal prediction (Algorithm 7)
3. A brute-force algorithm is performed on this remaining candidate set (Algorithm 5)
As before, We obtain a O[SS) [C] + (W]) time complexity for Algorithm Let us now prove that |S| O
We recall second condition of Proposition E.6:
p(n) (miin()) (n) p((a)) = Ec(p)
Then, the contrapositive writes:
n E S = p(n) 2 qie (n) p(an)
2 p(an) min dh (n)
We write D(n) the set of descandants of n. in T. (defined inclusively D(n). Let C(r) Then,
Σ
p(n)
N sSDD(c)) quen
nES
(ED(c)
34

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
Inequality holds also for because p(c) Amnin p(c). This can be rewritten:
[snD(o)s
1 min
Σ p(n)
BES nED(c)
$ p(m) wCD(e)
We recall. p(n) - E() p()). Then, on a given level of the hierarchy ie on set {n E N, dd(()) = d). there is no common leaf descendant between two elements of the set. We therefore have
Σ p(n) -
Σ p()) = p(c) (E((c)
nED(O)
d(n)=d
Then,
duea Σ
Σ p(n)
Σ p(n)= dmax p(c)
(ED(A)
d=1 NEN d(n)=d
Sp(c)
Which gives,
[SDD(c) < dmax p(c)
4min
And eventually:
|S| 1
[SnD(c)) $ 1
dmax
Σ p(c)
Amin
.EC(r)
eEC(r)
Finally this yields:
||| (dmax))
which completes the proof.
35

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
E.2. Subset of nodes decoding
E.2.1. ON THE CARDINALITY OF (V(
Proposition E.8. For T (N, where each non-leaf node has at least two children, the cardinality of MM satisfies (M) 2 2 W1 1.
Proof.
We define the following property: (na) "For a tree T = (W,8) with M = n, where every non-leaf node has at least two children, holds that [ 2 2
Let W n. We will use strong induction on n. Base Case: For 1, the tree T has only node, which is a leaf. Thus, |C] 1, and the inequality holds since
1
Induction Hypothesis: Assume that for all trees with nodes (where & n)) the number of leaves is least 5.2
Inductive Step: Consider tree T with nodes. We need to show that [ 2 2
Let be the deepest node in T. Let be the parent of v. Since all internal nodes have at least two children, has at least two children.
Let be the number of children u. All these children are leaves because e the deepest node.
We then removing these k leaves and their edges from T. This results in a smaller tree T' with n k nodes.
By the induction hypothesis, the number of leaves in T' is at least n-k
The total number of leaves in the original tree H. is the sum of:
The leaves that were removed.
The leaves the smaller tree T'.
We need to remove from the leaf count in T' è a leaf T' but not in H.
Therefore, by induction hypothesis, the number of leaves in T is least:
k: + n - k
2
By simplifying the expression obtain:
12 1
2k + n -
--2
n k
k: +
2
2
2
We need to show:
n + 2
n 2
2
Which is true if and only if:
n + k - -2
k-2 0 Since h 2 (all internal nodes have at least children), this is true. Therefore, by induction, for any tree with nodes, where every internal node has at least two children, the number of leaves [C] is at least 2.
Let T = EN, be a hierarchy. By applying Pnn) with n. = [ we have that has at least subset of these |C] leaves corresponds to a unique element of (MW)).
[ 2
leaves:
|
[
Each
2
There are -l different subsets of the | leaves (excluding the empty subset). Each of these subsets, forms a unique element of in MT (N).
Therefore,
MM 22 IX
36

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
This completes the proof.
E.2.2. THE CASE OF hF SCORES
Throughout this section, we will use concept analogous to risk, referred to as utility.
Definition E.9. Utility. Let p E A(C) and
P(N) then define the hF conditional expected utility of h as follows:
UuF y (hlp) Σ p(1) hF (h,
IEC
E.2.3. REFRAMING THE PROBLEM
We recall that
Mf(N) = (h ((1, E mh n2 = m & A(nz) and n2 & A(n1))
We also define,
UT(N) = ( h E(N))
Proposition E.10. The function MT (N) - (T(N), defined by ((h) haug is bijective.
Proof. An element of U4 (W) represent a subtree of T which contains the root node. This subtree is uniquely defined by the set of leaves in the subtree, which is an element of MT(N). This completes the proof.
We first prove that
Proposition E.11.
Let p E A(L) then
Shp, (p) E argmin UDF (hlp) argmin UnF (hlp) argmin UDF (hlp) (N)ly(N)
REP(N)
(eM)
Proof. We prove first the first equality. By definition of hF 8, hF (h, hF hh (h"" 1) for any I. Therefore, UnF (hpp)hlp) Unr (hm=)lp) and
argmin UnF (h)p) argmin UnF h (p) argmin UbF (hlp)
REP(N)
KEP(N)
kEl)((N)
(UT(())
Then for the second equality:
argmin ULF (hlp) = argmin ULF ( (6b())) argiii Unp, (hlp) (N)
(A))
heMr(N)
Last equlity holds by setting h' = = (h) and using Proposition E.2.3.
From now on the problem at stake is therefore
She, (p) argmin Unr, (hlp) (ell
37

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
E.2.4. MAIN RESULTS ABOUT hF
We begin by proving result we are going use lot. Let 3 E I2, let h E (N) and for n E N we denote d(n) the depth of node We have
hF (h, (1 11+83 B2) (lnA(()) [b] 32 (d(1) +1)
(8)
In fact,
hR(h,)) 1hN(A())
Ján A()
[A(D)
d(() +1
=d(0++
And,
hP(h, ((D)( [M]
And therefore,
(1+ 82)
(1 82)
(1+33) 1h n A())
hF hF (h,
6P(h.) + f3 hR(h.) ThAA(TT + 32 400+1
[1] + B (d(l) + 1)
We continue by proving the following result:
Lemma E.12. Let p E (()) and dmin maxtec d(l) the minimum depth of leaf nodes, then Shr, (p) * 0 and the optimal expected utility (Chr, (p)lp) is lower-bounded as follows
1 1 1 32
Unr (p)lp) 2 + 32. (dmin 1)
(9)
Proof.
UnF 0
And,
(1 + g2)
r A(T)
1 82 1 (2 1)
UnF (rlp) =
<
r + 32.
d(l) + 1)
dhin
Therefore, as UnF, (rlp) UnF (0lp). Shr, (p) + and,
1 32 Unp (Shr, (p) 2 Uhr (rlp) 2 + 82. (dmin + 1)
This completes the proof.
Let us now prove the following lemma.
Lemma E. Let ((C) and n E (r)r and (m))( = maxie((1) d(l) the leaf nodes maximum depth among leaf descendants of n. Then,
p(n) (dmmat))))) 4mi
hFa
(n)
& (p)
Proof. Let E (NV) be non-empty. Let n E Nhh then,
38

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
(1+ 1 (
UnF ( Σ
p() hF -=) Ex(1)
p(1)
U {y) + (d(()) +1)
IEC
IEC
|M/+1
= =114411++1
=|hnA(01
(1 87) 1 {y) n()))
E p(l) (1+ 1 (y) n A())
Σ p(1)
[1| + + (d(()) 1)
[b| + 1+ (3((() +1)
IE (m)
(EC)C(n)
1+ 32
(1+ ( A11
Σ
p(1)
Σ p(1)
[b| + 1 - (3((()++ +1
M + + (d(1) +1)
(E((m)
LEL
Hence,
Unr,(h ( [m}) (n}) - Unr (h)
1+
(1+ 99) 1/1 A
(1+ (1+ 1/ 1 A(DI
Σ
p(1)
+ Σ p())
Σ p(l)
+++1+
1h] +1+ 3 (d(1) +1)
[h| (d((() +1)
(EC(m)
IEC
IEC
Combining second and third term we obtain:
Une ( (mbll) Unp (hlp)
1 1+ 12 g²
(1 + BP) (A
Σ p(()
Σ p(l)
h + + 82
d(1))
(1h) + + 32 d(I) + ))((m] + (d(((() + 1))
IEL(M)
IEC
2daa+i +1
1 32
Σ p(()
1
p(1)
(1 B2) 1h n A())
h + + 32 (cmin
[ + 1 + B2 (dmmax (n) +1
[/] + (2(((() +1)
IEC(n)
LEC
=p(n)
-Une (hlp)
1 32
h 1 82 (dmin 1) p((())))))))
[h] 1 (dmmm (n) + 1) UnF (hlp)
Now, let us conclude the proof.
If Eür, e (p) = (r] then hF, c {n N. N..(()) 2 (x) } because p(r) 1. If Eūr, (p) # (x) then Lemma E.2.4 gives us Shr, (p) # 0.
Now suppose, f (p) {n EN, 2 [+ J: it exists n E Chr, (p) such that p(n) < (+33a(mmal))11) Then consider h = Ehr, (p) {n), then previous result give us
1 + $32
Unr (CiP, (p)lp) UnF (hlp) =
p(n)
UnF (hip)
|h| 1++1+ 32 (dmia + 1)
|h| + 1 (2 (n) + 1)
1482
(fmaaaass))))))) (rr) (1)
(4
By reducing to the same denominator we obtain:
UnF (Chr, (p)lp) UnF; (hlp)
|71/32
(dmin dynar (n)) < 0
(1h) + 1 (dmin 1))(1 (d (n. + []) + 1 + (2(mmax (n) + 1)) + 52 + 1))
50
39

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
which is impossible because by definition of Shr, (p). have 2 (h),((),(()))))))) UnF (hlp). This concludes the proof SAF (p) C {n E p((n) 2 (doa +1)
Lemma E.14. Let T be hierarchy, and dmaa maxieL, d(I) the maximum depth of its leaf nodes. Let p E A(C) and n E WV {r}. Then, ShF, (p) c E
14.8"dortt)) == Q(p). and therefore, [hhF, (p)l S [Q(p)) where
[2(p] & Naa = (1+ + (dmax + 1)) (Amax + 1) = (
Proof. The first result is direct implication of Lemma E.13. Let us now show that, [Q()] (d
Let (C),, the first result implies that:
n Sup,, (p) = p(n) 2
1 + 3 (2(mmxx + 1)
Therefore,
Σ REhFA #
p(n)
2 1hr, 14 B2 (2 1)
1
1+. (claac))
This can be rewritten:
Shf (p)) S (1 (dmax + +1))
Σ p(n)
"ES (p)
p(n)
NCN
We already proved Equation of the proof of Lemma E.3 that,
Σ REN
p(n) S dmnx
This finally gives,
ShF e (p)1 S (1 (d + 1)) (dmax + 1)
Denoting Nmax = (1 + (dmax + 1)) (dmax + 1). we have
Therefore KLF (p)] < Nmax and Nmax (d
This completes the proof.
Let us now prove the main theoretical result of the article.
Theorem E.15. Let dmax maxiec d(l) be the leaf nodes maximum depth. Let A(C), then the optimal decision rule SEF, (p) can be obtained through an algorithm of O( -W]) time complexity.
Let us recall that the task, to find the optimal decision rule for the metric hFg, which is given by EhF, : A(C H, where:
Eur, (p) argmax Unz (hlp)
(N)
We adopt here similar approach Waegeman et al. (2014) to deal with the optimization problem. Let [W]
J, let us
denote U (N) {h P(N), h = nuu and [h| }}} the set of parts of N of k elements which belong U7 (N) then
Che, (p) = argmaa argmaxx Unps(hslp)
AE RE(1I..(N1) (N)
With Lemma 14 we can restrict the search
40

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
h < 1())
h4 (p)
And therefore, we can rewrite the problem as follows:
ShF, (p)
argmax argmax Unp, (hulp) (E(I..12(p)) (N)
bg (g))
Next, we rewrite UhF (hlp) as follows:
Unp UhF,(hpp) = Σ
p()) (h)
IEC
Σ (mEhnA()) EEN
(1 +1+ B²)
1n A(I)
Σ p(1)
1
B (d(t) +1
LEC
(1+182)
Σ p(I)
Σ1(n 1(n E (n)
[h] + (2(((1) + +1)
IEC
PEN
Σi Σ p(1)1(y A(I))
[1| d(l) +1
leC
1 12
Ii(nEh) Σ p(1)
[h] |1|+ 30 (d(1))
nEN
(E((n)
So that, when |/| = le we have,
1 1+ 82 k+ (d((()) +1
(hxlp)=
In( Σ p(1)
nEN IE((m)
ma))(m)
Therefore the problem can be rewritten:
Shr, (p)
argmax kE(LL..(Q()))) bu EUf (N) nEA
argmax
Σ 1nn E h)4
(10)
hxCQ(p)
Based on Equation 10 propose then the following strategy to find the optimal decision rule
1. We obtain Q(p) and compute A (n) for & < [(p)) and Q(p)
2. For each k < [((p),, we find hi which consists in the nodes that correspond to the top-k (A (1)) and compute Unr, (hīlp) ΣnErt (g)
3. We find optimal rule with hept max 2(e) Unr (hilp) and Shr, (p) him

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
Algorithm 9 Computation of depths
1: function DREC(n, 8, d)
2: if L then
3: d(n) 6 8
4: return
5: else
6: for
C C(r) do d(n) 6
7:
8:
DREC(e, 5 + 1, d)
9: end for
10: end if
11: end function
12: function DO
13: d d+00ja]
0.A4] DREC(r, 0, d)
15: return d
16: end function
Algorithm 10 Computation of Q(p)
1: function QREc(n, P. d, Q)
2: if p(n)= 2 (dmattn) then
3:
Q QU (n)
4: if E L then
5: return
6:
else
7:
for C(n) do QREC(E, p. d, Q)
8:
end for 10: end if
9:
11: else
12:
return
13:
end if
14:
end function
function Q(p, d)
Q レ 0
QREC(r, p. d, Q)
18: return
19: end function
42

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
Algorithm 11 Computation of A
1: function DELTAREC(1, p. d, k. A, 3, d)
2: if n L then
3: ((n) t p(n) =+((((m)+1)
1+0²
4: return (n)
5: else
6:
(nn) - Σ DELTAREC(G, p. k. A, 3. cEC(N)
7: return A(n)
8: end
9: end function
function DELTA(P, d, 3.
11:
A < 100xX
12:
for k +- to do
13:
DELTAREC(T, p, d, k (kk), 8)
14: end for
15: return
end function
Algorithm 12 Optimal decision rule for hF'3
[H]
function OPTIMAL ((K, A, Q)
2: ht argtopk ((n)
REQ
3:
E Engh- A(n)
4: return h",
5: end function
6: function OPTIMAL(A, Q)
+ 0 7: h
8: Mmmxx + 00
9: for [1... [ do
h, u OPTIMALK(K. A(k), Q)
11:
if Umax then
12:
Umax
13:
h" <- h
14:
end
15: end for
return h
end function
Algorithm 13 General Algorithm for hF 3
1: function FINDOPTIMAL (Preaves 3)
2:
p f- PROBANODESS(Iewvee)
D(
4:
Q <- Q(p. d)
5:
A <- DELTA(P. d, 3, (Q)
6:
h* +- OPTIMAL(A, Q)
7: return h²
8: end function
Complexity
43

---

To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hicrarchical Classifiers
General algorithm for finding fhr (p) is summarized in Algorithm 12.
It consists in:
1. Node probability computation. This is performed through a tree traversal which visit exactly once each node. Therefore the time complexity ((M)
2. Depths computation. Similarly, it is tree traversal which has ([[]) time complexity
3. (p) computation. This also performed through tree traversal which visit at most each node one. Therefore the time complexity is ((V)). This three first steps can be performed simultaneously. For convenience, we separate to make it more understandable.
4. A computation. For each & in {1... @(p)], A(k) is computed through tree traversal in which each node is visited exactly once. Therefore this step has (()) (W1) = O [W])-
5. The last step consists in enumerating all & E {1... [pp)] Each step requires first to find the top & elements of among [Q(p] which can be performed in [p)) operation and then compute the sum this & element. Overall each step has then a (1)((p) + k) = ((1(())) = (dfmax time complexity. Then, in total the total complexity is Odd
In total the algorithm has therefore overall time complexity of (dl [W]). Ths completes the proof.
44


Reviews:
[{"review_id": "hOcczlHAJ8", "reviewer": "Reviewer_maE5", "summary": "The paper introduces a framework for optimal decoding in hierarchical classification, where predictions are structured in a tree-like taxonomy. Unlike standard classification, the severity of errors varies based on the distance in the hierarchy between the predicted and true labels.\n\nMost existing methods use heuristics (like argmax or thresholding) for decoding model outputs, which may not align with the evaluation metric. The authors propose post-hoc optimal decision rules tailored to specific hierarchical evaluation metrics (e.g., hFβ score, Tree Distance Loss, Wu-Palmer).\n\nExperimental results show that the optimal decoding method outperforms heuristics by 1–5%, and up to 10% for mistake severity across various datasets and models. A higher value of the method is demonstrated in uncertain scenarios, like when input images are blurred, where simple decoding baselines struggle.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We warmly thank the reviewer maE5 for their positive feedback and their acknowledgement of the significance of our work.\n\nWe answer below to your different points.\n\n*One comment is regarding the runtime estimations, it would make sense to add the runtime based on the number of inference examples, and with that include the pre-processing complexity of Algorithm 1 to overall computations.*\n\nIndeed, varying the total number of test instances and analyzing the overall runtime evolution, including the preprocessing time of Algorithm 1, would provide a more comprehensive evaluation. We acknowledge that Table 9 in Appendix C.3 does not currently account for this. We will conduct this experiment and include the results in Appendix C.3.\n\n*The only missing item, as acknowledged by the authors, is the exploration of the set of nodes decoding strategy, and the paper could benefit from some experimental study on this. However, this is a more complicated and less practical scenario, so in my opinion it doesn’t diminish the value of the paper.*\n\nThe reviewer is correct when pointing out that we did not develop **heuristic** decoding strategies for *subset of nodes* decoding, which would have ensured a fair comparison with our **optimal** *subset of nodes* decoding strategies for the $hF_{\\beta}$-score of Section 4.3. We did attempt to design a simple heuristic based on thresholding derived from Lemma 4.6, but it resulted in poor performance.\n\n*Kulesza, 2007: Structured learning with approximate inference.*\n\nThis is indeed a reference we missed and which is relevant to our problem. We will incorporate it in the paper.", "claims_and_evidence": "All main claims are supported by clear and convincing evidence, such as:\n\n1. The proof of algorithm’s optimality, which is novel, and a solid contribution in this area;\n\n2. The experiments showing improvement over the baselines, which follows from the optimality principle;\n\n3. Demonstration of the method at various levels of classifier quality, defined by the image blurring setup, clearly explaining that the algorithm works the best in cases when the original classifier is not accurate.\n\nOne comment is regarding the runtime estimations, it would make sense to add the runtime based on the number of inference examples, and with that include the pre-processing complexity of Algorithm 1 to overall computations.", "methods_and_evaluation_criteria": "The proposed evaluation methods are sufficient and fully explore the leaf/node decoding strategies, showing advantages and pitfalls (related to reduced method’s value vs simple baselines in case of accurate classifiers).\n\nThe only missing item, as acknowledged by the authors, is the exploration of the set of nodes decoding strategy, and the paper could benefit from some experimental study on this. However, this is a more complicated and less practical scenario, so in my opinion it doesn’t diminish the value of the paper.", "theoretical_claims": "All theoretical claims appear to be valid, providing solid results in reasonable assumptions on the loss hierarchy.", "experimental_designs_or_analyses": "The experimental setup is methodologically sound, diverse, and directly aligned with the paper’s claims. The paper could benefit from tests on larger scale datasets, but it is not necessary.", "relation_to_broader_scientific_literature": "From the broader context, the paper doesn’t consider learning scenario, only taking a given classifier output (it is acknowledged by the authors). From that perspective there is a pool of works which integrate label hierarchy into the training process, from hierarchical softmax and its variations, to the multi-label scenarios. As mentioned by the authors, it would be really interesting to see how the framework can be incorporated in model training.", "essential_references_not_discussed": "All references essential for the paper, such as [Karthik, 2021] and [Ramaswamy, 2015] are discussed. Potentially, the authors could relate the work to structured prediction, as in (Kulesza, 2007): Structured learning with approximate inference.", "other_strengths_and_weaknesses": "Overall, this appears to be a clear and well–structured paper with solid contribution, walking through all necessary details, with a comprehensive experimental study. Some mentioned shortcomings, such as absence of empirical study for this set of nodes decoding strategy, or not applying the strategy in training, to me do not diminish the paper value and can be considered as future work.", "other_comments_or_suggestions": "No other comments", "questions_for_authors": "No other questions", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VtL3DTGP8J", "reviewer": "Reviewer_k32x", "summary": "In this paper, the authors study the problem of hierarchical classification, i.e., a variant of multiclass classification problem with a predefined label hierarchy. The main focus of this paper is the decoding of optimal prediction w.r.t. a family of performance metrics called hierarchically reasonable metric from the estimated class probability. The authors first show that the family of performance metrics include a number of existing metrics, and then provide general decoding algorithms with optimality guarantees. Extensive experiments on different real-world hierarchical classification benchmarks and different metrics demonstrates the effectiveness of the proposed decoding method.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We warmly thank reviewer k32x for its positive feedback and very insightful comments.\n\nWe try below to answer your questions.\n\n*it is encouraged to include the proposed algorithms or provide a more detailed description of them in the main body.*\n\nAs the reviewer suggests, we will include the proposed algorithms within the core of the paper.\n\n*According to the problem formulation, the class probability of a label can be non-zero only if it is a leaf node of the node hierarchy, while [1,2] is free of this assumption. Indeed, this condition implicitly assumes that the hierarchy is a 'complete' one: an instance belong to a superclass/internal node means that it must be classified into its leaf descendant, which may be a strict condition. It can be helpful discuss the proposed methods without this assumption.*\n\nWe thank the reviewer for this insightful question. We acknowledge that our framework may appear more restrictive than that of [1,2], and this was a key consideration in our research.\n\nOne practical way to relax this assumption while remaining within our framework is to modify the hierarchy **before** training. Specifically, we can introduce a \"stopping\" node (a leaf node) at **each** internal node n of the hierarchy. The likelihood of this stopping node would represent the probability of belonging to any subcategory of node n, **excluding** the children of n already present in the hierarchy. This effectively \"completes\" the hierarchy, making it more general, though it prevents us from using pre-trained models and also introduces additional technical considerations and modifications to the hierarchy structure. In such a case, our theorems remain valid.\n\nLastly, we also adopted our current setup to align with recent work in the field, including Karthik et al. (2021) and Jain et al. (2023), and because the considered datasets fulfill the leaf node label assumption (meaning each instance is categorized as a leaf).\n\nWe appreciate this discussion and will consider incorporating these clarifications into the paper.\n\n*While this framework provides theoretically grounded decoding methods from class probability, the estimated 'flat' class probability may not be perfect and may affect the performance of the decoding methods.*\n\nAgain, this represents a very interesting subject for which we plan to explore further in future work. Specifically, one promising direction is to investigate how to adjust either the optimal strategy or the probability distributions when accounting for the fact that these estimations are imperfect.", "claims_and_evidence": "The claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The selected benchmark datasets are well-suited for hierarchical classification scenarios, while sample blurring effectively simulates the increasing “hardness” of samples.", "theoretical_claims": "The claims are valid and rigorously proved.", "experimental_designs_or_analyses": "The experiment designs and analyses are valid and of real-world significance.", "relation_to_broader_scientific_literature": "The prior related findings, including optimality analyses of certain hierarchical classification metrics and their heuristic decoding, are naturally related to this work since they can be seen as the special case of the proposed method.", "essential_references_not_discussed": "The related works are thoroughly discussed and compared in Section 2.", "other_strengths_and_weaknesses": "1. This work provides a unified framework of eliciting Bayes optimal prediction of from class probability, which is flexible and can be combined with arbitrary proper scoring rule for class probability estimation. \n\n2. The perspective of this work is also novel in that it focuses on the inference of optimal prediction over potentially complex prediction space, which is often neglected in the research of traditional multiclass/multilabel classification.", "other_comments_or_suggestions": "it is encouraged to include the proposed algorithms or provide a more detailed description of them in the main body.", "questions_for_authors": "1. According to the problem formulation, the class probability of a label can be non-zero only if it is a leaf node of the node hierarchy, while [1,2] is free of this assumption. Indeed, this condition implicitly assumes that the hierarchy is a 'complete' one: an instance belong to a superclass/internal node means that it must be classified into its leaf descendant, which may be a strict condition. It can be helpful discuss the proposed methods without this assumption. \n\n2. While this framework provides theoretically grounded decoding methods from class probability, the estimated 'flat' class probability may not be perfect and may affect the performance of the decoding methods. \n\n[1]. Ramaswamy, H.,Tewari, A., and Agarwal, S. Convex calibrated surrogates for hierarchical classification. ICML'15\n\n[2]. Cao,Y., Feng,L., and An,B. Consistent hierarchical classification with a generalized metric. AISTATS'24.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3CEfrXgYij", "reviewer": "Reviewer_NL1p", "summary": "This paper tackles optimal decoding in hierarchical classification by developing universal algorithms for hierarchically reasonable metrics and a specialized algorithm for hF$_β$-scores. These methods, designed to find the best prediction given a posterior probability distribution, are particularly effective in underdetermined classification tasks, as demonstrated empirically.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback even though we find the review quite unfair and not very detailed.\n\nWe try to answer the few elements you point out in the review.\n\n*The proposed method assumes that the exact posterior probability distribution is given, which is a significant limitation.*\n\nWe respectfully disagree with the reviewer on this point. We develop theoretical algorithms that are, in fact, based on the knowledge of the exact posterior probability distribution. However, in all our experiments, that restriction is relaxed, and we apply these algorithms to the estimated posterior probability distribution. We then show the empirical superiority of these theoretical algorithms.\n\n*In fact, I believe that estimating the posterior probability distribution is more challenging than the 'Bayes-optimal decoding' itself. Therefore, I do not consider the method presented in this paper to be significant.*\n\nThese are, in fact, two distinct research directions, and we believe both are interesting but they also can be seen as orthogonal problems. We strongly believe that Bayes-Optimal Decoding is worth investigating and is significant for several key reasons, which we outline below.\n\nFirst, the use of pre-trained models is becoming increasingly common and many users lack the computational resources or expertise to train these models themselves: knowing how to correctly decode these pre-trained models for a given application is therefore crucial. Second, the costs associated with misclassification errors are not necessarily known during training. Lastly, these misclassification costs are of course context-dependent across applications, and can vary through time.\n\nOur paper thus aims to provide a general framework for decoding hierarchical classifiers with respect to any specified metric.\n\n*The visibility of Figure 2 is poor.*\n\nWe will improve the visibility of Figure 2 for better clarity.\n\n*Could the authors add the missing error bars and statistical significance testing for the experiments?*\n\nFigure 2 is a boxplot, which already provides information about the distribution of results across models. \n\nHowever, it is true that we did not run multiple experiments for each of the 19 models tested, and there are several reasons for this.\n\nFirst, unlike learning algorithms, our decoding algorithms are deterministic, meaning the same probability will always produce the same prediction, regardless of the context.\n\nSecond, when using pre-trained models, they come with a single checkpoint and a predefined test set, making it uncommon to report confidence intervals in this setup. \n\nLastly, for fine-tuned models with hierarchical losses, we could have conducted multiple trainings (with different seeds), but we chose not to, in order to avoid creating a dissymmetry with the pre-trained models.\n\n*How does the proposed method compare to prior work, for example, Cao et al. (2024), when used with the tree distance loss and its generalized forms?*\n\nThe comparison of our newly introduced Bayes-optimal decodings to prior work is presented throughout the experimental section (Section 5). We have selected 8 baselines for comparison, as shown in Figure 2.\n\nCao et al. (2024) provide a theoretical result on Bayes-optimal decoding for the generalized version of the tree distance loss. We propose a more general framework and recover the Cao et al. result with Lemma 4.3, as discussed in Section 4.2.1.\n\nIn our empirical results, we chose to use only the Tree Distance Loss rather than its generalized version, due to its limited adoption in the hierarchical classification literature. However, if we had used the generalized version, our algorithm would have performed equivalently to Cao et al.'s closed-form decoding, as both are optimal.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I did not check the proofs.", "experimental_designs_or_analyses": "Figure 2 and Tables 3 through 9 lack error bars and statistical significance testing. Therefore, I cannot determine the significance of the reported results.", "relation_to_broader_scientific_literature": "The discussion of related work in Section 2 appears reasonable.", "essential_references_not_discussed": "N/A.", "other_strengths_and_weaknesses": "The proposed method assumes that the exact posterior probability distribution is given, which is a significant limitation. In fact, I believe that estimating the posterior probability distribution is more challenging than the 'Bayes-optimal decoding' itself. Therefore, I do not consider the method presented in this paper to be significant.", "other_comments_or_suggestions": "The visibility of Figure 2 is poor.", "questions_for_authors": "1. Could the authors add the missing error bars and statistical significance testing for the experiments?\n2. How does the proposed method compare to prior work, for example, Cao et al. (2024), when used with the tree distance loss and its generalized forms?\n\n## Update after rebuttal\n\nThe reviewer has addressed several of my earlier concerns, which has helped me better appreciate the main contributions of the paper. However, one important issue remains unresolved: the comparison between the proposed algorithm and that of Cao et al. (2024)—particularly in terms of the tree distance loss and its generalized variants. Despite my explicit request in the review, the authors did not provide any empirical results on this point. I consider this a significant omission, and therefore, I maintain my current score.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lhTtwOtXdt", "reviewer": "Reviewer_vH3L", "summary": "This papers investigates the problem of Bayes-optimal prediction in hierarchical multi-class classification. A decision-theoretic framework is assumed, where probabilities are estimated during training, and the Bayes-optimal prediction is computed at test time. \n\nThe authors consider three types of settings, where the output of the Bayes-optimal classifier is a leaf, a tree node, or a set of tree nodes, respectively. For the three settings, they show how Bayes-optimal predictions can be obtained for various loss functions. In the experiments, Bayes-optimal and heuristic decodings are compared to each other, showing that Bayes-optimal decodings give better results. Additional experiments are conducted to show that the advantage of Bayes-optimal decondings becomes bigger for specific probability distributions.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback and insightful points. Below, we address each question concisely.\n\n*On Theorem 4.7 and the Jaccard Index*\n\nWe would like to clarify that Theorem 4.7 and Section 4.3 **only** applies to hFβ-score and not to the Jaccard Index, or any other metric. As stated, Th. 4.7 is correct, though we will refine its formulation for clarity.\n\nDuring our research, we did attempt to extend Th. 4.7 to the Jaccard Index but were unsuccessful. This highlights the complexity of directly optimizing the Jaccard Index, which is indeed known to be an NP-hard problem.\nThe reviewer's observation on the link between F1 and Jaccard aligns with Waegeman et al. (2014), who provide theoretical bounds on the regret of using F1 decoding as a surrogate for the Jaccard Index. This suggests that Th. 4.7 could offer an alternative to bypass the intractability of Jaccard Index decoding in hierarchical classification.\n\nOverall, and as noted by the reviewer, we also decided not to use the Jaccard Index as a metric due to its limited adoption in the context of hierarchical classification.\n\n*On Theorem 4.4 and Complexity*\n\nA brute-force algorithm that evaluates all nodes has a time complexity of O(N * L), not O(N). In fact, for each node n, computing the expectation E[L(n,Y)]= Σ_l p(l) L(n, l) requires O(L) operations. Our O(d_max * L + N) algorithm therefore improves upon the O(N * L) brute-force search.\n\n*On Paper Readability and Algorithm Placement*\n\nWe acknowledge the clarity concern and will integrate key algorithms into the main text for better readability.\n\n*On Basic Concept Inclusion*\n\nIn fact, we had a hard time deciding what to include and what to exclude. One of our goals was to make the paper accessible to the hierarchical classification community, which may not be deeply familiar with Bayes-optimal decoding concepts as it is often an overlooked aspect in empirical research on hierarchical classification. This led us to include some fundamental explanations which may appear basic for an initiated reader. Still, we will try to figure out a way to make it more straightforward, as the reviewer suggests. \n\n*On Novelty in Section 4*\n\nWe acknowledge this remark and will clarify contributions by adding an introduction to Section 4. Key novelties are:\n\n**Node candidate set (Th. 4.4)**: A general optimal decoding algorithm for *hierarchically reasonable* metrics, improving complexity to O(d_max * L + N) from O(N * L).\\\n**Subset of nodes candidate set (Th. 4.7)**: An optimal decoding algorithm for hF_β scores in O(d_max² * N), improving on intractable brute-force search.\n\n*On Training with Flat/Hierarchical Classifiers and applicability of our decoding methods to hierarchically-aware probability estimates*\n\nOur decoding algorithms **do not make any assumptions** about the probability estimation procedure. They only require a probability distribution over leaves, which can be obtained from either a flat or a hierarchically-aware classifier. In practice, **we did use hierarchical-aware classifiers**. As detailed in Subsubsection Models of Section 5, our experiments included several hierarchy-aware classifiers, including the hierarchical softmax (referred to as conditional softmax, as in its original introduction). The decision to use flat classifiers from the PyTorch library was primarily driven by their applicability to our task as well their widespread availability, which facilitated the scalability of our experiments. \n\nHowever, we acknowledge that our selected models did not include nested dichotomies or probabilistic classifier trees.\n\n*On Dataset Scope*\n\nWhile we acknowledge that additional datasets could have been included, we believe the current scope is already comprehensive. As reported, we provide results for 6 metrics, compare our methods against 8 baselines, and evaluate 19 different models across 2 datasets. We draw inspiration from recent literature (Bertinetto et al., 2020; Kharthik et al., 2021; Valmadre, 2022; Garg et al., 2022; and Jain et al., 2023), which focuses on these 2 datasets.\nThat said, we have initiated experiments on a text dataset (Web of Science, Koswari et al., 2018), and we will consider adding them in the paper.\n\n*On Problem-Dependence of Bayes-Optimal Decoding*\n\nThe phenomenon highlighted by the reviewer regarding the dependency of improvement on the underlying distribution closely aligns with our experiment using progressive blurring of images. By applying blur, we shift the underlying probability distributions towards the center of the simplex. As shown in Figure 4, increased blurriness further emphasizes the importance of optimal decoding.\n\nWe agree that the theoretical study of the regret associated with using a heuristic algorithm versus the optimal algorithm is an interesting topic, as explored in works such as Waegeman et al. (2014). While such theoretical considerations are indeed challenging, we view them as a future research direction.", "claims_and_evidence": "I think that most claims are supported by convincing evidence. \n\nHowever, the claim in Theorem 4.7 is hard to believe. I think that this claim can only hold if additional restrictions are made for the loss function. For the hierarchical F-measure, this claim is probably true, but I would be surprised that the claim holds for the hierarchical Jaccard-measure (as far as I know, this measure has not been used in hierarchical classification, but it only differs from the F-measure via an extra term in the denominator). Some authors, such as Chierchetti et al. have claimed that optimal decoding for the Jaccard is and NP-hard problem. \n\nF. Chierichetti, R. Kumar, S. Pandey, and S. Vassilvitskii. Finding the Jaccard median. In\nProceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 293–311,\n2010.\n\nSo, I think that Theorem 4.7 has to be reviewed by the authors. \n\nTheorem 4.4 also looks a bit weird to me. It says that the Bayes-optimal prediction can be computed in O(d_max x |L| + |N|) time, but the the prediction is a single node, so a brute-force algorithm that investigates all nodes is also linear in the number of nodes? What I am missing here? \n\nOverall I find the paper not very easy to follow, because essential information is put in appendices. I would have liked to see the algorithms in the main paper. Section 3 could be written in a more compact manner by removing the definition environments for basic concepts. It is also not very easy to assess what the key novelty is. The paper considers a rather general setting, with three types of predictions, for which theoretical results have been established in previous works. In Section 4 I was missing a clear description of what is novel, and what is incremental to previous papers.", "methods_and_evaluation_criteria": "For me it is a weird choice to use flat classifiers during training. These classifiers ignore the hierarchy, but more specialized probabilistic models have been proposed in the past, such as nested dichotomies, probabilistic classifier trees and neural networks with hierarchical softmax output layer. It is unclear whether the proposed algorithms can be used together with hierarchical probabilistic classifiers. \n\nThe authors only analyze two datasets. I find this quite limited, because there are other hierarchical classification datasets available from several domains (vision, text, biology, etc. ). Having more datasets could be useful to study the issues reported in Section 5.2 and 5.3 more in detail. More specifically, the authors report that the improvement of Bayes-optimal decodings over heuristic is problem dependent. Similar issues have been reported in multi-label classification. For example, the improvement of Bayes-optimal versus heuristic algorithms for the F-measure depends on the underlying probability distribution. For the case where labels are independent, heuristic algorithms work better. Perhaps similar phenomena exist in hierarchical classification, which could also be studied in a more theoretical manner.", "theoretical_claims": "See above.", "experimental_designs_or_analyses": "See above.", "relation_to_broader_scientific_literature": "I believe that the topic of the paper is relevant, but it is still a bit unclear to me what's novel and what's incremental to previous work.", "essential_references_not_discussed": "I think that the most important references are included.", "other_strengths_and_weaknesses": "Strengths:\n- I think that the paper contains novel theoretical results, but I am not sure. \n- The paper is relatively well written, but some improvements can be made. \n\nWeaknesses:\n- The story is a bit unclear. \n- I am not convinced of some of the theoretical results. \n- More datasets in the experiments could be useful.", "other_comments_or_suggestions": "No.", "questions_for_authors": "See above. \n\nFor the moment I am voting for rejecting the paper, but I might change my mind after the rebuttal phase.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper addresses the inference problem in hierarchical multi-class classification. The Authors propose a new inference algorithm that operates on estimated label probabilities and achieves reduced time complexity for loss functions that are hierarchically reasonable.

The paper is in general interesting and its contribution is solid. However, some Reviewers noted that the writing could be significantly improved, as the current presentation makes it difficult to grasp the main message. Additionally, the empirical evaluation would benefit from the inclusion of more datasets. If accepted, the paper should be thoroughly revised to address the main issues raised by the Reviewers.
Decision: Accept (poster)