A bound on the label complexity of agnostic active learning
Published 20 June 2007
Steve Hanneke
Citations247
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
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.
Abstract
We study the label complexity of pool-based active learning in the agnostic PAC model. Specifically, we derive general bounds on the number of label requests made by the A2 algorithm proposed by Balcan, Beygelzimer & Langford (Balcan et al., 2006). This represents the first nontrivial general-purpose upper bound on label complexity in the agnostic PAC model.
Keywords
Computer Science
TechnometricsStatistical Learning Theory
26,913 Citations1999Yuhai Wu, Vladimir Vapnik
Presenting a method for determining the necessary and sufficient conditions for consistency of learning process, the author covers function estimates from small data pools, applying these estimations to real-life problems, and much more.
Journal of the ACMLearnability and the Vapnik-Chervonenkis dimension
1,852 Citations1989Anselm Blumer, Andrzej Ehrenfeucht +2 more
This paper shows that the essential condition for distribution-free learnability is finiteness of the Vapnik-Chervonenkis dimension, a simple combinatorial parameter of the class of concepts to be learned.
Neural network learning theoretical foundations
1,357 Citations2009Martin Anthony, Peter L. Bartlett
The authors explain the role of scale-sensitive versions of the Vapnik Chervonenkis dimension in large margin classification, and in real prediction, and discuss the computational complexity of neural network learning.
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.
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.
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.
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.
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.
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.
Journal of the ACMHow many queries are needed to learn?
96 Citations1996Lisa Hellerstein, Krishnan Pillaipakkamnatt +2 more
It is shown that an honest class is exactly polynomial-query learnable if and only if it is learnable using an oracle for Γp4, and a new relationship between query complexity and time complexity in exact learning is shown.
Machine LearningLearning Nested Differences of Intersection-Closed Concept Classes
69 Citations1990David P. Helmbold, Robert H. Sloan +1 more
A new framework for constructing learning algorithms which involve master algorithms which use learning algorithms for intersection-closed concept classes as subroutines and show that these algorithms are optimal or nearly optimal with respect to several different criteria.
Machine LearningActive Learning Using Arbitrary Binary Valued Queries
61 Citations1993Sanjeev R. Kulkarni, Sanjoy K. Mitter +1 more
A form of distribution-free learning in which the learner knows the distribution being used, so that “distribution-free” refers only to the requirement that the number of queries can be obtained uniformly over all distributions.
IEEE Transactions on Neural NetworksOn the sample complexity of PAC learning half-spaces against the uniform distribution
32 Citations1995Philip M. Long
An Omega(d/epsilon+1/ep silonlog1/delta) lower bound on the PAC (probably approximately correct) learning sample complexity of learning half-spaces against the uniform distribution on the unit ball in R(d).
Theoretical Computer ScienceThe consistency dimension and distribution-dependent learning from queries
20 Citations2002José L. Balcázar, Jorge Castro +2 more
A new combinatorial characterization of polynomial learnability from equivalence queries is proved and two models of query learning in which there is a probability distribution on the instance space are proposed.
On Metric Entropy, Vapnik-Chervonenkis Dimension, and Learnability for a Class of Distributions
20 Citations1989Sanjeev R. Kulkarni
It is pointed out that the condition for learnability obtained in [4] is equivalent to the notion of finite metric entropy (which has been studied in other contexts) and some relationships, in addition to those shown in], between the VC dimension of a concept class and its metric entropy with respect to various distributions are discussed.
Journal of Computer and System SciencesA New Abstract Combinatorial Dimension for Exact Learning via Queries
18 Citations2002José L. Balcázar, Jorge Castro +1 more
An abstract model of exact learning via queries that can be instantiated to all the query learning models currently in use, while being closer to them than previous unifying attempts is introduced.
Lecture notes in computer scienceThe Optimal PAC Algorithm
9 Citations2004Manfred K. Warmuth
After drawing this many examples (consistent with any concept in C), then with probability at least 1–δ, the error of the produced concept is at most e, and the accuracy is measured with respect to the same distribution.
Lecture notes in computer scienceA New PAC Bound for Intersection-Closed Concept Classes
8 Citations2004Peter Auer, Ronald Ortner
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)Center for Intelligent Control Systems
6 Citations1992Sanjoy K. Mitter
This report contains results of research on perceptual systems, multiscale signal and image analysis, intelligent control, learning control of linear and nonlinear systems, computation, communication and distributed computation.