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")