Vision Systems & Engineering

Active Learning

How a model chooses which unlabelled images to send for labelling next, by uncertainty, disagreement, coverage or typicality, and why the best choice depends on how many labels have been bought.

intermediate

Active learning is a way of building a labelled training set in which the model takes part in choosing what gets labelled. Starting from a few labelled images and a large pool of unlabelled ones, a model is trained, an acquisition function ranks the unlabelled images by how useful their labels are expected to be, the top-ranked images go to an annotator (the oracle), and the model is retrained on the enlarged set. The loop repeats until the labelling budget is spent or the model is good enough (Gal, Islam & Ghahramani, 2017, §1; Beluch, Genewein, Nürnberger & Köhler, 2018, §3.1). The acquisition functions in use fall into a few families: the model’s own uncertainty, disagreement within a committee or ensemble, coverage of the feature space, and typicality. Which family works depends strongly on the budget: Hacohen, Dekel and Weinshall (2022) argue, in theory and experiment, that with very few labels the most typical images are the best to query and that the uncertain ones only pay off later.

This article covers the pool-based loop, the main acquisition functions for image classification, how they extend to detection, pose and segmentation, and the cold-start problem. It assumes the uncertainty measures of uncertainty estimation, which owns their definitions and calibration, and the labelling workflow of image annotation, which owns model-assisted labelling, box verification and the Segment Anything data engine. Choosing a subset of an already labelled set once, without a model in the loop, is data pruning, covered under dataset curation. The robotic sense of choosing where to look next belongs to active perception.

Purpose

Labels are the expensive part of a supervised vision system. Beluch et al. (2018, §1) note that in medical imaging labelling needs trained specialists, so labelling resources rather than computing power or model capacity becomes the main bottleneck. Gal et al. (2017, §1) open with the same point: obtaining labelled data can be a long, laborious and costly process. Active learning addresses this by spending the labelling budget where the current model expects to learn most, instead of on a uniform random sample. Its goal, as Beluch et al. put it, is the smallest labelled set that reaches a given accuracy.

The size of the possible saving is an empirical question. On MNIST with a small Bayesian CNN, Gal et al. (2017, Table 1) report that reaching 5% test error took 295 acquired images with the Variation Ratios acquisition function and 835 with random acquisition. On CIFAR-10 with a DenseNet, Beluch et al. (2018, Table 2) report that an ensemble with Variation Ratio needed on average 2,906 fewer labelled images (29.2%) than a single network with entropy to reach 85% accuracy. Such gains are reported for particular models, budgets and datasets; the cold-start results below show settings where the usual acquisition functions do no better than random selection.

When to Use It

Active learning fits when:

  • unlabelled images are plentiful and labels are costly, as for medical images (Beluch et al. evaluate on diabetic retinopathy; Gal et al. on skin-lesion images from ISIC 2016) or industrial defects;
  • labelling can be done in rounds, with a model retrained between them, so that annotators and training are coordinated;
  • the classes or conditions of interest are rare, so that a random sample would spend most labels on common, easy cases. Beluch et al. (2018, §4.5) observed that on a diabetic retinopathy dataset with 19.34% unhealthy images, their ensemble-based acquisition selected unhealthy images with a significantly increased probability.

It helps less, or needs care, when:

  • the budget is very small. Hacohen et al. (2022, §1) cite several studies in which random selection outperformed most deep active learning strategies when the initial labelled set was small or absent, the “cold start” problem described below;
  • the pool is not representative of deployment. The loop selects from the pool it is given; images that are not in it cannot be queried;
  • semi-supervised learning is used anyway. Hacohen et al. (2022, §1) note recent reports that active learning adds little over random selection when combined with semi-supervised learning, and show that a strategy designed for low budgets changes this (see Evidence and Impact). Semi-supervised learning owns pseudo-labels and consistency training.
  • the goal is correct labels for one fixed set rather than a model. The LSUN cascade labels a fixed pool by classifying and discarding images, and its authors stress how this differs from active learning.

How It Works

The pool-based loop

Beluch et al. (2018, §3.1) describe pool-based active learning as follows: there is a large unlabelled pool UU and a small initial labelled set LL. In each step a model MM is trained on LL, an acquisition function a(U,M)a(U, M) chooses ss points to be labelled by an external oracle, and these are added to LL; the process is repeated, training MM from scratch with the new labels, until a budget is exhausted or a target performance is reached. Gal et al. (2017, §4) write the single-query form as x∗=arg⁡max⁡x∈Dpoola(x,M)x^* = \arg\max_{x \in D_\text{pool}} a(x, M). Hacohen et al. (2022, §3.1) use the same loop with L0L_0 the initial labelled set and call the case L0=∅L_0 = \emptyset “initial pool selection”.

The parts to decide are:

  1. The initial set, random or chosen by a label-free method.
  2. The acquisition function, below.
  3. The batch size BB per round. Deep models are retrained in rounds, so several images are queried at once; Hacohen et al. (2022, App. A.1) note that deep active learning is practical only in batch settings, which makes diversity within the batch more important.
  4. The pool scored each round. Beluch et al. (2018, §4.1) score a random subsample of fixed size from the remaining unlabelled data (for example 2,000 images on MNIST, Table 1); on CIFAR-10, Yoo and Kweon (2019, §4.1) score a random subset of 10,000 images in each cycle, a scheme they adopt from earlier work because the KK most uncertain images of the whole pool often overlap in content.
  5. The stopping rule: a fixed budget or a target accuracy on validation data.

Uncertainty sampling

The simplest functions score each unlabelled image by the model’s predicted class probabilities pc(x)p_c(x):

  • least confidence: 1−max⁡cpc(x)1 - \max_c p_c(x);
  • margin: the gap p(1)(x)−p(2)(x)p_{(1)}(x) - p_{(2)}(x) between the two largest probabilities, smallest first;
  • entropy: −∑cpc(x)ln⁡pc(x)-\sum_c p_c(x) \ln p_c(x), largest first.

Hacohen et al. (2022, §4.1) use these three as baselines under the names Uncertainty (“lowest max softmax output”), Margin and Entropy. For two classes least confidence and entropy are decreasing functions of ∣p1−12∣|p_1 - \tfrac12| and the margin equals 2∣p1−12∣2|p_1 - \tfrac12|, so with the margin taken smallest first all three rank images identically (our derivation; the example’s check C4a confirms it numerically); with more classes they differ. Gal et al. (2017, §4) call the entropy of the predictive distribution Max Entropy and define Variation Ratios as 1−max⁡yp(y∣x,Dtrain)1 - \max_y p(y \mid x, D_\text{train}), which is least confidence applied to the averaged predictive distribution. The entropies and their decomposition into aleatoric and epistemic parts are defined in uncertainty estimation, which also gives Mukhoti et al.’s (2023) warning that an acquisition rule should avoid inputs with high aleatoric but low epistemic uncertainty.

Bayesian acquisition and committees

A single deterministic model gives one probability vector per image. Gal et al. (2017, §3–4) instead sample TT models from an approximate posterior with Monte Carlo dropout and average their predictions. This makes a further function available: BALD, the mutual information between the prediction and the model parameters, I[y,ω∣x,Dtrain]=H[y∣x,Dtrain]−Ep(ω∣Dtrain)H[y∣x,ω]\mathbb{I}[y, \omega \mid x, D_\text{train}] = \mathbb{H}[y \mid x, D_\text{train}] - \mathbb{E}_{p(\omega \mid D_\text{train})} \mathbb{H}[y \mid x, \omega], which Gal et al. attribute to Houlsby et al. (2011). It is large when the sampled models are each confident but disagree. Gal et al. estimate it from the TT stochastic forward passes. They also evaluated BALD, Variation Ratios and Max Entropy with a deterministic CNN (dropout used only for regularization); the Bayesian versions attained higher accuracy early on and converged to a higher accuracy (§5.2, Fig. 2).

Query-by-committee uses several models and queries where they disagree. Beluch et al. (2018) compare an ensemble of five networks with identical architecture and different random initializations against Monte Carlo dropout with 25 forward passes and against a single network, using the same acquisition functions (entropy, BALD, Variation Ratio and the variance of the softmax outputs) on the averaged outputs. Their Variation Ratio for an ensemble is the share of members whose predicted label is not the modal one (Eq. 4). They mention bootstrapping or different architectures as further ways to de-correlate members (§3.2) but did not use them. On MNIST and CIFAR-10 the ensemble-based approach outperformed the others by a clear margin (§4.2), and the ensembles were better calibrated in the low-data regime (§4.3). Their experiments attribute part of Monte Carlo dropout’s gap to shared initialization and part to reduced effective capacity; fixing the order of training images had a negligible effect.

Coverage: the core-set approach

Uncertainty-based batches can be redundant: the top-BB images by one score may be near-duplicates of each other, the problem that dataset curation treats for whole datasets. Coverage methods choose images that represent the pool instead. Sener and Savarese (2018) introduced the core-set approach, as Hacohen et al. (2022, App. A.1) report; as Beluch et al. (2018, §3.3) describe the simpler of its two implementations, in the 2017 arXiv version they cite (titled “A Geometric Approach to Active Learning for Convolutional Neural Networks”), it chooses points that minimize the largest distance from any pool point to its nearest selected point, greedily: at each step add

u=arg⁡max⁡i∈[n]∖s  min⁡j∈sdist⁡(xi,xj),u = \arg\max_{i \in [n] \setminus s} \; \min_{j \in s} \operatorname{dist}(x_i, x_j),

the unlabelled point farthest from everything already labelled, starting from the training images, with distances in the feature space of the network’s last fully connected layer. This k-centre greedy rule is the same minimax facility-location idea that PatchCore applies to its memory bank in visual anomaly detection. In Beluch et al.’s experiments it performed similarly to random acquisition on MNIST, significantly worse than random on CIFAR-10 with a small Keras CNN, and better than random with a DenseNet (§4.2); they suggest that outliers may hinder the greedy approach.

Typicality: TypiClust

Hacohen et al. (2022) propose the opposite of querying the most confusing images when the budget is small. They define the typicality of an image as the inverse of its mean Euclidean distance to its KK nearest neighbours in a learned feature space (Eq. 4, K=20K = 20), a density estimate that uses no labels. TypiClust (§3.2) has three steps:

  1. learn a representation on the unlabelled pool by self-supervised learning (SimCLR for CIFAR and TinyImageNet, DINO for ImageNet subsets; App. F.1) and use the penultimate layer as features;
  2. cluster the pool into ∣Li−1∣+B|L_{i-1}| + B clusters with k-means, so that at least BB clusters contain no labelled image;
  3. query the most typical image of each of the BB largest uncovered clusters.

The implementation details (App. F.1) cap the number of clusters at the smaller of ∣Li−1∣+B|L_{i-1}| + B and a hyperparameter max_clusters, set to 500 for CIFAR-10 and CIFAR-100 and 1,000 for TinyImageNet and the ImageNet subsets; scikit-learn’s KMeans for up to 50 clusters and MiniBatchKMeans above; typicality from min⁡{20,cluster size}\min\{20, \text{cluster size}\} neighbours; and a greedy order of picks: among clusters with the fewest labelled points, the largest. The appendix says in one sentence that clusters “with less than 5 samples” were dropped and in the next that picks come from clusters “of size larger than 5”, which leaves a cluster of exactly five undecided; the example below uses “more than 5”. Because TypiClust needs no model trained on labels, it can also choose the initial set. Its ablations (§4.3.3) found both parts necessary: a random image per cluster, the least typical image per cluster and the most typical images without clustering all did worse.

Learned acquisition

Two methods learn what to query with an extra network. Yoo and Kweon (2019) attach a small loss prediction module to the target network that predicts, from features at several layers, the loss the network will incur on an unlabelled input; the images with the largest predicted losses are queried. Because the loss shrinks as training proceeds, a mean-squared-error target failed in their experiments, and the module is trained instead with a pairwise ranking loss with margin ξ=1\xi = 1 that only asks it to order pairs of images by their true losses (§3.3, Eq. 2; §4). Since it needs only a loss, the method applies unchanged to classification, object detection and human pose estimation, on which they evaluate it (CIFAR-10, PASCAL VOC 2007+2012 and MPII). VAAL (Sinha, Ebrahimi & Darrell, 2019) learns a latent space with a variational autoencoder trained on labelled and unlabelled images together with an adversarial discriminator that tries to tell them apart; the unlabelled images to which the discriminator gives the lowest probability of being labelled are queried (§3.3, Alg. 2). It does not use the task model’s uncertainty, and the authors evaluate it on image classification and on semantic segmentation of Cityscapes and BDD100K.

Cold start and the budget

Effective deep active learning strategies are known to need a large initial labelled set, and with a small or empty one random selection has been shown to beat most of them (Hacohen et al., 2022, §1, citing several earlier studies). This is the cold start. Hacohen et al. report that it is often explained by the poor ability of neural networks to estimate uncertainty from few labels, an explanation they attribute to earlier work. Their own account is different. In a mixture model in which one region of the data can be learned from fewer examples than the other, they show that the best sampling bias changes sign with the budget, “reminiscent of phase transition” (abstract): with few labels it pays to over-sample the easy region, with many labels the hard one (§2, Theorems 1–3). They prove that a mixture of two linear classifiers trained by least squares has an error score with this “undulating” behaviour (§2.4.1), and relate the easy region to high-density points by a nearest-neighbour argument that motivates density and diversity (§2.4.2). To test whether better uncertainty would rescue uncertainty sampling at low budgets, they selected CIFAR-10 queries by the margin of an “oracle” network trained on the whole labelled dataset; it still performed poorly, worse even than the ordinary uncertainty-based methods (§4.3.4, Fig. 8). Where the transition between low and high budgets lies depends on the task and data, and they leave its determination for future work (§5).

How to Apply It

A practical loop needs a pool, an annotation interface, a model that can be retrained in reasonable time, a held-out test set labelled independently of the loop, and a random-selection baseline run with the same budget. The example below compares eight query strategies on synthetic images whose labels are known exactly, so that the oracle is perfect and every strategy can be scored against the same test set. It is an analogue of the papers’ experiments: fixed HOG features and multinomial logistic regression take the place of a network and a self-supervised embedding, and the outcomes test this analogue, not the papers’ networks.

Data. Each image is 24×2424 \times 24 pixels and shows one of four shapes (disk, square, triangle, plus sign), either plain or striped, giving 8 classes (label = 2 × shape + striped). The nuisances are drawn independently of the label: circumradius 5 to 9 pixels, centre offset up to 3 pixels in each direction, any rotation, background level 0.2 to 0.4, contrast 0.15 to 0.6, stripes of period 3.5 to 6 pixels at any orientation (with the same mean intensity as a plain fill), zero to three thin clutter segments, a Gaussian blur of 0.5 pixels and Gaussian noise of standard deviation 0.06. Shapes are rendered with 4×44 \times 4 supersampling in (row, column) coordinates with the origin at the image centre. Each image is described by 324 HOG numbers (9 orientations, 6×66 \times 6-pixel cells, 2×22 \times 2 cells per block, L2-Hys), standardized with the pool’s own mean and standard deviation, which uses no labels.

Each seed draws two pools of 5,000 images, each with its own test set of 5,000 images from the same distribution: a balanced pool with 625 images per class, on which the hypotheses are decided, and an imbalanced pool with class shares proportional to 0.7k0.7^k for class k=0,…,7k = 0, \dots, 7 (1,592 images of class 0 down to 131 of class 7), on which the class balance of the labelled set is printed and nothing is decided.

Loop. Every strategy except typ-init starts from the same 10 random images. Each round queries B=10B = 10 images and refits the model from scratch, up to 600 labels. Test accuracy is read at 10, 20, 30, 40, 50, 60, 80, 100, 150, 200, 300, 400, 500 and 600 labels. The model’s probabilities cover only the classes present in the labelled set. The eight strategies are:

  • random;
  • least-conf, margin and entropy, the three uncertainty scores above;
  • committee: five logistic regressions fitted on bootstrap resamples of the labelled set, scored by the vote entropy −∑c(vc/5)ln⁡(vc/5)-\sum_c (v_c/5) \ln (v_c/5) of their five predicted labels. This is our departure from Beluch et al., whose ensemble members differ by random initialization and are scored by Variation Ratio among other functions: a convex learner reaches the same optimum from any initialization, so the members here differ by bootstrap, the de-correlation that Beluch et al. mention as an option. The learning curve uses the single model fitted on all labels, as for every other strategy; because Beluch et al. evaluate the ensemble itself, the committee’s own accuracy (the argmax of its members’ mean probabilities) is printed as well;
  • k-centre: the greedy rule above on the standardized HOG features;
  • typiclust: TypiClust on HOG features instead of a self-supervised embedding, with min⁡(∣L∣+B,50)\min(|L| + B, 50) k-means clusters (KMeans, n_init=3, random_state the seed), typicality from the min⁡(20,size−1)\min(20, \text{size} - 1) nearest other members of a cluster, picks from clusters with more than five members, and the shared random initial set (the set-up of Hacohen et al.’s ablation in §4.3.1);
  • typ-init: the same, but also choosing its own initial 10 (L0=∅L_0 = \emptyset, Alg. 1), as in Hacohen et al.’s main experiments. The sources leave this choice open for our comparison, so both are run.

The cap of 50 clusters is ours: Hacohen et al. used 500 for the 50,000 images of CIFAR, 1% of the pool, and 1% of 5,000 is 50, which is also where they switch from KMeans to MiniBatchKMeans. Ties in the uncertainty and committee scores are broken at random with each strategy’s own seeded generator; ties in k-centre and typicality go to the lowest index.

Checks and hypotheses. The planned checks were: C1, the model fitted on all 5,000 pool labels is learnable but not trivial, with test accuracy in [0.25, 0.95] on the balanced pool (twice chance) and [0.37, 0.95] on the imbalanced one (the majority share 0.318 plus 0.05, rounded); C2, no fit reaches the iteration limit of 5,000; C3, the class counts are exactly as designed and the drawn radius, offset and contrast lie in their ranges; C4, each component is right on an exact case: (a) the three uncertainty scores rank 1,000 random two-class probability vectors identically, (b) the incremental k-centre greedy picks the same 20 points as a brute-force recomputation, (c) typicality agrees with scikit-learn’s NearestNeighbors to a relative 10−910^{-9}, (d) vote entropy matches its closed form for three vote patterns to 10−1210^{-12}, and (e) typ-init’s first 10 picks fall in 10 different clusters.

The hypotheses, taken from the papers and decided on the balanced pool on means over seeds 0–4 with a tolerance τ=0.005\tau = 0.005 in accuracy, were:

  • H1 (cold start, Hacohen et al.): at the lowest budgets typicality ≥ random ≥ uncertainty, in separate cells: typiclust − random ≥ −τ-\tau at 20, 30 and 40 labels; typ-init − random ≥ −τ-\tau at 10, 20, 30 and 40; and random − uu ≥ −τ-\tau at 20, 30 and 40 for each of least-conf, margin and entropy;
  • H2 (high budget): margin − random ≥ −τ-\tau at 600 labels;
  • H3 (the committee, after Beluch et al.’s ensemble finding, analogue only): the committee’s accuracy minus least-conf’s, averaged over the learning curve from 20 to 600 labels, is at least −τ-\tau, (a) with the single model and (b) with the committee’s own accuracy;
  • H4: margin needs fewer labels than random to reach 95% of the full-pool accuracy (per seed, the first label count on the grid at which the target is reached). H4 holds if both reach it on all five seeds and margin’s mean count is lower, or if margin reaches it on every seed and random does not; otherwise it fails.

C1’s bars were set after a planning script: run on seed 0’s data before the plan’s section on bars was written, it printed the full-pool test accuracies that appear for seed 0 on the C1 lines below (0.3450 and 0.4800), other values of the same fits (training accuracy and iteration counts), and the time taken to generate one pool, to fit the full-pool model and to fit a 300-label model, which were used for the runtime estimate. The tolerance and every hypothesis were written before any script ran. The code uses NumPy 2.3.5, SciPy 1.16.3, scikit-image 0.25.2 and scikit-learn 1.7.2 on one BLAS thread. It loops over the seeds given on the command line (python al.py 0 1 2 3 4) and makes 5,510 logistic-regression fits. It took about 8 minutes on one CPU thread (476 and 460 seconds in two runs), and the two runs printed identical output.

The script was first run on seed 0 alone as a pilot, with every strategy, pool, check and hypothesis line; seed 0 is one of the five seeds below. The pilot’s estimate of the runtime of five seeds was above five minutes, and the editor approved running it unchanged.

# Pool-based active learning on rendered shapes: random, uncertainty, committee, k-centre and typicality.
# Usage: python al.py SEED [SEED ...]   (pilot: 0; first run: 0 1 2 3 4)
import os, sys
os.environ["OMP_NUM_THREADS"] = "1"; os.environ["OPENBLAS_NUM_THREADS"] = "1"; os.environ["MKL_NUM_THREADS"] = "1"
import numpy as np
from scipy.ndimage import gaussian_filter
from skimage.feature import hog
from sklearn.cluster import KMeans
from sklearn.linear_model import LogisticRegression
from sklearn.neighbors import NearestNeighbors

# ---------------- data: 8 classes = 4 shapes x {plain, striped}, 24 x 24 pixels ----------------
S, SS, K = 24, 4, 8
g = (np.arange(S * SS) + 0.5) / SS - S / 2          # supersampled pixel centres, origin at the image centre
YY, XX = np.meshgrid(g, g, indexing="ij")           # (row, column)
SHARES_IMB = 0.7 ** np.arange(K) / (0.7 ** np.arange(K)).sum()

def render(label, rng):
    shape, striped = divmod(label, 2)
    r = rng.uniform(5, 9)                            # circumradius, px
    cy, cx = rng.uniform(-3, 3, 2)                   # centre offset, px
    th = rng.uniform(0, 2 * np.pi)                   # rotation
    bg, c = rng.uniform(0.2, 0.4), rng.uniform(0.15, 0.6)
    y, x = YY - cy, XX - cx
    u = np.cos(th) * x + np.sin(th) * y
    v = -np.sin(th) * x + np.cos(th) * y
    if shape == 0:
        m = u**2 + v**2 <= r**2                                      # disk
    elif shape == 1:
        m = (np.abs(u) <= 0.75 * r) & (np.abs(v) <= 0.75 * r)       # square
    elif shape == 2:
        m = np.ones_like(u, bool)                                    # equilateral triangle
        for k in range(3):
            a = np.pi / 2 + 2 * np.pi * k / 3
            m &= u * np.cos(a) + v * np.sin(a) <= r / 2
    else:
        m = ((np.abs(u) <= r) & (np.abs(v) <= 0.3 * r)) | ((np.abs(v) <= r) & (np.abs(u) <= 0.3 * r))  # plus
    if striped:
        P, ph, phi = rng.uniform(3.5, 6), rng.uniform(0, 2 * np.pi), rng.uniform(0, np.pi)
        tex = 0.5 + 0.5 * np.cos(2 * np.pi * (XX * np.cos(phi) + YY * np.sin(phi)) / P + ph)
    else:
        tex = 0.5                                    # same mean as the stripes
    img = bg + c * m * tex
    for _ in range(rng.integers(0, 4)):              # clutter: 0-3 thin segments
        p0, p1 = rng.uniform(-12, 12, 2), rng.uniform(-12, 12, 2)
        d = p1 - p0
        t = np.clip(((YY - p0[0]) * d[0] + (XX - p0[1]) * d[1]) / (d @ d + 1e-12), 0, 1)
        dist = np.hypot(YY - p0[0] - t * d[0], XX - p0[1] - t * d[1])
        img = img + rng.uniform(-0.3, 0.3) * (dist <= 0.5)
    img = img.reshape(S, SS, S, SS).mean(axis=(1, 3))
    img = gaussian_filter(img, 0.5, mode="nearest")
    return img + rng.normal(0, 0.06, img.shape), (r, cy, cx, c)

def class_counts(n, imbalanced):
    if not imbalanced:
        return np.full(K, n // K)
    raw = SHARES_IMB * n; cnt = np.floor(raw).astype(int)
    cnt[np.argsort(-(raw - cnt), kind="stable")[: n - cnt.sum()]] += 1   # largest remainder
    return cnt

def make(n, imbalanced, rng):
    y = np.repeat(np.arange(K), class_counts(n, imbalanced)); rng.shuffle(y)
    imgs, pars = zip(*(render(c, rng) for c in y))
    X = np.array([hog(im, orientations=9, pixels_per_cell=(6, 6), cells_per_block=(2, 2), block_norm="L2-Hys")
                  for im in imgs])                                    # 324 label-free features
    return X, y, np.array(pars), np.array(imgs)

# ---------------- learner ----------------
MAXIT = 5000
FITS = [0, 0]                                        # [fits, fits that reached max_iter]

class Const:                                         # guard: a labelled set with a single class
    def __init__(self, c): self.classes_ = np.array([c])
    def predict_proba(self, X): return np.ones((len(X), 1))
    def predict(self, X): return np.full(len(X), self.classes_[0])

def fit(X, y):
    if len(np.unique(y)) < 2:
        return Const(y[0])
    m = LogisticRegression(C=1.0, max_iter=MAXIT).fit(X, y)
    FITS[0] += 1; FITS[1] += int(m.n_iter_[0] >= MAXIT)
    return m

def full_proba(m, X):                                # probabilities over all K classes, 0 for unseen ones
    P = np.zeros((len(X), K)); P[:, m.classes_] = m.predict_proba(X); return P

# ---------------- acquisition scores ----------------
def least_conf(P): return 1 - P.max(1)
def margin(P):
    s = np.sort(P, 1); return -(s[:, -1] - (s[:, -2] if P.shape[1] > 1 else 0))
def entropy(P): return -(P * np.log(np.where(P > 0, P, 1))).sum(1)
def vote_entropy(votes):                             # votes: (n, members) integer labels
    f = np.stack([(votes == c).mean(1) for c in range(K)], 1)
    return -(f * np.log(np.where(f > 0, f, 1))).sum(1)

def top_b(score, cand, b, rng):                      # largest scores first, random tie-break
    order = np.lexsort((rng.random(len(cand)), -score[cand]))
    return cand[order[:b]]

def kcentre_pick(F, labelled, b):
    mind = np.full(len(F), np.inf)
    for i in labelled:
        mind = np.minimum(mind, np.linalg.norm(F - F[i], axis=1))
    mind[labelled] = -1; out = []
    for _ in range(b):
        j = int(np.argmax(mind)); out.append(j)      # ties: lowest index
        mind = np.minimum(mind, np.linalg.norm(F - F[j], axis=1)); mind[out] = -1
    return np.array(out)

def typicality(Fc):                                  # inverse mean distance to min(20, size-1) other members
    k = min(20, len(Fc) - 1)
    sq = (Fc ** 2).sum(1)
    D = np.sqrt(np.maximum(sq[:, None] + sq[None, :] - 2 * Fc @ Fc.T, 0))   # pairwise Euclidean distances
    np.fill_diagonal(D, np.inf)
    return 1 / np.sort(D, 1)[:, :k].mean(1)

CLU = {}
def clustering(F, k, seed):
    if k not in CLU:
        lab = KMeans(k, n_init=3, random_state=seed).fit(F).labels_
        typ = np.zeros(len(F))
        for c in range(k):
            idx = np.flatnonzero(lab == c)
            if len(idx) > 1: typ[idx] = typicality(F[idx])
        CLU[k] = (lab, typ)
    return CLU[k]

def typiclust_pick(F, labelled, b, seed, max_clusters=50):
    lab, typ = clustering(F, min(len(labelled) + b, max_clusters), seed)
    isl = np.zeros(len(F), bool); isl[labelled] = True; out = []
    for _ in range(b):
        sizes = np.bincount(lab, minlength=lab.max() + 1)
        nlab = np.bincount(lab[isl], minlength=len(sizes))
        free = np.bincount(lab[~isl], minlength=len(sizes))
        ok = np.flatnonzero((sizes > 5) & (free > 0))
        ok = ok[nlab[ok] == nlab[ok].min()]
        c = ok[np.argmax(sizes[ok])]                  # largest of the least-covered clusters; ties: lowest index
        idx = np.flatnonzero((lab == c) & ~isl)
        j = idx[np.argmax(typ[idx])]; out.append(j); isl[j] = True
    return np.array(out)

STRATS = ["random", "least-conf", "margin", "entropy", "committee", "k-centre", "typiclust", "typ-init"]
GRID = [10, 20, 30, 40, 50, 60, 80, 100, 150, 200, 300, 400, 500, 600]
B, NMAX, NCOM = 10, 600, 5

def run_strategy(s, F, y, Ft, yt, init, seed, pool):
    rng = np.random.default_rng([seed, pool, STRATS.index(s)])
    if s == "typ-init":
        lab = typiclust_pick(F, np.array([], int), B, seed)
    else:
        lab = init.copy()
    acc, acc_com = {}, {}
    while True:
        n = len(lab)
        model_based = s in ("least-conf", "margin", "entropy")
        m = fit(F[lab], y[lab]) if (model_based or n in GRID) else None
        if n in GRID:
            acc[n] = (m.predict(Ft) == yt).mean()
        if s == "committee" and (n < NMAX or n in GRID):
            members = [fit(F[bi], y[bi]) for bi in (rng.choice(lab, n, replace=True) for _ in range(NCOM))]
            if n in GRID:
                acc_com[n] = (np.mean([full_proba(mb, Ft) for mb in members], 0).argmax(1) == yt).mean()
        if n >= NMAX:
            break
        cand = np.setdiff1d(np.arange(len(F)), lab)
        if s == "random":
            new = rng.choice(cand, B, replace=False)
        elif s in ("least-conf", "margin", "entropy"):
            P = m.predict_proba(F)
            new = top_b({"least-conf": least_conf, "margin": margin, "entropy": entropy}[s](P), cand, B, rng)
        elif s == "committee":
            votes = np.stack([mb.predict(F) for mb in members], 1)
            new = top_b(vote_entropy(votes), cand, B, rng)
        elif s == "k-centre":
            new = kcentre_pick(F, lab, B)
        else:
            new = typiclust_pick(F, lab, B, seed)
        lab = np.concatenate([lab, new])
    return acc, acc_com, lab

def checks_exact(F, seed):
    rng = np.random.default_rng(12345)
    p = rng.random(1000); P2 = np.stack([p, 1 - p], 1)
    o = [np.argsort(-f(P2), kind="stable") for f in (least_conf, margin, entropy)]
    c4a = int((o[0] != o[1]).sum() + (o[0] != o[2]).sum())
    Z = rng.normal(size=(300, 5)); init = np.array([0, 1, 2])
    inc = kcentre_pick(Z, init, 20)
    sel, brute = list(init), []
    for _ in range(20):
        D = np.linalg.norm(Z[:, None] - Z[None, sel], axis=2).min(1); D[sel] = -1
        j = int(np.argmax(D)); brute.append(j); sel.append(j)
    c4b = int((inc != np.array(brute)).sum())
    lab10 = KMeans(10, n_init=3, random_state=seed).fit(F).labels_
    Fc = F[lab10 == 0]; k = min(20, len(Fc) - 1)
    dist, _ = NearestNeighbors(n_neighbors=k + 1).fit(Fc).kneighbors(Fc)
    ref = 1 / dist[:, 1:].mean(1)
    c4c = float(np.max(np.abs(typicality(Fc) - ref) / ref))
    v = np.array([[0, 0, 0, 0, 0], [0, 0, 0, 1, 1], [0, 1, 2, 3, 4]])
    c4d = float(np.max(np.abs(vote_entropy(v) - np.array([0, -(0.6 * np.log(0.6) + 0.4 * np.log(0.4)), np.log(5)]))))
    return c4a, c4b, c4c, c4d, lab10

seeds = [int(a) for a in sys.argv[1:]] or [0]
POOLS = ["balanced", "imbalanced"]
R = {}                                               # (pool, seed) -> results
for seed in seeds:
    for pool, imb in enumerate((False, True)):
        CLU.clear()
        rng = np.random.default_rng([seed, pool])
        F, y, pars, imgs = make(5000, imb, rng)
        Ft, yt, _, imgs_t = make(5000, imb, rng)
        mu, sd = F.mean(0), F.std(0) + 1e-12
        F, Ft = (F - mu) / sd, (Ft - mu) / sd
        init = np.random.default_rng([seed, pool, 99]).choice(5000, 10, replace=False)
        full = fit(F, y)
        res = dict(full=(full.predict(Ft) == yt).mean(),
                   c3=(np.array_equal(np.bincount(y, minlength=K), class_counts(5000, imb))
                       and np.array_equal(np.bincount(yt, minlength=K), class_counts(5000, imb))),
                   pars=(pars[:, 0].min(), pars[:, 0].max(), pars[:, 1:3].min(), pars[:, 1:3].max(),
                         pars[:, 3].min(), pars[:, 3].max()),
                   finite=bool(np.isfinite(imgs).all() and np.isfinite(imgs_t).all()), y=y)
        if pool == 0:
            res["c4"] = checks_exact(F, seed)
        for s in STRATS:
            acc, acc_com, lab = run_strategy(s, F, y, Ft, yt, init, seed, pool)
            res[s] = acc; res[s + "/lab"] = lab
            if s == "committee": res["committee/own"] = acc_com
            if s == "typ-init" and pool == 0:
                lab10 = clustering(F, 10, seed)[0]
                res["c4e"] = len(np.unique(lab10[lab[:10]]))
        R[(pool, seed)] = res

# ---------------- report ----------------
TAU = 0.005
print(f"seeds {seeds}; pools of 5000, tests of 5000; B={B}, up to {NMAX} labels; tolerance {TAU}")
print("\nChecks")
for pool, lo in ((0, 0.25), (1, 0.37)):            # lower bars: 2 x chance (balanced); majority share + 0.05 (imbalanced)
    fa = [R[(pool, s)]["full"] for s in seeds]
    print(f"C1 {POOLS[pool]:10s} full-pool test accuracy per seed {' '.join(f'{a:.4f}' for a in fa)} "
          f"(bar {lo}-0.95): {'held' if all(lo <= a <= 0.95 for a in fa) else 'failed'}")
print(f"C2 fits {FITS[0]}, reaching max_iter {FITS[1]} (bar 0): {'held' if FITS[1] == 0 else 'failed'}")
for pool in (0, 1):
    for s in seeds:
        r = R[(pool, s)]; p = r["pars"]
        ok = r["c3"] and r["finite"] and p[0] >= 5 and p[1] <= 9 and p[2] >= -3 and p[3] <= 3 and p[4] >= 0.15 and p[5] <= 0.6
        print(f"C3 {POOLS[pool]:10s} seed {s}: counts {np.bincount(r['y'], minlength=K).tolist()} as designed {r['c3']}, "
              f"r {p[0]:.2f}-{p[1]:.2f}, offset {p[2]:.2f}-{p[3]:.2f}, contrast {p[4]:.3f}-{p[5]:.3f}, finite {r['finite']}: "
              f"{'held' if ok else 'failed'}")
for s in seeds:
    a, b, c, d, _ = R[(0, s)]["c4"]; e = R[(0, s)]["c4e"]
    print(f"C4 seed {s}: a two-class rank differences {a} (bar 0) {'held' if a == 0 else 'failed'}; "
          f"b k-centre differing picks {b} (bar 0) {'held' if b == 0 else 'failed'}; "
          f"c typicality max rel. diff {c:.2e} (bar 1e-9) {'held' if c < 1e-9 else 'failed'}; "
          f"d vote entropy max abs. error {d:.2e} (bar 1e-12) {'held' if d < 1e-12 else 'failed'}; "
          f"e typ-init clusters hit {e} (bar 10) {'held' if e == 10 else 'failed'}")

def curve(pool, s, n, key=None):
    return np.array([R[(pool, sd)][key or s][n] for sd in seeds])

for pool in (0, 1):
    print(f"\nTest accuracy, {POOLS[pool]} pool: mean [min-max] over seeds")
    print("labels  " + "  ".join(f"{s:>21s}" for s in STRATS))
    for n in GRID:
        cells = []
        for s in STRATS:
            v = curve(pool, s, n); cells.append(f"{v.mean():.4f} [{v.min():.3f}-{v.max():.3f}]")
        print(f"{n:6d}  " + "  ".join(f"{c:>21s}" for c in cells))
    if pool == 0:
        print("committee's own accuracy (members' mean probabilities): " +
              " ".join(f"{n}:{curve(0, None, n, 'committee/own').mean():.4f}" for n in GRID))

def cell(name, d):
    ok = d.mean() >= -TAU
    print(f"{name}: per seed {' '.join(f'{x:+.4f}' for x in d)}; mean {d.mean():+.4f} "
          f"[{d.min():+.4f}..{d.max():+.4f}] -> {'held' if ok else 'failed'}")

print("\nHypotheses (balanced pool; held if mean >= -tolerance)")
for n in (20, 30, 40):
    cell(f"H1 n={n:3d} typiclust - random  ", curve(0, "typiclust", n) - curve(0, "random", n))
for n in (10, 20, 30, 40):
    cell(f"H1 n={n:3d} typ-init - random   ", curve(0, "typ-init", n) - curve(0, "random", n))
for u in ("least-conf", "margin", "entropy"):
    for n in (20, 30, 40):
        cell(f"H1 n={n:3d} random - {u:10s}", curve(0, "random", n) - curve(0, u, n))
cell("H2 n=600 margin - random     ", curve(0, "margin", 600) - curve(0, "random", 600))
G1 = [n for n in GRID if n > 10]
area = lambda key: np.array([np.mean([R[(0, sd)][key][n] for n in G1]) for sd in seeds])
cell("H3a curve mean committee - least-conf (single model)  ", area("committee") - area("least-conf"))
cell("H3b curve mean committee (own) - least-conf           ", area("committee/own") - area("least-conf"))
n95 = {}
for s in ("margin", "random"):
    n95[s] = []
    for sd in seeds:
        tgt = 0.95 * R[(0, sd)]["full"]
        hit = [n for n in GRID if R[(0, sd)][s][n] >= tgt]
        n95[s].append(hit[0] if hit else None)
    print(f"H4 {s:6s}: labels to 95% of full-pool accuracy per seed {n95[s]}")
mg, rd = n95["margin"], n95["random"]
if all(v is not None for v in mg) and all(v is not None for v in rd):
    h4 = np.mean(mg) < np.mean(rd); why = f"mean margin {np.mean(mg):.1f} vs random {np.mean(rd):.1f}"
elif all(v is not None for v in mg):
    h4 = True; why = "margin reached on every seed, random not"
else:
    h4 = False; why = "margin did not reach the target on every seed"
print(f"H4: {why} -> {'held' if h4 else 'failed'}")

print("\nClass balance, imbalanced pool (decides nothing): TV distance to the pool's class distribution | "
      "share of the 3 rarest classes")
print(f"pool share of the 3 rarest classes: {class_counts(5000, True)[-3:].sum() / 5000:.3f}")
for s in STRATS:
    out = []
    for n in (50, 100, 300, 600):
        tv, rare = [], []
        for sd in seeds:
            r = R[(1, sd)]; lab = r[s + "/lab"][:n]
            q = np.bincount(r["y"][lab], minlength=K) / n; p = np.bincount(r["y"], minlength=K) / 5000
            tv.append(0.5 * np.abs(q - p).sum()); rare.append(q[-3:].sum())
        tv, rare = np.array(tv), np.array(rare)
        out.append(f"n={n}: {tv.mean():.3f} [{tv.min():.3f}-{tv.max():.3f}] | {rare.mean():.3f}")
    print(f"{s:10s} " + "   ".join(out))
seeds [0, 1, 2, 3, 4]; pools of 5000, tests of 5000; B=10, up to 600 labels; tolerance 0.005

Checks
C1 balanced   full-pool test accuracy per seed 0.3450 0.3466 0.3496 0.3554 0.3324 (bar 0.25-0.95): held
C1 imbalanced full-pool test accuracy per seed 0.4800 0.4880 0.4834 0.4842 0.4826 (bar 0.37-0.95): held
C2 fits 5510, reaching max_iter 0 (bar 0): held
C3 balanced   seed 0: counts [625, 625, 625, 625, 625, 625, 625, 625] as designed True, r 5.00-9.00, offset -3.00-3.00, contrast 0.150-0.600, finite True: held
C3 balanced   seed 1: counts [625, 625, 625, 625, 625, 625, 625, 625] as designed True, r 5.00-9.00, offset -3.00-3.00, contrast 0.150-0.600, finite True: held
C3 balanced   seed 2: counts [625, 625, 625, 625, 625, 625, 625, 625] as designed True, r 5.00-9.00, offset -3.00-3.00, contrast 0.150-0.600, finite True: held
C3 balanced   seed 3: counts [625, 625, 625, 625, 625, 625, 625, 625] as designed True, r 5.00-9.00, offset -3.00-3.00, contrast 0.150-0.600, finite True: held
C3 balanced   seed 4: counts [625, 625, 625, 625, 625, 625, 625, 625] as designed True, r 5.00-9.00, offset -3.00-3.00, contrast 0.150-0.600, finite True: held
C3 imbalanced seed 0: counts [1592, 1114, 780, 546, 382, 268, 187, 131] as designed True, r 5.00-9.00, offset -3.00-3.00, contrast 0.150-0.600, finite True: held
C3 imbalanced seed 1: counts [1592, 1114, 780, 546, 382, 268, 187, 131] as designed True, r 5.00-9.00, offset -3.00-3.00, contrast 0.150-0.600, finite True: held
C3 imbalanced seed 2: counts [1592, 1114, 780, 546, 382, 268, 187, 131] as designed True, r 5.00-9.00, offset -3.00-3.00, contrast 0.150-0.600, finite True: held
C3 imbalanced seed 3: counts [1592, 1114, 780, 546, 382, 268, 187, 131] as designed True, r 5.00-9.00, offset -3.00-3.00, contrast 0.150-0.600, finite True: held
C3 imbalanced seed 4: counts [1592, 1114, 780, 546, 382, 268, 187, 131] as designed True, r 5.00-9.00, offset -3.00-3.00, contrast 0.150-0.600, finite True: held
C4 seed 0: a two-class rank differences 0 (bar 0) held; b k-centre differing picks 0 (bar 0) held; c typicality max rel. diff 5.40e-16 (bar 1e-9) held; d vote entropy max abs. error 2.22e-16 (bar 1e-12) held; e typ-init clusters hit 10 (bar 10) held
C4 seed 1: a two-class rank differences 0 (bar 0) held; b k-centre differing picks 0 (bar 0) held; c typicality max rel. diff 4.52e-16 (bar 1e-9) held; d vote entropy max abs. error 2.22e-16 (bar 1e-12) held; e typ-init clusters hit 10 (bar 10) held
C4 seed 2: a two-class rank differences 0 (bar 0) held; b k-centre differing picks 0 (bar 0) held; c typicality max rel. diff 4.67e-16 (bar 1e-9) held; d vote entropy max abs. error 2.22e-16 (bar 1e-12) held; e typ-init clusters hit 10 (bar 10) held
C4 seed 3: a two-class rank differences 0 (bar 0) held; b k-centre differing picks 0 (bar 0) held; c typicality max rel. diff 4.64e-16 (bar 1e-9) held; d vote entropy max abs. error 2.22e-16 (bar 1e-12) held; e typ-init clusters hit 10 (bar 10) held
C4 seed 4: a two-class rank differences 0 (bar 0) held; b k-centre differing picks 0 (bar 0) held; c typicality max rel. diff 4.25e-16 (bar 1e-9) held; d vote entropy max abs. error 2.22e-16 (bar 1e-12) held; e typ-init clusters hit 10 (bar 10) held

Test accuracy, balanced pool: mean [min-max] over seeds
labels                 random             least-conf                 margin                entropy              committee               k-centre              typiclust               typ-init
    10   0.1461 [0.116-0.176]   0.1461 [0.116-0.176]   0.1461 [0.116-0.176]   0.1461 [0.116-0.176]   0.1461 [0.116-0.176]   0.1461 [0.116-0.176]   0.1461 [0.116-0.176]   0.1499 [0.123-0.165]
    20   0.1621 [0.159-0.169]   0.1598 [0.129-0.189]   0.1518 [0.121-0.168]   0.1590 [0.133-0.197]   0.1637 [0.135-0.198]   0.1490 [0.137-0.162]   0.1673 [0.138-0.199]   0.1605 [0.133-0.198]
    30   0.1739 [0.164-0.186]   0.1680 [0.137-0.193]   0.1618 [0.147-0.179]   0.1685 [0.136-0.191]   0.1645 [0.147-0.183]   0.1531 [0.142-0.168]   0.1662 [0.142-0.191]   0.1691 [0.146-0.187]
    40   0.1740 [0.165-0.190]   0.1792 [0.149-0.203]   0.1664 [0.147-0.178]   0.1711 [0.146-0.195]   0.1712 [0.163-0.185]   0.1617 [0.149-0.172]   0.1720 [0.163-0.188]   0.1732 [0.155-0.197]
    50   0.1874 [0.176-0.203]   0.1892 [0.172-0.212]   0.1648 [0.142-0.178]   0.1800 [0.151-0.198]   0.1783 [0.163-0.188]   0.1650 [0.153-0.180]   0.1806 [0.161-0.197]   0.1821 [0.165-0.196]
    60   0.1931 [0.176-0.210]   0.1913 [0.170-0.209]   0.1696 [0.153-0.179]   0.1841 [0.154-0.202]   0.1812 [0.161-0.195]   0.1710 [0.161-0.183]   0.1848 [0.159-0.203]   0.1816 [0.168-0.205]
    80   0.1954 [0.183-0.211]   0.1985 [0.183-0.218]   0.1843 [0.152-0.196]   0.1863 [0.157-0.201]   0.1841 [0.161-0.196]   0.1798 [0.159-0.201]   0.1955 [0.178-0.211]   0.1974 [0.176-0.212]
   100   0.1989 [0.188-0.209]   0.2016 [0.193-0.215]   0.1981 [0.170-0.211]   0.1881 [0.163-0.205]   0.1906 [0.167-0.205]   0.1856 [0.163-0.214]   0.2012 [0.176-0.214]   0.2001 [0.176-0.215]
   150   0.2119 [0.198-0.222]   0.2101 [0.202-0.216]   0.2076 [0.185-0.222]   0.2036 [0.188-0.214]   0.2052 [0.188-0.219]   0.2034 [0.180-0.233]   0.2094 [0.198-0.216]   0.2100 [0.197-0.221]
   200   0.2235 [0.209-0.233]   0.2177 [0.210-0.231]   0.2157 [0.207-0.225]   0.2068 [0.192-0.214]   0.2178 [0.208-0.226]   0.2142 [0.199-0.238]   0.2135 [0.201-0.223]   0.2171 [0.205-0.225]
   300   0.2341 [0.225-0.245]   0.2203 [0.213-0.233]   0.2259 [0.207-0.235]   0.2121 [0.198-0.223]   0.2328 [0.221-0.247]   0.2339 [0.224-0.241]   0.2264 [0.212-0.238]   0.2277 [0.218-0.239]
   400   0.2380 [0.230-0.250]   0.2349 [0.226-0.240]   0.2384 [0.219-0.245]   0.2251 [0.217-0.233]   0.2434 [0.233-0.259]   0.2476 [0.237-0.254]   0.2343 [0.229-0.242]   0.2328 [0.222-0.240]
   500   0.2442 [0.235-0.257]   0.2453 [0.238-0.251]   0.2466 [0.232-0.255]   0.2359 [0.233-0.241]   0.2499 [0.244-0.260]   0.2554 [0.247-0.264]   0.2376 [0.230-0.245]   0.2385 [0.235-0.241]
   600   0.2534 [0.245-0.265]   0.2530 [0.245-0.262]   0.2563 [0.241-0.264]   0.2406 [0.238-0.243]   0.2528 [0.242-0.262]   0.2636 [0.256-0.272]   0.2434 [0.236-0.253]   0.2421 [0.232-0.248]
committee's own accuracy (members' mean probabilities): 10:0.1503 20:0.1608 30:0.1600 40:0.1715 50:0.1734 60:0.1815 80:0.1800 100:0.1896 150:0.2129 200:0.2198 300:0.2344 400:0.2389 500:0.2508 600:0.2544

Test accuracy, imbalanced pool: mean [min-max] over seeds
labels                 random             least-conf                 margin                entropy              committee               k-centre              typiclust               typ-init
    10   0.3217 [0.255-0.374]   0.3217 [0.255-0.374]   0.3217 [0.255-0.374]   0.3217 [0.255-0.374]   0.3217 [0.255-0.374]   0.3217 [0.255-0.374]   0.3217 [0.255-0.374]   0.3084 [0.283-0.335]
    20   0.3361 [0.300-0.375]   0.3385 [0.263-0.385]   0.3432 [0.316-0.369]   0.3440 [0.304-0.372]   0.3230 [0.226-0.361]   0.2925 [0.242-0.337]   0.3312 [0.285-0.365]   0.3391 [0.315-0.374]
    30   0.3426 [0.303-0.374]   0.3251 [0.256-0.381]   0.3569 [0.321-0.371]   0.3341 [0.289-0.367]   0.3244 [0.225-0.373]   0.2874 [0.233-0.334]   0.3453 [0.325-0.374]   0.3621 [0.334-0.382]
    40   0.3482 [0.325-0.372]   0.3299 [0.288-0.365]   0.3632 [0.348-0.385]   0.3422 [0.276-0.372]   0.3283 [0.252-0.372]   0.2642 [0.226-0.294]   0.3534 [0.328-0.364]   0.3610 [0.341-0.385]
    50   0.3582 [0.340-0.373]   0.3352 [0.293-0.360]   0.3691 [0.335-0.397]   0.3339 [0.259-0.374]   0.3272 [0.258-0.368]   0.2762 [0.213-0.326]   0.3632 [0.356-0.374]   0.3568 [0.350-0.366]
    60   0.3555 [0.346-0.370]   0.3242 [0.277-0.362]   0.3667 [0.352-0.389]   0.3367 [0.277-0.375]   0.3206 [0.267-0.350]   0.2740 [0.234-0.340]   0.3656 [0.350-0.382]   0.3650 [0.354-0.380]
    80   0.3527 [0.336-0.371]   0.3247 [0.273-0.359]   0.3694 [0.361-0.393]   0.3334 [0.270-0.381]   0.3355 [0.290-0.364]   0.3200 [0.262-0.364]   0.3770 [0.372-0.384]   0.3711 [0.357-0.376]
   100   0.3525 [0.331-0.372]   0.3258 [0.279-0.368]   0.3706 [0.362-0.394]   0.3383 [0.281-0.384]   0.3466 [0.310-0.367]   0.3484 [0.313-0.384]   0.3752 [0.366-0.391]   0.3738 [0.358-0.387]
   150   0.3645 [0.341-0.386]   0.3264 [0.294-0.372]   0.3675 [0.341-0.386]   0.3434 [0.305-0.378]   0.3627 [0.331-0.379]   0.3740 [0.359-0.385]   0.3820 [0.371-0.398]   0.3844 [0.375-0.394]
   200   0.3700 [0.354-0.394]   0.3397 [0.299-0.377]   0.3739 [0.356-0.388]   0.3431 [0.310-0.378]   0.3640 [0.334-0.390]   0.3696 [0.351-0.396]   0.3873 [0.377-0.398]   0.3864 [0.378-0.400]
   300   0.3689 [0.360-0.386]   0.3588 [0.324-0.399]   0.3826 [0.372-0.400]   0.3512 [0.307-0.382]   0.3724 [0.350-0.404]   0.3610 [0.346-0.379]   0.3838 [0.368-0.393]   0.3881 [0.374-0.396]
   400   0.3718 [0.363-0.394]   0.3734 [0.348-0.419]   0.3920 [0.383-0.404]   0.3622 [0.326-0.388]   0.3815 [0.361-0.410]   0.3625 [0.348-0.373]   0.3913 [0.373-0.401]   0.3918 [0.374-0.401]
   500   0.3735 [0.358-0.392]   0.3889 [0.369-0.418]   0.3990 [0.387-0.422]   0.3708 [0.330-0.399]   0.3860 [0.364-0.407]   0.3612 [0.341-0.383]   0.3929 [0.382-0.406]   0.3960 [0.389-0.410]
   600   0.3749 [0.354-0.402]   0.3953 [0.375-0.423]   0.4022 [0.394-0.412]   0.3868 [0.351-0.413]   0.3826 [0.354-0.406]   0.3727 [0.358-0.394]   0.3903 [0.377-0.400]   0.3941 [0.381-0.403]

Hypotheses (balanced pool; held if mean >= -tolerance)
H1 n= 20 typiclust - random  : per seed +0.0076 +0.0404 +0.0062 -0.0068 -0.0212; mean +0.0052 [-0.0212..+0.0404] -> held
H1 n= 30 typiclust - random  : per seed -0.0144 +0.0190 -0.0024 -0.0196 -0.0214; mean -0.0078 [-0.0214..+0.0190] -> failed
H1 n= 40 typiclust - random  : per seed -0.0184 +0.0142 -0.0026 +0.0030 -0.0062; mean -0.0020 [-0.0184..+0.0142] -> held
H1 n= 10 typ-init - random   : per seed -0.0340 +0.0322 +0.0092 -0.0162 +0.0280; mean +0.0038 [-0.0340..+0.0322] -> held
H1 n= 20 typ-init - random   : per seed -0.0322 +0.0394 +0.0148 -0.0176 -0.0124; mean -0.0016 [-0.0322..+0.0394] -> held
H1 n= 30 typ-init - random   : per seed -0.0124 +0.0092 +0.0222 -0.0254 -0.0178; mean -0.0048 [-0.0254..+0.0222] -> held
H1 n= 40 typ-init - random   : per seed -0.0284 +0.0052 +0.0254 +0.0072 -0.0138; mean -0.0009 [-0.0284..+0.0254] -> held
H1 n= 20 random - least-conf: per seed -0.0240 +0.0176 +0.0008 -0.0130 +0.0300; mean +0.0023 [-0.0240..+0.0300] -> held
H1 n= 30 random - least-conf: per seed -0.0104 +0.0268 -0.0190 +0.0054 +0.0268; mean +0.0059 [-0.0190..+0.0268] -> held
H1 n= 40 random - least-conf: per seed -0.0122 +0.0196 -0.0202 -0.0324 +0.0196; mean -0.0051 [-0.0324..+0.0196] -> failed
H1 n= 20 random - margin    : per seed -0.0032 +0.0126 -0.0032 +0.0066 +0.0388; mean +0.0103 [-0.0032..+0.0388] -> held
H1 n= 30 random - margin    : per seed +0.0112 +0.0246 +0.0026 +0.0070 +0.0152; mean +0.0121 [+0.0026..+0.0246] -> held
H1 n= 40 random - margin    : per seed +0.0120 +0.0036 +0.0084 -0.0078 +0.0218; mean +0.0076 [-0.0078..+0.0218] -> held
H1 n= 20 random - entropy   : per seed -0.0126 +0.0260 +0.0066 -0.0286 +0.0242; mean +0.0031 [-0.0286..+0.0260] -> held
H1 n= 30 random - entropy   : per seed -0.0034 +0.0358 -0.0122 -0.0052 +0.0120; mean +0.0054 [-0.0122..+0.0358] -> held
H1 n= 40 random - entropy   : per seed -0.0044 +0.0276 +0.0102 -0.0216 +0.0030; mean +0.0030 [-0.0216..+0.0276] -> held
H2 n=600 margin - random     : per seed -0.0032 -0.0010 +0.0012 +0.0098 +0.0080; mean +0.0030 [-0.0032..+0.0098] -> held
H3a curve mean committee - least-conf (single model)  : per seed -0.0066 -0.0090 -0.0003 -0.0112 +0.0142; mean -0.0026 [-0.0112..+0.0142] -> held
H3b curve mean committee (own) - least-conf           : per seed -0.0091 -0.0077 +0.0038 -0.0127 +0.0100; mean -0.0031 [-0.0127..+0.0100] -> held
H4 margin: labels to 95% of full-pool accuracy per seed [None, None, None, None, None]
H4 random: labels to 95% of full-pool accuracy per seed [None, None, None, None, None]
H4: margin did not reach the target on every seed -> failed

Class balance, imbalanced pool (decides nothing): TV distance to the pool's class distribution | share of the 3 rarest classes
pool share of the 3 rarest classes: 0.117
random     n=50: 0.138 [0.072-0.242] | 0.144   n=100: 0.106 [0.058-0.129] | 0.132   n=300: 0.045 [0.025-0.064] | 0.134   n=600: 0.035 [0.012-0.052] | 0.128
least-conf n=50: 0.202 [0.164-0.244] | 0.168   n=100: 0.198 [0.164-0.221] | 0.206   n=300: 0.154 [0.124-0.191] | 0.203   n=600: 0.145 [0.123-0.159] | 0.196
margin     n=50: 0.139 [0.107-0.175] | 0.164   n=100: 0.121 [0.081-0.194] | 0.182   n=300: 0.096 [0.081-0.108] | 0.165   n=600: 0.091 [0.079-0.107] | 0.166
entropy    n=50: 0.187 [0.104-0.235] | 0.192   n=100: 0.202 [0.174-0.231] | 0.232   n=300: 0.194 [0.164-0.221] | 0.238   n=600: 0.180 [0.163-0.205] | 0.213
committee  n=50: 0.207 [0.161-0.317] | 0.176   n=100: 0.175 [0.128-0.234] | 0.202   n=300: 0.167 [0.131-0.181] | 0.211   n=600: 0.164 [0.138-0.196] | 0.208
k-centre   n=50: 0.468 [0.402-0.534] | 0.092   n=100: 0.418 [0.378-0.444] | 0.136   n=300: 0.314 [0.302-0.345] | 0.155   n=600: 0.243 [0.228-0.258] | 0.153
typiclust  n=50: 0.153 [0.123-0.176] | 0.068   n=100: 0.170 [0.129-0.241] | 0.062   n=300: 0.145 [0.131-0.156] | 0.073   n=600: 0.123 [0.100-0.137] | 0.085
typ-init   n=50: 0.138 [0.076-0.203] | 0.084   n=100: 0.178 [0.129-0.271] | 0.064   n=300: 0.146 [0.131-0.157] | 0.073   n=600: 0.125 [0.101-0.139] | 0.084

Checks. Every check held. C1 held on every seed: each printed full-pool test accuracy lies inside its pool’s bar. C2 held, with none of the 5,510 fits at the iteration limit. C3 held for both pools on every seed. C4 held on every seed: no rank differences (a), no differing k-centre picks (b), relative differences from NearestNeighbors of the order of 10−1610^{-16} in typicality (c) and absolute errors of the same order in vote entropy (d), and 10 distinct clusters for typ-init’s first picks (e).

H1. For typiclust against random, H1 held at 20 labels (mean difference +0.0052) and 40 labels (−0.0020) and failed at 30 labels (−0.0078). For typ-init against random it held at all four budgets: +0.0038 at 10, −0.0016 at 20, −0.0048 at 30 and −0.0009 at 40. For random against least-conf it held at 20 (+0.0023) and 30 (+0.0059) and failed at 40 (−0.0051). For random against margin it held at all three budgets (+0.0103, +0.0121, +0.0076), and for random against entropy likewise (+0.0031, +0.0054, +0.0030). Of H1’s 16 cells, 14 held and 2 failed.

H2 held: at 600 labels margin minus random was +0.0030 on average, with per-seed differences from −0.0032 to +0.0098.

H3 held in both forms: averaged over the curve, the committee minus least-conf was −0.0026 with the single model (H3a) and −0.0031 with the committee’s own accuracy (H3b), both within the tolerance.

H4 failed: neither margin nor random reached 95% of the full-pool accuracy within 600 labels on any of the five seeds.

On the imbalanced pool, which decides nothing, the three rarest classes make up 0.117 of the pool. At 600 labels each of the four uncertainty and committee strategies had chosen a larger share of them than random (0.128), k-centre too, and both typicality strategies a smaller share than the pool’s. The total-variation distance from the pool’s class distribution at 600 labels was smallest for random (0.035) and largest for k-centre (0.243).

Pilot against first run. The pilot ran on seed 0 only, so its “means” are seed 0’s values, which appear as the first per-seed value on each hypothesis line above. Its outcomes differ from the five-seed outcomes in these cells: typiclust against random at 40 labels failed in the pilot (−0.0184) and held over five seeds; typ-init against random failed in the pilot at all four budgets and held at all four over five seeds; random against least-conf failed in the pilot at 20 and 30 labels and held over five seeds (it failed in both at 40); random against entropy at 20 labels failed in the pilot and held over five seeds; and H3a and H3b failed in the pilot (−0.0066 and −0.0091) and held over five seeds. Every other cell, and every check, has the same outcome in both. No setting, print or line of the code changed between the pilot and the first run.

Departures from the batch plan’s example, each approved at the pilot: 8 classes (the plan allowed 4–10); rotation, blur and noise added to the planned nuisances; an imbalanced second pool on which nothing is decided; two TypiClust variants for the open initial-set choice; the cluster cap of 50 and n_init=3; a bootstrap committee with its own accuracy printed beside the single-model one; a grid of 14 label counts instead of every round; the hypothesis cells, budgets and tolerance as stated above, which the plan gave only in words; and C1’s bars set from the planning script.

Variants

  • Uncertainty from a deterministic model, an approximate posterior or an ensemble: the scores are the same; the probabilities come from one network, Monte Carlo dropout (Gal et al., 2017) or several networks (Beluch et al., 2018).
  • Diversity and hybrids. Hacohen et al. (2022, App. A.1) list many methods that add diversity to the queried batch and note that diversity is orthogonal to uncertainty and can be added to almost any strategy. They list Kirsch et al. (2019) and Ash et al. (2020) among these methods, and compare against BADGE (Ash et al.) and a baseline they call BALD, citing Kirsch et al. (§4.1); neither paper was read for this article.
  • Learned acquisition: a loss predictor (Yoo & Kweon, 2019) or a labelled-against-unlabelled discriminator (Sinha et al., 2019).
  • Low-budget strategies: TypiClust and other methods that use self-supervised or semi-supervised representations of the pool (Hacohen et al., 2022, App. A.2).
  • Detection, pose and segmentation. A loss-based score extends to any task with a loss: Yoo and Kweon (2019) evaluate on PASCAL VOC for object detection and MPII for human pose estimation. Sinha et al. (2019) apply VAAL to semantic segmentation on Cityscapes and BDD100K. When the cost of a label depends on the image (a crowded scene costs more boxes than an empty one), the budget is better counted in annotation time than in images; the image annotation article gives measured times for the label types.
  • Combined with semi-supervised learning: the unlabelled pool also trains the model, with pseudo-labels or consistency (semi-supervised learning); Hacohen et al. (2022, §4.2.3) evaluate TypiClust’s queries with FlexMatch.
  • Model-assisted labelling, in which the model’s predictions are corrected by the annotator rather than used only to choose images, and verification instead of drawing are covered by image annotation.

Best Practices

  • Always run random selection with the same budget, model and training schedule. Beluch et al. (2018, §4.2) show each method next to its own random-acquisition counterpart, and Hacohen et al. (2022, §4.2.1) found in the low-budget regime that all baseline active learning methods performed on par with random selection or worse.
  • Repeat over seeds and report the spread. Gal et al. (2017, §5.1) repeated each experiment three times, Beluch et al. (2018, §4.1) five times and Hacohen et al. (2022, Fig. 4) ten times on CIFAR. In the example, seed 0 alone and the five-seed means gave different outcomes in ten hypothesis cells.
  • Report results at several budgets, from very low to high, since the best strategy can change with the budget (Hacohen et al., 2022).
  • Match the strategy to the budget. At a few labels per class, Hacohen et al. recommend typical and diverse queries; uncertainty-based queries suit larger budgets.
  • Use a fixed, independently labelled test set. Images chosen by the loop are not a random sample of the pool, so accuracy measured on them is not an estimate of accuracy on the pool.
  • Check the class balance of what was queried. Hacohen et al. (2022, §4.3.2) measure the total-variation distance between the labelled set’s class distribution and the true one; Beluch et al. (2018, §4.5) report the share of the minority class among acquired images.
  • Use one evaluation framework shared across methods when comparing them. Hacohen et al. (2022, §4.1) adopt the framework of Munjal et al. (2020), which implements several methods under one protocol.

Pitfalls

  • Assuming active learning always beats random. At low budgets the reviewed sources report the opposite for most strategies (Hacohen et al., 2022, §1, §4.2.1).
  • Querying redundant batches. Taking the top BB by one score can select near-duplicates; Yoo and Kweon (2019, §4.1) cite this as the reason for scoring a random subset of the pool each cycle, and diversity methods address it directly.
  • Comparing strategies trained or evaluated differently. Beluch et al. (2018, Fig. 2b) separated acquisition quality from the accuracy of the evaluated model by training a Monte Carlo dropout network on the images an ensemble chose, and the reverse.
  • Reading an uncertainty-based gain as proof of good uncertainty. Beluch et al. (2018, §4.3) found that using epistemic uncertainty alone in their acquisition functions did not improve results, and Hacohen et al. (2022, §4.3.4) found that even an oracle’s margin performed poorly at low budget.
  • Ignoring how the queried set differs from the pool. The labelled set is biased by construction; class shares, conditions and difficulty can differ from the deployment distribution. In the example’s imbalanced pool, the share of the three rarest classes in the labelled set at 600 labels was above the pool’s 0.117 for six strategies and below it for the two typicality strategies.
  • Tuning on a large validation set the loop could not have had. Gal et al. (2017, §5.1) optimized weight decay on a validation set of 100 labelled images, which they call realistic for active learning, against the 5,000 used in comparable semi-supervised work.

Evidence and Impact

  • MNIST and skin lesions. Gal et al. (2017) reached 5% MNIST test error with 295 images acquired by Variation Ratios against 835 with random acquisition, and 1.64% error with 1,000 labelled images (§1, Tables 1 and 2). In their comparison, Random and Mean STD under-performed BALD, Variation Ratios and Max Entropy (§5.1, Fig. 1). They also apply the approach to melanoma diagnosis on ISIC 2016 by fine-tuning VGG16.
  • Ensembles. On CIFAR-10 after acquiring 14,500 images, Beluch et al. (2018, §1) report 91.5% accuracy for the ensemble-based approach against 88.4% for Monte Carlo dropout and 88.2% for the core-set method. Their abstract, in a sentence on MNIST and CIFAR-10, gives a test accuracy of 90% with roughly 12,200 labelled images. On diabetic retinopathy with 21,000 acquired images, ensemble Variation Ratio reached an AUC of 0.983 against 0.965 for random acquisition (§4.5). On ImageNet with a ResNet-50 and acquisitions of 40,000 images, there was initially no difference from random, and a small improvement appeared after the third acquisition (160,000 images; §4.4, Table 4).
  • Low budgets. Hacohen et al. (2022) evaluate with 1 to 10 labelled examples per class per round on average (§4.2). In the low-budget regime TypiClust outperformed the baselines they compared in the fully supervised, self-supervised-embedding and semi-supervised frameworks (§4.2, Figs. 4–6), on CIFAR-10, CIFAR-100, TinyImageNet and ImageNet subsets (FlexMatch was not run on ImageNet); Fig. 9 summarizes its gains over random selection. With FlexMatch on CIFAR-10, 10 labelled examples chosen by TypiClust gave 93.2% accuracy, which the abstract describes as an improvement of 39.4% over random selection. On a class-imbalanced CIFAR-10 subset, TypiClust outperformed the other methods at low budget and under-performed at high budget (§4.3.5).
  • Learned acquisition. Yoo and Kweon (2019) report that their method consistently outperformed the previous methods they compared on classification, detection and pose estimation (abstract), and Sinha et al. (2019) report state-of-the-art results at the time on CIFAR-10/100, Caltech-256, ImageNet, Cityscapes and BDD100K (abstract).

Related

  • Semi-Supervised Learning

    Training a classifier on a few labelled images together with many unlabelled ones, through pseudo-labels, consistency between perturbed views, teacher–student training or label propagation on a similarity graph, and the assumptions and failure modes that decide whether the unlabelled images help.

  • Image Annotation

    How people attach labels to images for training and evaluating vision models, from image tags and bounding boxes to masks, keypoints, tracks and 3D cuboids, and how guidelines, agreement checks, quality control, model assistance and fair pay decide whether those labels can be trusted.

  • Class Imbalance

    When some classes have far more training images than others, as in long-tailed recognition, classifiers favour the frequent classes; how imbalance is measured, why it hurts, and the remedies of resampling, reweighting, rebalanced losses, decoupled training and post-hoc logit adjustment for a prior shift.

  • k-Means Clustering

    The clustering method that splits data into k groups by alternately assigning each point to the nearest of k centres and moving each centre to the mean of its points; its sum-of-squares objective, Lloyd's algorithm and why it stops at a local minimum, k-means++ seeding and restarts, how to choose k, its spherical-cluster assumptions, and its uses in colour quantization, segmentation, superpixels and visual vocabularies.

  • Logistic Regression

    The linear classifier that models the probability of a class as a sigmoid (or, for several classes, a softmax) of a weighted sum of image features, fitted by maximum likelihood; its log-odds reading, Newton's method as iteratively reweighted least squares, what happens on separable data, regularization, multiclass schemes, calibration and class imbalance.

  • LSUN

    The Large-scale Scene Understanding dataset from Princeton, about ten million web images in 10 scene categories and 59 million in 20 object categories labelled by a cascade of deep classifiers with crowd workers in the loop; its label precision, the LSUN challenges at CVPR 2015–2017, and its second life as a generative-modelling benchmark (bedrooms, churches, cats, cars), where FID protocols differ from paper to paper.

References

  1. Gal, Y., Islam, R. & Ghahramani, Z. (2017). Deep Bayesian Active Learning with Image Data. Proceedings of the 34th International Conference on Machine Learning (ICML), PMLR 70, 1183–1192.
  2. Beluch, W. H., Genewein, T., Nürnberger, A. & Köhler, J. M. (2018). The Power of Ensembles for Active Learning in Image Classification. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR).
  3. Hacohen, G., Dekel, A. & Weinshall, D. (2022). Active Learning on a Budget: Opposite Strategies Suit High and Low Budgets. Proceedings of the 39th International Conference on Machine Learning (ICML), PMLR 162, 8175–8195.
  4. Yoo, D. & Kweon, I. S. (2019). Learning Loss for Active Learning. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR).
  5. Sinha, S., Ebrahimi, S. & Darrell, T. (2019). Variational Adversarial Active Learning. IEEE/CVF International Conference on Computer Vision (ICCV).
  6. Sener, O. & Savarese, S. (2018). Active Learning for Convolutional Neural Networks: A Core-Set Approach. International Conference on Learning Representations (ICLR) (not read).
  7. Houlsby, N., Huszár, F., Ghahramani, Z. & Lengyel, M. (2011). Bayesian Active Learning for Classification and Preference Learning. arXiv:1112.5745 (not read).
  8. Munjal, P., Hayat, N., Hayat, M., Sourati, J. & Khan, S. (2020). Towards Robust and Reproducible Active Learning Using Neural Networks. arXiv:2002.09564 (not read).
  9. Kirsch, A., van Amersfoort, J. & Gal, Y. (2019). BatchBALD: Efficient and Diverse Batch Acquisition for Deep Bayesian Active Learning. Advances in Neural Information Processing Systems 32 (NeurIPS) (not read).
  10. Ash, J. T., Zhang, C., Krishnamurthy, A., Langford, J. & Agarwal, A. (2020). Deep Batch Active Learning by Diverse, Uncertain Gradient Lower Bounds. International Conference on Learning Representations (ICLR) (not read).