Learnability and the Vapnik-Chervonenkis dimension

Anselm Blumer; Andrzej Ehrenfeucht; David Haussler; Manfred K. Warmuth

doi:10.1145/76359.76371

Abstract

Valiant's learnability model is extended to learning classes of concepts defined by regions in Euclidean space E n . The methods in this paper lead to a unified treatment of some of Valiant's results, along with previous results on distribution-free convergence of certain pattern recognition algorithms. 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. Using this parameter, the complexity and closure properties of learnable classes are analyzed, and the necessary and sufficient conditions are provided for feasible learnability.

Keywords

LearnabilityVC dimensionDimension (graph theory)MathematicsSimple (philosophy)Closure (psychology)Euclidean spaceComputer scienceClass (philosophy)Theoretical computer scienceDiscrete mathematicsArtificial intelligenceCombinatorics

Affiliated Institutions

Related Publications

Scale-sensitive dimensions, uniform convergence, and learnability

Noga Alon , Shai Ben-David , Nicolò Cesa‐Bianchi +1 more

Learnability in Valiant's PAC learning model has been shown to be strongly related to the existence of uniform laws of large numbers. These laws define a distribution-free conve...

1997 Journal of the ACM 341 citations

Structural risk minimization over data-dependent hierarchies

John Shawe‐Taylor , Peter L. Bartlett , Robert C. Williamson +1 more

The paper introduces some generalizations of Vapnik's (1982) method of structural risk minimization (SRM). As well as making explicit some of the details on SRM, it provides a r...

1998 IEEE Transactions on Information Theory 527 citations

An Introduction to Computational Learning Theory

Michael Kearns , Umesh Vazirani

Emphasizing issues of computational efficiency, Michael Kearns and Umesh Vazirani introduce a number of central topics in computational learning theory for researchers and stude...

1994 The MIT Press eBooks 1717 citations

Circular backpropagation networks for classification

Sandro Ridella , Stefano Rovetta , Rodolfo Zunino

The class of mapping networks is a general family of tools to perform a wide variety of tasks. This paper presents a standardized, uniform representation for this class of netwo...

1997 IEEE Transactions on Neural Networks 136 citations

Distributed Learning, Communication Complexity and Privacy

Maria-Florina Balcan , Avrim Blum , Shai Fine +1 more

We consider the problem of PAC-learning from distributed data and analyze fundamental communication complexity questions involved. We provide general upper and lower bounds on t...

2012 arXiv (Cornell University) 113 citations

Publication Info

Year: 1989
Type: article
Volume: 36
Issue: 4
Pages: 929-965
Citations: 1830
Access: Closed

External Links

View on DOI.org

Social Impact

Altmetric

Learnability and the Vapnik-Chervonenkis dimension

PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

1830

OpenAlex

Cite This

APA Style

                            
                                
                                    Anselm Blumer, 
                                
                                    Andrzej Ehrenfeucht, 
                                
                                    David Haussler
                                
                                et al.
                            
                            (1989). 
                            Learnability and the Vapnik-Chervonenkis dimension. 
                            Journal of the ACM
                            , 36
                            (4)
                            , 929-965.
                            https://doi.org/10.1145/76359.76371
                        

Identifiers

DOI: 10.1145/76359.76371