- ▪E.D. Sontag, "VC dimension of neural networks", In Neural Networks and Machine Learning, pp. 69-95, 1998. pdf
Abstract
The Vapnik-Chervonenkis (VC) dimension is an integer which helps to characterize distribution-independent learning of binary concepts from positive and negative samples. This paper, based on lectures delivered at the Isaac Newton Institute in August of 1997, presents a brief introduction, establishes various elementary results, and discusses how to estimate the VC dimension in several examples of interest in neural network theory. (It does not address the learning and estimation-theoretic applications of VC dimension, and the applications to uniform convergence theorems for empirical probabilities, for which many suitable references are available.)
- ▪E.D. Sontag, "Shattering all sets of k points in `general position' requires (k-1)/2 parameters", Neural Computation, vol. 9, no. 2, pp. 337–348, 1997. pdfmachine learning · artificial intelligence · neural networks · VC dimension · real-analytic functions
Abstract
For classes of concepts defined by certain classes of analytic functions depending on k parameters, there are nonempty open sets of samples of length 2k+2 which cannot be shattered. A slighly weaker result is also proved for piecewise-analytic functions. The special case of neural networks is discussed.