Results on learnability and the Vapnik-Chervonenkis dimension
Published 1 January 1988
Nathan Linial, Yishay Mansour, Ronald L. Rivest
Citations32
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 notion of dynamic sampling, wherein the number of examples examined can increase with the complexity of the target concept, is introduced and is used to establish the learnability of various concept classes with an infinite Vapnik-Chervonenkis (VC) dimension.
Abstract
The problem of learning a concept from examples in a distribution-free model is considered. The notion of dynamic sampling, wherein the number of examples examined can increase with the complexity of the target concept, is introduced. This method is used to establish the learnability of various concept classes with an infinite Vapnik-Chervonenkis (VC) dimension. An important variation on the problem of learning from examples, called approximating from examples, is also discussed. The problem of computing the VC dimension of a finite concept set defined on a finite domain is considered.>
Keywords
Computer Science
AutomaticaModeling by shortest data description
5,944 Citations1978J. Rissanen
The number of digits it takes to write down an observed sequence x1,...,xN of a time series depends on the model with its parameters that one assumes to have generated the observed data.
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.
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.
Information science and statisticsEstimation of Dependences Based on Empirical Data
2,238 Citations2006Vladimir Vapnik
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 LearningLearning Decision Lists
761 Citations1987Ronald L. Rivest
This paper introduces a new representation for Boolean functions, called decision lists, and shows that they are efficiently learnable from examples, and strictly increases the set of functions known to be polynomially learnable, in the sense of Valiant (1984).
Information and ComputationInferring decision trees using the minimum description lenght principle
665 Citations1989J. R. Quinlan, Ronald L. Rivest
The use of Rissanen's minimum description length principle for the construction of decision trees is explored and empirical results comparing this approach to other methods are given.
Information and ComputationA general lower bound on the number of examples needed for learning
414 Citations1989Andrzej Ehrenfeucht, David Haussler +2 more
This paper proves a lower bound on the number of random examples required for distribution-free learning of a concept class C and shows that for many interesting concept classes, including k CNF and k DNF, the bound is actually tight to within a constant factor.
Machine LearningLearning decision lists
355 Citations1987Ronald L. Rivest
This paper introduces a new representation for Boolean functions, called decision lists, and shows that they are efficiently learnable from examples, and strictly increases the set of functions known to be polynomially learnable, in the sense of Valiant (1984).
On the learnability of Boolean formulae
293 Citations1987Michael Kearns, M. Li +2 more
The goals are to prove results and develop general techniques that shed light on the boundary between the classes of expressions that are learnable in polynomial time and those that are apparently not, and to employ the distribution-free model of learning.
Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension
170 Citations1986Anselm Blumer, Andrzej Ehrenfeucht +2 more
It is shown 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.
Information and ComputationEquivalence of models for polynomial learnability
142 Citations1991David Haussler, Michael Kearns +2 more
Comparisons and equivalences are given between Valiant's model and the prediction learning models of Haussler, Littlestone, and Warmuth and show that several simplifying assumptions on polynomial learning algorithms can be made without loss of generality.
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.
Theoretical Computer ScienceOn finding a minimum dominating set in a tournament
53 Citations1988Nimrod Megiddo, Uzi Vishkin
It is shown that if the problem of finding a minimum dominating set in a tournament can be solved in n O(log n ) time, then for every constant C, there is also a polynomial-time algorithm for the satisfiability problem of boolean formulas in conjunctive normal form with m clauses and C log 2 m variables.
DSpace@MIT (Massachusetts Institute of Technology)Inferring Decision Trees Using the Minimum Description Length Principle
6 Citations1987Quinlan, L. Ross, Rivest, Ronald L.