Why does using pseudo-labeling non-trivially affect the results?

Question

I've been looking into semi-supervised learning methods, and have come across the concept of "pseudo-labeling".

As I understand it, with pseudo-labeling you have a set of labeled data as well as a set of unlabeled data. You first train a model on only the labeled data. You then use that initial data to classify (attach provisional labels to) the unlabeled data. You then feed both the labeled and unlabeled data back into your model training, (re-)fitting to both the known labels and the predicted labels. (Iterate this process, re-labeling with the updated model.)

The claimed benefits are that you can use the information about the structure of the unlabeled data to improve the model. A variation of the following figure is often shown, "demonstrating" that the process can make a more complex decision boundary based on where the (unlabeled) data lies.

Image from Wikimedia Commons by Techerin CC BY-SA 3.0

However, I'm not quite buying that simplistic explanation. Naively, if the original labeled-only training result was the upper decision boundary, the pseudo-labels would be assigned based on that decision boundary. Which is to say that the left hand of the upper curve would be pseudo-labeled white and the right hand of the lower curve would be pseudo-labeled black. You wouldn't get the nice curving decision boundary after retraining, as the new pseudo-labels would simply reinforce the current decision boundary.

Or to put it another way, the current labeled-only decision boundary would have perfect prediction accuracy for the unlabeled data (as that's what we used to make them). There's no driving force (no gradient) which would cause us to change the location of that decision boundary simply by adding in the pseudo-labeled data.

Am I correct in thinking that the explanation embodied by the diagram is lacking? Or is there something I'm missing? If not, what is the benefit of pseudo-labels, given the pre-retraining decision boundary has perfect accuracy over the pseudo-labels?

Answer 1

Pseudo-labeling doesn't work on the given toy problem

Oliver et al. (2018) evaluated different semi-supervised learning algorithms. Their first figure shows how pseudo-labeling (and other methods) perform on the same toy problem as in your question (called the 'two-moons' dataset):

The plot shows the labeled and unlabeled datapoints, and the decision boundaries obtained after training a neural net using different semi-supervised learning methods. As you suspected, pseudo-labeling doesn't work well in this situation. They say that pseudo-labeling "is a simple heuristic which is widely used in practice, likely because of its simplicity and generality". But: "While intuitive, it can nevertheless produce incorrect results when the prediction function produces unhelpful targets for [the unlabeled data], as shown in fig. 1."

Why and when does pseudo-labeling work?

Pseudo-labeling was introduced by Lee (2013), so you can find more details there.

The cluster assumption

The theoretical justification Lee gave for pseudo-labeling is that it's similar to entropy regularization. Entropy regularization (Grandvalet and Bengio 2005) is another semi-supervised learning technique, which encourages the classifier to make confident predictions on unlabeled data. For example, we'd prefer an unlabeled point to be assigned a high probability of being in a particular class, rather than diffuse probabilities spread over multiple classes. The purpose is to take advantage the assumption that the data are clustered according to class (called the "cluster assumption" in semi-supervised learning). So, nearby points have the same class, and points in different classes are more widely separated, such that the true decision boundaries run through low density regions of input space.

Why pseudo-labeling might fail

Given the above, it would seem reasonable to guess that the cluster assumption is a necessary condition for pseudo-labeling to work. But, clearly it's not sufficient, as the two-moons problem above does satisfy the cluster assumption, but pseudo-labeling doesn't work. In this case, I suspect the problem is that there are very few labeled points, and the proper cluster structure can't be identified from these points. So, as Oliver et al. describe (and as you point out in your question), the resulting pseudo-labels guide the classifier toward the wrong decision boundary. Perhaps it would work given more labeled data. For example, contrast this to the MNIST case described below, where pseudo-labeling does work.

Where it works

Lee (2013) showed that pseudo-labeling can help on the MNIST dataset (with 100-3000 labeled examples). In fig. 1 of that paper, you can see that a neural net trained on 600 labeled examples (without any semi-supervised learning) can already recover cluster structure among classes. It seems that pseudo-labeling then helps refine the structure. Note that this is unlike the two-moons example, where several labeled points were not enough to learn the proper clusters.

The paper also mentions that results were unstable with only 100 labeled examples. This again supports the idea that pseudo-labeling is sensitive to the initial predictions, and that good initial predictions require a sufficient number of labeled points.

Lee also showed that unsupervised pre-training using denoising autoencoders helps further, but this appears to be a separate way of exploiting structure in the unlabeled data; unfortunately, there was no comparison to unsupervised pre-training alone (without pseudo-labeling).

Grandvalet and Bengio (2005) reported that pseudo-labeling beats supervised learning on the CIFAR-10 and SVHN datasets (with 4000 and 1000 labeled examples, respectively). As above, this is much more labeled data than the 6 labeled points in the two-moons problem.

References

• Grandvalet and Bengio (2005). Semi-supervised learning by entropy minimization.

• Lee (2013). Pseudo-Label: The Simple and Efficient Semi-Supervised Learning Method for Deep Neural Networks.

• Oliver et al. (2018). Realistic Evaluation of Semi-Supervised Learning Algorithms.

Answer 2

What you may be overlooking in how self-training works is that:

1. It's iterative, not one-shot.

2. You use a classifier that returns probabilistic values. At each iteration, you only add psuedo-labels for the cases your algorithm is most certain about.

In your example, perhaps the first iteration is only confident enough to label one or two points very near each of the labeled points. In the next iteration the boundary will rotate slightly to accommodate these four to six labeled points, and if it's non-linear may also begin to bend slightly. Repeat.

It's not guaranteed to work. It depends on your base classifier, your algorithm (how certain you have to be in order to assign a pseudo-label, etc), your data, and so on.

There are also other algorithms that are more powerful if you can use them. What I believe you're describing is self-training, which is easy to code up, but you're using a single classifier that's looking at the same information repeatedly. Co-training uses multiple classifiers that are each looking at different information for each point. (This is somewhat analogous to Random Forests.) There are also other semi-supervised techniques -- such as those that explicitly cluster -- though no overall "this always works and this is the winner".

IN RESPONSE to the comment: I'm not an expert in this field. We see it as very applicable to what we typically do with clients, so I'm learning and don't have all the answers.

The top hit when I search for semi-supervised learning overviews is: Semi-Supervised Learning Literature Survey, from 2008. That's ages ago, computer-wise, but it talks about the things I've mentioned here.

I hear you that a classifier could rate unlabeled points that are farthest from the labeled nodes with the most certainty. On the other hand, our intuitions may fool us. For example, let's consider the graphic you got from Wikipedia with the black, white, and gray nodes.

First, this is in 2D and most realistic problems will be in higher dimensions, where our intuition often misleads us. High-dimensional space acts differently in many ways -- some negative and some actually helpful.

Second, we might guess that in the first iteration the two right-most, lower-most gray points would be labeled as black, since the black labeled point is closer to them than the white labeled point. But if that happened on both sides, the vertical decision boundary would still tilt and no longer be vertical. At least in my imagination, if it were a straight line it would go down the diagonal empty space between the two originally-labeled points. It would still split the two crescents incorrectly, but it would be more aligned to the data now. Continued iteration -- particularly with a non-linear decision boundary -- might yield a better answer than we anticipate.

Third, I'm not sure that once-labeled, always-labeled is how it should actually work. Depending on how you do it and how the algorithm works, you might end up first tilting the boundary while bending it (assuming non-linear), and then some of the misclassified parts of the crescents might shift their labels.

My gut is that those three points, combined with appropriate (probably higher-dimensional) data, and appropriate classifiers can do better than a straight-up supervised with a very small number of training (labeled) samples. No guarantees, and in my experiments I've found -- I blame it on datasets that are too simple -- that semi-supervised may only marginally improve over supervised and may at times fail badly. Then again, I'm playing with two algorithms that I've created that may or may not actually be good.

Answer 3

Warning, I am not an expert on this procedure. My failure to produce good results is not proof that the technique cannot be made to work. Furthermore, your image has the general description of "semi-supervised" learning, which is a broad area with a variety of techniques.

I agree with your intuition, I'm not seeing how a technique like this could work out of the box. In other words, I think you'd need a lot of effort to make it work well for a specific application, and that effort would not necessarily be helpful in other applications.

I tried two different instances, one with a banana-shaped dataset like the one in the example image, and another easier dataset with two simple normal distributed clusters. In both cases I could not improve on the initial classifier.

As a small attempt to encourage things, I added noise to all predicted probabilities with the hope that this would cause better outcomes.

The first example I re-created the above image as faithfully as I could. I don't think psuedo-labeling will be able to help at all here.

The second example is much easier, but even here it fails to improve on the initial classifier. I specifically chose the one labeled point from the center of the left class, and the right side of the right class hoping it would shift in the correct direction, no such luck.

Code for example 1 (example 2 is similar enough that I won't duplicate here):

import numpy as np
from sklearn.ensemble import RandomForestClassifier
import matplotlib.pyplot as plt
import seaborn

np.random.seed(2018-10-1)
N = 1000

_x = np.linspace(0, np.pi, num=N)
x0 = np.array([_x, np.sin(_x)]).T
x1 = -1 * x0 + [np.pi / 2, 0]

scale = 0.15
x0 += np.random.normal(scale=scale, size=(N, 2))
x1 += np.random.normal(scale=scale, size=(N, 2))

X = np.vstack([x0, x1])

proto_0 = np.array([[0], [0]]).T # the single "labeled" 0
proto_1 = np.array([[np.pi / 2], [0]]).T # the single "labeled" 1

model = RandomForestClassifier()
model.fit(np.vstack([proto_0, proto_1]), np.array([0, 1]))
for itercount in range(100):
    labels = model.predict_proba(X)[:, 0]
    labels += (np.random.random(labels.size) - 0.5) / 10 # add some noise
    labels = labels > 0.5
    model = RandomForestClassifier()
    model.fit(X, labels)

f, axs = plt.subplots(1, 2, squeeze=True, figsize=(10, 5))

axs[0].plot(x0[:, 0], x0[:, 1], '.', alpha=0.25, label='unlabeled x0')
axs[0].plot(proto_0[:, 0], proto_0[:, 1], 'o', color='royalblue', markersize=10, label='labeled x0')
axs[0].plot(x1[:, 0], x1[:, 1], '.', alpha=0.25, label='unlabeled x1')
axs[0].plot(proto_1[:, 0], proto_1[:, 1], 'o', color='coral', markersize=10, label='labeled x1')
axs[0].legend()

axs[1].plot(X[~labels, 0], X[~labels, 1], '.', alpha=0.25, label='predicted class 0')
axs[1].plot(X[labels, 0], X[labels, 1], '.', alpha=0.25, label='predicted class 1')
axs[1].plot([np.pi / 4] * 2, [-1.5, 1.5], 'k--', label='halfway between labeled data')
axs[1].legend()
plt.show()

Answer 4

Here is my guess (I do not know much about this topic either, just wanted to add my two cents to this discussion).

I think that you're right, there's no point in training a classical model and using its predictions as data, because as you say, there's no incentive to the optimiser to do any better. I would guess that randomised-starting algorithms are more likely to find the same optimum because they'd be "more sure" that the previously found optimum is correct, due to the larger data set, but this is irrelevant.

That said, the first answer you received has a point - that example on Wikipedia talks about clustering, and I think that makes all the difference. When you've got unlabelled data, you essentially have a bunch of unlabelled points lying on some shared "latent feature space" as the other labelled ones. You can only really do better than a classification algorithm trained on the labelled data, if you can uncover the fact that the unlabelled points can be separated and then classified based on what class the labelled points belong to, on this latent feature space.

What I mean is, you need to do this:

$$labelled\;data \rightarrow clustering \rightarrow classification$$

... and then repeat with unlabelled data. Here, the learned cluster boundaries will not be the same, because clustering doesn't care for class labels, all it accounts for is transforming the feature space. The clustering generates a latent feature space, on which the classification boundary is learned, and this depends only on labelled data.

Algorithms that do not perform any sort of clustering, I believe, will not be able to change their optimum based on the unlabelled data set.

By the way, the image that you linked does a fair job I think of explaining what's going on here; a decision boundary is learned based solely on the clustering algorithm. You have no idea what the correct classes are here - it may be the case that they're all random - we don't know. All we can now is that there seems to be some structure in the feature space, and there seems to be some mapping from the feature space to the class labels.

Don't really have references but on this Reddit post, as I understand it, there's a discussion about a GAN performing semi-supervised learning. It is a hunch of mine that it implicitly performs a clustering, followed by classification.