Learnability and the Vapnik-Chervonenkis dimension

1989/10/01 by Anselm Blumer, Andrzej Ehrenfeucht, David Haussler +1 · 8 citations
Computer Science · Mathematics · #Machine Learning and Algorithms #Computability, Logic, AI Algorithms #Domain Adaptation and Few-Shot Learning #Learnability #VC dimension #Dimension (graph theory) #Mathematics #Simple (philosophy) #Closure (psychology) #Euclidean space #Computer science #Class (philosophy) #Theoretical computer science #Discrete mathematics #Artificial intelligence #Combinatorics

paper · pdf · doi:10.1145/76359.76371

openalex publication_date 1989/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/23

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.

Citations

• Estimation of Dependences Based on Empirical Data
• Linear Programming in Linear Time When the Dimension Is Fixed
• Fast probabilistic algorithms for hamiltonian circuits and matchings
• Approximation algorithms for combinatorial problems
• Computational Complexity of Probabilistic Turing Machines
• Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities

Cited by

• Spectral methods: crucial for machine learning, natural for quantum computers?
• Pseudo-dimension of quantum circuits
• Sample compression schemes for balls in structurally sparse graphs
• Characterizations of learnability for classes of O, …, n -valued functions
• Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables
• Almost optimal set covers in finite VC-dimension
• Learning in the presence of concept drift and hidden contexts
• Vapnik–Chervonenkis dimension [wikipedia]