A Compression Technique for Analyzing Disagreement-Based Active Learning

Yair Wiener, Steve Hanneke, Ran El-Yaniv

Abstract

We introduce a new and improved characterization of the label complexity of disagreement-based active learning, in which the leading quantity is the version space compression set size. This quantity is defined as the size of the smallest subset of the training data that induces the same version space. We show various applications of the new characterization, including a tight analysis of CAL and refined label complexity bounds for linear separators under mixtures of Gaussians and axis-aligned rectangles under product densities. The version space compression set size, as well as the new characterization of the label complexity, can be naturally extended to agnostic learning problems, for which we show new speedup results for two well known active learning algorithms.

Introduction

In the field of active learning, algorithms aim to achieve high accuracy while minimizing the number of labeled examples required. A prominent strategy is disagreement-based active learning, where an algorithm selectively requests labels for data points upon which the current set of candidate hypotheses—the version space—disagrees. While theoretically robust, existing analyses of these methods often rely on the "disagreement coefficient," which can lead to loose upper bounds on label complexity, typically overestimating the required labels by a factor proportional to the VC dimension of the hypothesis class. This paper addresses this gap by introducing a tighter complexity measure based on version space compression.

The CAL Algorithm and Disagreement-Based Learning

The CAL (Cohn, Atlas, and Ladner) algorithm is a foundational disagreement-based active learning method. It maintains a version space $V_m$ of hypotheses consistent with all labels seen so far. For each new unlabeled point $x_m$, the algorithm checks if there is any disagreement within $V_m$ regarding its label. If disagreement exists, it requests the label; otherwise, it infers the label and proceeds.

The CAL (Cohn, Atlas, and Ladner) active learning algorithm.

Methods: Version Space Compression

The core contribution of this work is the introduction of the version space compression set size. For a given labeled dataset that defines a version space, the compression set is the smallest subset of those points that yields the exact same version space. The size of this set serves as a more precise metric for the information content required to narrow down the hypothesis space.

By linking this compression set size to the traditional disagreement coefficient, the authors demonstrate that the two metrics are related within a factor of the VC dimension (up to logarithmic factors). This relationship allows for a more granular analysis of algorithm performance, particularly for the CAL algorithm, where the label complexity is shown to be fundamentally tied to the compression set size.

Key Results and Theoretical Improvements

The application of this new framework yields significantly tighter bounds for several classic learning problems:

  • Linear Separators: For learning linear classifiers under mixtures of Gaussians, the upper bound's exponent on the logarithmic factor is reduced from $\Theta(k^2)$ to $\Theta(k)$, where $k$ is the data dimension.
  • Axis-Aligned Rectangles: Under product densities, the dependence on dimension $k$ is improved from $\Theta(k^3 \log^2(k))$ to $\Theta(k \log^2(k))$. This result is shown to be minimax optimal within logarithmic factors.
  • Agnostic Learning: The framework is extended to agnostic settings (where noise is present) by defining version spaces relative to the infimal hypothesis (the model with the lowest possible error). This leads to new exponential label complexity speedups for algorithms like $A^2$ and RobustCAL under Mammen-Tsybakov noise conditions.

Conclusion

This work provides a refined mathematical lens for understanding active learning. By shifting the focus to version space compression, the authors bridge the gap between existing loose bounds and the actual performance of disagreement-based algorithms. While the analysis is primarily theoretical and assumes certain noise conditions, it sets a new standard for characterizing label complexity and opens avenues for analyzing more complex hypothesis classes in both realizable and agnostic settings.

Summary updated

Abstract

We introduce a new and improved characterization of the label complexity of disagreement-based active learning, in which the leading quantity is the version space compression set size. This quantity is defined as the size of the smallest subset of the training data that induces the same version space. We show various applications of the new characterization, including a tight analysis of CAL and refined label complexity bounds for linear separators under mixtures of Gaussians and axis-aligned rectangles under product densities. The version space compression set size, as well as the new characterization of the label complexity, can be naturally extended to agnostic learning problems, for which we show new speedup results for two well known active learning algorithms.
BibTeX
@article{wiener2015compression,
  author = {Yair Wiener and Steve Hanneke and Ran El-Yaniv},
  title = {{A Compression Technique for Analyzing Disagreement-Based Active Learning}},
  journal = {J. Mach. Learn. Res.},
  year = {2015},
  url = {https://openreview.net/forum?id=7d_EvJzfPGb},
}
Figure