Exact Class-Prior Correction for Tree-Structured Classifiers on Long-Tailed Data

When a dataset has a few very common classes and thousands of rare ones, a standard classifier learns to favor the common ones. A widely used fix is to divide the model's predicted probability for each class by how often that class appeared in training. This is easy in a flat classifier, which scores every class at once. It is not obvious how to do the same in a tree-structured classifier, which predicts a class through a sequence of small left-or-right decisions. Tree classifiers matter in this setting for two reasons. They are cheap when there are hundreds of thousands of classes. They also let a rare species borrow strength from the many training examples routed through its genus and family.

This note argues that the obvious recipe, correcting each node of the tree by the training frequency of its subtrees, is wrong in a specific way: it systematically under-boosts rare classes that sit inside subtrees dominated by common ones. We derive the exact correction. We show that it can be computed at test time with a best-first search whose cost depends on how uniform class frequencies are within each subtree. We then use that dependence as an objective for learning the tree itself, initialized from the biological taxonomy.

Core Claim

A tree-structured output layer (hierarchical softmax, where each class is a leaf and its probability is the product of branch probabilities along its root-to-leaf path) can be trained cheaply on the ordinary training likelihood, because each example only touches the nodes on its own path. The difficulty is entirely at prediction time.

For a test distribution that is uniform over classes, the correct decision is

$$\hat{y}(x) = \arg\max_j \; \frac{p_{\text{tr}}(j \mid x)}{n_j},$$

where $p_{\text{tr}}(j \mid x)$ is the tree's path-product probability and $n_j$ is the training count of class $j$. This is the same correction that Balanced Meta-Softmax builds into a flat softmax.

The tempting node-local version replaces each branch probability $p_{\text{tr}}(c \mid x)$ with one rescaled by $K_c/N_c$, where $N_c$ is the total training count and $K_c$ the number of classes in subtree $c$. The exact branch score instead multiplies $p_{\text{tr}}(c \mid x)$ by

$$f_c(x) = \sum_{j \in c} \frac{p_{\text{tr}}(j \mid x, c)}{n_j}, \qquad f_{\text{leaf } j} = \frac{1}{n_j}.$$

This factor is computable by an upward recursion: $f_c = \sum_{\text{children } c'} p_{\text{tr}}(c' \mid x, c)\, f_{c'}$.

The local factor $K_c/N_c$ equals $f_c(x)$ only when the model cannot tell apart the classes inside subtree $c$. When the input clearly belongs to a rare class $j$ inside a head-heavy subtree, $f_c(x)$ approaches $1/n_j$, which is far larger than $K_c/N_c$. The local correction then suppresses exactly the classes it was meant to rescue.

The same quantity yields an exact, pruned prediction rule. The bound $p_{\text{tr}}(c \mid x) / \min_{j \in c} n_j$ never underestimates the corrected score of any leaf under $c$. Best-first search with this bound therefore returns the exact corrected argmax. It prunes well precisely when frequencies within subtrees are homogeneous.

This explains why the frequency bins of Balanced Group Softmax (BAGS) work. BAGS splits classes into two levels of frequency-sorted groups, which is the regime where local correction becomes exact. It also explains their cost: the groups ignore semantics. The tree we want trades semantic coherence against within-subtree frequency homogeneity.

Research Program

The first component is analytical and diagnostic. We formalize the gap between local and exact correction as a function of within-subtree frequency heterogeneity. A natural measure is the coefficient of variation of $n_j$ inside each subtree, weighted by subtree mass. We then measure the gap empirically on trees with different structures. These are the biological taxonomy, a Huffman tree as in Efficient Estimation of Word Representations in Vector Space (which deliberately puts rare classes deep), a BAGS-style frequency tree, and a Brown-style clustered tree following Exploration of Tree-based Hierarchical Softmax for Recurrent Language Models. From the last paper we also reuse the parallel path computation (p-tHSM), which evaluates a whole path as one matrix-vector product.

The second component is the inference procedure: best-first search over the tree with the bound above. Cost is reported as node evaluations per query and wall-clock latency. We compare it against brute-force exact scoring of all leaves.

The third component learns the tree. Learning tree structure from scratch by gradient descent collapses into dense routing, as Arboreal Neural Network reports; that work avoids collapse by initializing from a pre-trained boosted tree. We take the same lesson but initialize from the known taxonomy (order, family, genus, species). We then allow classes to move between sibling subtrees through a soft class-to-subtree assignment. The assignment is relaxed with a scaled softmin and annealed toward a hard assignment, in the manner of RADDT's ReLU+Argmin reformulation. The objective combines the training likelihood with a penalty on expected search cost, which is a differentiable function of the soft assignment and the frequencies.

This differs from Simultaneous Learning of Trees and Representations. That method reassigns labels online to balance sample counts and purity, without regard to the class prior. It also differs from Hierarchy-Guided Multimodal Representation Learning, which uses the taxonomy only to regularize embeddings and keeps a flat head.

As a training-time variant, we train with leaf-level Balanced Softmax computed through the tree, using the recursive normalizer. This costs about as much as a flat layer during training and tests whether post-hoc exact correction of an ordinary tree loses anything.

Baselines

The naive reference point is an ordinary taxonomy-structured hierarchical softmax trained on cross-entropy with no correction, alongside a flat softmax with no correction. These two show how badly both heads favor head classes.

The strongest existing competitor is a flat classifier with prior correction. We use two forms. The first is Balanced Softmax from Balanced Meta-Softmax, without its meta-sampler, so that compute matches. The second is the decoupled classifier adjustment of Decoupling Representation and Classifier for Long-Tailed Recognition, which freezes features and rescales the classifier with learnable weight scaling (LWS) or re-trains it with class-balanced sampling. Kang et al. report 72.5% top-1 on iNaturalist 2018 with ResNet-152, and 49.9% overall on ImageNet-LT with ResNeXt-50 and LWS, with few-shot accuracy rising from roughly 8% to roughly 30%.

All heads will sit on the same instance-balanced backbone. Each will get the same epochs and the same hyperparameter search budget. Each will be run with a shared head-only fine-tuning stage, so differences come from the output layer alone. Beating these baselines means matching overall accuracy while improving few-shot and singleton accuracy beyond seed variance across three runs. On label spaces too large for a flat head, it means matching flat accuracy at a fraction of node evaluations.

Three further baselines isolate the key ingredient. The first is the same tree with node-local correction. The second is the same tree with brute-force exact correction, which separates the search's speed from its accuracy. The third is BAGS-style frequency grouping, the setting in which local correction should already be exact. On YFCC100M, the extreme-label reference is the learned tree of Jernite et al., reported at 32.1% precision against 27.2% for fastText at dimension 50.

Why not just…?

Why not just use flat Balanced Softmax or LWS? For label spaces of a few thousand species, a flat head is cheap and these methods are strong. This is a real threat on iNaturalist. The tree's case there rests only on statistical sharing for very rare classes. If flat Balanced Softmax ties our method on few-shot and singleton accuracy on iNaturalist and BIOSCAN-5M, we will report that. In that case the contribution narrows to the correction theory and to large label spaces such as YFCC100M, where a flat head is impractical.

Why not just apply Balanced Softmax at each node of a taxonomy tree? This is the obvious combination, and our analysis predicts its failure mode: rare classes inside head-heavy genera are under-boosted. The local-versus-exact ablation tests this directly. The prediction is falsified if the accuracy gap does not grow with within-subtree frequency heterogeneity.

Why not just score every leaf in parallel and divide by $n_j$? With p-tHSM this is a single batched product, and it is exactly correct. For moderate label counts it may be the right engineering answer. The search matters only if its node-evaluation savings are large at extreme scale. The brute-force baseline is included to measure that, and the learned tree must reduce search cost relative to the raw taxonomy to justify itself.

Why not just use BAGS frequency groups? These groups make local correction exact, but they throw away the taxonomy. Hierarchy-Guided Multimodal Representation Learning shows the taxonomy carries real signal under noise, reporting an accuracy gain of over 14% on BIOSCAN-1M. The comparison shows whether semantic trees plus exact correction beat frequency trees.

Proposed Experiments

The main benchmarks are iNat2017 and iNaturalist 2018, BIOSCAN-5M, ImageNet-LT, and YFCC100M. iNat2017 has 5,000+ species, and Van Horn et al. report 67.7% top-1 for Inception-ResNet-V2-SE. BIOSCAN-5M has a full insect taxonomy and many singleton classes; no reported result was found on Lacuna for BIOSCAN-5M classification accuracy. ImageNet-LT uses a WordNet-derived tree, as in Morin and Bengio. YFCC100M has 312,000 tags and tests extreme scale.

We report top-1 accuracy split into many-, medium- and few-shot classes, accuracy on singleton classes, node evaluations and latency per query, and the measured ratio between $f_c(x)$ and $K_c/N_c$ along true paths.

The decisive check is a plot of accuracy loss from local correction against within-subtree frequency heterogeneity, made across tree types and across individual subtrees. A rising relationship confirms the central claim; a flat one refutes it. The second check is whether best-first search cost on the learned tree falls clearly below that on the raw taxonomy while few-shot accuracy holds. The third is whether exact-corrected tree heads beat flat Balanced Softmax on BIOSCAN-5M singletons. If they do not, the sharing argument for trees on long-tailed data fails.