A General Agnostic Active Learning Algorithm.

Published 3 December 2007

Sanjoy Dasgupta, Claire Monteleoni, Daniel Hsu

Citations210

TL;DR

This work presents an agnostic active learning algorithm for any hypothesis class of bounded VC dimension under arbitrary data distributions, using reductions to supervised learning that harness generalization bounds in a simple but subtle manner and provides a fall-back guarantee that bounds the algorithm's label complexity by the agnostic PAC sample complexity.

Abstract

We present a simple, agnostic active learning algorithm that works\nfor any hypothesis class of bounded VC dimension, and any data distribution.\nOur algorithm extends a scheme of Cohn, Atlas, and Ladner to the agnostic\nsetting, by (1) reformulating it using a reduction to supervised learning and\n(2) showing how to apply generalization bounds even for the non-i.i.d. samples\nthat result from selective sampling. We provide a general characterization of\nthe label complexity of our algorithm. This quantity is never more than the\nusual PAC sample complexity of supervised learning, and is exponentially\nsmaller for some hypothesis classes and distributions. We also demonstrate\nimprovements experimentally.Pre-2018 CSE ID: CS2007-0898

Keywords

Computer Science

On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities

3,175 Citations2015Vladimir Vapnik, Alexey Chervonenkis

This chapter reproduces the English translation by B. Seckler of the paper by Vapnik and Chervonenkis in which they gave proofs for the innovative results they had obtained in a draft form in July 1966 and announced in 1968 in their note in Soviet Mathematics Doklady.

Machine LearningImproving Generalization with Active Learning

1,311 Citations1994David Cohn, Les Atlas +1 more

A formalism for active concept learning called selective sampling is described and it is shown how it may be approximately implemented by a neural network.

View PDF

Machine LearningSelective Sampling Using the Query by Committee Algorithm

1,118 Citations1997Yoav Freund, H. Sebastian Seung +2 more

It is shown that if the two-member committee algorithm achieves information gain with positive lower bound, then the prediction error decreases exponentially with the number of queries, and this exponential decrease holds for query learning of perceptrons.

View PDF

Lecture notes in computer scienceIntroduction to Statistical Learning Theory

490 Citations2004Olivier Bousquet, Stéphane Boucheron +1 more

This tutorial introduces the techniques that are used to obtain results in the form of so-called error bounds in statistical learning theory.

Lecture notes in computer scienceMargin Based Active Learning

296 Citations2007Maria-Florina Balcan, Andrei Broder +1 more

The effectiveness of the framework for margin based active learning of linear separators both in the realizable case and in a specific noisy setting related to the Tsybakov small noise condition is analyzed.

Agnostic active learning

282 Citations2006Maria-Florina Balcan, Alina Beygelzimer +1 more

The first active learning algorithm which works in the presence of arbitrary forms of noise is state and analyzed, and it is shown that A2 achieves an exponential improvement over the usual sample complexity of supervised learning.

Coarse sample complexity bounds for active learning

254 Citations2005Sanjoy Dasgupta

The sample complexity of active learning problems is characterized in terms of a parameter which takes into account the distribution over the input space, the specific target hypothesis, and the desired accuracy.

A bound on the label complexity of agnostic active learning

247 Citations2007Steve Hanneke

General bounds on the number of label requests made by the A2 algorithm proposed by Balcan, Beygelzimer & Langford are derived, which represents the first nontrivial general-purpose upper bound on label complexity in the agnostic PAC model.

Lecture notes in computer scienceAnalysis of Perceptron-Based Active Learning

224 Citations2005Sanjoy Dasgupta, Adam Tauman Kalai +1 more

A simple selective sampling algorithm is presented, which combines a modification of the perceptron update with an adaptive filtering rule for deciding which points to query and reaches generalization error e after asking for just O(d log 1/∈) labels.

Lecture notes in computer scienceActive Learning in the Non-realizable Case

101 Citations2006Matti Kääriäinen

It is shown that under the assumption that the best classifier in the learner's hypothesis class has generalization error at most β > 0, the label complexity of active learning is Ω(β 2 /∈ 2 log(1/δ)), where the accuracy parameter e measures how close to optimal within the hypothesis class the active learners has to get and δ is the confidence parameter.