Active Learning Query Strategy Sample Selection

# Active Learning: Query Strategy & Sample Selection

## Introduction & Motivation

Active learning selects informative samples for labeling, reducing annotation cost. Uncertainty sampling: query high-uncertainty predictions; query-by-committee: disagreement among ensemble. Pool-based: select from unlabeled pool; stream-based: online decision. Combines supervised learning with strategic sampling. Critical when labeling expensive (rare diseases, expert knowledge).

Motivation: Random sampling wastes budget on easy examples. Active selection prioritizes informative unknowns.

Applications: Medical diagnosis, text classification, computer vision, rare event detection.

---

## Core Concepts & Theory

### Uncertainty Sampling

Query examples model is most uncertain: max_x H(ŷ|x) or min_x max_c P(c|x).

### Query by Committee

Multiple hypotheses vote; query where most disagreement. Variance reduction via ensemble.

### Expected Model Change

Query examples causing largest parameter updates. Expensive; approximated via gradient norms.

---

## Mathematical Formulation

Entropy-based uncertainty:
$$H(Y|x) = -\sum_c P(c|x) \log P(c|x)$$

Margin sampling (binary):
$$ ext{margin}(x) = P(y_1|x) - P(y_2|x)$$

QBC disagreement:
$$ ext{vote\_entropy}(x) = -\sum_c \frac{V_c}{M} \log \frac{V_c}{M}$$

where V_c = votes for class c, M = committee size.

---

## Advanced Theory & Extensions

### Batch Active Learning

Select informative batch; avoid redundancy via diversity. BALD: Bayesian active learning by disagreement.

### Cost-Sensitive Active Learning

Different labeling costs per example; acquire lowest cost/informativeness ratio.

### Deepactive

Deep networks + uncertainty via dropout (MC-dropout) or ensembles.

---

## Computational Considerations

Uncertainty sampling: O(n) forward passes.

QBC: O(M × n) for M committee members.

Expected model change: O(n × d²) for Hessian computation.

Batch selection: O(n² d) with diversity penalty.

---

## Practical Implementation Strategies

### Uncertainty Estimation

Softmax entropy (cheap); Monte Carlo dropout (better); ensemble (best, expensive).

### Batch Diversity

Penalize redundant selections: diversity = euclidean distance in feature/prediction space.

### Warm-start

Initialize with labeled + random samples; avoid cold-start bias.

---

## Benchmark Datasets & Evaluation

CIFAR-10/100: Simulate budget-constrained labeling.

20 Newsgroups: Text classification; 1000s of documents.

Medical Imaging: Limited expert annotations.

Learning curves: Accuracy vs. labeled percentage; compare strategies.

---

## Key Challenges & Limitations

### Cold Start

Initial model poor; uncertainty estimates unreliable early on.

### Outliers

High-uncertainty may be outliers, not informative. Filter noise.

### Batch Effects

Batch diversity important; greedy per-sample suboptimal.

---

## Hyperparameter Tuning

Batch size: 10-100 depending on labeling cost.

Uncertainty method: Entropy (fast) vs. ensemble (accurate).

Diversity weight: 0.1-1.0; balance informativeness-diversity.

---

## Real-World Applications & Case Studies

Medical Diagnosis: Query ambiguous cases; reduce radiologist burden.

NLP: Active learning for NER; label rare entity types.

Rare Event Detection: Fraud detection; query near-boundary examples.

---

## Integration with Other Methods

Active Learning + Semi-Supervised → query then self-train.

Active Learning + Transfer Learning → query on target domain.

---

## Summary & Key Takeaways

Active learning strategically selects informative samples for labeling, reducing annotation cost via uncertainty sampling, query-by-committee, or expected model change.

Principles:
1. Entropy-based uncertainty prioritizes high-entropy predictions.
2. QBC leverages ensemble disagreement.
3. Batch selection balances informativeness and diversity.
4. Cost-sensitive strategies handle variable labeling costs.
5. Early uncertainty estimates unreliable; warm-start recommended.

---

---

## Appendix: Practical Labs

### Lab 1: Uncertainty Sampling

import numpy as np
from sklearn.linear_model import LogisticRegression
from sklearn.datasets import make_classification

def entropy(probs):
 """Shannon entropy of probability distribution"""
 return -np.sum(probs * np.log(probs + 1e-8), axis=1)

# Data
X, y = make_classification(n_samples=300, n_features=10, n_informative=5, random_state=42)
X_labeled, y_labeled = X[:20], y[:20]
X_unlabeled = X[20:]

# Train
model = LogisticRegression(max_iter=200)
model.fit(X_labeled, y_labeled)

# Uncertainty on unlabeled
probs = model.predict_proba(X_unlabeled)
uncertainties = entropy(probs)

# Select top-k uncertain
k = 10
top_uncertain_idx = np.argsort(uncertainties)[-k:]
top_uncertain_scores = uncertainties[top_uncertain_idx]

print(f"Top {k} uncertainty scores: {top_uncertain_scores}")
assert len(top_uncertain_idx) == k, "Should select k samples"
assert uncertainties.max() >= top_uncertain_scores.min(), "Should be top scores"
print("✓ Uncertainty sampling working")

if __name__ == "__main__":
 print("Lab 1: Uncertainty - PASSED")

### Lab 2: Query by Committee

import numpy as np
from sklearn.ensemble import BaggingClassifier
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import make_classification

def vote_entropy(ensemble_preds):
 """Entropy of class votes from ensemble"""
 n_samples = ensemble_preds[0].shape[0]
 n_classes = max(ensemble_preds[0].max(), ensemble_preds[1].max()) + 1
 
 votes = np.zeros((n_samples, n_classes))
 for preds in ensemble_preds:
 for i in range(n_samples):
 votes[i, preds[i]] += 1
 
 probs = votes / len(ensemble_preds)
 return -np.sum(probs * np.log(probs + 1e-8), axis=1)

# Data
X, y = make_classification(n_samples=300, n_features=10, n_informative=5, random_state=42)
X_labeled, y_labeled = X[:20], y[:20]
X_unlabeled = X[20:]

# Train committee (3 trees)
committee = [DecisionTreeClassifier(max_depth=5, random_state=i) for i in range(3)]
for learner in committee:
 learner.fit(X_labeled, y_labeled)

# Get predictions
ensemble_preds = [learner.predict(X_unlabeled) for learner in committee]
disagreement = vote_entropy(ensemble_preds)

# Select top disagreement
k = 10
top_disagree_idx = np.argsort(disagreement)[-k:]

print(f"Top {k} disagreement scores: {disagreement[top_disagree_idx]}")
assert len(top_disagree_idx) == k, "Should select k samples"
print("✓ Query by committee working")

if __name__ == "__main__":
 print("Lab 2: QBC - PASSED")

### Lab 3: Margin Sampling

import numpy as np
from sklearn.svm import SVC
from sklearn.datasets import make_classification

def margin(probs):
 """Probability margin: P_1 - P_2"""
 sorted_probs = np.sort(probs, axis=1)[:, ::-1]
 return sorted_probs[:, 0] - sorted_probs[:, 1]

# Data
X, y = make_classification(n_samples=300, n_features=10, n_informative=5, random_state=42)
X_labeled, y_labeled = X[:30], y[:30]
X_unlabeled = X[30:]

# Train SVM
model = SVC(kernel='rbf', probability=True)
model.fit(X_labeled, y_labeled)

# Margin on unlabeled
probs = model.predict_proba(X_unlabeled)
margins = margin(probs)

# Select smallest margin (most uncertain)
k = 10
least_confident_idx = np.argsort(margins)[:k]

print(f"Least confident margins: {margins[least_confident_idx]}")
assert len(least_confident_idx) == k, "Should select k samples"
assert margins[least_confident_idx].max() <= margins.max(), "Should be smallest margins"
print("✓ Margin sampling working")

if __name__ == "__main__":
 print("Lab 3: Margin - PASSED")

### Lab 4: Batch Active Learning with Diversity

import numpy as np
from sklearn.datasets import make_classification
from scipy.spatial.distance import pdist, squareform

def batch_selection(X_unlabeled, uncertainties, k=10, diversity_weight=0.5):
 """Greedy batch selection balancing uncertainty and diversity"""
 selected = []
 available = set(range(len(X_unlabeled)))
 
 # Compute pairwise distances
 distances = squareform(pdist(X_unlabeled, metric='euclidean'))
 
 for _ in range(k):
 best_score = -np.inf
 best_idx = None
 
 for idx in available:
 # Uncertainty score
 uncertainty_score = uncertainties[idx]
 
 # Diversity: avg distance to already selected
 if len(selected) > 0:
 diversity_score = np.mean([distances[idx, s] for s in selected])
 else:
 diversity_score = 0
 
 # Combined score
 score = uncertainty_score - diversity_weight * diversity_score
 
 if score > best_score:
 best_score = score
 best_idx = idx
 
 if best_idx is not None:
 selected.append(best_idx)
 available.remove(best_idx)
 
 return np.array(selected)

# Data
X, y = make_classification(n_samples=300, n_features=10, n_informative=5, random_state=42)
X_unlabeled = X[50:]
uncertainties = np.random.rand(len(X_unlabeled))

batch_idx = batch_selection(X_unlabeled, uncertainties, k=10, diversity_weight=0.5)

print(f"Selected batch indices: {batch_idx}")
assert len(batch_idx) == 10, "Should select 10 samples"
assert len(np.unique(batch_idx)) == 10, "Should be unique"
print("✓ Batch active learning working")

if __name__ == "__main__":
 print("Lab 4: Batch - PASSED")