PaperlayerView exact revision on arXiv

Source-linked AI summary

Hierarchical Utility Calibration for Structured Multiclass Decisions

Futoshi Futami, Jerry Huang, Ichiro Takeuchi

arXiv:2609.36532v1stat.MLcs.LG

TL;DR

In hierarchical multiclass prediction, aggregate utility calibration can leave utility errors in parts of the tree unclear because internal-node contributions may cancel. The paper decomposes the utility residual and proposes HUC to assess utility-relevant contributions before cancellation; numerical experiments report reduced hierarchical utility error.

  • Problem

    Utility calibration of nested-subtree indicators does not determine branch probabilities conditional on reaching a parent, leaving utility evaluation within the hierarchy insufficiently resolved.

    Source: §2.2 · p. 5

  • Method

    HUC decomposes the utility residual into internal-node contributions and evaluates utility-relevant contributions before cancellation while keeping the target utility and predicted-utility cell fixed.

    Source: §1 · p. 2, §2.2 · p. 5

  • Results

    The utility residual admits an exact internal-node decomposition, and numerical experiments demonstrate the proposed approach’s effectiveness in reducing hierarchical utility error.

    Source: §1 · p. 2, §6 · p. 11

  • Takeaways & Limitations

    A branch-probability discrepancy can be utility-irrelevant when child-subtree mean utilities are equal, so auditing should focus on contributions that affect the target utility.

    Source: §2.2 · p. 5

    The analysis assumes a semantically fixed finite rooted label tree and a utility class specified before analysis, and UC does not by itself guarantee decision optimality.

    Source: §6 · p. 11

Abstract

from arXiv · show

In multiclass probabilistic prediction, Utility Calibration (UC), which focuses auditing on specified utilities, has recently received attention as a way to guarantee downstream decisions while controlling computational and sample requirements. At the same time, some multiclass problems have meaningful label hierarchies that play important roles in medicine and image classification, yet how UC evaluates utility within a hierarchy remains insufficiently understood. We show that the difference between realized utility and predicted mean utility admits an exact decomposition into a sum of contributions from the internal nodes of the label tree. This decomposition shows that positive and negative contributions from different nodes can cancel, and that even when UC is small, the utility errors remaining in parts of the hierarchy need not be small. To address this problem, we propose Hierarchical Utility Calibration (HUC), which evaluates each node contribution before summation while retaining the same target utility, subgroup, and predicted-utility interval. We further provide finite-sample evaluation over all predicted-utility intervals and propose HUC-Boost, which updates only violated internal nodes, with theoretical guarantees for both.

1 Introduction

Utility Calibration focuses audits on specified utilities, but hierarchical labels leave unclear how utility errors should be assessed across a tree. The paper decomposes the utility residual into internal-node contributions and proposes methods to audit and correct them.

1 Introduction

  • UC audits agreement between realized and predicted mean utility within predicted-utility intervals, focusing on specified decisions rather than the full prediction vector.Several decisions can be covered by specifying a utility class.Source: §1 · pp. 1–2
  • In hierarchical tasks, coarse and fine-grained decisions use different parts of the label tree, leaving unclear how UC aggregates their errors.The paper describes such hierarchies in medicine and image classification.Source: §1 · p. 2
  • The utility residual decomposes exactly into internal-node contributions, whose positive and negative values can cancel and leave branch errors despite small UC.UC may therefore fail to identify which branch should be inspected or corrected.Source: §1 · p. 2
  • HUC evaluates node contributions before aggregation while retaining the same target utility, subgroup, and predicted-utility interval.Its finite-sample estimator has a uniform theoretical guarantee over predicted-utility intervals; HUC-Boost updates only violated internal nodes and has theoretical guarantees.Source: §1 · p. 2
  • The paper evaluates HUC-Boost across datasets with different modalities and hierarchical structures, comparing it with direct UC-Boost and recalibration approaches.The listed comparisons include parametric methods and two-stage combinations with UC-Boost or HUC-Boost.Source: §1 · pp. 2–3

2 Preliminaries and a Limitation of Utility Calibration

The preliminaries define calibration around agreement between predictions and realized outcomes, then focus utility auditing on specified decisions. For hierarchical labels, the section shows that summing node-level utility errors can conceal their location, motivating audits that preserve a common target and predicted-utility interval.

2.1 Multiclass Calibration and Utility Calibration

  • Calibration asks whether predicted probabilities match realized frequencies among observations receiving the same prediction; testing canonical calibration without assumptions requires exponentially many samples in the number of classes.The paper motivates utility-focused auditing for a few known downstream decisions.Source: §2.1 · p. 3
  • UC evaluates whether realized utility agrees with predicted mean utility within intervals of that predicted mean, for prespecified utilities and subgroups.A utility can represent the final outcome-dependent value after a prediction-based action rule.Source: §2.1 · pp. 3–4

2.2 Cancellation in UC and Requirements for Hierarchical Auditing

  • For a fixed prediction on the four-leaf tree, the conditional utility residual decomposes into a sum of root and lower-node contributions.Each contribution compares child-subtree mean utilities under true and predicted branch probabilities, weighted by the true probability of reaching the parent.Source: §2.2 · p. 5
  • Because UC sums node contributions within each predicted-utility interval, positive and negative terms can cancel, leaving individual-level errors even when UC is small.UC alone also does not identify which internal decision to inspect when it is large.Source: §2.2 · p. 5
  • Leaf calibration does not determine conditional branch probabilities, while auditing every branch may use different populations or include branches irrelevant to the target utility.A branch-probability discrepancy need not affect utility when its child subtrees have equal mean utility.Source: §2.2 · p. 5
  • Hierarchical auditing should isolate utility-relevant node contributions before cancellation while keeping the target utility, subgroup, and predicted-utility cell fixed.This compares error sources within the same audit population and avoids including utility-irrelevant nodes.Source: §2.2 · p. 5

3 Hierarchical Utility Calibration

The section decomposes utility residuals into internal-node contributions and introduces HUC to evaluate those contributions separately under the original audit conditions. It also gives a finite-sample HUC estimator and HUC-Boost, a branch-local correction method with theoretical guarantees.

3.1 Utility-Error Decomposition and HUC on General Trees

  • Along a root-to-leaf path, node contributions telescope to the realized leaf utility minus the predicted root mean, locating the residual’s branching-step components.The decomposition applies to general trees and preserves the target utility.Source: §3.1 · pp. 6–7
  • For fixed tree and prediction, node contributions are uniquely determined and mutually orthogonal under the predictive distribution, yet their true expected values can still cancel.This separates predictive-distribution structure from the cancellation that can occur under the true distribution.Source: §3.1 · p. 7
  • HUC audits node contributions separately under the same subgroup, target utility, and predicted-utility interval, preventing cancellation across nodes.Nodes that do not affect the target utility contribute zero and can be excluded.Source: §3.1 · p. 7
  • The finite-sample HUC evaluation guarantee holds uniformly over predicted-utility intervals when the predictor, tree, and finite audit classes are fixed independently of the audit sample.Source: §3.1 · p. 8

3.2 HUC-Boost: Branch-Local Post-Hoc Correction

  • HUC-Boost selects a violated audit candidate and changes branch probabilities only at the corresponding internal node, unlike UC-Boost’s global leaf-logit updates.The algorithm uses node-wise logits to implement the local update.Source: §3.2 · p. 8
  • HUC-Boost monotonically decreases population log loss and terminates within 2Llog(f0)/ε^2 updates with HUC error at most ε.The guarantee assumes finite initial population log loss.Source: §3.2 · p. 9

4 Related Work

Related work covers calibration methods for probabilities, subgroups, and specified decisions, as well as hierarchical classification methods. This paper’s focus is probabilistic utility calibration localized to relevant nodes in a label hierarchy.

Calibration and decision-focused methods

  • Calibration work ranges from class-wise and subgroup audits to canonical calibration, whose distribution-free testing can require exponentially many samples in the number of classes.Utility Calibration instead audits prespecified utilities over predicted-utility intervals.Source: §4 · p. 9
  • Decision-oriented methods study which decisions and losses predictions can support; this paper decomposes the same target-utility residual along a hierarchy before node contributions cancel.Source: §4 · p. 9

Hierarchical classification and calibration

  • Most hierarchical classification methods use the tree for training, loss design, or output selection rather than probabilistic calibration; HUC localizes utility errors without calibrating every branch.Source: §4 · p. 9

5 Experiments

Experiments evaluate HUC-Boost on a controlled hierarchical toy problem and real datasets. The reported results show that HUC-Boost reduces hierarchical utility error, while two-stage variants can reduce update counts and improve selected metrics.

5.1 Toy data

  • The toy experiment uses a medically motivated synthetic eight-leaf tree, seven internal nodes, three decision utilities, and whole-population audits.UC- and HUC-Boost share the initial prediction and calibration labels at each sample size.Source: §5.1 · p. 10
  • After UC-Boost, HUC remains in the toy setting, whereas after HUC-Boost it decreases with sample size, despite similar decreasing UC errors.The result illustrates how node contributions can cancel when UC evaluates their sum.Source: §5.1 · p. 10

5.2 Real data

  • The real-data evaluation uses SUPPORT2’s five medically arranged outcomes and nine utilities, and iNaturalist’s 30 species in a depth-seven taxonomy.The iNaturalist utility measures top-1 correctness at class, order, family, genus, and species levels.Source: §5.2 · p. 10
  • HUC-Boost substantially reduces HUC relative to Baseline on both real datasets; after temperature or vector scaling, it yields lower mean HUC and higher mean AUC in both.The Dirichlet-based variant improves these metrics only on SUPPORT2, and all two-stage variants use substantially fewer HUC-Boost updates than direct HUC-Boost.Source: Table 1 · p. 11, §5.2 · p. 11

6 Conclusion and Limitations

The paper concludes that hierarchical utility residuals decompose into internal-node contributions, motivating HUC and HUC-Boost. Its analysis is limited to fixed finite trees and prespecified utilities, and calibration alone does not guarantee optimal decisions.

6 Conclusion and Limitations

  • The utility residual decomposes into internal-node contributions, motivating HUC’s pre-cancellation evaluation and HUC-Boost’s correction of violated branches.The conclusion also reports numerical experiments reducing hierarchical utility error.Source: §6 · p. 11
  • The analysis assumes a semantically fixed finite rooted tree and a utility class specified before analysis; it does not cover changing hierarchies or decisions outside that class.Agreement between predicted and realized utilities in expectation does not by itself guarantee decision optimality.Source: §6 · p. 11

AI use statement

The authors describe broad AI assistance across theoretical, experimental, and editorial work, while retaining responsibility for the work.

AI use statement

  • AI tools assisted with theory, proofs, experiments, data preparation, literature review, editing, and artifact preparation.The authors reviewed the assisted work, checked mathematical arguments and references, tested the implementation, and take full responsibility.Source: AI use statement · p. 12

Guide to the Appendices

The appendices define the tree-based utility and probability framework, develop binary-tree intuition, and establish the path decomposition used in the paper.

Appendix Content and proof locations

  • Appendices A–K locate proofs, empirical protocols, related work, and additional experiments across the paper’s technical and applied results.The guide identifies formal tree definitions, HUC and HUC-Boost proofs, finite-sample evaluation, and real-data studies.Source: Appendix Content and proof locations · p. 16

A.1 Utility Functions and Decision-Making

  • Utilities include fixed payoff, rank-based, and decision-induced forms; subtree-indicator utility is one when the true label lies in the reported subtree.Its predicted mean is the probability assigned to that subtree, and the appendix also specifies experiment-specific utility classes and rules.Source: §A.1 · p. 17

A.2 Probability Space, Label Tree, and Predictor

  • The theory represents labels as leaves of a finite rooted tree and defines conditional label probabilities given the predictor output.It assumes positive predicted leaf probabilities; one-child nodes have zero residual and utility contrast and do not contribute to HUC.Source: §A.2 · pp. 17–18

A.3 Tree Probabilities and Subtree Mean Utilities

  • Predicted leaf probabilities factor into conditional branch probabilities along the root-to-leaf path.The appendix also defines subtree mean utilities and node-wise audit moments for utilities, subgroups, and predicted-utility intervals.Source: §A.3 · pp. 19–20

B.1 Binary Classification: A Single Branching Node

  • The binary-classification example expresses utility error as a local utility contrast multiplied by a branch residual.The contrast is the difference between child utilities, and the residual compares the observed branch indicator with its predicted probability.Source: §B.1 · pp. 20–21

B.2 A Single Internal Node of a Binary Tree

  • At a binary internal node, the local contribution equals the child-subtree mean utility minus the parent mean for labels in that child, and is zero outside the node.The binary node’s contrast is the right-child mean minus the left-child mean.Source: §B.2 · p. 21

B.3 Path Decomposition and Conditional Means on a Binary Tree

  • On a binary tree, summing node contributions along a leaf’s path telescopes to the utility residual, while nodes outside the path contribute zero.The conditional mean of a branch residual compares the true probability of the child subtree with its predicted branch probability times the true probability of reaching its parent.Source: §B.3 · p. 22

B.4 Four-Leaf Mean-Utility Decomposition in Section 2.2

The appendix verifies the four-leaf decomposition and connects it to the general-tree construction, which uses vector-valued node quantities.

B.4 Four-Leaf Mean-Utility Decomposition in Section 2.2

  • In the four-leaf tree, the full utility residual is the sum of the top-node and two lower-node terms, each a conditional mean of the utility increment at its node.The lower-node contributions retain their true reach probabilities, and the terms correspond to the general-node contributions.Source: §B.4 · pp. 23–24

C Extension to General Trees

  • For a general internal node, the local branch residual and utility contrast are vectors whose dimensions equal the node’s number of children.The construction uses probabilities determined by the leaf distribution and introduces no auxiliary stochastic process.Source: C Extension to General Trees · p. 24

C.1 Local Algebra on a General Tree

  • The general-tree local algebra establishes recursions for subtree probabilities and mean utilities, with a local residual equal to zero for labels outside the node’s subtree.The appendix uses these identities to establish the general-tree utility-error decomposition.Source: §C.1 · pp. 24–25

C.2 Utility-Error Decomposition and Conditional Means on a General Tree

The section extends the utility-error decomposition to general trees, relates its node contributions to HUC, and studies their orthogonal representation and calibration implications.

C.2 Utility-Error Decomposition and Conditional Means on a General Tree

  • For general trees, the utility residual decomposes into internal-node contributions formed from local utility contrasts and branch residuals.The node terms are determined by the true probability of reaching each node and the true-versus-predicted child probabilities.Source: §C.2 · pp. 25, 27
  • Under the common subgroup and predicted-utility interval, each relevant node’s audit moment is bounded by HUC; irrelevant nodes contribute zero.This identity retains the same target utility, subgroup, and predicted-utility cell across nodes.Source: §C.2 · p. 27

C.3 Orthogonality and Uniqueness of the Node Decomposition

  • For a fixed tree and positive predictive distribution, node components form a probability-weighted orthogonal basis and give a unique least-squares expansion of centered utility.This characterization is conditional on the chosen tree and predictive distribution; it does not assert that either the tree or HUC’s outer aggregation is optimal.Source: §C.3 · pp. 28–29

D.1 UC–HUC Comparison and the Implication of Canonical Calibration

  • The four-leaf example has UC equal to zero but HUC equal to 1/4 because opposite node contributions cancel.A separate example shows that zero indicator-utility UC and zero class-wise calibration error need not guarantee agreement of conditional branch probabilities.Source: §D.1 · p. 30, §D.2 · pp. 31–32
  • With positive prediction probabilities, zero conditional branch residuals at every internal node are equivalent to canonical calibration.Canonical calibration also implies zero HUC for the considered utilities and audit conditions.Source: §D.1 · pp. 29–30

D.3 Branch Errors versus Utility Impact

The appendix illustrates why branch-probability error alone may misidentify a target utility’s error source and why node audits must retain a shared predicted-utility population. It also establishes the path-product and update properties used in HUC-Boost’s proof.

D.3 Branch Errors versus Utility Impact

  • A branch with the largest probability error can contribute nothing to target-utility error, while a smaller error at another node contributes 1/20.In the four-leaf example, the left-node error is 2/5 but its utility contrast is zero; the right-node error is 1/10 and contributes 1/20.Source: §D.3 · pp. 32–33

D.4 Node-Specific Branch Cells Can Audit Different Populations

  • Node-specific branch-score cells can select disjoint groups, so their node contributions do not compare errors within a common population.For the same predicted-utility value 1/4, group a has a root contribution of 1/16 and group b a right-node contribution of −1/20.Source: §D.4 · p. 34
  • A full branch audit can include finite-sample fluctuations in utility-irrelevant branches, even when population branch-probability error is zero.The left-node contribution is multiplied by a zero utility contrast, so its empirical fluctuations do not affect the specified utility.Source: §D.4 · p. 34

E.1 Softmax Branches, Leaf Distribution, and Log Loss

  • Node-wise softmax branch probabilities define a positive leaf distribution whose recovered conditional branch probabilities equal the original softmax probabilities.This establishes that the update’s branch representation is consistent with its induced leaf predictions.Source: §E.1 · p. 35

E.2 Proof of Theorem 3.5

The proof shows that HUC-Boost’s one-node logit updates preserve a localized probability structure and decrease population log loss until all candidate audit moments meet the tolerance. It also explains why ordinary leaf Brier loss does not provide the same branch-local guarantee.

E.2 Proof of Theorem 3.5

  • A one-node logit update preserves probabilities outside the selected subtree, the selected node’s reach probability, and conditional leaf distributions within child subtrees.The update changes only the selected node’s branch probabilities.Source: §E.2 · pp. 35–36
  • At termination, every candidate has |Γc,u,I,v(fT)| ≤ ε; before termination, |Γt| > ε and Λt ≤ 1, so each update decreases log loss by more than ε²/2.Source: §E.2 · p. 38

E.3 Ordinary Leaf Brier Loss Is Not Branch-Local

  • Ordinary leaf Brier loss can increase for a sufficiently small update even when the local HUC residual is zero, so its first-order term does not generally yield a decrease guarantee.The mismatch arises because a full-simplex projected update need not be branch-local.Source: §E.3 · p. 39

E.4 Auxiliary Results for Softmax Path Products

  • The node-wise softmax path product defines a positive leaf probability distribution and recovers the original conditional branch probabilities.The two auxiliary results establish normalization and consistency of the induced leaf distribution.Source: §E.4 · pp. 39–40

F Finite-Sample Evaluation and Exact Auditing

This section establishes finite-sample control for HUC, shows how it reduces to UC in trees with at most one relevant node, and gives exact interval-auditing and operation-count procedures. The computational comparison identifies how localization affects the scan cost.

F. Finite-Sample Evaluation and Exact Auditing

  • For a fixed predictor independent of the audit sample, the finite-sample analysis controls HUC uniformly over predicted-utility intervals and candidate triples.The proof reduces intervals to half-lines, uses score-ordered Rademacher partial sums, then applies symmetrization, concentration, and a union bound.Source: F Finite-Sample Evaluation and Exact… · p. 40, §F.1 · p. 42

F.2 Reduction to UC with At Most One Relevant Node

  • When each utility has at most one relevant node, HUC equals UC; a flat tree recovers multiclass UC and a two-leaf tree recovers binary UC.The empirical versions also coincide under the stated condition.Source: §F.2 · p. 43

F.3 Exact Empirical Maximization over All Intervals

  • Exact empirical maximization over all intervals groups tied scores and reduces candidate intervals to contiguous blocks of ordered distinct scores.A prefix-extrema scan finds a maximizing interval in O(n log n) time from unsorted inputs, or O(n) when score order is available.Source: §F.3 · pp. 43, 45

Computational complexity of UC

  • UC precomputation for general dense utilities costs O(n|U|K), because each predicted utility requires evaluating K leaf utilities and their weighted sum.Its score sorting costs O(n|U| log n), and interval scans cost O(n|C||U|).Source: Computational complexity of UC · p. 46

Computational complexity of HUC

  • After contracting unary nodes, HUC’s dense-utility precomputation is linear in K, and its overall leading order matches UC’s stated order.The tree traversal adds linear-in-K work; the interval scan processes relevant nodes on each observation’s realized path.Source: Computational complexity of HUC · p. 47

F.4 Computational Comparison of Exact UC and HUC Auditing

  • For general dense utilities, both exact audits have leading order O(n|U|K + n|U| log n) when the subgroup class is fixed.HUC’s localization scan costs depend on relevant nodes along realized root-to-leaf paths, rather than separately enumerating intervals for every node.Source: Computational complexity of HUC · p. 47

Computational complexity of HUC

  • When subtree quantities are already available, localization’s additional scan cost is controlled by relevant nodes on realized paths, not by enumerating intervals separately for each node.The scan costs O(nDu) per subgroup and utility, where Du bounds relevant nodes on a realized path.Source: Computational complexity of HUC · p. 47

G Post-processing and HUC

The appendix relates HUC to subtree-aggregated utilities, showing how its node-wise errors bound post-processing gaps and calibration errors across fixed tree boundaries.

G Post-processing and HUC

  • S determines where each root-to-leaf path stops; leaves below that boundary share the original utility averaged under the predictive distribution within their subtree.With no branches, the aggregated utility is the predicted mean; retaining every branch recovers the original leaf utility.Source: G Post-processing and HUC · p. 48
  • Under predictive distribution p, uS remains in [−1, 1] and has the same predicted mean as u, but their means need not match under the actual label distribution.The equality is specifically under the predictive distribution.Source: G Post-processing and HUC · pp. 48–49
  • For any target utility, threshold, and ancestor-closed S, the post-processing gap is at most 2 UC(f; {1}, {uS}) and 2|S ∩ VT(u)| HUC(f; {1}, {u}).The first bound applies UC to the aggregated utility; the second bounds that error using node-wise HUC errors.Source: G Post-processing and HUC · p. 49
  • HUC bounds calibration error simultaneously for all fixed tree boundaries, with the bound scaling by the number of included utility-relevant nodes.Refining a boundary node isolates that node’s contribution under the same audit conditions.Source: G Post-processing and HUC · pp. 50–51
  • Each node contribution is the additional calibration residual from one refinement; HUC controls individual contributions that ordinary UC may hide through cancellation.For an aggregated utility, the sum is restricted to selected nodes, so small UC for the original utility alone need not imply small post-processing gaps.Source: G Post-processing and HUC · p. 51

H Empirical HUC-Boost and Fixed-Step Sample Complexity

  • HUC-Boost’s main experimental implementation uses adaptive empirical node-logit steps, while the appendix’s sample-complexity theorems cover the fixed-step specialization.The implementation also supports prescribed fixed step sizes.Source: H Empirical HUC-Boost and Fixed-Step… · p. 51

H.1 Fixed-Step Sample Complexity of HUC-Boost

This section establishes finite termination and population HUC guarantees for fixed-step HUC-Boost with fixed or learned initializers, deriving a sufficient sample-size threshold under stated conditions. It also specifies how Dirichlet, temperature, and vector initial models fit those assumptions.

H.1 Fixed-Step Sample Complexity of HUC-Boost

  • For every fixed sample, fixed-step HUC-Boost from a fixed initializer terminates after finitely many updates; with ε-independent Dfix and Ncand, n = eO(ε^-4) suffices for fixed δ.Source: §H.1 · pp. 52–53

H.2 Fixed-Step HUC-Boost with a Learned Initializer

  • Learning the initial recalibration parameter from the same audit sample retains the fixed-initializer sufficient order eO(ε^-4) for fixed δ, when the stated initializer parameters do not depend on ε.The analysis also covers pretraining on independent data when its output satisfies the fixed-initializer condition with Dfix independent of ε.Source: §H.2 · p. 54

H.3 Proofs of Theorems H.1 and H.2 for Fixed-Step HUC-Boost

  • For a fixed initializer, the proof bounds the uniform generalization gap over predictors reachable within the update budget, then combines it with terminal empirical HUC at most 3ε/4 to obtain population HUC at most ε.Reachable audit-value vectors are controlled by counting possible prediction vectors and interval-membership sets on the sample and an independent ghost sample.Source: §H.3 · pp. 55–57

H.4 Proofs for the Fixed-Step Two-Stage Method

  • For a learned initializer, the proof uses a randomized perturbation and a reference distribution to transfer the fixed-initializer generalization bound, then combines it with terminal empirical HUC to bound population HUC.The transfer bounds the sample-dependent initializer’s joint distribution with the audit sample by a product distribution involving the reference measure.Source: §H.4 · pp. 57–59

H.5 Explicit sample complexity analysis

  • Corollary H.13 gives an explicit sufficient threshold n⋆(T, Λ, ε, δ), and every integer n at least that threshold satisfies the sample condition.The corollary removes n from the right-hand side of the sufficient condition.Source: §H.5 · p. 59
  • n ≥ 2A + 2C log(2C) is sufficient for the stated sample-size condition leading to Eq. (186).The bound follows by applying log t ≤ t − 1 with t = n/(2C).Source: §H.5 · p. 59

H.6 Dirichlet, Temperature, and Vector Initial Models

  • Under the stated lower-bound and regularization assumptions, a Dirichlet initial model yields HUC(f̂; C, U) ≤ ε with probability at least 1 − δ under its substituted sample condition.The proposition’s noise width depends on qmin and K; the supplied passage gives the width as 2{1 + K log(1/qmin)}.Source: §H.6 · pp. 59–60
  • Temperature scaling satisfies the stated condition with d = 1 and Lθ = Lq; vector scaling satisfies it with d = 2K and Lθ = Lq + 1.Vector scaling requires a bounded fitted domain and initial empirical log loss bounded by D0. For temperature scaling, a bounded fitting interval with βmin > aε preserves positive inverse temperature.Source: §H.6 · p. 60
  • A fixed initializer needs no perturbation, whereas a same-sample learned initializer uses one random perturbation to transfer the uniform generalization bound at density cost Λε.The selected width aε = ε²/(2Lθ) limits the initial empirical log-loss increase to ε² and adds four to the update bound.Source: §H.6 · p. 61

I Additional Comparison with Related Work

J.1 Experimental Settings of the Main Experiment

The experiments use hierarchical label trees to evaluate utility calibration and compare HUC-Boost with UC-Boost and other recalibration methods. On iNaturalist, HUC-Boost has lower mean HUC than the fixed-step correction, while the fixed-step method retains more updates and has higher mean UC and lower mean AUC.

J.1 Experimental Settings of the Main Experiment

  • The toy experiment uses an eight-leaf, seven-internal-node tree and three decision utilities whose relevant-node sets together cover all seven internal nodes.The synthetic tree represents staged classification, and the three utilities are binary action comparisons with specified outcome sets and thresholds.Source: §J.1 · p. 62

J.2 Interpretation of the Decision Utilities

  • The decision threshold selects an action by comparing predicted expected payoffs; in the experiment, it is the conditional predicted probability of an action-1-favoring outcome within the active set.Outcomes outside the active set receive zero utility.Source: §J.2 · pp. 63–64

K Real Data

  • Each real-data comparison evaluates UC and HUC alongside accuracy and AUC, using the same target utilities and subgroups within each comparison.The methods include direct UC-Boost and HUC-Boost, temperature scaling, vector scaling, Dirichlet calibration, and two-stage combinations.Source: §K.1 · pp. 64–65, K Real Data · p. 64

K.1 Common Experimental Settings

  • The six real-data base predictors classify leaf labels directly; their internal-node probabilities are sums of descendant-leaf probabilities.Comparisons use separate training, calibration, validation, and test data, with all methods sharing base predictions within each split.Source: §K.1 · p. 64

K.2 iNaturalist 2019 (Van Horn et al., 2018)

  • HUC-Boost gives lower mean HUC than the fixed-step correction on iNaturalist, while the fixed-step method retains more updates and has higher mean UC and lower mean AUC.Across base predictors, the fixed-step method has much larger HUC for LR, GNB, and DT; RF and XGB are small exceptions.Source: §K.2 · p. 67, Table 4 · p. 67

K.3 SUPPORT2 (Knaus et al., 1995)

  • SUPPORT2 uses five functional outcomes in a binary tree and nine utilities spanning three action comparisons at three thresholds.The main comparison includes all nine utilities, and the synthetic utilities are not treatment effects or clinical guidelines.Source: §K.3 · pp. 67, 69

K.3.1 Main Results

On SUPPORT2, HUC-Boost reduces mean HUC relative to Baseline and the fixed-step correction; the supplementary results also examine utility-class expansion and other datasets. Across these settings, the reported ordering between update rules is not uniform.

K.3.1 Main Results

  • HUC-Boost reduces mean HUC relative to Baseline and the fixed-step correction on SUPPORT2, while the fixed-step method retains more updates and has higher mean UC and lower mean Accuracy.The pooled comparison covers nine utilities, six base predictors, and five data splits.Source: §K.3.1 · p. 70, Table 7 · p. 70

K.3.2 Additional Results

  • As the SUPPORT2 utility class expands, HUC-Boost keeps HUC at a similar level while selected updates grow; the fixed-step correction has higher mean HUC for every pooled class.For the two larger classes, HUC-Boost also yields lower mean HUC than direct UC-Boost.Source: §K.3.2 · p. 72, Table 10 · p. 72

K.4 MASSIVE (FitzGerald et al., 2023; Bastianelli et al., 2020)

  • On MASSIVE, both HUC-Boost and the fixed-step correction reduce mean HUC relative to Baseline, without the update-rule ordering seen in the main experiments.The reported results are for a TF–IDF logistic-regression predictor over five data splits.Source: §K.4 · p. 73, Table 11 · p. 74

K.5 NSL-KDD (Tavallaee et al., 2009)

  • The NSL-KDD results report means and sample standard deviations for ten methods over six base predictors and five data splits.The supplied passage does not state a comparative outcome among the methods.Source: §K.5 · p. 75, Table 12 · p. 75

K.6 N-BaIoT (Meidan et al., 2018)

  • The N-BaIoT results report ten methods, with means and sample standard deviations across six base predictors and five data splits; calibration and validation subsets are small.The passage does not state which method performs best.Source: §K.6 · p. 76, Table 13 · p. 76

Related papers

Loading 2609.36532v1…