From on-line to batch learning
Conference on Learning TheoryPublished 1 December 1989
Nick Littlestone
Citations123
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.
Abstract
We contrast on-line and batch settings for concept learning, and describe an on-line learning model in which no probabilistic assumptions are made. We briefly mention some of our recent results pertaining to on-line learning algorithms developed using this model. We then turn to the main topic, which is an analysis of a conversion to improve the performance of on-line learning algorithms in a batch setting. For the batch setting we use the PAC-learning model. The conversion is straightforward, consisting of running the given on-line algorithm, collecting the hypotheses it uses for making predictions, and then choosing the hypothesis among them that does the best in a subsequent hypothesis testing phase. We have developed an analysis, using a version of Chernoff bounds applied to supermartingales, that shows that for some target classes the converted algorithm will be asymptotically optimal.
Keywords
Computer Science
Springer series in statisticsProbability Inequalities for sums of Bounded Random Variables
6,947 Citations1994Wassily Hoeffding
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.
The Annals of Mathematical StatisticsA Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
3,567 Citations1952Herman Chernoff
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.
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.
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.
Machine LearningLearning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm
1,376 Citations1988Nick Littlestone
This work presents one such algorithm that learns disjunctive Boolean functions, along with variants for learning other classes of Boolean functions.
Information Processing LettersOccam's Razor
1,077 Citations1987Anselm Blumer, Andrzej Ehrenfeucht +2 more
It is shown that a polynomial learning algorithm, as defined by Valiant (1984), is obtained whenever there exists aPolynomial-time method of producing, for any sequence of observations, a nearly minimum hypothesis that is consistent with these observations.
Journal of the ACMComputational limitations on learning from examples
532 Citations1988Leonard Pitt, Leslie G. Valiant
It is shown for various classes of concept representations that these cannot be learned feasibly in a distribution-free sense unless R = NP, and relationships between learning of heuristics and finding approximate solutions to NP-hard optimization problems are given.
The weighted majority algorithm
307 Citations1989N. Littlestone, Manfred K. Warmuth
A simple and effective method, based on weighted voting, is introduced for constructing a compound algorithm in a situation in which a learner faces a sequence of trials, and the goal of the learner is to make few mistakes.
Mistake bounds and logarithmic linear-threshold learning algorithms
184 Citations1990N. Littlestone
An analysis that shows that a straightforward transformation applied to mistake bounded algorithms, consisting of adding a hypothesis testing phase, produces algorithms that have asymptotically optimal PAC-learning bounds for certain target classes.
IEEE Transactions on Pattern Analysis and Machine IntelligenceAutomatic pattern recognition: a study of the probability of error
144 Citations1988Luc Devroye
The Vapnik-Chervonenkis method can be used to choose the smoothing parameter in kernel-based rules, to choose k in the k-nearest neighbor rule, and to choose between parametric and nonparametric rules.
Elsevier eBooksRecent Results on Boolean Concept Learning
130 Citations1987Michael Kearns, Ming Li +2 more
A recently introduced model of concept learning that pays particular attention to computational feasibility is described and the various directions in which the model can be extended are discussed.
Predicting (0, 1)-functions on randomly drawn points
89 Citations1988David Haussler, N. Littlestone +1 more
The authors consider the problem of predicting (0, 1)-valued functions on R/sup n/ and smaller domains, based on their values on randomly drawn points, and construct prediction strategies that are optimal to within a constant factor for any reasonable class F of target functions.