Shared-Ancestor Diversity for Batch Active Learning in Hyperbolic Space

Batch active learning picks a whole set of unlabeled examples to send to annotators at once. Its main failure is redundancy: the examples a model is most unsure about tend to sit next to each other, so a batch of the top-scoring ones repeats the same question many times. Methods that fix this measure "diversity" with ordinary straight-line distances between feature vectors. Many real pools, however, are organized like trees, for example animal categories that split into breeds or objects that split into subtypes. In a tree, two examples are redundant when they share a deep common ancestor, meaning they come from the same narrow branch. That is a different notion from being close in Euclidean space. Hyperbolic embeddings place points in a curved space whose volume grows exponentially, like the leaves of a tree, and every pair of points has a well-defined "lowest common ancestor": the point on the curved shortest path between them that lies closest to the origin. We propose to build batches that are uncertain and that avoid deep shared ancestry. Each new example is chosen so that its common ancestor with every already-selected example is as shallow as possible.

The intended setting is one where the tree is real but hidden. Under subpopulation shift, a classifier trained on some breeds of "dog" fails on unseen breeds. BREEDS measures accuracy drops of 30% to 40% on held-out subpopulations. The learner sees only coarse labels, so it does not know which sub-branches exist in the unlabeled pool. We claim that shared-ancestor diversity covers those hidden sub-branches with fewer labels than Euclidean diversity, and fewer than the obvious hyperbolic variant of plugging curved distance into an existing diversity sampler. We also claim that separating ancestor depth from distance to the origin resolves an open contradiction about what that distance means.

Core Claim

The only prior hyperbolic active learner, HALO, scores each pixel independently by the product of hyperbolic radius and prediction entropy. It reports 74.5% mIoU on GTAV→Cityscapes with a 5% labeling budget. Its argument is that radius tracks data scarcity, with a correlation of −0.899 against class frequency. HALO has no batch diversity term. It also works in domain adaptation, where a labeled source domain already exists, rather than in pool-based class-level selection.

The tempting extension is to rerun BADGE's seeding step, or a determinantal point process (a sampler that favors sets whose similarity matrix has a large determinant, as in Biyik et al.), with hyperbolic distance in place of Euclidean distance. That extension has a structural flaw. In a tree metric, the distance between two points decomposes as

$$d(x,y) = d(o,x) + d(o,y) - 2\,\delta(x,y),$$

where $o$ is the origin (root), $d$ is geodesic distance, and $\delta(x,y)$ is the depth of their lowest common ancestor, measured as its distance from $o$. In hyperbolic space this identity holds up to a small additive constant, which is the sense in which hyperbolic space is "tree-like". Geodesic distance therefore mixes two signals. One is how far each point is from the origin, which reflects specificity in Poincaré embeddings and scarcity in HALO. The other is how much ancestry the pair shares. A distance-based diversity sampler is pulled toward boundary points even when they all hang off the same branch.

We instead score redundancy directly by ancestor depth. Starting from an empty batch $S$, we draw each new point $x$ with probability proportional to

$$p(x \mid S) \propto u(x)\,\exp\!\big(-\beta \max_{s\in S} \delta(x,s)\big),$$

where $u(x)$ is a classifier uncertainty score (the margin between the top two predicted probabilities) and $\beta$ controls how strongly shared ancestry is penalized. This "shared-ancestor diversity" keeps uncertainty and branch coverage as separate signals. Radius enters only through $u$, if at all, and never through diversity.

Research Program

The model is a standard backbone followed by a hyperbolic projection head. We use the Lorentz model, which avoids the blow-up near the Poincaré boundary, and also test a Poincaré head with HALO's feature reweighting to stabilize it. The head is trained with the coarse classification loss plus the continuous Dasgupta-cost triplet loss from HYPHC. That loss is computed on labeled and unlabeled points alike, so it organizes the unlabeled pool into a continuous tree without fine labels. HYPHC supplies the method: its continuous lowest common ancestor is exactly our $\delta$. HYPHC never used the tree to choose queries, and that is the step we add. Unlike Cluster-Margin, which runs Euclidean agglomerative clustering once on the initial features and never updates it, our tree is re-embedded at every round as the classifier changes. This addresses the stale-clustering limitation that Cluster-Margin leaves open. For pools too large for the $O(nk)$ greedy step, we decode a discrete tree with HYPHC's fast greedy decoder and replace exact ancestor depths with tree-node depths. That gives a hierarchical analogue of Cluster-Margin's round-robin sampling across clusters.

A second, analytical thread tests the radius contradiction head-on. Xu et al. and Nickel and Kiela read radius as hierarchical depth, while HALO reads it as scarcity. On BREEDS pools we will deliberately oversample some fine subpopulations and starve some coarse classes, then measure the partial correlation of radius with frequency and with WordNet depth. If radius tracks depth once frequency is controlled, HALO's radius-times-entropy score will waste budget on dense, specific leaves, and shared-ancestor diversity should be most useful exactly there.

Baselines

The naive reference is uniform random sampling at the same batch sizes. The simplest uncertainty baseline is top-k margin sampling, which Discriminative Batch Mode Active Learning identifies as redundancy-prone.

The strongest general competitors are BADGE and Cluster-Margin. BADGE runs k-means++ seeding on gradient embeddings computed from the last layer. Cluster-Margin runs agglomerative clustering once, then samples margin-filtered points round-robin across clusters, smallest cluster first. Cluster-Margin is the most relevant of the two because it already uses a hierarchy to diversify. Its reported strength is at scale: on Open Images v6 it reached pooled AP 0.76 with about 920K labels at 100K batch size, which is 29% fewer labels than the next best baseline Batch Active Learning at Scale. No reported result was found on Lacuna for any active learning method on BREEDS, so all BREEDS numbers will come from our own reruns.

Every method shares the same backbone, initial labeled set, batch schedule, and retraining recipe. Each gets the same hyperparameter search budget, for example over $\beta$ for ours, cluster count for Cluster-Margin, and so on. We report three seeds per method.

We include a HALO-style score, radius times entropy with top-k selection, computed from our hyperbolic head. This isolates the gain from adding batch diversity to HALO's idea.

Three ablations isolate the key ingredient. The first is hyperbolic-geodesic k-means++, which uses the same head and the same uncertainty weighting but measures diversity by distance. Comparing it with our method tests the decomposition argument. The second is Cluster-Margin run on our hyperbolic features, which separates the effect of geometry from the effect of re-clustering each round. The third removes the HYPHC loss from training the head.

Finally, an oracle sampler stratifies over the true WordNet subclasses. Beating our method by this oracle gives an upper reference rather than a competitor.

Our method counts as beating the field if, across BREEDS tasks, it reaches the target-subpopulation accuracy of the best of BADGE, Cluster-Margin, and geodesic k-means++ with a clearly smaller label budget, outside seed variance, and closes a meaningful share of the gap to the oracle.

Why not just…?

Why not just run BADGE or Cluster-Margin on ordinary, higher-dimensional features? This is the default and could be enough, since high-dimensional Euclidean space can hold much of a hierarchy. Nickel and Kiela's evidence that Euclidean space needs far more dimensions to avoid crowding comes from embedding known taxonomies, not from active learning. It motivates our hypothesis but does not prove it. The direct test is the head-to-head on BREEDS with matched features. We also run Euclidean Cluster-Margin with re-clustering each round, so that any gain cannot be credited to freshness rather than geometry. If Euclidean methods match ours on subpopulation coverage, the geometric claim fails.

Why not just stratify by the known taxonomy? When the fine hierarchy is known, this is simple and probably hard to beat, so we treat it as the oracle rather than a rival. Our claim applies only when sub-branches are latent, which is the BREEDS regime by construction. We also measure how much of the oracle's advantage the learned tree recovers.

Why not just plug hyperbolic distance into k-means++ or a determinantal point process? This is the most serious threat, because it is a one-line change. Our argument against it rests on the decomposition above: geodesic distance rewards large radius, so batches drift toward boundary points from shared branches. The ablation settles the question. We will report subpopulation coverage, defined as the fraction of target subclasses that receive at least one label, together with the mean radius of selected points for both samplers. If geodesic k-means++ performs as well, we will report the simpler method as the contribution.

Why not just add a Euclidean diversity step to HALO's score? This combines HALO's scarcity signal with a standard fix for redundancy. Its weakness is the radius ambiguity. The controlled-imbalance experiment shows whether radius times entropy over-selects dense specific leaves. Shared-ancestor diversity should be robust to that failure because it ignores radius.

Proposed Experiments

The main benchmark is the four BREEDS tasks: LIVING-17, NON-LIVING-26, ENTITY-13, and ENTITY-30. The learner starts from labeled source subpopulations and queries coarse labels from an unlabeled pool that contains the unseen target subpopulations. We report three measures as functions of labels spent: accuracy on target subpopulations, worst-subpopulation accuracy, and subpopulation coverage. Coverage is computed from WordNet subclasses that the learner never sees.

CIFAR-100, with 20 superclasses each containing 5 classes, serves as a second testbed using coarse-only queries. The CIFAR-10 and SVHN settings from the BADGE and Cluster-Margin papers act as a no-hierarchy control, where we expect no gain. A gain there would point to a generic effect rather than a hierarchical one.

A scale check on a subset of Open Images v6 at large batch sizes tests whether the tree-decoded variant keeps Cluster-Margin's efficiency.

The decisive checks are four. The first is our method against geodesic k-means++ on coverage. The second is our method against Cluster-Margin re-run on hyperbolic features each round. The third is the controlled-imbalance study of whether radius tracks depth or scarcity. The fourth is the flat-data control, where we predict no advantage. If the first check shows no difference, the central claim is wrong.