@InProceedings{LMR88b,
replaced-by = { LMR91 },
author = { Nathan Linial and Yihshay Mansour and Ronald L. Rivest },
title = { Results on Learnability and the Vapnik-Chervonenkis dimension },
pages = { 120--129 },
doi = { 10.1109/SFCS.1988.21930 },
booktitle = { Proceedings of the Twenty-Ninth Annual Symposium on the Foundations of Computer Science },
publisher = { IEEE },
date = { 1988-10 },
OPTyear = { 1988 },
OPTmonth = { October 24--26, },
OPTeditor = {},
eventtitle = { FOCS'88 },
eventdate = { 1988-10-24/1988-10-26 },
venue = { White Plains, New York },
keywords = { Vapnik-Chervonenkis dimension, distribution-free model, dynamic sampling, finite
concept set, finite domain, learnability, learning systems },
abstract = {
The problem of learning a concept from examples in a distribution-free model
is considered. The notion of dynamic sampling, wherein the number of examples examined
can increase with the complexity of the target concept, is introduced. This method is used
to establish the learnability of various concept classes with an infinite Vapnik-Chervonenkis
(VC) dimension. An important variation on the problem of learning from examples, called approximating
from examples, is also discussed. The problem of computing the VC dimension of a finite concept
set defined on a finite domain is considered.
}
}