Research map / Learning theory and algorithms / Prediction and decision losses
To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hierarchical Classifiers
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives post-hoc Bayes-optimal decoding rules for probabilistic hierarchical classifiers under hierarchical metrics, including an efficient algorithm for hF-beta scores over node subsets, and shows gains over heuristics on image hierarchies.
Problem
Heuristic decoding rules (argmax over leaves, thresholds, top-down) in hierarchical classification often do not match the task's hierarchical evaluation metric, so predictions are suboptimal, especially for underdetermined inputs.
Approach
Adapts cost-sensitive minimum-expected-cost decoding to hierarchies: for hierarchically reasonable metrics, a lemma on node probability thresholds prunes candidate nodes to O(depth) before brute force; for hF-beta over subsets of nodes, a decomposition by augmented-set cardinality yields a polynomial algorithm.
Key results
- Optimal decoding achieves the best average score across models and metrics; the relative gain over heuristics is about 1% to 5% for most metrics and about 10% for Mistake Severity.
- The algorithms are on average 60x faster than brute force for the node candidate set, taking a few microseconds per sample.
- Relative gains of optimal decoding grow as input blur increases, i.e., as the posterior becomes more underdetermined.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use optimal decoding instead of heuristic decoding | Hierarchical classifiers · TieredImageNet-H and iNat19-H | target hierarchical evaluation metrics: from $1\%$ to $5\%$ for all metrics except Mistake Severity, which achieves a relative gain of $10\% | Helped |
| Use optimal decoding instead of heuristic decoding | Hierarchical classifiers on blurred images · Blurred test images; hFβ | relative performance decrease versus optimal decoding | Helped |
| Use the proposed optimal decoder rather than heuristics | Mistake Severity decoding · TieredImageNet-H, ConvNeXt Tiny | Mistake Severity: 0.83 -> 0.79 | Hurt |
Surprising findings
- Argmax over leaves, a common heuristic, is not optimal even for the Top-1 error metric, despite frequent use.
- Heuristics that are leaf-based are recall-oriented, and node-based ones are precision-oriented, shifting which heuristic is best across beta values.
Limitations
- Evaluated only on image datasets with tree hierarchies; text and non-tree hierarchies are not studied.
- Assumes an accurate posterior; the paper does not address calibration or estimation of the probabilities.
- No heuristic was found for set-of-nodes decoding, and the lemma-based heuristic gave poor results.
Experimental setup
Datasets: tieredImageNet-H iNat19
Benchmarks: tieredImageNet-H iNat19
Metrics: Tree distance loss Wu-Palmer similarity Zhao similarity hF-beta (beta 0.5, 1, 2) Mistake severity
Baselines: Leaf argmax Top-down HiE-self Majority rule Plurality rule Darts algorithm Expected Information
Builds on: cost-sensitive decoding for flat classification Majority decoding Darts algorithm hF-beta score
Closest papers by meaning
- Hierarchical Conformal Classification (NeurIPS 2026 · similarity 0.84)
- Principled Algorithms for Optimizing Generalized Metrics in Binary Classification (ICML 2025 · similarity 0.84)
- Learning curves theory for hierarchically compositional data with power-law distributed features (ICML 2025 · similarity 0.84)
- Expected Probabilistic Hierarchies (NeurIPS 2024 · similarity 0.84)
- A General Online Algorithm for Optimizing Complex Performance Metrics (ICML 2024 · similarity 0.83)
- Hierarchical Selective Classification (NeurIPS 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.