To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hierarchical Classifiers

We thank the reviewer for their valuable feedback and insightful points. Below, we address each question concisely.

On Theorem 4.7 and the Jaccard Index

We 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.

During 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. The 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.

Overall, 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.

On Theorem 4.4 and Complexity

A 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.

On Paper Readability and Algorithm Placement

We acknowledge the clarity concern and will integrate key algorithms into the main text for better readability.

On Basic Concept Inclusion

In 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.

On Novelty in Section 4

We acknowledge this remark and will clarify contributions by adding an introduction to Section 4. Key novelties are:

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).
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.

On Training with Flat/Hierarchical Classifiers and applicability of our decoding methods to hierarchically-aware probability estimates

Our 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.

However, we acknowledge that our selected models did not include nested dichotomies or probabilistic classifier trees.

On Dataset Scope

While 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. That 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.

On Problem-Dependence of Bayes-Optimal Decoding

The 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.

We 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.

We thank the reviewer for their feedback even though we find the review quite unfair and not very detailed.

We try to answer the few elements you point out in the review.

The proposed method assumes that the exact posterior probability distribution is given, which is a significant limitation.

We 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.

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.

These 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.

First, 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.

Our paper thus aims to provide a general framework for decoding hierarchical classifiers with respect to any specified metric.

The visibility of Figure 2 is poor.

We will improve the visibility of Figure 2 for better clarity.

Could the authors add the missing error bars and statistical significance testing for the experiments?

Figure 2 is a boxplot, which already provides information about the distribution of results across models.

However, it is true that we did not run multiple experiments for each of the 19 models tested, and there are several reasons for this.

First, unlike learning algorithms, our decoding algorithms are deterministic, meaning the same probability will always produce the same prediction, regardless of the context.

Second, 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.

Lastly, 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.

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?

The 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.

Cao 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.

In 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.

We warmly thank reviewer k32x for its positive feedback and very insightful comments.

We try below to answer your questions.

it is encouraged to include the proposed algorithms or provide a more detailed description of them in the main body.

As the reviewer suggests, we will include the proposed algorithms within the core of the paper.

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.

We 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.

One 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.

Lastly, 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).

We appreciate this discussion and will consider incorporating these clarifications into the paper.

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.

Again, 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.

We warmly thank the reviewer maE5 for their positive feedback and their acknowledgement of the significance of our work.

We answer below to your different points.

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.

Indeed, 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.

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.

The 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.

Kulesza, 2007: Structured learning with approximate inference.

This is indeed a reference we missed and which is relevant to our problem. We will incorporate it in the paper.