Monthly
288 pp. per issue
6 x 9, illustrated
ISSN
0899-7667
E-ISSN
1530-888X
2014 Impact factor:
2.21

Neural Computation

May 15, 1997, Vol. 9, No. 4, Pages 771-776
(doi: 10.1162/neco.1997.9.4.771)
© 1997 Massachusetts Institute of Technology
Lower Bound on VC-Dimension by Local Shattering
Article PDF (48.88 KB)
Abstract

We show that the VC-dimension of a smoothly parameterized function class is not less than the dimension of any manifold in the parameter space, as long as distinct parameter values induce distinct decision boundaries. A similar theorem was published recently and used to introduce lower bounds on VC-dimension for several cases (Lee, Bartlett, & Williamson, 1995). This theorem is not correct, but our theorem could replace it for those cases and many other practical ones.