Semi-supervised learning

Points that are close to each other are more likely to share a label. This is also generally assumed in supervised learning and yields a preference for geometrically simple decision boundaries. In the case of semi-supervised learning, the smoothness assumption additionally yields a preference for decision boundaries in low-density regions, so few points are close to each other but in different classes.

The data tend to form discrete clusters, and points in the same cluster are more likely to share a label (although data that shares a label may spread across multiple clusters). This is a special case of the smoothness assumption and gives rise to feature learning with clustering algorithms.

The data lie approximately on a manifold of much lower dimension than the input space. In this case learning the manifold using both the labeled and unlabeled data can avoid the curse of dimensionality. Then learning can proceed using distances and densities defined on the manifold.

The manifold assumption is practical when high-dimensional data are generated by some process that may be hard to model directly, but which has only a few degrees of freedom. For instance, human voice is controlled by a few vocal folds,[3] and images of various facial expressions are controlled by a few muscles. In these cases distances and smoothness in the natural space of the generating problem, is superior to considering the space of all possible acoustic waves or images, respectively.

Generative approaches to statistical learning first seek to estimate ${\displaystyle p(x|y)}$, the distribution of data points belonging to each class. The probability ${\displaystyle p(y|x)}$ that a given point ${\displaystyle x}$ has label ${\displaystyle y}$ is then proportional to ${\displaystyle p(x|y)p(y)}$ by Bayes' rule. Semi-supervised learning with generative models can be viewed either as an extension of supervised learning (classification plus information about ${\displaystyle p(x)}$) or as an extension of unsupervised learning (clustering plus some labels).

Generative models assume that the distributions take some particular form ${\displaystyle p(x|y,\theta )}$ parameterized by the vector ${\displaystyle \theta }$. If these assumptions are incorrect, the unlabeled data may actually decrease the accuracy of the solution relative to what would have been obtained from labeled data alone.[8] However, if the assumptions are correct, then the unlabeled data necessarily improves performance.[6]

The unlabeled data are distributed according to a mixture of individual-class distributions. In order to learn the mixture distribution from the unlabeled data, it must be identifiable, that is, different parameters must yield different summed distributions. Gaussian mixture distributions are identifiable and commonly used for generative models.

The parameterized joint distribution can be written as ${\displaystyle p(x,y|\theta )=p(y|\theta )p(x|y,\theta )}$ by using the chain rule. Each parameter vector ${\displaystyle \theta }$ is associated with a decision function ${\displaystyle f_{\theta }(x)={\underset {y}{\operatorname {argmax} }}\ p(y|x,\theta )}$. The parameter is then chosen based on fit to both the labeled and unlabeled data, weighted by ${\displaystyle \lambda }$:

${\displaystyle {\underset {\Theta }{\operatorname {argmax} }}\left(\log p(\{x_{i},y_{i}\}_{i=1}^{l}|\theta )+\lambda \log p(\{x_{i}\}_{i=l+1}^{l+u}|\theta )\right)}$[9]

Another major class of methods attempts to place boundaries in regions with few data points (labeled or unlabeled). One of the most commonly used algorithms is the transductive support vector machine, or TSVM (which, despite its name, may be used for inductive learning as well). Whereas support vector machines for supervised learning seek a decision boundary with maximal margin over the labeled data, the goal of TSVM is a labeling of the unlabeled data such that the decision boundary has maximal margin over all of the data. In addition to the standard hinge loss ${\displaystyle (1-yf(x))_{+}}$ for labeled data, a loss function ${\displaystyle (1-|f(x)|)_{+}}$ is introduced over the unlabeled data by letting ${\displaystyle y=\operatorname {sign} {f(x)}}$. TSVM then selects ${\displaystyle f^{*}(x)=h^{*}(x)+b}$ from a reproducing kernel Hilbert space ${\displaystyle {\mathcal {H}}}$ by minimizing the regularized empirical risk:

${\displaystyle f^{*}={\underset {f}{\operatorname {argmin} }}\left(\displaystyle \sum _{i=1}^{l}(1-y_{i}f(x_{i}))_{+}+\lambda _{1}\|h\|_{\mathcal {H}}^{2}+\lambda _{2}\sum _{i=l+1}^{l+u}(1-|f(x_{i})|)_{+}\right)}$

An exact solution is intractable due to the non-convex term ${\displaystyle (1-|f(x)|)_{+}}$, so research focuses on useful approximations.[9]

Other approaches that implement low-density separation include Gaussian process models, information regularization, and entropy minimization (of which TSVM is a special case).

Graph-based methods for semi-supervised learning use a graph representation of the data, with a node for each labeled and unlabeled example. The graph may be constructed using domain knowledge or similarity of examples; two common methods are to connect each data point to its ${\displaystyle k}$ nearest neighbors or to examples within some distance ${\displaystyle \epsilon }$. The weight ${\displaystyle W_{ij}}$ of an edge between ${\displaystyle x_{i}}$ and ${\displaystyle x_{j}}$ is then set to ${\displaystyle e^{\frac {-\|x_{i}-x_{j}\|^{2}}{\epsilon }}}$.

Within the framework of manifold regularization,[10][11] the graph serves as a proxy for the manifold. A term is added to the standard Tikhonov regularization problem to enforce smoothness of the solution relative to the manifold (in the intrinsic space of the problem) as well as relative to the ambient input space. The minimization problem becomes

${\displaystyle {\underset {f\in {\mathcal {H}}}{\operatorname {argmin} }}\left({\frac {1}{l}}\displaystyle \sum _{i=1}^{l}V(f(x_{i}),y_{i})+\lambda _{A}\|f\|_{\mathcal {H}}^{2}+\lambda _{I}\int _{\mathcal {M}}\|\nabla _{\mathcal {M}}f(x)\|^{2}dp(x)\right)}$[9]

where ${\displaystyle {\mathcal {H}}}$ is a reproducing kernel Hilbert space and ${\displaystyle {\mathcal {M}}}$ is the manifold on which the data lie. The regularization parameters ${\displaystyle \lambda _{A}}$ and ${\displaystyle \lambda _{I}}$ control smoothness in the ambient and intrinsic spaces respectively. The graph is used to approximate the intrinsic regularization term. Defining the graph Laplacian ${\displaystyle L=D-W}$ where ${\displaystyle D_{ii}=\sum _{j=1}^{l+u}W_{ij}}$ and ${\displaystyle \mathbf {f} }$ the vector ${\displaystyle [f(x_{1})\dots f(x_{l+u})]}$, we have

${\displaystyle \mathbf {f} ^{T}L\mathbf {f} =\displaystyle \sum _{i,j=1}^{l+u}W_{ij}(f_{i}-f_{j})^{2}\approx \int _{\mathcal {M}}\|\nabla _{\mathcal {M}}f(x)\|^{2}dp(x)}$.

The Laplacian can also be used to extend the supervised learning algorithms: regularized least squares and support vector machines (SVM) to semi-supervised versions Laplacian regularized least squares and Laplacian SVM.

Some methods for semi-supervised learning are not intrinsically geared to learning from both unlabeled and labeled data, but instead make use of unlabeled data within a supervised learning framework. For instance, the labeled and unlabeled examples ${\displaystyle x_{1},\dots ,x_{l+u}}$ may inform a choice of representation, distance metric, or kernel for the data in an unsupervised first step. Then supervised learning proceeds from only the labeled examples.

Self-training is a wrapper method for semi-supervised learning.[12] First a supervised learning algorithm is trained based on the labeled data only. This classifier is then applied to the unlabeled data to generate more labeled examples as input for the supervised learning algorithm. Generally only the labels the classifier is most confident in are added at each step.[13]

Co-training is an extension of self-training in which multiple classifiers are trained on different (ideally disjoint) sets of features and generate labeled examples for one another.[14]