Label-Aware Tree Marginalization for Cold-Start Active Learning

Active learning with no labels has a well-known fix: organize the unlabeled data into a hierarchy of clusters, ask for labels in coarse clusters first, and only look inside a cluster when the labels you get back disagree. The weakness of this fix is that the hierarchy is built once, greedily, from noisy distances, and every merge it makes is permanent. If two classes were joined near the bottom of the tree, no later label can separate them, and the learner has to query almost every point underneath. We propose to stop committing to one tree. Instead, the learner keeps a probability distribution over many trees, stored compactly in a shared structure of candidate clusters. Each new label enters this distribution as evidence, so a wrongly merged cluster loses probability mass instead of trapping the learner.

The computation is exact dynamic programming over a pool of candidate clusters drawn from several seed trees. Adding labels to it costs a small term per cluster, so conditioning on each new label is cheap and deterministic. The result is a cold-start learner that can undo bad early merges without Markov chain sampling, without rebuilding the tree from scratch, and without trusting a classifier that has not been trained yet. The claim to test is concrete. On benchmarks where tree-based active learning is already strong (MNIST, Statlog Shuttle, 20 Newsgroups, and CIFAR-10/100 on pretrained features), marginalizing over trees conditioned on labels should need clearly fewer labels than pruning the best single tree. The gap should widen as the seed tree is deliberately corrupted.

Where the gap is

Two lines of work use a cluster tree to escape the cold start, and both freeze the tree. Hierarchical sampling for active learning keeps a "pruning" of a precomputed tree, meaning a set of clusters that together cover the data. It samples labels inside those clusters and splits a cluster into its children when confidence intervals show it is mixed. It is consistent and needs no initial classifier, and on Statlog Shuttle it found a rare class in 880 queries where random sampling needed more than 8,000. But an impure low-level merge forces it down to the leaves. Flattening a Hierarchical Clustering through Active Learning chooses a flat cut of a fixed tree using pairwise queries and tolerates noisy answers. Its authors state that performance is capped by the quality of the tree. These two papers motivate the proposal, because they show the tree is the bottleneck.

Three lines of work attack irreversible merging without any labels. Scalable Hierarchical Clustering with Tree Grafting (GRINCH) repairs trees with local rotations and non-local grafts. It reaches dendrogram purity 1.0 on chain-shaped data where other scalable methods sit near 0.85, but it is deterministic and passive. Tree-Based Inference for Dirichlet Process Mixtures uses Bayesian Hierarchical Clustering (BHC). BHC computes a lower bound on the marginal likelihood of a Dirichlet process mixture by summing over all partitions consistent with a tree. The paper tightens that bound by summing over trees produced by branch swaps. Cluster Trellis goes further. It builds a directed acyclic graph whose nodes are clusters and runs dynamic programming over it to get exact partition functions and exact cluster marginals. Its sparse version, seeded from a few approximate trees, nearly matches exact results with about 2% of the full cluster set. These papers supply our method. We reuse the sparse trellis recursion and the BHC hypothesis test. We add what they lack: label evidence and a rule for choosing queries.

The closest prior attempt to combine the pieces is Interactive Bayesian Hierarchical Clustering. It puts a Dirichlet diffusion tree prior over hierarchies, asks users triplet questions (which two of these three belong together), and explores trees with constrained Metropolis–Hastings moves that cut and regraft subtrees. It constrains our design in two ways. First, its authors report that the sampler is slow and was evaluated only on small subsets. Second, it assumes feedback is noiseless and consistent with a single tree. We differ on all three axes. Our marginalization is deterministic dynamic programming instead of sampling. Our queries are ordinary class labels instead of triplets. Our label model tolerates impure clusters instead of treating each answer as a hard constraint.

Core Claim

A cold-start learner should never commit to one hierarchy. It should keep a sparse trellis, meaning a pool of candidate clusters taken from several seed trees. It should update the exact posterior over all trees composable from that pool after every label, and it should query where posterior mass sits on clusters whose labels are uncertain. Recovery from bad merges then follows from Bayesian conditioning rather than from heuristic surgery on the tree. When mass concentrates on clusters that no candidate can make pure, the learner adds new candidate clusters, so the pool itself adapts.

Research Program

Let the leaves be data points, or micro-clusters for large pools. Build a trellis from several seed trees: complete linkage, average linkage, Ward, BHC, and GRINCH, all run on the same fixed features. Let $X_C$ be the features and $y_C$ the labels observed so far inside cluster $C$. Extending the BHC test to include labels, the evidence for a trellis node satisfies

$$ p(X_C, y_C) = \pi_C\, p(X_C \mid H_1)\, p(y_C \mid H_1) + (1-\pi_C) \sum_{(A,B)\in \mathcal{S}(C)} w_{AB}\, p(X_A, y_A)\, p(X_B, y_B). $$

Here $H_1$ is the hypothesis that $C$ is a single mixture component. $\pi_C$ is its prior weight from the Dirichlet process. $p(X_C \mid H_1)$ is the usual conjugate feature likelihood. $p(y_C \mid H_1)$ is a Dirichlet–multinomial likelihood of the labels in $C$, whose concentration parameter controls how much label noise a single cluster may hold. $\mathcal{S}(C)$ is the set of two-way splits of $C$ available in the trellis, and $w_{AB}$ are split weights. The factor $p(y_C \mid H_1)$ is the only addition to the unsupervised recursion.

A new label changes this factor only for clusters that contain the labeled point. Updating the posterior therefore costs time proportional to the number of trellis edges above that point, not a rebuild. An outside pass, the second half of standard dynamic programming on the graph, then gives each cluster's posterior probability of appearing as a component. Combined with that cluster's posterior label distribution, this yields a predicted label for every unlabeled point, averaged over trees.

The query rule mirrors hierarchical sampling but works on marginals. We choose a cluster with probability proportional to its posterior component mass times its expected label entropy under the posterior. We then query a point inside that cluster, picked either uniformly or as its medoid. At zero labels, the label entropy is the same for every cluster. Queries then spread across the coarse, high-mass clusters, which gives the coverage behaviour that cold-start methods such as Cold-Start Active Correlation Clustering obtain by explicit allocation of queries across regions.

Trellis expansion handles the case where every candidate cluster is wrong. Suppose a cluster keeps high posterior mass and high label entropy even though all of its trellis children are also impure. The learner then proposes new children: a two-means split of that cluster, and grafts that pull the subtree of its labeled minority toward that minority's nearest pure neighbour, as in GRINCH. This is the only non-exact step. We will report how often it fires.

Scaling is handled by making leaves micro-clusters (for example, 2,000 k-means centroids of pretrained features) when the pool is in the tens of thousands. The trellis then has at most a few multiples of $2K$ nodes for $K$ seed trees over those leaves. The analysis part of the project will state a simple bound on the number of labels the method needs. The target is a bound in terms of the posterior mass on the best pruning within the trellis, analogous to the bound in Dasgupta and Hsu's paper stated in terms of the best pruning of a single tree. We will then check this bound empirically.

Baselines

The naive reference is random sampling of labels, followed by label propagation through the same features and a downstream classifier. Active Finetuning reports 14.9% CIFAR-100 accuracy for random selection at a 1% budget, and 17.6% for flat k-means. We also include random seeding followed by entropy sampling, because that is what practitioners actually do.

The strongest tree-based competitor is Hierarchical sampling for active learning. It is the direct ancestor of this proposal, it needs no initial classifier, and it is the method whose failure mode we target. It reports roughly 12% MNIST error from a 50-node pruning with 400 labels, and 880 queries to find the rare Shuttle class. We run it on each seed tree separately and report both the best and the average tree. Running it on the best tree gives the baseline oracle knowledge that the learner would not have in practice.

For pretrained image features, the strongest cold-start competitor is ActiveFT, with a reported 26.1% CIFAR-100 accuracy at a 1% budget. We run it on identical frozen DeiT-Small features with the same fine-tuning recipe. We also compare to Flattening a Hierarchical Clustering through Active Learning. It reports 9.52% MNIST test error for N-WDP with 250 queries on a complete-linkage tree. Its queries are pairwise, so we simulate pairwise answers from labels and compare at matched oracle cost, and we state this caveat wherever the number appears.

All methods get the same features, the same pool, the same query budgets, and the same number of hyperparameter configurations tuned on a held-out split. The trellis method must use no more wall-clock time than rerunning a seed HAC once per round.

Two ablations isolate the key ingredient. The first uses a trellis built from a single seed tree with label likelihoods. It isolates conditioning within one tree from marginalizing across trees. The second uses the full trellis without label likelihoods: the unsupervised MAP tree is fixed, and hierarchical sampling runs on it. It isolates whether labels, rather than a better unsupervised tree, drive the gains.

Beating the field means the following. The method needs fewer labels than hierarchical sampling on its best seed tree to reach the same error on MNIST and 20 Newsgroups. It finds the rare Shuttle class in fewer than 880 queries. It matches or exceeds ActiveFT's 26.1% on CIFAR-100 at 1%.

Why not just…?

Why not just rebuild the tree with must-link and cannot-link constraints after each labeled batch? This is the most serious threat, because it also lets labels undo merges. Its weaknesses are that each rebuild is again greedy, that its cost grows with the pool size every round, and that it discards all probability information about which clusters were close calls. None of the file's papers test this, so we include constrained average-linkage rebuilding, fed to hierarchical sampling, as a full baseline at matched compute. If it matches our method, the honest conclusion is that marginalization adds nothing beyond label-conditioned reconstruction, and we would report that.

Why not just build one better tree with GRINCH or BHC and run hierarchical sampling on it? Better unsupervised trees help, but a better tree is still a single tree. Flattening a Hierarchical Clustering through Active Learning argues that errors in a static tree cap performance regardless of the cut. The second ablation above, and running hierarchical sampling on the GRINCH and BHC seed trees, measure this directly. The controlled corruption experiment below shows whether the benefit grows as tree quality falls.

Why not just select a diverse seed set with ActiveFT or k-means and switch to uncertainty sampling? Flat selection is fast and strong on pretrained features. However, it picks one resolution up front and has no mechanism for zooming into ambiguous regions. The Shuttle result in Hierarchical sampling for active learning shows why multi-scale sampling matters for rare classes. On balanced CIFAR with strong features, ActiveFT may well tie our method. We expect the separation to appear on imbalanced pools and on noisier features.

Why not just sample trees with Markov chain Monte Carlo, as in interactive BHC? Interactive Bayesian Hierarchical Clustering reports slow convergence and small-scale evaluation. We compare against it only on its own small UCI sets (Iris, Wine, Zoo), at equal wall-clock time, measuring the calibration of cluster marginals.

Proposed Experiments

The first experiment is a controlled corruption study on MNIST and 20 Newsgroups. We take a complete-linkage tree and inject a known number of wrong low-level merges by swapping subtrees across classes. We then plot, for each method, the number of labels needed to reach a target error against the number of injected errors. The prediction is that hierarchical sampling degrades roughly in proportion to the number of leaves under the corrupted nodes. The trellis method should degrade little, as long as any other seed tree contains the correct clusters.

The second experiment reproduces rare-class discovery on Statlog Shuttle, reporting queries until every class is found. The third runs CIFAR-10 and CIFAR-100 on frozen DeiT-Small features at 1% and 2% budgets. Here we report both accuracy under label propagation and accuracy after fine-tuning, using ActiveFT's reported protocol.

Across all experiments we report the posterior mass assigned to the true flat labeling, as a calibration check. We also report how often trellis expansion fires, and the runtime per query against rebuilding a single tree.

The decisive checks are two comparisons. The first is the gap between the full trellis and the single-tree ablation with label likelihoods: if this gap is zero, marginalizing across trees is not doing the work. The second is the gap between the full trellis and constrained tree rebuilding: if this gap is zero, the probabilistic machinery is not justified.