No subject

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

The following paper has been placed in the Neuroprose archive in file
maass.bounds.ps.Z . Retrieval instructions follow the abstract.

--Wolfgang Maass  (maass at igi.tu-graz.ac.at)


--------------------------------------------------------------------------------

 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 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 {0,1}. This provides the 
first known upper bound for the computational power and VC-dimension of 
such neural nets.
It is also shown that in the case of 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 addition we improve the best known lower bound for the VC-dimension of a 
neural net with w weights and gates that use the heaviside function
(or other common activation functions such as sigma) from Omega(w) to
Omega(w log w). This implies the somewhat surprising fact that the
Baum-Haussler upper bound for the VC-dimension of a neural net with heaviside
gates is asymptotically optimal. Finally it is shown that neural nets with
piecewise polynomial activation functions and a constant number of analog
inputs are probably approximately correct learnable (in Valiant's model for
PAC-learning, with hypotheses generated by a slightly larger neural net).


---------------------------------------------------------------------------------

To retrieve the paper by anonymous ftp:


unix> ftp archive.cis.ohio-state.edu   # (128.146.8.52)
Name: anonymous
Password:  neuron
ftp> cd pub/neuroprose
ftp> binary
ftp> get maass.bounds.ps.Z
ftp> quit
unix> uncompress maass.bounds.ps.Z
unix> lpr -P <printer name> maass.bounds.ps