Negative Sampling in Semi-Supervised learning

John Chen, Vatsal Shah, Anastasios Kyrillidis

Overview

Researchers have introduced Negative Sampling in Semi-Supervised Learning (NS³L), a lightweight "plug-and-play" loss term that significantly boosts the performance of existing semi-supervised algorithms. By teaching models to identify what an unlabeled image is not rather than guessing what it is, NS³L achieves state-of-the-art results on standard benchmarks like CIFAR and SVHN with minimal computational overhead.

The Challenge of Semi-Supervised Learning

Semi-supervised learning (SSL) is the art of training models using a tiny sliver of labeled data and a mountain of unlabeled data. While deep learning has mastered supervised tasks, labeling millions of images is prohibitively expensive and time-consuming.

Most current SSL methods rely on "consistency regularization" (small changes to an image shouldn't change the prediction) or "pseudo-labeling" (guessing the label of an unlabeled image and treating it as truth). However, these methods can be brittle. If the model makes a confident but wrong guess, it reinforces its own error. The authors identify a fundamental challenge: it is often much easier to determine which classes a sample does not belong to than to pinpoint its exact category.

The NS³L Approach

The authors propose NS³L, inspired by negative sampling and contrastive estimation (techniques famously used in Word2Vec).

The core algorithm is elegantly simple:

  1. Thresholding: For an unlabeled sample, the model generates a probability distribution across all classes.
  2. Identifying Negatives: If the predicted probability for a specific class falls below a certain threshold ($T$), the model assumes the sample definitely does not belong to that class.
  3. The Loss Term: A new loss term is added to the objective function. It penalizes the model if it starts assigning higher probabilities to these "negative" classes.
NS3L architecture integrated with VAT

Unlike standard SSL, which pushes the model toward a specific (potentially wrong) label, NS³L implicitly constrains the model by "fencing off" incorrect areas of the probability space. This makes it highly flexible; it can be added to existing heavy-hitters like Virtual Adversarial Training (VAT) or MixMatch by simply adding the NS³L term to their existing loss functions.

Evaluation Datasets

The researchers evaluated NS³L across four standard computer vision benchmarks:

  • CIFAR-10 & CIFAR-100: Small-scale natural images with 10 and 100 classes, respectively.
  • SVHN (Street View House Numbers): Images of digits cropped from house numbers.
  • STL-10: A dataset specifically designed for SSL, featuring 5,000 labeled images and 100,000 unlabeled images from a slightly different distribution.

Key Insights

  • Negative Evidence is Safer: In a 10-class problem, if you guess the positive label, you have a high chance of being wrong. If you pick a class with 0.1% probability and say "it's not this," you are almost certainly right. This "implicit negative evidence" provides a more stable signal for the learner.
  • Correcting Selection Bias: Labeled data often suffers from "selection bias" (e.g., only easy-to-identify examples are labeled). Standard SSL might follow this bias, but NS³L uses the uniform distribution of unlabeled data to push the decision boundary back toward the true center.
1D toy example demonstrating how negative sampling corrects selection bias
  • Efficiency: Because NS³L only requires a forward pass to identify negative labels and a simple log-likelihood calculation, it is computationally cheap. When run alone, it is more than 2x faster than VAT.

Performance Highlights

The addition of NS³L consistently improved every baseline it was tested against:

  • CIFAR-10: Adding NS³L to VAT reduced the test error from 14.72% to 13.94%.
  • MixMatch Integration: On CIFAR-10 with only 250 labeled samples, MixMatch + NS³L achieved a test error of 12.48%, a significant improvement over vanilla MixMatch (14.49%).
  • SVHN: VAT + NS³L reached a test error of 5.51%, outperforming VAT + Entropy Minimization.
  • Generalization: The authors tuned hyperparameters on CIFAR-10 and SVHN and found they transferred to CIFAR-100 with almost no extra tuning, suggesting the method is robust across different data complexities.

Limitations and Future Directions

While NS³L is effective, it does introduce two new hyperparameters: the probability threshold ($T$) and the loss weighting coefficient ($\lambda_1$). The authors' sensitivity analysis shows that while the model is somewhat sensitive to $T$, an optimal value (around 0.04 for 10-class problems) holds empirically across different settings.

Future work could explore more complex ways of choosing negative labels, such as using Nearest Neighbor searches or more sophisticated clustering, rather than relying solely on the model's current output probabilities. Additionally, exploring how NS³L performs on datasets with a massive number of classes (where negative sampling is even more intuitive) remains an open area for research.

Summary updated

Abstract

We introduce Negative Sampling in Semi-Supervised Learning (NS^3L), a simple, fast, easy to tune algorithm for semi-supervised learning (SSL). NS^3L is motivated by the success of negative sampling...
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