|
NeuroCOLT
Technical Report NC-TR-94-017
Bounds for the
Computational Power and Learning Complexity of Analog Neural Nets
Wolfgang
Maass
Institute for Theoretical Computer Science
Technische Universitaet Graz
Klosterwiesgasse 32/2
A-8010 Graz
Austria
Abstract
It is shown that high order feedforward neural nets of constant depth
with piecewise polynomial activation functions and arbitrary real
weights can be simulated for boolean inputs and outputs by neural
nets of a somewhat larger size and depth with heaviside gates and
weights from $\{-1,0,1\}$. This provides the first known upper bound
for the computational power of the former type of neural nets. It
is also shown that in the case of first order nets with piecewise
linear activation functions one can replace arbitrary real weights
by rational numbers with polynomially many bits, without changing
the boolean function that is computed by the neural net. In order
to prove these results we introduce two new methods for reducing nonlinear
problems about weights in multi-layer neural nets to linear problems
for a transformed set of parameters. These transformed parameters
can be interpreted as weights in a somewhat larger neural net.
As another application of our new proof technique we show that neural
nets with piecewise polynomial activation functions and a constant
number of analog inputs are probably approximately learnable (in Valiant's
model for PAC-learning).
Download Compressed
Postscript
|