Supervised learning relies on the assumption of vast, faithfully annotated training corpora $mathcal{D}_L = (x_i, y_i)_{i=1}^l$. In high-stakes empirical applications—ranging from medical diagnostics to molecular chemistry—label acquisition is prohibitively expensive, tedious, or hazardous, whereas unlabeled observations $mathcal{D}_U = (x_j)_{j=l+1}^{l+u}$ exist in overwhelming abundance ($u gg l$). Semi-Supervised Learning (SSL) and Active Learning (AL) exploit geometric and statistical structures in unlabeled data to break the sample complexity bottlenecks of supervised learning.
1. The Fundamental Assumptions of Semi-Supervised Learning
Unlabeled data $P(X)$ can inform prediction of conditional target $P(Y mid X)$ only if their underlying distributions are mathematically coupled. Modern SSL rests on three formal geometric postulates:
- The Smoothness Assumption: If two input vectors $x_1, x_2$ reside in high-density regions of $P(X)$ and are close under Riemannian distance, their output conditionals $P(Y mid x_1)$ and $P(Y mid x_2)$ are close.
- The Cluster Assumption: Decision boundaries should pass through low-density valleys of the input distribution $P(X)$, avoiding dense data clusters.
- The Manifold Assumption: High-dimensional input data concentrates near a low-dimensional manifold $mathcal{M}$. Conditional distributions vary smoothly along geodesic paths on $mathcal{M}$.
2. Graph-Based Semi-Supervised Learning: Harmonic Functions
In 2003, Xiaojin Zhu, Zoubin Ghahramani, and John Lafferty formulated semi-supervised learning as finding Harmonic Functions on graphs. Constructing an affinity matrix $W_{ij} = exp(-|x_i – x_j|^2 / 2sigma^2)$ over all $n = l + u$ points, the graph Dirichlet energy is defined by:
$$mathcal{E}(f) = frac{1}{2} sum_{i,j=1}^n W_{ij} (f(x_i) – f(x_j))^2 = f^T L f$$
where $L = D – W$ is the unnormalized combinatorial graph Laplacian. Partitioning $f = [f_L^T, f_U^T]^T$ where $f_L = y_L$ is clamped to known training labels, minimizing Dirichlet energy subject to boundary conditions yields harmonic functions satisfying $Delta f(x_i) = 0$ for all $x_i in mathcal{D}_U$:
$$L_{UU} f_U + L_{UL} y_L = 0 implies f_U^* = -L_{UU}^{-1} L_{UL} y_L$$
This closed-form analytical solution represents the equilibrium state of an absorbing Markov random walk, where $f_U(i)$ denotes the exact probability that a random walker starting at node $i$ gets absorbed into a labeled node of positive class.
3. Multi-View Learning: Blum and Mitchell’s Co-Training
In 1998, Avrim Blum and Tom Mitchell introduced Co-Training for data admitting naturally partitioned, independent feature views $x = (x^{(1)}, x^{(2)})$ (e.g., web page text vs. hyperlinked anchor text). If each view is conditionally independent given the true class label and individually sufficient for classification:
$$P(x^{(1)}, x^{(2)} mid y) = P(x^{(1)} mid y) P(x^{(2)} mid y)$$
Blum and Mitchell proved that maximizing consensus between two independent base classifiers across unlabeled instances allows learning with minimal initial supervision, provably bootstrapping weak initial seeds to optimal bayes rates.
4. Active Learning: Query by Committee and Information Acquisition
Instead of passively accepting random labels, Active Learning empowers the learning algorithm to strategically query an oracle (human expert) for labels on the most informative instances. Classical acquisition strategies include:
- Uncertainty Sampling (Shannon Entropy): Select points maximizing posterior predictive entropy:
$$x^* = argmax_{x in mathcal{D}_U} H(Y mid x) = -sum_{c} P(y=c mid x) log P(y=c mid x)$$
- Query by Committee (QBC): A committee of models $mathcal{C} = {theta_1, dots, theta_K}$ sampled from posterior $P(theta mid mathcal{D})$ votes on unlabeled instances; the algorithm queries points with maximal disagreement (Kullback-Leibler divergence from the consensus vote).
- Expected Information Gain / Fisher Information: Selecting instances that maximize the reduction in model uncertainty via the Fisher Information Matrix $mathcal{I}(theta) = mathbb{E}[ nabla_theta log p(y mid x, theta) nabla_theta log p(y mid x, theta)^T ]$, optimizing the Cramér-Rao lower bound of parameter estimators.
