On Metric Entropy, Vapnik-Chervonenkis Dimension, and Learnability for a Class of Distributions
Published 14 December 1989Open access
Sanjeev R. Kulkarni
Citations20
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 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.
Abstract
In [23], Valiant proposed a formal framework for distribution-free concept learning which has generated a great deal of interest. A fundamental result regarding this framework was proved by Blumer et al. [6] characterizing those concept classes which are learnable in terms of their Vapnik-Chervonenkis (VC) dimension. More recently, Benedek and Itai [4] studied learnability with respect to a fixed probability distribution (a variant of the original distribution-free framework) and proved an analogous result characterizing learnability in this case. They also stated a conjecture regarding learnability for a class of distributions. In this report, we first point 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). Some relationships, in addition to those shown in [4], between the VC dimension of a concept class and its metric entropy with respect to various distributions are then discussed. Finally, we prove some partial results regarding learnability for a class of distributions.
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.
Journal of the American Statistical AssociationProbability Inequalities for Sums of Bounded Random Variables
1,127 Citations1963Wassily Hoeffding
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.
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).
Discrete & Computational Geometryɛ-nets and simplex range queries
731 Citations1987David Haussler, Emo Welzl
The concept of an ɛ-net of a set of points for an abstract set of ranges is introduced and sufficient conditions that a random sample is an Â-net with any desired probability are given.
Machine LearningLearning From Noisy Examples
667 Citations1988Dana Angluin, Philip Laird
This paper shows that when the teacher may make independent random errors in classifying the example data, the strategy of selecting the most consistent rule for the sample is sufficient, and usually requires a feasibly small number of examples, provided noise affects less than half the examples on average.
Mathematics and its applications. Soviet seriesε-Entropy and ε-Capacity of Sets In Functional Spaces
513 Citations1993V. М. Tikhomirov
Machine LearningLearning from noisy examples
398 Citations1988Dana Angluin, Philip Laird
This paper shows that when the teacher may make independent random errors in classifying the example data, the strategy of selecting the most consistent rule for the sample is sufficient, and usually requires a feasibly small number of examples, provided noise affects less than half the examples on average.
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.
Metric Entropy of Some Classes of Sets with Differentiable Boundaries
187 Citations2010R. M. Dudley
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.
Learning disjunction of conjunctions
167 Citations1985Leslie G. Valiant
Positive results are shown for significant subclasses that allow not only propositional predicates but also some relations and under certain restrictions on these subclasses the learning algorithms are well suited to implementation on neural networks of threshold elements.
Journal of Approximation TheoryMetric entropy of some classes of sets with differentiable boundaries
157 Citations1974R. M. Dudley
Discrete MathematicsSome special vapnik-chervonenkis classes
147 Citations1981Roberta S. Wenocur, R. M. Dudley
Learning in the presence of malicious errors
128 Citations1988Michael Kearns, Ming Li
General methods for bounding the rate of error tolerable by any learning algorithm, efficient algorithms tolerating nontrivial rates of malicious errors, and equivalences between problems of learning with errors and standard combinatorial optimization problems are studied.
Results on learnability and the Vapnik-Chervonenkis dimension
32 Citations1988Nathan Linial, Yishay Mansour +1 more
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.
Elsevier eBooksExtending the Valiant Learning Model
31 Citations1988Jonathan Amsterdam
The question of whether learning by experimentation is equivalent to learning from examples in the general case is an important open problem; if they are equivalent, the suitability of the Valiant model for capturing the function of experiments in science is called into question.
Elsevier eBooksTwo New Frameworks for Learning
26 Citations1988B. K. Natarajan, Prasad Tadepalli
Two new formal frameworks for learning are presented, one exploring learning in the sense of improving computational efficiency as opposed to acquiring an unknown concept or function and the other exploring the acquisition of heuristics over problem domains of special structure.
Russian Mathematical SurveysKOLMOGOROV'S WORK ON $ \varepsilon$-ENTROPY OF FUNCTIONAL CLASSES AND THE SUPERPOSITION OF FUNCTIONS
19 Citations1963V. М. Tikhomirov
Complete Representations for Learning from Examples
6 Citations1998Eric B. Baum
Feedforward neural nets and also the transitive closure of 3-DNF formulae are shown to be ‘complete’ representations in the sense of Cook’s Theorem, and a proof that no class containing sufficiently many distinct functions is learnable by any repreentation under a strong but pragmatically interesting time restriction.