Access to Unlabeled Data can Speed up Prediction Time

Ruth Urner, Shai Shalev-Shwartz, Shai Ben-DavidICML 2011 · OpenReview

While most semi-supervised learning (SSL) research focuses on using unlabeled data to improve a model's accuracy, this paper explores a different paradigm: using unlabeled data to improve prediction speed. By leveraging a complex, slow model to label a massive amount of unlabeled data, the authors demonstrate that it is possible to train a simple, fast model (like a linear classifier) that performs significantly better than if it were trained on limited labeled data alone.

The Labeled Data Bottleneck

In machine learning, there is often a strict trade-off between a model's expressiveness (accuracy) and its computational efficiency (runtime). Complex models like Nearest Neighbors or Kernel-based methods can achieve high accuracy but are computationally expensive to run during inference. Conversely, "fast" models like linear classifiers are preferred for real-time applications but often require a massive amount of labeled data to reach their full potential.

The authors address this "labeled data bottleneck." Labeled data is expensive and scarce, while unlabeled data is cheap and abundant. The core question of the paper is whether we can use that mountain of unlabeled data to "distill" the wisdom of a slow, accurate model into a fast, simple one.

Methodology: The Teacher-Student Framework

The authors propose a straightforward two-phase algorithmic framework to achieve this distillation:

  1. The Teacher Phase: Use a small set of labeled data to train a high-capacity classifier (the "approximation class"). This model doesn't have to be fast; it just needs to be accurate. Examples include Nearest Neighbor (NN) or kernel-based classifiers.
  2. The Student Phase: Use this "teacher" model to assign labels to a large pool of unlabeled data. Then, take this newly "pseudo-labeled" dataset and use it to train a model from a "target class" of fast, interpretable predictors (like linear classifiers).

To provide a theoretical backbone for why this works, the authors introduce a new quantitative measure called Probabilistic Lipschitzness. This formalizes the "cluster assumption"—the idea that points close to each other in space likely share the same label. By quantifying this assumption, they mathematically prove that unlabeled data can significantly reduce the "labeled sample complexity" (the amount of human-labeled data needed) for specific distributions.

Experimental Results

The researchers evaluated their framework using the MNIST digit recognition dataset, focusing on a binary classification task (grouping digits 0–4 vs. 5–9). They compared a standard supervised linear classifier against their SSL approach, which used either a Chamfer distance kernel classifier or a 1-Nearest Neighbor (1-NN) model as the initial "teacher" to label the unlabeled portion of the MNIST training set.

Error rates on MNIST comparing a standard linear classifier, a Chamfer kernel classifier, and the proposed SSL linear classifier.

The results demonstrated massive data savings. On the MNIST task, the "Linear with SSL" approach achieved the target performance threshold with only 3,500 labeled examples. In contrast, a standard supervised linear classifier required 20,000 labeled examples to reach that exact same error rate.

The SSL-trained linear classifier significantly outperformed the purely supervised linear classifier across all sample sizes, effectively "inheriting" some of the superior decision-making capabilities of the slower Chamfer-kernel model.

Discussion and Limitations

This paper effectively reframes the goal of SSL: instead of trying to beat the best possible accuracy, the goal can be to reach a target accuracy level using a model that is orders of magnitude faster at runtime. This concept closely mirrors what is now widely known as "knowledge distillation" in deep learning, applying a similar logic to classical learning theory.

However, the approach has limitations:

  • Dependence on the Teacher: The success of the second stage is entirely dependent on the accuracy of the first stage. If the complex model has high error, it will provide "noisy" labels to the fast model, potentially leading to poor performance.
  • The Cluster Assumption Requirement: The benefits of this method are most pronounced when the data follows the cluster assumption (quantified by their Lipschitzness measure). If the data is highly interleaved or lacks clear geometric structure, the gains from unlabeled data may diminish.

Ultimately, this work proves that when a sufficiently large unlabeled sample is available, a fast classifier can be learned from much fewer labeled examples than without such a sample, paving the way for more efficient real-time machine learning systems.

Summary updated

Abstract

Semi-supervised learning (SSL) addresses the problem of training a classifier using a small number of labeled examples and many un-labeled examples. Most previous work on SSL focused on how availability of unlabeled data can improve the accuracy of the learned classifiers. In this work we study how un-labeled data can be beneficial for constructing faster classifiers. We propose an SSL algorithmic framework which can utilize unlabeled examples for learning classifiers from a predefined set of fast classifiers. We formally analyze conditions under which our algorithmic paradigm obtains significant improvements by the use of unlabeled data. As a side benefit of our analysis we propose a novel quantitative measure of the so-called cluster assumption. We demonstrate the potential merits of our approach by conducting experiments on the MNIST data set, showing that, when a sufficiently large unlabeled sample is available, a fast classifier can be learned from much fewer labeled examples than without such a sample.
BibTeX
@inproceedings{urner2011access,
  author = {Ruth Urner and Shai Shalev-Shwartz and Shai Ben-David},
  title = {{Access to Unlabeled Data can Speed up Prediction Time}},
  booktitle = {International Conference on Machine Learning},
  year = {2011},
  url = {https://openreview.net/forum?id=Hy4Gk3bOWH},
}
Figure