|
NeuroCOLT
Technical Report NC-TR-99-034
On
the Sample Complexity for Nonoverlapping Neural Networks
Michael Schmitt
Keywords:
Neural networks, read-once formulas, threshold gates, sigmoidal gates,
PAC learning, Vapnik-Chervonenkis dimension
Abstract
A neural network is said to be nonoverlapping if there is at
most one edge outgoing from each node. We investigate the number of
examples that a learning algorithm needs when using nonoverlapping
neural networks as hypotheses. We derive bounds for this sample complexity
in terms of the Vapnik-Chervonenkis dimension. In particular, we consider
networks consisting of threshold, sigmoidal and linear gates. We show
that the class of nonoverlapping threshold networks and the class
of nonoverlapping sigmoidal networks on n inputs both have Vapnik-Chervonenkis
dimension (n log n). This bound is asymptotically tight for
the class of nonoverlapping threshold networks. We also present an
upper bound for this class where the constants involved are considerably
smaller than in a previous calculation. Finally, we argue that the
Vapnik-Chervonenkis dimension of nonoverlapping threshold or sigmoidal
networks cannot become larger by allowing the nodes to compute linear
functions. This sheds some light on a recent result that exhibited
neural networks with quadratic VC dimension.
Download Compressed Postscript
|