Bushy Trees for Safer Pseudo-Labels: Retreating to Ancestor Classes in Self-Training

Self-training (a model labels unlabeled data with its own guesses, then trains on those guesses) breaks down on fine-grained data. The model confuses sibling species, grows confident in the wrong one, and then trains on that mistake until it hardens. Current fixes offer three responses to an uncertain guess. They keep it, shrink its weight, or flatten it into a uniform distribution. Each response discards a fact the model usually has right, namely which group of classes the image belongs to. We propose that when the model cannot name the leaf class, it should pseudo-label the image with the deepest ancestor in a class tree that it can name reliably, and train on "this is some genus-G species" instead of on a wrong species or on nothing. A statistical calibration procedure called split conformal prediction chooses that ancestor. The procedure uses a small labeled held-out set to pick a confidence threshold that holds with a guaranteed error rate.

The second half of the claim concerns the shape of the tree. Most trees learned from data are forced to be binary: every parent has exactly two children. Real taxonomies are "bushy," with parents that have many children. A binary tree splits a many-way family into a chain of made-up pairwise "ghost" groups. An abstaining pseudo-labeler climbing such a tree stops at these arbitrary pairs, which are either uninformative or unstable from one training round to the next. We predict that multifurcating trees, whether given or learned, yield more specific and more stable ancestor pseudo-labels than binary trees with the same leaf groupings. We also predict that this difference shows up in final accuracy, especially for unlabeled images of species the labeled set never contains.

Core Claim

The calibrated guarantee does not depend on tree shape, because conformal coverage holds for any fixed hierarchy. What depends on shape is how informative the retained label is and how consistent it stays across self-training rounds. The proposal therefore makes two claims. The first is that conformal ancestor pseudo-labels beat flat keep/down-weight/uniform treatments on fine-grained, open-set benchmarks. The second is that, holding the leaf grouping fixed, removing the binary constraint improves these pseudo-labels further. The second claim is the new one. We isolate it with an ablation that binarizes the true taxonomy. That ablation keeps every true group intact and only inserts ghost nodes.

Relation to Prior Work

The mechanism comes from Hierarchical Selective Classification. That work introduces the Climbing rule, which walks from the top leaf toward the root until an ancestor's summed probability clears a conformally calibrated threshold, and it reports a 14.94% hierarchical gain over standard selective classification on ImageNet-1k. It applies this only at test time, on frozen models, with a fixed tree, and it never asks how branching factor matters. We move Climbing inside the training loop and make tree shape the experimental variable.

The flat noise-mitigation methods motivate the gap and serve as the main competitors. Adaptive Conformal Guidance scales loss weights inversely with conformal set size. Combating Noise down-weights uncertain regions and uses soft multi-peak targets. RoPAWS sends far-from-labeled samples toward uniform predictions through an in-domain prior. All three treat uncertainty as a scalar and keep the label space flat.

The benchmark evidence comes from The Semi-Supervised iNaturalist Challenge. It reports that errors are non-random and fall within kingdom or phylum, and that the unlabeled pool contains 1,629 out-of-class species alongside 810 in-class ones. Out-of-class species are exactly the case where an ancestor label can be correct while any leaf label must be wrong. Many unseen species belong to a genus or family that the labeled classes also span.

The tree-learning tools come from Direction 1. Bayesian Hierarchical Community Discovery adds "absorb" operations to pairwise joins, so a node can become one more child of an existing parent. Binary to Bushy replaces the binary Kingman prior with a Beta coalescent and reports better purity (0.492 vs 0.474) and subtree score (0.720 vs 0.651) than the binary version. Expected Probabilistic Hierarchies gives a differentiable non-binary tree objective. We use absorb/join agglomeration on class-confusion statistics because it is cheap and discrete. We keep EPH as a second learner.

Deep Taxonomic Networks constrains the design. It names its complete-binary-tree assumption as its main limitation, which is one reason we do not build on a fixed binary latent tree. The nearest online-hierarchy method is Hierarchical Cluster Dynamics for ReID. It updates a split/merge label bank during training, but its gains saturate at two fixed levels, and it has neither a calibration guarantee nor a class tree.

Research Program

Each self-training round has four steps.

  1. Build the class tree $T$ over the $K$ labeled classes. Depending on the arm, $T$ is either given (the Linnaean taxonomy or the CIFAR-100 superclasses) or learned by agglomerating a symmetric confusion matrix. The confusion matrix is computed on held-out labeled data from the current model.
  2. Calibrate a threshold. On a labeled calibration split, we pick a threshold $\hat\theta$ so that the Climbing rule's chosen node contains the true class with probability at least $1-\epsilon$, following the HSC calibration algorithm.
  3. Pseudo-label each unlabeled image $x$. Climbing assigns $x$ the deepest node $v$ with $\sum_{c \in S(v)} p_\theta(c \mid x) \ge \hat\theta$. Here $S(v)$ is the set of labeled leaf classes under $v$ and $p_\theta(c \mid x)$ is the model's softmax probability for class $c$. The image is then trained with the ancestor loss

$$\ell(x, v) = -\log \sum_{c \in S(v)} p_\theta(c \mid x),$$

which rewards putting mass anywhere inside the subtree without choosing among siblings. It reduces to ordinary cross-entropy when $v$ is a leaf and to zero when $v$ is the root, so it contains both "accept" and "reject" as special cases.

  1. Retrain on the new pseudo-labels. The model trains on the labeled data plus the ancestor-labeled unlabeled data. The tree is then re-learned, and the round repeats.

The learned-tree arms raise a stability question. A binary tree re-learned from a slightly different confusion matrix can reshuffle its ghost pairs. When that happens, the same image receives a different ancestor pseudo-label in the next round even though nothing about it changed. We measure this directly as the fraction of images whose assigned subtree changes between rounds. We expect bushy trees to change less, because absorb operations attach an uncertain class to a stable parent instead of pairing it with whichever sibling happens to be nearest.

Out-of-class images need separate treatment. Calibration on in-class labeled data does not guarantee coverage for them, since the exchangeability assumption fails. We therefore measure ancestor coverage empirically. To have ground truth for the unseen species, we hold out a subset of in-class species from the labeled set and treat them as known-truth out-of-class species.

Baselines

The naive reference is supervised training on the labeled in-class set alone. For this reference, the Semi-iNat report gives 41.0% top-1 with an ImageNet-pretrained ResNet-50, against a 94.3% fully labeled oracle (Semi-iNat).

The flat-threshold reference is FixMatch at a 0.95 confidence threshold. The Semi-iNat report says standard methods like this fail under long tails and out-of-class data. We rerun it rather than quote it.

The strongest existing competitor on Semi-iNat is RoPAWS. The file reports 43.0% accuracy for it, 5.3 points above PAWS and 1.7 points above CCSSL (RoPAWS). It is the strongest competitor because it targets exactly our regime of uncurated pools with out-of-class images. Its answer to those images, reverting them to uniform, is the one our ancestor labels are meant to improve on.

The strongest conformal competitor is AdaConG-style weighting. It keeps a flat leaf pseudo-label and weights it inversely to conformal set size (AdaConG). The file reports only a relative gain for it, up to 5.98 points over FixMatch and FlexMatch on CIFAR-10 with 40 labels. We found no reported result on Lacuna for AdaConG on Semi-iNat or CIFAR-100, so we run it ourselves.

For fairness, every method shares the same backbone, the same pretraining, the same labeled/calibration split, and the same number of training epochs. Each method also receives the same hyperparameter search budget, set in advance as a fixed number of trials on a validation split.

Beating RoPAWS means a gain of more than 1.7 points on Semi-iNat top-1, averaged over three seeds with non-overlapping standard errors. That margin is the same size as RoPAWS's own gain over its predecessor.

Two ablations isolate the key ingredients. The first is "Climbing without a tree," which uses the raw conformal prediction set as the partial label in the ancestor loss and so tests whether nesting in a hierarchy matters at all. The second is the binarized-taxonomy ablation, which tests whether the branching factor matters once the true groupings are held fixed.

Why not just…?

Why not just use the conformal prediction set itself as a partial label, with no tree? This is the most serious threat. An arbitrary set is at least as flexible as any subtree, and it could match or beat us. Our reasons to expect otherwise are specific. Per-image sets can join unrelated classes. They carry no structure shared across images. And they cannot represent "a species of genus G not in my label set," because such a set can only list known leaves. The tree-free ablation settles the question. If it ties the tree methods on in-class accuracy and on held-out-species accuracy, we will report that hierarchy is unnecessary and drop the claim.

Why not just use Semi-iNat's given coarse labels with a multi-level classification loss? When a trustworthy taxonomy exists, it is the natural choice, and we include it as an upper reference. The given taxonomy only tells us whether ancestor supervision helps; it does not test the claim about branching or about learned trees. The binarized-taxonomy arm and the CIFAR-100 arms with the taxonomy hidden cover the realistic case where no taxonomy is available.

Why not just train on the full soft softmax distribution as the target? Soft targets copy the teacher's errors along with its hedges. Token-Level Ensemble Distillation shows students inheriting teacher blind spots from uncalibrated targets. Soft targets also offer no calibrated guarantee on the retained information. We still run soft-target self-training at matched budget, because a tie with it would weaken the case for calibration.

Why not just learn a binary tree, since agglomeration is simpler and well understood? A learned binary tree is one of our arms. The prediction is that it loses to a learned bushy tree on both specificity and round-to-round stability. The evidence from Binary to Bushy and Deep Taxonomic Networks concerns clustering quality only, so this proposal is the first test of whether that advantage carries over to pseudo-label quality.

Proposed Experiments

Datasets. The main benchmark is Semi-iNat, using both its Linnaean taxonomy and its out-of-class pool. For controlled studies we use CIFAR-100 with 20 superclasses of 5 classes each, a naturally bushy two-level tree, in low-label regimes. We also stress-test long-tail bias on CIFAR-10-LT at imbalance factor 100, where the tree must be learned.

Tree arms. On every dataset we compare six conditions:

  1. no tree (flat baselines);
  2. the true multifurcating taxonomy;
  3. the true taxonomy binarized, with each polytomy resolved by average linkage;
  4. the same binarization resolved at random;
  5. a learned binary tree;
  6. a learned bushy tree built with absorb/join agglomeration.

Metrics. We report top-1 leaf accuracy. For pseudo-labels, we report ancestor coverage, meaning the fraction whose subtree contains the true class. We report specificity as the mean information retained, $\log(K/|S(v)|)$, which counts how many binary choices the label makes. We report round-to-round subtree churn. Finally, we report accuracy separately on held-out-species images, scored by whether their ancestor labels are correct at genus and family level.

Decisive checks. Three results decide the outcome.

  • If ancestor pseudo-labels on the true taxonomy fail to beat RoPAWS and AdaConG weighting on Semi-iNat, the premise is wrong.
  • If the true and binarized taxonomies tie on accuracy, specificity, and churn, the binary-constraint claim is false. We would then present hierarchical abstention alone.
  • If learned bushy trees recover most of the gap between the learned binary tree and the true taxonomy on CIFAR-100 with superclasses hidden, the method is usable without a given hierarchy. This third check is the result that would make the work matter beyond biology.