Active Learning for Convolutional Neural Networks: A Core-Set Approach

What came before

Classical active-learning heuristics assume single-point (b=1) querying: uncertainty-based selection (max-entropy, BALD, Variation Ratios), Bayesian methods using MC-dropout as approximate inference (Gal et al.'s DBAL), and batch methods that combine uncertainty with a diversity term (BMDR, minimizing MMD between the pool and selected points; CEAL for weakly-supervised CNNs). The paper's own empirical study finds these ineffective for CNNs in the batch-query setting required in practice, because querying many points per round (rather than one) correlates the selected samples.

The problem

Training a CNN to convergence for every single-point query is intractable, so active learning for CNNs must select a batch of points per round; existing batch heuristics still rely on per-point uncertainty scores that become redundant/correlated once many points are chosen at once, and none of them come with a bound relating the selected subset's size and geometry to the resulting model's population risk.

The idea

Reformulate batch active learning as core-set selection: choose a subset $\mathbf{s}$ such that a model trained on $\mathbf{s}$ has population risk close to a model trained on the full pool. Bound the resulting "core-set loss" using only the geometric covering radius of $\mathbf{s}$ over the full dataset in a feature space (not label information), independent of how many labeled points are used; minimizing this bound is exactly the classical k-Center (minimax facility location) problem, solved with a greedy approximation and refined by an exact mixed-integer-program solver.

How it works

Decomposes population risk into generalization error, training error, and a "core-set loss" term $|\frac1n\sum_i l(x_i,y_i;A_\mathbf{s}) - \frac1{|\mathbf{s}|}\sum_{j\in\mathbf{s}} l(x_j,y_j;A_\mathbf{s})|$ (Eq. 3-4). Theorem 1 bounds this core-set loss by $\mathcal{O}(\delta_\mathbf{s}) + \mathcal{O}(1/\sqrt n)$ under a zero-training-error assumption, where $\delta_\mathbf{s}$ is the covering radius of $\mathbf{s}$ (every dataset point lies within $\delta_\mathbf{s}$ of some point in $\mathbf{s}$), given that the loss is Lipschitz in the input for fixed label/weights; Lemma 1 proves this Lipschitz property for a ReLU/max-pool CNN under an $\ell_2$ output loss. The practical objective becomes minimizing $\delta_\mathbf{s}$, i.e. the k-Center problem $\min_{\mathbf{s}^1}\max_i\min_{j\in\mathbf{s}^0\cup\mathbf{s}^1}\Delta(x_i,x_j)$ with $\Delta$ the $\ell_2$ distance between final-fully-connected-layer activations. Since k-Center is NP-hard, a greedy furthest-point algorithm (k-Center-Greedy, Algorithm 1: repeatedly add the point farthest from the current selected set) gives a 2-OPT solution used to initialize an exact refinement — a mixed-integer program (Algorithm 2/Eq. 6, solved with Gurobi via LP-relaxation and branch-and-bound, with binary search over the covering radius $\delta$) that also tolerates up to $\Xi$ outlier points not required to be covered. Selection is entirely unsupervised (uses only image features, never labels), applied iteratively over multiple query rounds, with a fresh VGG-16 trained from scratch (RMSProp) after each round, in both fully-supervised (train only on labeled points) and weakly-supervised (Ladder-network semi-supervised training using unlabeled points too) variants. In the loop: only the CNN being actively trained/queried each round (no separate teacher, generator, or bi-level optimization).

Evidence

CIFAR-10, CIFAR-100 and SVHN, fully- and weakly-supervised active learning (Figs. 3-4, accuracy vs. number of labeled points, averaged over 5 random initial pools): k-Center-Greedy (with the robust MIP refinement) outperforms Random selection, Best Empirical Uncertainty, DBAL (Bayesian MC-dropout), Best Oracle Uncertainty (which even sees the true labels to compute uncertainty), k-Medoids, and BMDR across the labeled-point budget curve, by a large margin in the weakly- supervised setting; the paper attributes weakly-supervised methods' extra edge to better learned feature geometry, which its purely geometric criterion exploits more directly. The method is comparatively less effective on CIFAR-100 than CIFAR-10/SVHN, which the paper attributes directly to its own bound scaling with the number of classes $C$. tSNE qualitative check (Fig. 5): the method's queries evenly cover the feature-space distribution, while the uncertainty-oracle baseline's queries cluster and fail to cover large regions of the space, visually confirming the covering-radius rationale. Exact vs. greedy solver (Fig. 6, Table 1, CIFAR-100, $b{=}5k$, $|\mathbf{s}^0|{=}10k$): the MIP-refined solution gives a "small but significant" accuracy improvement over the 2-OPT greedy solution alone, at a runtime of 360.23s total (104.2s distance matrix + 2s greedy 2-OPT + 244.03s MIP search) versus greedy alone, both tractable at 50k-image scale on a single workstation CPU.

Limitations

The paper's own theoretical bound scales with the number of classes $C$, and the method is empirically weaker on the 100-class CIFAR-100 than on 10-class CIFAR-10/SVHN — an explicit class-count limitation. Theorem 1's Lipschitz proof (Lemma 1) is derived for an $\ell_2$ output loss, not the cross-entropy loss actually used in the reported experiments; the paper states its "theoretical study does not extend to cross-entropy loss" though experiments suggest the resulting algorithm still works well with it. The zero-training-error assumption underlying Theorem 1 is acknowledged as "not entirely realistic." The exact MIP refinement is not polynomial-time in the worst case (only empirically tractable at the tested 50k-image scale); the method is never tested at ImageNet scale, and incorporating uncertainty information into the otherwise purely geometric criterion is explicitly left as "an open problem and a fruitful future research direction."