Pruning the Unlabeled Data to Improve Semi-Supervised Learning

In recent years, extensive research has centered around the domain of deep semi-supervised learning (SSL), showcasing remarkable effectiveness across various domains. This success largely arises from the abundance of unlabeled data, in contrast with labeled data whose collection usually demands costly human annotation. Accordingly, most of the previous works focused on the creation and improvement of optimization algorithms that can utilize both labeled and unlabeled data. Differently, we focus on improving SSL performance by manipulating the unlabeled data directly.

Traditionally, SSL paradigms assume that both labeled and unlabeled data stem from the same underlying distribution. This is a reasonable assumption – when there is a significant disparity between the unlabeled and labeled data, the learning model may learn the wrong dependencies across these datasets. Consequently, this misalignment can lead to errors in generalization, ultimately mitigating the advantages that could otherwise be gained from incorporating unlabeled data.

Our investigation indicates that reliance on this assumption may not be optimal in the context of SSL. In particular, we demonstrate that modifying the distribution of unlabeled examples to enhance their distinctiveness boosts the performances of numerous deep SSL algorithms. With this objective, we present PruneSSL, a systematic approach designed to identify and prune unlabeled instances that undermine separability within the unlabeled dataset, thereby boosting overall performance.

More specifically, instances are considered to undermine the separability of the dataset if, given some meaningful embedding of the dataset and its corresponding labeling function, simple classifiers fail to accurately classify these instances when trained on the complete dataset. Clearly, executing this process directly on the unlabeled dataset is unfeasible due to the absence of labels. Consequently, the challenge lies in devising a technique capable of identifying these instances without relying on a labeling function.

Our proposed method, called PruneSSL, starts by employing a deep representation task over the unlabeled data, resulting in a meaningful embedding space. Subsequently, it calculates pseudo-labels for the unlabeled data using a deep-clustering algorithm or k-means within the embedding space. Equipped with both the embedding space and the pseudo labels, PruneSSL trains a simple classifier on the data and prunes instances that elicit the lowest levels of confidence from the classifier.

To illustrate this concept, we present a step-by-step visualization of each stage of PruneSSL in Fig. 1, utilizing a binary subset extracted from CIFAR-10. The figure shows a comparison between random instance pruning from the unlabeled dataset and the PruneSSL approach. For visualization purposes, the data is projected into a 2-dimensional space using t-SNE. Note that this projection serves exclusively for visualization purposes, as all computations occur within the original embedding space. Evidently, even in the projected space, the resulting data exhibits increased separation, as the 2 clusters in this case are more distinct. The exact details of this experiment are described in Section 3.

The inherent modularity of PruneSSL presents clear advantages as well as potential drawbacks. On the positive side, this modularity facilitates seamless integration of upcoming developments in both self-representation and pseudo-labeling tasks. Moreover, the framework readily adapts to diverse domain-specific challenges by tailoring the representation task accordingly. However, a notable drawback of PruneSSL lies in its reliance on the effectiveness of both the self-representation task and the pseudo-labeling process.

In Section 3 we present the outcome of our empirical investigation, demonstrating the effectiveness of PruneSSL. Despite its reduction of the unlabeled dataset’s size, we find that a diverse array of SSL algorithms gain significant performance boosts when trained with the pruned unlabeled set, compared to training with the entire unlabeled dataset. Notably, these advantages are even more pronounced when replacing the pseudo-labeling process with an oracle possessing knowledge of the actual unlabeled dataset labels. These results demonstrate the validity of the idea behind PruneSSL.

In Section 3.1, we describe the results of an ablation study, designed to assess the significance of each component within the PruneSSL algorithm, as well as the varying influence of several hyperparameters. Our findings reveal a consistent trend: PruneSSL consistently produces comparable qualitative outcomes across a diverse range of embedding spaces and pseudo-labeling techniques. Additionally, our analysis highlights an interesting discovery –- while an optimal value exists for the number of instances to be pruned, this parameter displays robustness, enabling the use of an extensive array of values with comparable effectiveness. Finally, we report that the benefits of PruneSSL increase as the size of the labeled set decreases.

Our approach bears a close connection to the fundamental cluster assumption of SSL (Chapelle et al., 2006). This assumption states that in order for any semi-supervised learning framework to work, even outside the realm of deep learning, the algorithm must assume that the data have inherent cluster structure, and thus, instances falling into the same cluster have the same class label. A direct result of this assumption is that the decision boundary of SSL algorithms should avoid intersecting high-density regions of the data. Instead, it should reside within low-density regions, thereby preserving the data’s cluster structure. By enhancing the separability of unlabeled data, our method guides various SSL algorithms away from solutions that might traverse high-density regions. This ultimately enhances the performance of deep SSL techniques in a broader context.

We consider a $K$-class classification scenario within a semi-supervised learning (SSL) framework. Here, $\mathcal{X}$ is the set of all possible examples, and $\mathcal{Y}$ is their corresponding labels. A semi-supervised learner denoted as $f:\mathcal{X}\rightarrow\mathcal{Y}$ is trained using a set of labeled examples $\mathcal{L}\subseteq\mathcal{X}\times\mathcal{Y}$ and unlabeled set of examples $\mathcal{U}\subseteq\mathcal{X}$. As labeled examples are often more expensive to obtain than unlabeled examples, traditionally the labeled pool $\mathcal{L}$ is significantly smaller than the unlabeled pool $\mathcal{U}$. The empirical generalization error of $f$ is its performance on a labeled test set distinct from both $\mathcal{L}$ and $\mathcal{U}$.

In many SSL scenarios, the labeled pool, unlabeled pool, and the test set all originate from the same underlying data distribution. In our experimental setup, we alter the distribution from which $\mathcal{U}$ is sampled. We observe that drawing $\mathcal{U}$ from the same distribution as $\mathcal{L}$ may not be ideal for learning. Specifically, our findings indicate that increasing the separability of $\mathcal{U}$, achieved by pruning hard examples from it, significantly improves the learning of $f$.

Let $\mathcal{U}^{\prime}\subseteq\mathcal{U}$ denote a subset of the unlabeled pool $\mathcal{U}$, obtained by applying some pruning method. In our experimental setup, we explore three distinct unsupervised pool types: (i) $\mathcal{U}^{\prime}_{rand}$ is obtained by uniformly and randomly removing examples from $\mathcal{U}$ while preserving its original distribution. (ii) $\mathcal{U}^{\prime}_{prune}$ is obtained by removing points as suggested by PruneSSL, without relying on any labels of $\mathcal{U}$ to guide it. (iii) $\mathcal{U}^{\prime}_{oracle}$ is similar to $\mathcal{U}^{\prime}_{prune}$, but here the removal of points by PruneSSL is guided by the true labels of $\mathcal{U}$, rather than its using an inferred pseudo-labeling function.

When constructing $\mathcal{U}^{\prime}_{oracle}$ and $\mathcal{U}^{\prime}_{prune}$, our objective is to generate distributions that exhibit enhanced separability as compared to the original unlabeled pool $\mathcal{U}$. To achieve this, we outline a 4-step general protocol for the creation of these unlabeled datasets:

1. 1.

   Conduct a deep-representation task on $\mathcal{U}$, resulting in an embedding space in which the problem is more linearly separated than in the original pixel space.

2. 2.

   Obtain labels for the unsupervised pool $\mathcal{U}$, using the real labels for $\mathcal{U}^{\prime}_{oracle}$ and pseudo-labels for $\mathcal{U}^{\prime}_{prune}$.

3. 3.

   Train a simple classifier using the representation from step (1) and the labels obtained in step (2).

4. 4.

   Use the classifier’s confidence to determine which examples are hardest to classify, and prune them from the unlabeled pool.

For a detailed algorithmic representation, please refer to Alg. 1. Additionally, an illustrative visualization of this process can be found in Fig. 1.

In our work, we explored various alternatives for each step outlined above, yielding consistent qualitative outcomes, as elaborated in the subsequent section. Concerning embedding methods, we employed self-representation tasks like SimCLR (Chen et al., 2020) and transfer learning based on the Inception network (Szegedy et al., 2015) trained on ImageNet (Deng et al., 2009). In terms of the simple classifier, we evaluated choices including a linear SVM, SVM with an RBF kernel, or a small fully connected deep network. The SVM’s confidence score was calculated based on the examples’ distance from the separating hyperplane, while for the neural network, confidence was determined by the logit corresponding to the example’s label. These diverse approaches consistently produced the same qualitative results, as shown in the following section.

In this paper, we propose a way to improve the unlabeled dataset used in SSL algorithms by making it more separable. Our practical approach called PruneSSL, focuses on pruning examples that hinder the separability of the unlabeled data, thus highlighting the inherent cluster structure of the data. The paper presents a comprehensive empirical investigation, demonstrating that this pruning technique notably enhances the performance of various competitive SSL algorithms across a diverse range of image classification tasks.

The structure of PruneSSL involves a sequence of steps: a self-representation task followed by pseudo-labeling, and finally, a simple classifier. Through an in-depth analysis presented in the paper, we observe that each of these individual components are adaptable to a different method, suggesting that PruneSSL could accommodate future improvements in each respective field. Testing the limits of its effectiveness, we find that PruneSSL yields better results when the labeled dataset is smaller and the data itself is more challenging.

This work was supported by grants from the Israeli Council of Higher Education and the Gatsby Charitable Foundations.