a Machine Learning method that solves a Classification problem, i.e., when you have to determine the class or category of a specific data point, it’s likely that you’ll think about gathering a training dataset where every single 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 it comes to training a Machine Learning model, and among the other bottlenecks are compute resources and time necessary to train the model.
The classic pyramid chart, here showing some of the bottlenecks when training a machine learning model.(Image by author)
One can also argue that all of these contrains equate to money. For instance, you need money to acquire or invest in creating more data, to provision hardware for higher compute volumes and, the time you spend training and tuning your model also represents a business opportunity cost.
On top of this, there are several problem areas where it’s hard to get good quality labeled data. For example it’s hard and expensive to get data for image classification or drug discovery.
To address the fact that in real world problems labeled data can be scarse, researchers developed a family of Machine Learning algorithms that, in addition to using labeled data, can also use unlabeled data points to train a classifier.
This family of Machine Learning algorithms is called Semi-Supervised Learning.
Supervised vs Semi-Supervised Learning
A typical Supervised Learning problem is mathematically described like this
Mathematical definition the set of labeled data points (Image by author)
You have a set of labeled data points of size l and 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 the case of a classification problem.
After training the model, you can give it a never-seen-before data point x*, and the model would be able to predict its label y*.
This is great but, as mentioned before, in the real world you might not have enough labeled data to train a model with acceptable performance for your use case. So one approach is to leverage unlabeled data and thus develop a Semi-Supervised Machine Learning model, that combines:
- labeled data points, i.e., for which the true label (ground thruth) is known
- unlabelled data points, i.e., without information about its true label (ground truth)
Mathematical definition the set of data points use in Semi-Supervised Machine Learning algorithms (Image by author)
At this point you might be thinking In any situation where labeled data is scarce or expensive, I can just add unlabeled data and my model will be better?
It would be amazing if you could have your small labeled dataset and then, just by adding a ton more of unlabelled data build a model that is exponentially better than the one you built before, solely with labeled data.
We can’t just assume just by adding unlabelled data the algorithm will necessarily improve (Image by author)
Because more data is equal to a better algorithm, no?
Unfortunately, it’s not that simple.
Adding tons of unlabelled data to the algorithm’s training process is not enough to guarantee it’s going to improve predictions. It’s necessary that the unlabelled data carries information useful for label prediction, that is not yet present in the labeled data and can’t be easily extracted from it.
In fact, multiple research papers go into detail about specific scenarios where adding unlabelled data can and can not provide useful information to improve predtictions [2].
Data Assumptions for Semi-Supervised Learning
In order to be able to use unlabelled data, it’s necessary that the underlying marginal data distribution p(x) over the input space contains information about the posterior distribution p(y|x) [1]. Otherwise, it’s been proved that it’s virtually impossible to improve the prediction accuracy just by adding unlabelled data [2].
In sum, the distribution of unlabelled data needs to follow a set of assumptions, in order to effectively improve the classifier [1].
Different algorithms will follow one or more of these assumptions about the data:
- Smoothness Assumption
- Cluster Assumption
- Low-Density Assumption
- Manifold Assumption
Let’s go through each one in a little more detail.
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 is stating that if the Euclidean distance between two points is small, their label should be the same [3].
Representation of the Smoothness Assumption. (Image by author)
Cluster Assumption
We can use unlabelled data to find clusters.
This assumption is related to the Smoothness Assumption in the sense that it’s said that you can use unlabelled data to find clusters of data and, therefore, propagate labels to data points to unlabelled if they are in the same cluster as labeled data points [3].
Transitively applying labels to unlabelled data points. (Image by author)
Low-Density Assumption
The decision boundary shouldn’t pass through high density areas in the input space.
The decision boundary is the invisible line or plane that separates the data points in different classes or labels. So it makes sense that if a decision boundary would to be drawn, and in fact separate groups of data points in different classes, it would tend to be in an region of the hyperplane that doesn’t have that many points, i.e., it’s low density.
There are always a few data points that are close to the decision boundary, but in a much lower density compared to the clusters or groups of data points with the same label.
This assumption is also referred to in literature as an instance of the clustering assumption.
Manifold Assumption
We will assume that 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 the Euclidean space, the observed data points in a high-dimensional space, tend to be concentrated in low-dimension subvectors, called the manifolds.
If we can identify the manifolds and the data points that lie in each manifold, given this assumption, we can propagate labels to previously unlabelled data points, based on the known labels from the data points in that manifold.
So, in practice, this is very similar to the Smoothness Assumption, which states that similar points tend to belong to similar groups.
Inductive vs Transductive Algorithms
There are tons of different Semi-Supervised Machine Learning algorithms [1], each one based on a different set of assumptions but they primarily are divided in two major groups:
- Inductive Algorithms
- Transductive Algorithms
Inductive algorithms are the ones most people are familiar with because, they focus on creating a model that generates predictions for data points that were never seen before by the algorithm, i.e., they were not included in the training dataset. These algorithms optimize an objective function with components for both labelled and unlabelled data.
On the other hand, Transductive algorithms instead of creating a model, provide the predictions right away, with all the optimizations being done against the predictions and not the prediction model.
When using Machine Learning to solve classification problems, most people think about building a classifier and then using it to make predictions. However, Transductive algorithms don’t do that, they try to propagate information through connections encoded directly in the data. Hence, these methods are primarily graph-based [1].
And instead of the typical training and testing phases, for Transductive algorithms have three-phases:
- graph building: similar data points (nodes) are connected based on pairwise similarity, thus forming a graph
- graph weighting: attributing weights to the edges, i.e., the links, in the graph based on the strenght of the pairwise similarity between nodes
- inference: the graph is used to assign labels to unlabelled nodes
Conclusion
It seems like using Semi-Supervised Learning is almost like making a big bet, in the sense that you can add unlabelled data, but it has to follow certain assumptions and it’s not guaranteed that it will in fact improve performance.
On top of this, these assumptions can be hard to prove and there’s not a methodogy to test or detect if a semi-supervised method will improve prediction performance without actually building the model and running predictions. So, sometimes, trying to prove these hypotheses and assumptions may defeat their purpose [3].
So, is it worth it?
There are several real world problems that are so complex and for which data is so scarce, that there’s not a direct answer, a single answer or methodolgy that 100% guarantees success. That’s why researchers tend to develop a toolkit and explore many hypothesis using different techniques.
In light of that, the authors of this survey paper [2] suggest that we should see Semi-Supervised Learning as another algorithm in the researcher’s toolkit. Something to experiment with and apply to a particular use case and, along with theoretical and empirical evaluations, see if it can improve the prediction performance.
There are indeed cases where the introduction of unlabelled data and the application of Semi-Supervised Learning improved prediction performance [2, 3] but there’s not a silver bullet. Perfomance improvement will depend on the problem space, the amount of data available (both labelled and unlabelled) and the assumptions conisdered for the marginal distribution of the data.
Hope you enjoyed learning a bit more about Semi-Supervised Learning, the approaches taken with different algorithms and the limitations of using unlabelled data.
This is just scratching the surface, thanks for reading!
References
- J. E. van Engelen and H. H. Hoos, “A survey on semi-supervised learning,” Machine Learning, vol. 109, no. 2, pp. 373–440, Feb. 2020.
- X. Zhu, “Semi-Supervised Learning Literature Survey,” Computer Sciences, University of Wisconsin-Madison, Madison, WI, USA, 2008
- A. Mey and M. Loog, “Improved Generalization in Semi-Supervised Learning: A Survey of Theoretical Results,” in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 45, no. 4, pp. 4747-4767, 1 April 2023
Instagram Engineering
Shopify Engineering