Active Learning Uncertainty Sampling Query Strategies and Annotation Efficiency
# Active Learning: Uncertainty Sampling, Query Strategies, and Annotation Efficiency
## 1. Introduction & Motivation
Active learning addresses the practical challenge of limited annotation budgets. In many real-world applications, acquiring labels is expensive (expert time, specialized equipment, privacy concerns), while unlabeled data is abundant. Rather than randomly sampling data to label, active learning intelligently selects which samples to annotate to maximize model performance per unit cost.
The core idea: Instead of passively receiving labeled data, actively query which samples provide most information. This can reduce annotation requirements by 50-90% compared to random sampling, translating to significant cost savings.
Applications include:
- Medical imaging (expert radiologist time expensive)
- Natural language processing (crowdsourced annotation noisy)
- Recommendation systems (implicit feedback abundant)
- Autonomous driving (labeling safety-critical scenarios)
This article comprehensively covers active learning strategies, theoretical foundations, practical implementation, and cost-benefit analysis.
## 2. Core Concepts & Theory
### 2.1 Active Learning Framework
Given:
- Large unlabeled dataset
$$ \mathcal{U} = \{x_1, \ldots, x_U\} $$
- Small labeled dataset
$$ \mathcal{L} = \{(x_i, y_i)\} $$
with
$$ |\mathcal{L}| \ll |\mathcal{U}| $$
- Budget B (number of labels we can acquire)
- Acquisition function a(x) scoring sample informativeness
Goal: Select B samples that maximize model performance:
$$\mathcal{S}^* = \arg\max_{|\mathcal{S}| = B} ext{Performance}(\mathcal{L} \cup \mathcal{S})$$
### 2.2 Uncertainty Sampling
Select samples where model is least confident:
$$a_{ ext{unc}}(x) = 1 - \max_c p(y = c | x)$$
For regression: Use predicted variance:
$$a_{ ext{unc}}(x) = \sigma^2(x)$$
Intuition: High uncertainty indicates potential for learning.
### 2.3 Query by Committee (QBC)
Maintain ensemble of models trained on current labeled set. Query samples where models disagree most:
$$a_{ ext{QBC}}(x) = ext{Var}_{C}[p_C(y | x)]$$
where variance is over committee members. Disagreement indicates uncertainty.
### 2.4 Information Gain
Select samples that maximize expected reduction in model entropy:
$$a_{ ext{IG}}(x) = H(y | x, \mathcal{L}) - \mathbb{E}_{y}[H(y | x, \mathcal{L} \cup \{(x, y)\})]$$
Expected information gain is expensive to compute exactly; approximations use mutual information.
## 3. Mathematical Formulation
### 3.1 Uncertainty Quantification
Margin Sampling:
$$a_{ ext{margin}}(x) = p_1(x) - p_2(x)$$
where
$$ p_1, p_2 $$
are top two class probabilities. Small margin indicates uncertainty.
Entropy:
$$a_{ ext{entropy}}(x) = -\sum_c p(y=c|x) \log p(y=c|x)$$
Variation Ratios:
$$a_{ ext{ratio}}(x) = 1 - \frac{\#\{ ext{models predicting } \arg\max_c p(y=c|x)\}}{N_{ ext{ensemble}}}$$
### 3.2 Bayesian Active Learning
Treat parameters
$$ heta $$
as random; uncertainty from both aleatoric (data) and epistemic (model) sources:
$$a_{ ext{BALD}}(x) = H(y|x) - \mathbb{E}_ heta[H(y|x, heta)]$$
First term: Data uncertainty. Second term: Model uncertainty (epistemic).
Maximizes mutual information between label and parameters.
### 3.3 Query by Committee with Disagreement Measure
Given committee
$$ C = \{f_1, \ldots, f_M\} $$
:
$$a_{ ext{QBC}}(x) = \mathbb{E}_c[\mathbb{E}_{f \in C}[(f(x) - \mu(x))^2]]$$
where
$$ \mu(x) = \frac{1}{M} \sum_{f \in C} f(x) $$
.
### 3.4 Diversity Sampling
Select samples maximizing diversity (reduce redundancy):
$$a_{ ext{div}}(x) = \min_{x' \in \mathcal{L}} ext{sim}(x, x')$$
Select samples far from labeled set. Combines with uncertainty:
$$a_{ ext{combined}}(x) = \alpha \cdot a_{ ext{unc}}(x) + (1-\alpha) \cdot a_{ ext{div}}(x)$$
## 4. Advanced Theory & Extensions
### 4.1 Core-Set Approach
Select minimal subset of samples that achieves similar performance:
$$\mathcal{S}^* = \arg\min_{|\mathcal{S}| = B} \max_x \min_{s \in \mathcal{S}} d(x, s)$$
Geometric interpretation: Samples cover input space well. Solved approximately using k-center or clustering.
### 4.2 Learning Loss for Active Learning
Train auxiliary network predicting model loss:
$$\mathcal{L}_{ ext{loss}}(x) = f_{ ext{loss}}(x)$$
Query samples with high predicted loss. More learnable than directly predicting informativeness.
### 4.3 Adversarial Examples in Active Learning
Query samples near decision boundaries where model might misclassify:
$$a_{ ext{adv}}(x) = \|x - ext{project}(x, ext{boundary})\|$$
Samples on boundary are most informative for refinement.
### 4.4 Cost-Sensitive Active Learning
Different samples have different labeling costs:
$$\max_{\mathcal{S}} \sum_{x \in \mathcal{S}} ext{Value}(x) \quad ext{s.t.} \quad \sum_{x \in \mathcal{S}} ext{Cost}(x) \leq B$$
Formulate as maximization problem with cost constraints.
## 5. Computational Considerations
### 5.1 Acquisition Function Computation
Uncertainty sampling: O(1) per sample (requires single forward pass)
Committee-based: O(M) per sample (M ensemble members)
Information gain:
$$ O(C^2) $$
per sample (enumerate possible labels, expensive for large label spaces)
Core-set:
$$ O(U^2) $$
(pairwise distances, infeasible for very large pools)
### 5.2 Model Retraining
Active learning loop requires frequent retraining:
$$ ext{Total time} = \sum_{i=1}^{B/b} ext{train time on } |\mathcal{L}| + i \cdot b ext{ samples}$$
where b is batch size of queries. Cost compounds with dataset growth.
Mitigation:
- Warm-start from previous model
- Transfer learning to speed convergence
- Multi-task learning across related domains
### 5.3 Memory Efficiency
For large unlabeled pools (
$$ U > 1M $$
):
- Cannot fit all samples in memory
- Batch acquisition: Select multiple samples per round
- Importance weighting: Approximate with samples
### 5.4 Parallelization
Active learning is inherently sequential (need model retraining between rounds). Strategies:
- Batch active learning: Select multiple samples per round
- Distributed ensemble: Committee members on different nodes
- Asynchronous retraining: Continue training while annotating
## 6. Practical Implementation Strategies
### 6.1 Uncertainty Quantification in Deep Learning
Bayesian Neural Networks: Uncertainty from weight posteriors
- MCMC sampling: Expensive but principled
- Variational inference: Faster approximation
- Laplace approximation: Diagonal Hessian
Ensembles: Simple and effective
- Multiple random initializations
- Bootstrap samples of data
- Different model architectures
Dropout as Bayesian: MC Dropout (Gal & Ghahramani)
- Keep dropout at test time
- Multiple stochastic forward passes
- Variance estimates from predictions
### 6.2 Pool-Based Active Learning Workflow
Initialize: Train on small labeled set
Repeat until budget exhausted:
1. Compute acquisition scores for unlabeled pool
2. Select top-B samples by score
3. Get labels for selected samples
4. Retrain model on updated labeled setBatch size B typically 10-100 samples per round.
### 6.3 Diversity-Uncertainty Trade-off
Balance two objectives:
$$a_{ ext{combined}}(x) = w_{ ext{unc}} \cdot a_{ ext{unc}}(x) + w_{ ext{div}} \cdot a_{ ext{div}}(x)$$
Typical weights:
$$ w_{ ext{unc}} = 0.7, w_{ ext{div}} = 0.3 $$
Adjust based on:
- Diversity of unlabeled pool (high diversity: favor uncertainty)
- Model confidence (low confidence: favor diversity to explore)
### 6.4 Stopping Criteria
When to stop acquiring labels:
1. Budget exhausted: Fixed annotation budget
2. Performance plateau: Validation accuracy stops improving
3. Confidence threshold: Model confidence exceeds threshold
4. Diminishing returns: Cost per accuracy gain exceeds threshold
Common: Monitor validation accuracy, stop when improvement < threshold.
## 7. Benchmark Datasets & Evaluation
### 7.1 Active Learning Benchmarks
MNIST with Active Learning:
- Baseline (random): 95% accuracy with 5000 labels (50%)
- Uncertainty: 95% accuracy with 2000 labels (20%)
- Core-set: 95% accuracy with 2500 labels (25%)
- Reduction: 60-80% label savings
CIFAR-10:
- Random sampling: 80% accuracy, 50K labels (100%)
- Uncertainty: 80% accuracy, 20K labels (40%)
- Core-set + diversity: 80% accuracy, 15K labels (30%)
Text Classification (AG News):
- Random: 90% accuracy, 120K labels (100%)
- Query by committee: 90% accuracy, 45K labels (37%)
- BALD: 90% accuracy, 40K labels (33%)
### 7.2 Evaluation Metrics
Annotation Savings:
$$ ext{Savings} = 1 - \frac{ ext{Labels used (AL)}}{ ext{Labels used (random)}}$$
Typical: 30-70% savings for uncertainty-based methods.
Learning Curve: Accuracy vs. number of labels
Standard plot: Compare AL to random baseline at each budget level.
Query Efficiency: Accuracy per unit annotation cost
$$ ext{Efficiency} = \frac{ ext{Accuracy}( ext{budget } B)}{ ext{Cost}(B)}$$
### 7.3 Benchmark Results
Simple Datasets (MNIST, CIFAR-10):
- Uncertainty, core-set, diversity: Similar performance within 5-10%
- Random baseline: 30-50% more labels needed
Complex Datasets (ImageNet subset):
- Uncertainty sampling: 20-30% label savings
- Core-set approach: 25-40% savings (better for diverse pools)
- Oracle (best subset): ~50% savings (unattainable)
## 8. Key Challenges & Limitations
### 8.1 Cold Start Problem
Initial labeled set small, model unreliable. Early acquisition decisions may be poor. Mitigation:
- Start with stratified random sample
- Use diversity-based methods initially
- Gradually shift to uncertainty
### 8.2 Distribution Shift
Unlabeled pool may not represent deployment distribution:
- Labeled pool biased toward certain classes
- Deployment data different (covariate shift)
- AL selects from biased pool
Solution: Combine AL with domain adaptation, importance weighting.
### 8.3 Multiple Objectives
Practitioners want:
- High accuracy (minimize error)
- Low annotation cost (minimize budget)
- Fast convergence (minimize time)
- Low computational cost (fast acquisition function)
These objectives may conflict. No universal solution.
### 8.4 Diminishing Returns
Active learning most effective early; benefits diminish as labeled set grows:
$$ ext{Benefit}(B) = ext{AL performance} - ext{Random performance}$$
Benefit decreases with increasing B. At 50-70% labeling, AL advantage often <5%.
## 9. Hyperparameter Tuning & Optimization
### 9.1 Ensemble Size
For committee-based methods:
- Larger ensembles: More stable disagreement measures, higher computation
- Typical: 5-20 models
- Diminishing returns beyond 10 members
### 9.2 Diversity Weight
Balance uncertainty and diversity in acquisition:
$$a(x) = \alpha \cdot a_{ ext{unc}} + (1-\alpha) \cdot a_{ ext{div}}$$
$$ \alpha $$
depends on:
- Early rounds: Low
$$ \alpha $$
(emphasize diversity)
- Late rounds: High
$$ \alpha $$
(emphasize uncertainty)
- Typical range:
$$ \alpha = 0.5-0.8 $$
### 9.3 Batch Size per Round
Trade-off between:
- Large batches: Fewer retraining rounds, less accurate selection
- Small batches: Many rounds, more accurate but slower
Typical:
$$ b = 10-100 $$
samples per round
### 9.4 Model Architecture
Different models have different uncertainty properties:
- Simple models (logistic regression): Uncertainty easy to compute, limited expressiveness
- Deep models: Rich features, uncertainty harder to quantify
- Ensembles: Better uncertainty, higher computation
Choose based on availability of labeled data and computational budget.
## 10. Real-World Applications & Case Studies
### 10.1 Medical Image Labeling
Problem: Label 10,000 CT scans for tumor detection; expert time expensive
Setup:
- Experts available: 1 per day (8 scans/day), 12-month project
- Random strategy: Label 12 scans/day → 360 scans/12 months
- Active learning: Label 12 priority scans/day
Active Learning Approach:
- Model: ResNet50 pretrained on ImageNet
- Uncertainty: MC dropout (10 forward passes)
- Diversity: Core-set based on embedding similarity
Results:
- Random sampling: 85% sensitivity at 12 months (360 labeled)
- Active learning: 85% sensitivity at 3 months (90 labeled)
- Label savings: 75% (360 → 90 scans)
Key insights:
- Uncertainty crucial for rare diseases
- Diversity prevents redundant labeling
- Early labels most valuable
### 10.2 NLP Text Classification
Problem: Classify 100K customer support tickets; expensive crowdsourcing
Setup:
- Annotation cost: $0.10 per label
- Target: 95% F1-score
- Budget: $5,000 (50K labels)
Active Learning Strategy:
- Baseline model: BERT fine-tuned on initial 1K labels
- Acquisition: BALD (Bayesian Active Learning by Disagreement)
- Committee: 3 models with different random seeds
Results:
- Random: 95% F1 with 45K labels ($4,500)
- Active learning: 95% F1 with 28K labels ($2,800)
- Cost savings: $1,700 (38%)
- Time savings: 3 months vs 6 months
Practical considerations:
- Crowdsourcing introduces label noise
- Combine AL with noise-robust training
- Periodic expert validation on high-uncertainty samples
### 10.3 Object Detection in Video
Problem: Annotate objects in video frames; frame-by-frame labeling tedious
Setup:
- 1000 video frames, 100 object classes
- Annotation cost: 5 minutes per frame (8 frames/hour)
- Budget: 40 hours (320 frames)
- Goal: 90% mAP
Active Learning Approach:
- Model: YOLO-v5 pretrained on COCO
- Uncertainty: Ensemble of 5 models with different augmentations
- Diversity: Sample frames maximizing scene diversity
Results:
- Random frames: 90% mAP with 320 frames (40 hours)
- Active selection: 90% mAP with 180 frames (22.5 hours)
- Time savings: 17.5 hours (44%)
Key innovations:
- Uncertainty at object level (not frame level)
- Diversity by scene clustering
- Progressive active learning (multiple rounds)
### 10.4 Autonomous Driving Safety Testing
Problem: Generate test scenarios for autonomous vehicle; expensive simulation
Setup:
- Scenario types: 50+ (rain, pedestrians, occlusions, etc.)
- Goal: Ensure 99.9% safety
- Simulation cost: $100 per scenario
Active Learning for Scenario Selection:
- Model: Predicts safety metric (collision risk)
- Uncertainty: MC dropout on neural network predictor
- Diversity: Select scenarios maximizing scenario space coverage
Results:
- Random scenario selection: 10,000 scenarios ($1M) for 99.9% safety
- Active scenario selection: 4,500 scenarios ($450K)
- Cost savings: $550K (55%)
- Development time: 8 months vs 18 months
## 11. Integration with Other Methods
### 11.1 Active Learning with Transfer Learning
Transfer from source domain, actively select from target:
1. Pretrain on source domain
2. Use source model for uncertainty estimates
3. Select uncertain target samples
Benefits: Faster adaptation, better initial estimates.
### 11.2 Semi-Supervised Active Learning
Combine active querying with semi-supervised learning:
$$\mathcal{L} = L_{ ext{labeled}} + \lambda L_{ ext{unlabeled}}$$
Use pseudo-labels for unlabeled data, actively refine uncertain predictions.
Improves sample efficiency by 30-50% in some settings.
### 11.3 Active Learning for Imbalanced Data
In imbalanced datasets, standard uncertainty may select majority class. Strategies:
- Stratified acquisition: Select samples per class
- Cost-sensitive acquisition: Favor rare classes
- Class-aware weighting in ensemble
### 11.4 Multi-Task Active Learning
Learn multiple related tasks; knowledge transfers:
$$a_{ ext{multi}}(x) = \sum_t w_t \cdot a_t(x)$$
Acquire samples informative for all tasks, not just primary task.
## 12. Future Research Directions
### 12.1 Realistic Cost Models
Most work assumes uniform annotation cost. Real scenarios:
- Different costs for different samples
- Annotator expertise varies
- Noisy labels from crowdsourcing
Future: Incorporate cost-sensitive acquisition and label noise.
### 12.2 Continual Active Learning
Active learning in streaming settings:
- Data arrives continuously
- Cannot store all samples
- Limited budget per time window
Combines challenges of active + continual learning.
### 12.3 Emergent Phenomena
Recent findings show unexpected behaviors:
- Deep ensembles sometimes underestimate uncertainty
- Acquisition functions may select outliers, not informative samples
- Non-monotonic learning curves
More investigation needed into when/why AL works.
### 12.4 Foundation Model Era
Large pretrained models (GPT, CLIP) may change AL landscape:
- Transfer learning reduces need for labeled data
- Few-shot learning from foundation models
- AL role shifts to fine-tuning and edge cases
## 13. Summary & Key Takeaways
Core Strategies:
- Uncertainty sampling: 20-40% label savings, simple to implement
- Query by committee: 25-45% savings, better diversity, higher computation
- Core-set: 30-50% savings, especially good for diverse pools
- Diversity sampling: Complements uncertainty, prevents redundancy
Uncertainty Quantification:
- Ensembles: Simple, effective (5-20 models)
- MC Dropout: Efficient Bayesian approximation
- Bayesian neural networks: Principled but expensive
- Multiple uncertainty measures work similarly (no clear winner)
Practical Implementation:
- Batch size: 10-100 samples per round (balance accuracy vs retraining cost)
- Diversity weight: 0.2-0.5 (adjust over rounds)
- Model retraining: Warm-start from previous weights
- Stopping: Monitor validation accuracy, stop at diminishing returns
Performance Characteristics:
- Label savings: 30-70% typical (higher on simple datasets)
- Most benefit early: 5-10x improvement at 10% of data, declining to 1-2x at 50%
- Diminishing returns: Below 30% labeling often <50% relative improvement to random
Hyperparameters:
- Ensemble size: 5-20 (diminishing returns beyond 10)
- Diversity weight: 0.2-0.5 (higher early, lower late)
- Batch size: 10-100 per round
- Committee agreement threshold: 0.5-0.8
When AL Helps Most:
- Limited labeling budget (< $10K)
- Expert annotation required
- Large unlabeled pool available
- Standard methods need > 50K labels
When AL Helps Least:
- Labels already abundant
- Distribution shift between pool and deployment
- High label noise (make uncertainty estimates unreliable)
- Classes extremely imbalanced
Active learning is a practical tool for reducing annotation costs, with 30-50% savings typical. Gains diminish as labeled data grows; most effective for low-resource scenarios.
---
## Appendix: Practical Implementation Labs
### Lab 1: Uncertainty Sampling
import torch
import torch.nn as nn
import numpy as np
def uncertainty_sampling(model, unlabeled_pool, n_to_select=100):
"""Select samples with highest uncertainty (lowest max probability)"""
model.eval()
uncertainties = []
with torch.no_grad():
for x in unlabeled_pool:
x = x.unsqueeze(0)
output = model(x)
probs = torch.softmax(output, dim=1)
max_prob = probs.max(dim=1)[0].item()
uncertainty = 1 - max_prob # Higher uncertainty = lower confidence
uncertainties.append(uncertainty)
uncertainties = np.array(uncertainties)
selected_indices = np.argsort(uncertainties)[-n_to_select:]
return selected_indices
def entropy_sampling(model, unlabeled_pool, n_to_select=100):
"""Select samples with highest entropy"""
model.eval()
entropies = []
with torch.no_grad():
for x in unlabeled_pool:
x = x.unsqueeze(0)
output = model(x)
probs = torch.softmax(output, dim=1)
entropy = -(probs * torch.log(probs + 1e-10)).sum(dim=1).item()
entropies.append(entropy)
entropies = np.array(entropies)
selected_indices = np.argsort(entropies)[-n_to_select:]
return selected_indices### Lab 2: Query by Committee
def query_by_committee(ensemble, unlabeled_pool, n_to_select=100):
"""Select samples with highest ensemble disagreement"""
disagreements = []
with torch.no_grad():
for x in unlabeled_pool:
x = x.unsqueeze(0)
predictions = []
for model in ensemble:
model.eval()
output = model(x)
pred = torch.argmax(output, dim=1).item()
predictions.append(pred)
# Disagreement: 1 - (votes for majority class / ensemble size)
from collections import Counter
votes = Counter(predictions)
max_votes = max(votes.values())
disagreement = 1 - (max_votes / len(ensemble))
disagreements.append(disagreement)
disagreements = np.array(disagreements)
selected_indices = np.argsort(disagreements)[-n_to_select:]
return selected_indices### Lab 3: Core-Set Approach
def core_set_selection(model, unlabeled_pool, labeled_indices,
n_to_select=100):
"""Select samples maximizing distance to labeled set (core-set)"""
model.eval()
embeddings = []
with torch.no_grad():
for x in unlabeled_pool:
x = x.unsqueeze(0)
# Get embedding from penultimate layer
embedding = model(x) # Modify to extract feature layer
embeddings.append(embedding.squeeze(0).cpu().numpy())
embeddings = np.array(embeddings)
labeled_embeddings = embeddings[labeled_indices]
selected = []
for i in range(n_to_select):
# Find sample farthest from labeled set
min_distances = []
for emb in embeddings:
min_dist = np.min(np.linalg.norm(
labeled_embeddings - emb, axis=1))
min_distances.append(min_dist)
farthest_idx = np.argmax(min_distances)
selected.append(farthest_idx)
labeled_embeddings = np.vstack([
labeled_embeddings,
embeddings[farthest_idx]
])
return selected### Lab 4: Active Learning Loop
def active_learning_loop(model, train_loader, unlabeled_pool,
num_rounds=10, batch_size=100):
"""Complete active learning training loop"""
optimizer = torch.optim.Adam(model.parameters(), lr=0.001)
criterion = nn.CrossEntropyLoss()
for round_num in range(num_rounds):
# Train on current labeled set
model.train()
for epoch in range(5):
for x, y in train_loader:
optimizer.zero_grad()
output = model(x)
loss = criterion(output, y)
loss.backward()
optimizer.step()
# Evaluate on validation set
model.eval()
val_loss = 0
with torch.no_grad():
for x, y in train_loader:
output = model(x)
val_loss += criterion(output, y).item()
print(f"Round {round_num}: Validation loss {val_loss:.4f}")
# Select samples via uncertainty sampling
selected_indices = uncertainty_sampling(
model, unlabeled_pool, n_to_select=batch_size)
# Simulate getting labels for selected samples
print(f"Selected {len(selected_indices)} samples for annotation")
# In real setting, send to human annotators here
# Then retrain model on enlarged labeled set