Semi-Supervised Learning Label Propagation Pseudo-Labeling
# Semi-Supervised Learning: Label Propagation & Pseudo-Labeling
## Introduction & Motivation
Semi-supervised learning leverages unlabeled data (typically abundant) + small labeled set. Label propagation: spread labels via similarity graph; pseudo-labeling: self-train with high-confidence predictions on unlabeled data. Consistency regularization encourages smooth predictions under perturbation. Critical when labeling is expensive (medical imaging, rare events).
Motivation: Often have little labeled, lots of unlabeled data. Pure supervised wastes unlabeled. Pure unsupervised ignores labels.
Applications: Medical diagnosis, document classification, speech recognition, computer vision.
---
## Core Concepts & Theory
### Label Propagation
Iteratively update labels via graph: Y_new = (I - αL)^{-1} αS_L
where L = normalized graph Laplacian, S_L = seed labels.
### Pseudo-Labeling
Train on labeled; predict on unlabeled; add high-confidence to training. Iterate.
### Consistency Regularization
Perturb input; encourage same prediction. Combines supervised + unsupervised losses.
---
## Mathematical Formulation
Label propagation update:
$$\mathbf{Y}^{(t+1)} = \alpha \mathbf{P} \mathbf{Y}^{(t)} + (1-\alpha) \mathbf{Y}_L$$
where P = row-normalized adjacency, α ∈ [0,1] controls smoothing.
Pseudo-label confidence threshold:
$$ ext{Add to train if } \max_c \hat{P}(c | x) > au$$
Consistency loss:
$$\mathcal{L} = \mathcal{L}_{ ext{supervised}} + \lambda \mathbb{E}_{x,\xi}[D(f(x), f(x + \xi))]$$
---
## Advanced Theory & Extensions
### Transductive Learning
Optimize for specific unlabeled set (not general distribution). Label propagation naturally transductive.
### Co-Training
Multiple views; each view labels for other. Reduces variance via view disagreement.
### Generative Models
VAE/GAN on unlabeled; use learned representation for classification.
---
## Computational Considerations
Label propagation: O(n³) matrix inversion (precompute); O(n²) graph construction.
Pseudo-labeling: O(iterations × (train forward + predict unlabeled)).
Consistency regularization: 2× forward passes per batch.
---
## Practical Implementation Strategies
### Graph Construction
k-NN (efficient); RBF kernel (smooth similarities); balance sparsity-density.
### Pseudo-Label Confidence
Start τ high (0.95); lower gradually. Avoid early noisy labels.
### Data Augmentation
Use weak augmentation (consistency); strong augmentation (pseudo-label).
---
## Benchmark Datasets & Evaluation
CIFAR-10/100: Limited labels (e.g., 400 labels CIFAR-10).
ImageNet Subset: 1% labeled; protocol from PIRL.
Text: 20 Newsgroups, cite networks.
Metrics: Accuracy on test set; learning curves vs. labeled %.
---
## Key Challenges & Limitations
### Label Noise Propagation
Pseudo-labels amplify errors; noisy early on.
### Assumption Violation
Cluster assumption (same cluster → same class) may not hold.
### Evaluation Bias
Must use truly held-out labels; don't use unlabeled set for validation.
---
## Hyperparameter Tuning
α (label propagation): 0.1-0.9; higher = more smoothing.
τ (pseudo-label threshold): 0.9-0.95; lower = more pseudo-labels.
λ (consistency weight): 0.1-1.0; balance supervised-unsupervised.
---
## Real-World Applications & Case Studies
Medical Imaging: Limited annotated scans; pseudo-label on unlabeled.
NLP: Sentiment classification; semi-supervised pretraining (ELMo, BERT).
Speech: Pseudo-labeling for acoustic models; millions of unlabeled audio.
---
## Integration with Other Methods
Semi-supervised + Self-Supervised → combine pseudo-labels + contrastive loss.
Semi-supervised + Active Learning → query most informative unlabeled examples.
---
## Summary & Key Takeaways
Semi-supervised learning leverages unlabeled data via label propagation, pseudo-labeling, or consistency regularization, improving generalization when labeled data is scarce.
Principles:
1. Label propagation spreads labels via graph smoothness.
2. Pseudo-labeling iteratively self-trains on high-confidence examples.
3. Consistency regularization penalizes prediction changes under perturbation.
4. Cluster assumption: same cluster → same class.
5. Evaluate on separate test set; avoid label leakage.
---
---
## Appendix: Practical Labs
### Lab 1: Label Propagation
import numpy as np
from sklearn.metrics.pairwise import rbf_kernel
from scipy.linalg import solve
def label_propagation(X, y_labeled, indices_labeled, kernel_matrix=None, alpha=0.1, max_iter=100):
"""
X: (n, d) features
y_labeled: labels for indices_labeled
indices_labeled: indices with labels
"""
n = X.shape[0]
if kernel_matrix is None:
W = rbf_kernel(X, gamma=1.0)
else:
W = kernel_matrix
# Normalize
D = np.sum(W, axis=1)
D_inv_sqrt = np.diag(1.0 / np.sqrt(D + 1e-8))
P = D_inv_sqrt @ W @ D_inv_sqrt
# Initialize
Y = np.zeros((n, len(np.unique(y_labeled))))
Y[indices_labeled, y_labeled] = 1
# Iterate
for _ in range(max_iter):
Y = alpha * P @ Y + (1 - alpha) * Y
Y[indices_labeled, :] = 0
Y[indices_labeled, y_labeled] = 1
return Y
# Data
np.random.seed(42)
X = np.vstack([np.random.randn(30, 2) - 2, np.random.randn(30, 2) + 2])
y_true = np.concatenate([np.zeros(30), np.ones(30)])
indices_labeled = np.array([0, 5, 30, 35])
y_labeled = y_true[indices_labeled].astype(int)
Y = label_propagation(X, y_labeled, indices_labeled, alpha=0.5)
y_pred = np.argmax(Y, axis=1)
acc = (y_pred == y_true).mean()
print(f"Label propagation accuracy: {acc:.2%}")
assert 0 <= acc <= 1, "Accuracy should be in [0, 1]"
assert acc > 0.5, "Should beat random guess"
print("✓ Label propagation working")
if __name__ == "__main__":
print("Lab 1: Label Prop - PASSED")### Lab 2: Pseudo-Labeling
import numpy as np
from sklearn.linear_model import LogisticRegression
from sklearn.datasets import make_classification
# Data
X, y = make_classification(n_samples=200, n_features=10, n_informative=5, random_state=42)
X_labeled, y_labeled = X[:20], y[:20]
X_unlabeled = X[20:]
# Pseudo-labeling
model = LogisticRegression(max_iter=200)
model.fit(X_labeled, y_labeled)
# Predict on unlabeled
probs = model.predict_proba(X_unlabeled)
max_probs = np.max(probs, axis=1)
preds = np.argmax(probs, axis=1)
# Select high-confidence
threshold = 0.9
high_conf = max_probs > threshold
n_added = high_conf.sum()
print(f"Added {n_added} pseudo-labeled examples (threshold={threshold})")
assert n_added >= 0, "Should have non-negative pseudo-labels"
assert n_added <= len(X_unlabeled), "Should not exceed unlabeled set"
print("✓ Pseudo-labeling working")
if __name__ == "__main__":
print("Lab 2: Pseudo-Label - PASSED")### Lab 3: Consistency Regularization
import torch
import torch.nn as nn
import torch.optim as optim
from torch.utils.data import TensorDataset, DataLoader
import numpy as np
class SimpleNet(nn.Module):
def __init__(self, input_dim=10, output_dim=2):
super().__init__()
self.net = nn.Sequential(
nn.Linear(input_dim, 64),
nn.ReLU(),
nn.Linear(64, output_dim)
)
def forward(self, x):
return self.net(x)
def gaussian_noise(x, std=0.1):
return x + torch.randn_like(x) * std
# Data
np.random.seed(42)
X_labeled = torch.randn(30, 10)
y_labeled = torch.randint(0, 2, (30,))
X_unlabeled = torch.randn(100, 10)
model = SimpleNet(input_dim=10, output_dim=2)
optimizer = optim.Adam(model.parameters(), lr=0.001)
criterion = nn.CrossEntropyLoss()
# Train with consistency
losses = []
for epoch in range(20):
# Supervised loss
logits = model(X_labeled)
loss_sup = criterion(logits, y_labeled)
# Consistency loss
logits1 = model(gaussian_noise(X_unlabeled))
logits2 = model(gaussian_noise(X_unlabeled))
probs1 = torch.softmax(logits1, dim=1)
probs2 = torch.softmax(logits2, dim=1)
loss_cons = torch.mean((probs1 - probs2.detach())**2)
loss = loss_sup + 0.1 * loss_cons
optimizer.zero_grad()
loss.backward()
optimizer.step()
losses.append(loss.item())
print(f"Final loss: {losses[-1]:.4f}")
assert len(losses) == 20, "Should have 20 loss values"
assert all(np.isfinite(l) for l in losses), "All losses should be finite"
print("✓ Consistency regularization working")
if __name__ == "__main__":
print("Lab 3: Consistency - PASSED")### Lab 4: Self-Training
import numpy as np
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import make_classification
def self_train(X_labeled, y_labeled, X_unlabeled, n_iterations=3, threshold=0.9):
"""Iterative self-training"""
X_train = X_labeled.copy()
y_train = y_labeled.copy()
for iteration in range(n_iterations):
# Train
model = DecisionTreeClassifier(max_depth=5, random_state=42)
model.fit(X_train, y_train)
# Predict unlabeled
probs = model.predict_proba(X_unlabeled)
max_prob = np.max(probs, axis=1)
pred = np.argmax(probs, axis=1)
# Add high-confidence
high_conf = max_prob > threshold
if high_conf.sum() > 0:
X_train = np.vstack([X_train, X_unlabeled[high_conf]])
y_train = np.concatenate([y_train, pred[high_conf]])
X_unlabeled = X_unlabeled[~high_conf]
print(f"Iteration {iteration+1}: Added {high_conf.sum()} labels")
else:
break
return model, X_train, y_train
# Data
X, y = make_classification(n_samples=200, n_features=10, n_informative=5, random_state=42)
X_labeled, y_labeled = X[:20], y[:20]
X_unlabeled = X[20:]
model, X_final, y_final = self_train(X_labeled, y_labeled, X_unlabeled, n_iterations=2)
train_size_increase = len(y_final) - len(y_labeled)
print(f"Training set grew from {len(y_labeled)} to {len(y_final)}")
assert len(y_final) >= len(y_labeled), "Should not shrink"
assert train_size_increase >= 0, "Should add labels"
print("✓ Self-training working")
if __name__ == "__main__":
print("Lab 4: Self-Train - PASSED")