PaperlayerView exact revision on arXiv

Source-linked AI summary

Active Learning on a Budget: Opposite Strategies Suit High and Low Budgets

Guy Hacohen, Avihu Dekel, Daphna Weinshall

arXiv:2202.02794v4cs.LG

TL;DR

The paper studies how the best active-learning query strategy changes with labeling budget, addressing poor performance in the low-budget cold-start regime. It combines theoretical analysis and empirical evaluation to motivate TypiClust, which selects diverse typical examples for low-budget learning. Across supervised and semi-supervised settings, the paper reports that typical examples help at low budgets whereas atypical or confusing examples become preferable at high budgets, with strong low-budget gains from TypiClust.

  • Problem

    Existing deep active-learning strategies often require large labeled sets, while low-budget settings can favor random selection and create a cold-start problem.

  • Method

    The paper analyzes budget-dependent sampling in a mixture model and proposes TypiClust, which combines self-supervised representations, density estimation, and clustering to select diverse typical examples.

  • Results

    The paper finds that typical examples are most helpful at low budgets, whereas confusing examples are preferable at high budgets, across fully supervised and semi-supervised settings.

  • Takeaways & Limitations

    Active-learning query strategies should be matched to budget size, with TypiClust providing a low-budget strategy that substantially improves active and semi-supervised learning performance.

  • Takeaways & Limitations

    Determining which training sizes qualify as low-budget characteristics remains challenging and is left for future work.

Abstract

from arXiv · show

Investigating active learning, we focus on the relation between the number of labeled examples (budget size), and suitable querying strategies. Our theoretical analysis shows a behavior reminiscent of phase transition: typical examples are best queried when the budget is low, while unrepresentative examples are best queried when the budget is large. Combined evidence shows that a similar phenomenon occurs in common classification models. Accordingly, we propose TypiClust -- a deep active learning strategy suited for low budgets. In a comparative empirical investigation of supervised learning, using a variety of architectures and image datasets, TypiClust outperforms all other active learning strategies in the low-budget regime. Using TypiClust in the semi-supervised framework, performance gets an even more significant boost. In particular, state-of-the-art semi-supervised methods trained on CIFAR-10 with 10 labeled examples selected by TypiClust, reach 93.2% accuracy -- an improvement of 39.4% over random selection. Code is available at https://github.com/avihu111/TypiClust.

1. Introduction

Active learning strategies suit different labeling budgets: typical examples help in the low-budget regime, while atypical or uncertain examples become preferable at high budgets. The paper develops TypiClust for low-budget querying and reports broad empirical gains, including in semi-supervised learning.

  • Motivation: Deep active learning faces a cold-start problem because existing strategies require many labeled examples and can underperform random selection with small budgets.This matters when expert annotation is expensive.
  • Core insight: The paper argues that low- and high-budget regimes require opposite querying strategies: typical examples at low budgets and uncertain or atypical examples at high budgets.The theoretical analysis models this as a phase-transition-like phenomenon.
  • Theory and evidence: The analysis establishes sufficient conditions for this phase-transition-like behavior, proves that linear classifiers satisfy them, and finds empirical evidence that neural models may also satisfy them.This connects the theoretical prediction to commonly used classification models.
  • TypiClust: TypiClust selects diverse typical examples by learning representations, clustering the dataset, and sampling a high-density point from each cluster.The strategy is designed specifically for the low-budget regime.
  • Empirical results: Across datasets and architectures, TypiClust substantially improves low-budget generalization and reaches state-of-the-art results in many problems.Alternative active learning strategies are reported as ineffective or detrimental in this regime.
  • Semi-supervised learning: Using TypiClust in semi-supervised learning produces a large performance improvement, addressing a setting where prior active learning benefits were often marginal.The reported improvement is attributed to matching the low-budget setting with a strategy designed for it.

2. Theoretical Analysis

The theoretical analysis models active learning as sampling from regions with different learning difficulty and predicts a budget-dependent shift in the preferred oversampling strategy. This phase-transition-like behavior is supported for linear classifiers and investigated for deep neural networks.

  • Mixture model and sampling objective: Active learning selects B unlabeled examples from a pool U for oracle annotation, with budget m = B + L.The process may begin with an empty or small labeled set and repeats until the labeling budget or termination condition is reached.
  • Mixture model and sampling objective: The mixture model partitions the data domain into R1 and R2, each independently learned, with R1 defined as easier to learn than R2.The model evaluates expected generalization error as a function of training-set size across the two regions.
  • Phase transition: For budgets m ≤ m0, oversampling R1 is optimal, whereas for m > m0, oversampling R2 is optimal under the stated error-score conditions.A threshold test determines which region should receive additional samples, producing opposite preferred strategies in the low- and high-budget regimes.
  • Phase transition: In an exponential-error example with p = 0.8 and α = 0.1, favoring R1 helps at small m, while favoring R2 helps at large m.The simulated comparison uses a bias of Δ = ±0.01 relative to random sampling.
  • Conditions and classifier analyses: The phase-transition behavior is not guaranteed for every proper error score but follows from sufficient undulating or SP-undulating conditions, including exponential error scores.The paper states that commonly used learners may instead only admit exponential upper bounds, which can still imply undulating behavior.
  • Conditions and classifier analyses: The analysis connects low-budget oversampling to typicality and diversity, then uses these principles to guide deep active learning.For linear models, the paper bounds error as an exponential function of regional sample size; the framework is also empirically examined with deep neural networks.

3. Method: Low Budget Active Learning

TypiClust is a low-budget active learning strategy that selects representative examples while maintaining diversity. It combines self-supervised representations, clustering, and typicality-based querying to address noisy typicality estimates and redundant selections.

  • Framework and motivation: TypiClust incorporates max-density and diversity principles into a low-budget active learning strategy.It is designed to select typical examples while probing different regions of the data distribution.
  • Framework and motivation: Typicality is defined as the inverse average Euclidean distance to an example’s K nearest neighbors in a semantically meaningful feature space.The authors use K = 20, while reporting that other choices yield similar results.
  • Framework and motivation: TypiClust addresses noisy low-budget typicality estimates with self-supervised representation learning and addresses redundancy with clustering.Typical examples can be similar to one another, so diversity is needed to better represent the data distribution.
  • Three-step strategy: The method learns features from the unlabeled pool, partitions examples into clusters, and selects the most typical example from each selected uncovered cluster.The initial-pool algorithm takes U and budget B as input and returns B typical, diverse examples for annotation.
  • Three-step strategy: Clustering enforces diversity by selecting from uncovered clusters, while within-cluster typicality favors representative examples.The number of clusters is |L_{i−1}| + B, guaranteeing at least B clusters that do not intersect the existing labeled examples.
  • Variants and evidence: Both evaluated TypiClust variants outperform uncertainty-based strategies by a large margin in the low-budget regime.The variants differ in how self-supervised representation learning and clustering are implemented.

4. Empirical Study

The empirical study evaluates TypiClust across fully supervised, self-supervised embedding, and semi-supervised frameworks. In low-budget settings, TypiClust consistently outperforms baseline active-learning strategies, with clustering and typicality both contributing to its performance.

  • Evaluation frameworks: The study evaluates active learning in fully supervised, self-supervised embedding, and semi-supervised frameworks.The semi-supervised framework trains FlexMatch on labeled and unlabeled data.
  • Fully supervised framework: In low-budget fully supervised experiments, both TypiClust variants outperform baseline active-learning methods by a large margin.Other baselines perform at or below random selection, whereas typicality-based querying produces large accuracy gains.
  • Self-supervised embedding framework: TypiClust also outperforms all baselines when a linear classifier uses self-supervised embeddings.This framework outperforms fully supervised learning but remains behind the semi-supervised framework.
  • Semi-supervised framework: In semi-supervised experiments, TypiClust variants outperform random sampling by a large margin, while other active-learning baselines do not improve on random selection.FlexMatch is evaluated with 10 CIFAR-10, 300 CIFAR-100, or 1000 TinyImageNet examples.
  • Ablations: TypiClust retains its advantage after randomizing the initial pool, showing that its performance is not explained solely by non-random initialization.Non-random initial selection provides additional generalization gains when combined with active learning.
  • Ablations: Both clustering and high-density sampling are crucial: clustering alone and typicality without diversity each perform poorly.TypiClust selects typical examples from every cluster, combining diversity with typicality.
  • Oracle uncertainty: Even reliable oracle uncertainty produces poor low-budget performance, performing worse than baseline uncertainty methods.The experiment uses an oracle trained on all CIFAR-10 labels to estimate uncertainty through softmax margins.

5. Summary and Discussion

The paper concludes that active-learning strategies should reverse across budget regimes: typical examples help at low budgets, whereas confusing examples help at high budgets. This pattern is connected to curriculum-like learning and remains bounded by an uncertain, task-dependent transition point.

  • Main conclusion: The paper argues theoretically and empirically that low- and high-budget active learning require opposite querying principles.Typical examples are preferred initially, while confusing examples become preferable later.
  • Main conclusion: Semi-supervised algorithms receive a significant boost from labels of typical examples in the low-budget regime.The conclusion applies to both fully supervised and semi-supervised settings.
  • Relation to prior work: The findings relate to curriculum learning, hard-data mining, and self-paced learning, which favor easy examples early and hard examples later.The paper frames these connections as related work rather than as an equivalence.
  • Scope and limitation: The transition between low and high budgets depends on the task and its data distribution.Determining the training-size range that behaves as low budget remains an open challenge.
  • Relation to prior work: The proposed strategy queries diverse characteristic examples, unlike prior strategies that seek diverse uncharacteristic examples.This contrasts typicality-based selection with uncertainty-oriented diversity sampling.

B.1. Undulating Error Score: Sufficient Conditions

This appendix establishes sufficient conditions under which a mixture-model error score is undulating. Under these conditions, the optimal oversampling region changes at a budget threshold, producing phase-transition behavior.

  • Proof strategy: The proof develops lemmas for positive differentiable functions and applies them to characterize undulating error scores.The appendix uses limits, logarithmic transformations, monotonicity, and L’Hôpital’s rule.
  • Sufficient conditions: Theorem 2 states sufficient assumptions on a proper error score E(x) for it to be undulating.The assumptions include asymptotic conditions on E(x) and -log(E(x)).
  • Sufficient conditions: Under the theorem’s conditions, the error score is shown to be undulating.The proof concludes this directly from the preceding assumptions and lemmas.

B.2. SP-undulating Error Score: Sufficient Conditions

This appendix extends the undulating-error analysis to SP-undulating scores by adding monotonicity conditions. The resulting theorem and corollary describe when the preferred oversampling direction changes with region probability and budget.

  • Sufficient conditions: Theorem 3 gives sufficient conditions for an error score to be SP-undulating.It assumes an undulating proper error score plus one of two additional derivative conditions.
  • Proof strategy: The proof studies the auxiliary ratio H(x) and establishes its monotonic behavior from the derivative assumptions.The relevant function is defined as H(x) = E′(px) / E′(α(1-p)x).
  • Corollary: When region R1 has sufficiently small probability, the preferred oversampling directions are reversed.The corollary specifies the condition p < α/(1+α).
  • Linear-model connection: For a mixture of two linear models, the appendix states conditions yielding an undulating error score and phase-transition behavior.A separate bound shows that the error score of a single linear classifier decreases exponentially with training examples under mild conditions.

C.1.1. BOUNDING THE ERROR OF EACH MIXTURE COMPONENT

The paper bounds the expected error of each mixture component under boundedness, separability, covariance, and rank-related assumptions. The analysis uses covariance and mean estimation bounds to obtain an exponentially decreasing error bound.

  • When d > m, the sample covariance is rank deficient, so its inverse is undefined and the minimum-norm solution uses the Penrose pseudo-inverse.
  • The proof bounds covariance and mean estimation errors using matrix Bernstein, Hoeffding, union bounds, and assumptions on sample norms.
  • The component analysis assumes bounded samples, a margin-separable binary problem, and full-rank covariance with a positive smallest singular value.
  • Under the stated assumptions, the expected error of the learned component is bounded for every sample size and training sample.
  • The proof characterizes classification errors through deviations between the optimal and estimated predictors relative to the separation margin.

C.1.2. A MIXTURE CLASSIFIER

The mixture analysis combines two independently learned regions whose component errors decrease exponentially, yielding an undulating overall error score. For small budgets, selecting dense and diverse points is theoretically beneficial.

  • A MIXTURE CLASSIFIER: The mixture error score is a weighted combination of the expected errors of two independently learned components.
  • A MIXTURE CLASSIFIER: Theorem 5 shows that, under an additional limiting assumption, the mixture error score is undulating.
  • A MIXTURE CLASSIFIER: Each component error decreases monotonically, is bounded by an exponentially decreasing function, and converges to zero as its sample size grows.
  • A MIXTURE CLASSIFIER: For small training samples, oversampling a region with lower expected error than its complement can improve the outcome.
  • A MIXTURE CLASSIFIER: The 1-NN framework motivates selecting points from high-density regions while maintaining diversity through approximately independent local neighborhoods.
  • A MIXTURE CLASSIFIER: Figure 10 evaluates the mixture error score over 10k repetitions and compares oversampling from R1 or R2 with random sampling.

D.2. Error Scores of Deep Neural Networks

Deep-network error scores on image-classification tasks decrease rapidly with the number of examples and exhibit the same qualitative undulating behavior studied theoretically.

  • Across evaluated datasets, deep-network error decreases faster than an exponential function as the number of examples increases.
  • Because the error functions are bounded above by an exponential, they are also SP-undulating in practice.
  • Figure 12 visualizes 30 CIFAR-10 examples selected by TypiClust using clustering, labels, and log-density views.

F.1. Method Implementation Details

The implementation learns representations, clusters examples for diversity, filters small clusters, and iteratively selects the most typical point from underrepresented clusters.

  • Representation learning: For CIFAR-10, CIFAR-100, and TinyImageNet, representations come from SimCLR-trained ResNet18 models with 128-dimensional projection layers.
  • Representation learning: For ImageNet, representations are extracted from official ViT-S/16 DINO weights and use the L2-normalized penultimate layer.
  • Clustering for diversity: Clustering uses a maximum cluster count of 500 for CIFAR datasets and 1000 for TinyImageNet and ImageNet subsets.
  • Clustering for diversity: SCAN clustering uses only its first step, while K-Means switches to MiniBatchKMeans when the cluster count exceeds 50 to reduce runtime.
  • Typicality selection: Clusters with fewer than 5 samples are dropped, and typicality is estimated using min{20, cluster_size} nearest neighbors.
  • Typicality selection: At each iteration, TypiClust chooses the largest sufficiently sized cluster among those with fewest labeled points, then queries its most typical point.
  • Typicality selection: The limiting case of clusters with fewer than 5 samples is rarely encountered because clusters are usually balanced.

F.2.1. FULLY SUPERVISED EVALUATION

The fully supervised evaluation extends the active-learning comparison across datasets, budgets, and classifier settings. TypiClust outperforms competing methods across additional datasets and provides especially large gains when selecting initial labeled pools for linear evaluation.

  • Evaluation setup: The evaluation uses the Munjal et al. (2020) active-learning framework with ResNet18 training, SGD optimization, cosine scheduling, and standard image augmentations.The framework also reinitializes weights between iterations under extremely low budgets to address optimization issues caused by overconfident predictions.
  • Supervised results: An oracle-margin strategy works well in the high-budget regime for both the oracle and student networks.The oracle uncertainty measure is computed using margins from a VGG-19 network trained on CIFAR-10.
  • Evaluation setup: Additional supervised experiments cover CIFAR-10, CIFAR-100, TinyImageNet, ImageNet-50, ImageNet-100, and ImageNet-200 across multiple budget sizes.The reported extensions include additional examples per class, datasets, and budgets beyond the main-paper experiments.
  • Supervised results: TypiClust outperforms all competing methods on ImageNet-50, ImageNet-100, and TinyImageNet.These results extend the reported comparison to additional image datasets.
  • Supervised results: Random initial-pool sampling does not eliminate TypiClust’s improvement over random selection across several datasets and budget sizes.The additional evidence tests whether the method’s gain depends on a specially selected initial pool.
  • Supervised results: Linear evaluation over a self-supervised pre-trained embedding shows a very large performance boost from initial-pool selection, especially on ImageNet-50 and ImageNet-200.The linear classifier is trained over an embedding using a single layer of size d×C, with adjusted learning rate and training duration.

G.3. Semi-Supervised Framework

The semi-supervised experiments test TypiClust across alternative clustering and learning configurations. TypiClust consistently surpasses random selection in low-budget settings and improves performance beyond FlexMatch-specific results.

  • Experimental extensions: Additional semi-supervised experiments evaluate TypiClust with alternative budgets, clustering, and semi-supervised learning configurations.The experiments extend the settings shown in Fig. 6 and include TPCRUC and Semi-MMDC variants.
  • Experimental extensions: TPCRUC, a RUC-based variant designed to test dependence on SCAN, surpasses the comparison methods in all tested settings.The number of clusters is fixed to the number of dataset classes, with K-means subclustering when additional clusters are needed.
  • Experimental extensions: 40 examples on CIFAR-10 produce results similar to the corresponding 40-example experiment in Fig. 6a.This additional budget test uses the TPCRUC variant of TypiClust.
  • Semi-supervised results: TypiClust significantly increases performance for Semi-MMDC trained with 20 labels on CIFAR-10, paralleling the FlexMatch results.The experiment follows the Semi-MMDC code and training protocol provided by Lerner et al. (2020).
  • Semi-supervised results: Across all tested low-budget experiments, TypiClust surpasses the random baseline by a large margin.This conclusion covers the semi-supervised low-budget experiments reported in the section.
Loading 2202.02794v4…