A compression technique for analyzing disagreement-based active learning

By Yair Wiener, Steve Hanneke, Ran El-Yaniv. 2014

21 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Deep Active Learning with a Neural Architecture Search (2018, background): “Theoretically, active learning has a huge potential, especially in cases where exponential speedup in sample complexity can be achieved [10, 25, 9].”
The Relationship Between Agnostic Selective Classification Active Learning and the Disagreement Coefficient (2017, background): “For example, it was shown in [12], that for linear separators under mixture of Gaussians, and for axis-aligned rectangles under product densities over Rk, θ(r) is bounded by O(polylog(1/r)) for all r > 0.”