No subject

[maass@figids01.tu-graz.ac.at]

Re: Vapnik-Chervonenkis Dimension of Neural Nets

According to [BEHW] the Vapnik-Chervonenkis dimension (VC-dimension)
of a neural net is the key parameter for determining the number of
samples that are needed for training the net. For a feedforward neural
net C with heaviside gates that has e edges (or equivalently: e
adjustable weights) it was shown by Baum and Haussler [BH] in 1988
that the VC-dimension of C is bounded above by O(e log e). It has
remained an open problem whether the factor "log e" in this upper
bound is in fact needed, or whether a general upper bound O(e) would
also be valid.

This problem is solved by the following new result:

THEOREM: 
One can construct for every natural number n a feedforward
neural net C(n) of depth 4 with heaviside gates that has n input bits,
one output bit, and not more than 33n edges, such that the
VC-dimension of C(n) (or more precisely: of the class of boolean
functions that can be computed by C(n) by choosing suitable integer
weights from {-n,...,n}) is at least as large as n log n.

COROLLARY: 
The general upper bound of O(e log e) for the VC-dimension
of a neural net with e adjustable weights (due to Baum and Haussler
[BW]) is asymptotically optimal.

REMARKS: 
1. The proof of the Theorem is immediate from a quite
sophisticated circuit construction due to Lupanov (english translation
due to Gyorgy Turan [T]). Lupanov had shown that every boolean function
of n inputs can be computed by a threshold circuit of depth 4 with
O(2**(n/2 - log n/2)) gates.

2. This new lower bound for the VC-dimension of neural nets will
appear as a side-result in a paper "On the Theory of Neural Nets with
Piecewise Polynomial Activation Functions", that should be available
in October 1993. The main results of this paper are upper bounds for
the VC-dimension and for the computational power of neural nets with
arbitrary piecewise polynomial activation functions at the gates and
arbitrary real weights.  Preprints of this paper will be available
from the author:

Wolfgang Maass
Institute for Theoretical Computer Science
Technische Universitaet Graz
Klosterwiesgasse 32/2, A-8010 Graz, Austria
e-mail: maass at igi.tu-graz.ac.at
Tel.: (0316)81-00-63-22
Fax: (0316)81-00-63-5

References:

[BH] E.B.Baum, D. Haussler, What size nets gives valid generalization,
Neural Computation 1, 1989, 151-160

[BEHW] A. Blumer, A. Ehrenfeucht, D. Haussler, M.K. Warmuth,
Learnability and the Vapnik-Chervonenkis-dimension, Journal of the
ACM, 36, 1989, 929-965

[T] G. Turan, unpublished manuscript (1989)