Learnability and the Vapnik-Chervonenkis dimension
Learnability and the Vapnik-Chervonenkis dimension
Anselm Blumer,A. Ehrenfeucht,D. Haussler,Manfred K. Warmuth
1989 · DOI: 10.1145/76359.76371
2,280 Citations
TLDR
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.