Learnability and the Vapnik-Chervonenkis dimension. (English) Zbl 0697.68079

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

J. Assoc. Comput. Mach. 36, No. 4, 929-965 (1989).

MSC:

68T05	Learning and adaptive systems in artificial intelligence
68Q25	Analysis of algorithms and problem complexity
68T10	Pattern recognition, speech recognition
68R10	Graph theory (including graph drawing) in computer science

Keywords:

Vapnik-Chervonenkis dimension; geometrical problems and computations; probabilistic algorithms; concept learning; induction; learnability theory; learning from examples; Occam’s razor; PAC learning; sample complexity; Vapnik-Chervonenkis classes