Coarse sample complexity bounds for active learning
Published 5 December 2005
Sanjoy Dasgupta
Citations254
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
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.
Abstract
We characterize the sample complexity of active learning problems in terms of a parameter which takes into account the distribution over the input space, the specific target hypothesis, and the desired accuracy.
Keywords
Computer Science
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.
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.
Information and ComputationDecision theoretic generalizations of the PAC model for neural net and other learning applications
871 Citations1992David Haussler
Theorems on the uniform convergence of empirical loss estimates to true expected loss rates for certain hypothesis spaces H are given, and it is shown how this implies learnability with bounded sample size, disregarding computational complexity.
IEEE Transactions on Information TheoryStructural risk minimization over data-dependent hierarchies
527 Citations1998John Shawe‐Taylor, Peter L. Bartlett +2 more
A result is presented that allows one to trade off errors on the training sample against improved generalization performance, and a more general result in terms of "luckiness" functions, which provides a quite general way for exploiting serendipitous simplicity in observed data to obtain better prediction accuracy from small training sets.
Journal of Computer and System SciencesOn the Complexity of Teaching
277 Citations1995Sally A. Goldman, Michael Kearns
This paper studies the complexity of teaching by considering a variant of the on-line learning model in which a helpful teacher selects the instances, and measures the teaching dimension by a combinatorial measure.
Analysis of a greedy active learning strategy
266 Citations2004Sanjoy Dasgupta
The core search problem of active learning schemes is abstract out, and it is proved that a popular greedy active learning rule is approximately as good as any other strategy for minimizing this number of labels.
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 scienceA PAC-Style Model for Learning from Labeled and Unlabeled Data
106 Citations2005Maria-Florina Balcan, Avrim Blum
This paper describes a PAC-style framework that can be used to model many of these assumptions, and analyzes sample-complexity issues in this setting: that is, how much of each type of data one should expect to need in order to learn well, and what are the basic quantities that these numbers depend on.