Selective Sampling Using the Query by Committee Algorithm
Machine LearningPublished 1 August 1997Open access
Yoav Freund, H. Sebastian Seung, Eli Shamir, Naftali Tishby
Citations1,118
SJR quartileQ1
SJR score1.15
SNIP2.14
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
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.
Abstract
We analyze the "query by committee" algorithm, a method for filtering informative queries from a random stream of inputs. We show 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. We show that, in particular, this exponential decrease holds for query learning of perceptrons.
Keywords
Computer Science
A theory of the learnable
4,242 Citations1984Leslie G. Valiant
This paper regards learning as the phenomenon of knowledge acquisition in the absence of explicit programming, and gives a precise methodology for studying this phenomenon from a computational viewpoint.
Communications of the ACMA theory of the learnable
3,268 Citations1984Leslie G. Valiant
This paper regards learning as the phenomenon of knowledge acquisition in the absence of explicit programming, and gives a precise methodology for studying this phenomenon from a computational viewpoint.
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.
Query by committee
1,657 Citations1992H. Sebastian Seung, Manfred Opper +1 more
It is suggested that asymptotically finite information gain may be an important characteristic of good query algorithms, in which a committee of students is trained on the same data set.
Machine LearningQueries and Concept Learning
1,622 Citations1988Dana Angluin
This work considers the problem of using queries to learn an unknown concept, and several types of queries are described and studied: membership, equivalence, subset, superset, disjointness, and exhaustiveness queries.
The Annals of Mathematical StatisticsOn a Measure of the Information Provided by an Experiment
1,516 Citations1956D. V. Lindley
TechnometricsOptimum Experimental Designs
1,465 Citations1993Robert E. Wheeler, Anthony C. Atkinson +1 more
This book discusses experiments with both qualitative and quantitative factors, and the choice of a model and criteria for a good experiment, as well as the analysis of experiments.
Cambridge University Press eBooksOn the method of bounded differences
1,428 Citations1989Colin McDiarmid
Journal of Combinatorial Theory Series AOn the density of families of sets
866 Citations1972N. Sauer
This paper will answer the question in the affirmative by determining the exact upper bound of T if T is a family of subsets of some infinite set S then either there exists to each number n a set A ⊂ S with |A| = n such that |T ∩ A| = 2n or there exists some number N such that •A| c for each A⩾ N and some constant c.
Machine LearningQueries and concept learning
817 Citations1988Dana Angluin
This work considers the problem of using queries to learn an unknown concept, and several types of queries are described and studied: membership, equivalence, subset, superset, disjointness, and exhaustiveness queries.
Elsevier eBooksCommittee-Based Sampling For Training Probabilistic Classifiers
497 Citations1995Ido Dagan, Sean P. Engelson
A general method for efficiently training probabilistic classifiers, by selecting for training only the more informative examples in a stream of unlabeled examples, which is particularly attractive because it evaluates the expected information gain from a training example implicitly.
Neural Information Processing SystemsTraining Connectionist Networks with Queries and Selective Sampling
223 Citations1989Les Atlas, David Cohn +1 more
The approach is justified by its applicability to the problem of training a network for power system security analysis and the benefits are studied analytically, and the results are confirmed experimentally.
IEEE Transactions on Neural NetworksNeural net algorithms that learn in polynomial time from examples and queries
169 Citations1991Eric B. Baum
The author's algorithm is proved to PAC learn in polynomial time the class of target functions defined by layered, depth two, threshold nets having n inputs connected to k hidden threshold units connected to one or more output units, provided k=/<4.
Europhysics Letters (EPL)Improving a Network Generalization Ability by Selecting Examples
114 Citations1990Wolfgang Kinzel, P. Ruján
It is shown that the generalization ability of simple Perceptron-like devices is strongly enhanced by allowing the network itself to select the training examples.
Machine LearningBounds on the sample complexity of Bayesian learning using information theory and the VC dimension
55 Citations1994David Haussler, Michael Kearns +1 more
A systematic investigation and comparison of two fundamental quantities in learning and information theory: the probability of an incorrect prediction for an optimal learning algorithm, and the Shannon information gain is undertaken.
On the sample complexity of pac-learning using random and chosen examples
41 Citations1990Bonnie Eisenberg, Ronald L. Rivest