Almost Linear VC-Dimension Bounds for Piecewise Polynomial Networks
- 1 November 1998
- journal article
- Published by MIT Press in Neural Computation
- Vol. 10 (8) , 2159-2173
Abstract
We compute upper and lower bounds on the VC dimension and pseudodimension of feedforward neural networks composed of piecewise polynomial activation functions. We show that if the number of layers is fixed, then the VC dimension and pseudo-dimension grow as W log W, where W is the number of parameters in the network. This result stands in opposition to the case where the number of layers is unbounded, in which case the VC dimension and pseudo-dimension grow as W2. We combine our results with recently established approximation error rates and determine error bounds for the problem of regression estimation by piecewise polynomial networks with unbounded weights.Keywords
This publication has 15 references indexed in Scilit:
- The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the networkIEEE Transactions on Information Theory, 1998
- Neural Networks with Quadratic VC DimensionJournal of Computer and System Sciences, 1997
- Polynomial Bounds for VC Dimension of Sigmoidal and General Pfaffian Neural NetworksJournal of Computer and System Sciences, 1997
- Fat-Shattering and the Learnability of Real-Valued FunctionsJournal of Computer and System Sciences, 1996
- Efficient agnostic learning of neural networks with bounded fan-inIEEE Transactions on Information Theory, 1996
- Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik-Chervonenkis dimensionJournal of Combinatorial Theory, Series A, 1995
- Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbersMachine Learning, 1995
- Approximation and estimation bounds for artificial neural networksMachine Learning, 1994
- Decision theoretic generalizations of the PAC model for neural net and other learning applicationsInformation and Computation, 1992
- Nonparametric Maximum Likelihood Estimation by the Method of SievesThe Annals of Statistics, 1982