Introduction to Semi-Supervised Learning for Classification Problems

When solving a classification problem — determining the class or category of a specific data point — the natural instinct is to gather a training dataset where every data point is labeled with its corresponding class. This family of Machine Learning algorithms is called Supervised Learning.

However, data is one of the biggest bottlenecks when training a Machine Learning model, alongside compute resources and the time required to train it.

All of these constraints ultimately equate to money. You need money to acquire or create more data, to provision hardware for higher compute volumes, and the time spent training and tuning a model also represents a business opportunity cost.

On top of this, there are several problem domains where high-quality labeled data is difficult to obtain — image classification and drug discovery are two prominent examples.

To address the scarcity of labeled data in real-world problems, researchers developed a family of Machine Learning algorithms that can use both labeled and unlabeled data points to train a classifier. This family is called Semi-Supervised Learning.

Supervised vs Semi-Supervised Learning

A typical Supervised Learning problem is mathematically described as follows.

You have a set of labeled data points of size l, and each data point (xi, yi) is an object in space X such that each xi belongs to the space X and is associated with a label yi [1]. The label yi is the true label, or ground truth, for that data point in a classification problem.

After training the model, you can give it a never-seen-before data point x*, and the model will predict its label y*.

This works well, but as noted above, real-world scenarios often lack sufficient labeled data to train a model with acceptable performance. One approach is to leverage unlabeled data, developing a Semi-Supervised model that combines:

• Labeled data points — data for which the true label (ground truth) is known
• Unlabeled data points — data without information about its true label (ground truth)

At this point you might be thinking: In any situation where labeled data is scarce or expensive, can I just add unlabeled data and my model will improve?

It would be ideal if a small labeled dataset could be combined with a large volume of unlabeled data to produce a model exponentially better than one built solely on labeled data.

Unfortunately, it’s not that simple. Adding large volumes of unlabeled data to the training process does not guarantee improved predictions. It is necessary that the unlabeled data carries information useful for label prediction — information not already present in the labeled data and not easily extracted from it. Multiple research papers detail specific scenarios where adding unlabeled data can and cannot provide useful information for improving predictions [2].

Data Assumptions for Semi-Supervised Learning

In order to use unlabeled data effectively, the underlying marginal data distribution p(x) over the input space must contain information about the posterior distribution p(y|x) [1]. Without this, it has been proved that improving prediction accuracy by adding unlabeled data is virtually impossible [2].

In short, the distribution of unlabeled data must satisfy a set of assumptions in order to effectively improve the classifier [1]. Different algorithms follow one or more of the following assumptions:

• Smoothness Assumption
• Cluster Assumption
• Low-Density Assumption
• Manifold Assumption

Smoothness Assumption

If two samples x and x’ are close in the input space, their labels y and y’ should be the same.

This assumption states that if the Euclidean distance between two points is small, their labels should be the same [3].

Cluster Assumption

We can use unlabeled data to find clusters.

This assumption is related to the Smoothness Assumption. Unlabeled data can be used to identify clusters, and labels can then be propagated to unlabeled data points that fall within the same cluster as labeled points [3].

Low-Density Assumption

The decision boundary shouldn’t pass through high-density areas in the input space.

The decision boundary is the line or plane that separates data points into different classes. If a decision boundary separates groups of data points into different classes, it tends to fall in a region of the hyperplane with relatively few points — that is, a low-density region. There will always be some data points near the decision boundary, but at a much lower density compared to the clusters of same-label points. This assumption is also referred to in the literature as an instance of the Cluster Assumption.

Manifold Assumption

If two points x1, x2 ∈ X are close in the intrinsic geometry of P(X), then the conditional distributions P(y | x1) and P(y | x2) are similar [2].

When data is represented in Euclidean space, observed data points in a high-dimensional space tend to concentrate in low-dimensional subspaces called manifolds. By identifying these manifolds and the data points within each one, labels can be propagated to previously unlabeled points based on the known labels of other points in the same manifold. In practice, this is closely related to the Smoothness Assumption: similar points tend to belong to similar groups.

Inductive vs Transductive Algorithms

There are many different Semi-Supervised Machine Learning algorithms [1], each based on a different set of assumptions, but they primarily divide into two major groups:

• Inductive Algorithms
• Transductive Algorithms

Inductive algorithms are the ones most people are familiar with. They focus on building a model that generates predictions for data points never seen during training. These algorithms optimize an objective function with components for both labeled and unlabeled data.

Transductive algorithms, by contrast, do not build a reusable model. Instead, they produce predictions directly, with all optimizations applied to the predictions themselves rather than to a prediction model. These methods try to propagate information through connections encoded directly in the data, making them primarily graph-based [1].

Rather than the typical training and testing phases, transductive algorithms operate in three phases:

• Graph building — similar data points (nodes) are connected based on pairwise similarity, forming a graph
• Graph weighting — weights are assigned to edges (links) based on the strength of pairwise similarity between nodes
• Inference — the graph is used to assign labels to unlabeled nodes

Conclusion

Using Semi-Supervised Learning involves a significant trade-off: unlabeled data can be incorporated to improve a model, but only if it satisfies certain assumptions, and there is no guarantee it will actually improve performance. These assumptions can be difficult to prove, and there is no established methodology for testing whether a semi-supervised approach will outperform a supervised baseline without actually building and evaluating the model. Despite these challenges, Semi-Supervised Learning remains a valuable tool when labeled data is scarce or expensive, and understanding its underlying assumptions is the essential first step toward applying it effectively.