Negative sampling in semi-supervised learning

John Chen, Vatsal Shah, Anastasios Kyrillidis

Abstract

We introduce Negative Sampling in Semi-Supervised Learning (NS3L), a simple, fast, easy to tune algorithm for semi-supervised learning (SSL). NS3L is motivated by the success of negative sampling/contrastive estimation. We demonstrate that adding the NS3L loss to state-of-the-art SSL algorithms, such as the Virtual Adversarial Training (VAT), significantly improves upon vanilla VAT and its variant, VAT with Entropy Minimization. By adding the NS3L loss to MixMatch, the current state-of-the-art approach on semi-supervised tasks, we observe significant improvements over vanilla MixMatch. We conduct extensive experiments on the CIFAR10, CIFAR100, SVHN and STL10 benchmark datasets.

Introduction

Semi-supervised learning (SSL) aims to leverage large amounts of unlabeled data alongside a small set of labeled examples. While deep learning has achieved remarkable success in supervised tasks, the cost of labeling massive datasets remains a significant bottleneck. Most existing SSL methods focus on "positive evidence"—either by generating pseudo-labels for unlabeled data or using consistency regularization to ensure model stability under perturbations. However, these approaches can be computationally intensive and sensitive to hyperparameters.

This paper explores the utility of "negative evidence." In multi-class classification, it is often easier to determine what an object is not than what it is. By formalizing this intuition, the authors propose Negative Sampling in Semi-Supervised Learning (NS3L), a plug-and-play loss term designed to complement existing SSL frameworks.

Methodology: The NS3L Framework

NS3L is inspired by negative sampling techniques used in natural language processing, such as word2vec. The core mechanism involves three steps:

  1. Thresholding: For any unlabeled image, the model produces a probability distribution across all possible classes.
  2. Identifying Negatives: Classes with a predicted probability below a predefined threshold $T$ are identified as negative labels.
  3. Loss Formulation: A new loss term is introduced to penalize the model if it assigns high probability to these negative classes. Specifically, it encourages the sum of probabilities for unlikely classes ($\\sum_i \\mu_i$) to remain near zero, effectively minimizing $1 - \\sum_i \\mu_i$.
Integration of NS3L with VAT and MixMatch frameworks.

A key advantage of NS3L is its simplicity. It does not require complex adversarial perturbations or multiple forward passes, making it significantly faster than methods like Virtual Adversarial Training (VAT). It can be easily integrated into existing pipelines like MixMatch or VAT by simply adding the NS3L term to the total loss.

Theoretical Motivation: Correcting Selection Bias

One of the primary challenges in SSL with very few labels is selection bias. Small labeled sets may not be representative of the true data distribution (e.g., containing only "easy" examples). The authors demonstrate that incorporating negative samples from the broader unlabeled distribution can shift the model's decision boundary ($\hat{w}_S$) closer to the optimal boundary ($w^*$).

Illustration of how negative sampling corrects selection bias in small labeled datasets.

As shown in the figure above, while few supervised samples lead to a biased threshold (b), allowing unsupervised data into the mix and considering negative samples based on a threshold (c) helps shift the threshold closer to the ideal state (d).

Experimental Results

The researchers evaluated NS3L on standard benchmarks including CIFAR-10, CIFAR-100, SVHN, and STL-10.

  • MixMatch Integration: On CIFAR-10 with 250 labels, adding NS3L reduced the test error from 14.49% to 12.48%.
  • VAT Integration: On the SVHN dataset, VAT combined with NS3L achieved a test error of 5.51%, outperforming both vanilla VAT (6.20%) and VAT with Entropy Minimization (6.10%).
  • Efficiency: NS3L alone is more than twice as fast as VAT, providing a computationally efficient way to enhance model performance.

Conclusion

NS3L provides a simple yet effective way to incorporate negative evidence into semi-supervised learning. While the method shows robustness across datasets, future work could explore its scalability to datasets with thousands of classes and further refine the selection strategies for negative labels. Currently, a simple thresholding approach ($T \approx 0.04$ for 10-class problems) remains the most effective and efficient strategy.

Summary updated

Abstract

We introduce Negative Sampling in Semi-Supervised Learning (NS3L), a simple, fast, easy to tune algorithm for semi-supervised learning (SSL). NS3L is motivated by the success of negative sampling/contrastive estimation. We demonstrate that adding the NS3L loss to state-of-the-art SSL algorithms, such as the Virtual Adversarial Training (VAT), significantly improves upon vanilla VAT and its variant, VAT with Entropy Minimization. By adding the NS3L loss to MixMatch, the current state-of-the-art approach on semi-supervised tasks, we observe significant improvements over vanilla MixMatch. We conduct extensive experiments on the CIFAR10, CIFAR100, SVHN and STL10 benchmark datasets.
BibTeX
@inproceedings{chen2020negative,
  author = {John Chen and Vatsal Shah and Anastasios Kyrillidis},
  title = {{Negative sampling in semi-supervised learning}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=1-3quI7X-Vm},
}
Figure