Bounds for the Computational Power and Learning Complexity of Analog Neural Nets (Extended Abstract)

) Wolfgang Maass* Institute for Theoretical Computer Science Technische Universitaet Graz Klosterwiesgasse 32/2 A-8010 Graz, Austria e-mail: maass@igi.tu-graz.ac.at October 23, 1992 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 f0; 1g. 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 suc..