|
About
NeuroCOLT
Papers
Archive
Books
info@neurocolt.org
|
NeuroCOLT
Technical Report NC-TR-97-037
Discontinuities
in Recurrent Neural Networks
Ricard
Gavaldą
Universitat Politecnica de Catalunya
Spain
Hava
Siegelmann
Technion
Israel
Abstract
This paper studies the computational power of various discontinuous
real computational models that are based on the classical analog recurrent
neural network (ARNN). This ARNN consists of finite number of neurons;
each neuron computes a polynomial net-function and a sigmoid-like
continuous activation-function. The authors introduce ``arithmetic
networks'' as ARNN augmented with a few simple discontinuous (eg.,
threshold) neurons. They argue that even with weights restricted to
polynomial time computable reals, arithmetic networks are able to
compute arbitrary complex recursive functions. A proof is provided
to show that arithmetic networks are computationally equivalent to
networks comprised of neurons that compute divisions and polynomials
net-functions inside sigmoid-like continuous activation functions.
Further, the authors prove that these arithmetic networks are equivalent
to the Blum-Shub-Smale (BSS) model, when the latter is restricted
to a bounded number of registers. With regards to implementation on
digital computers, the authors demonstrate that arithmetic networks
with rational weights require exponential precision; but even with
very simple real weights arithmetic networks are not subject to precision
bounds. As such, they can not be approximated on digital machines.
This is in contrast with the ARNN that are known to demand only precision
that is linear in the computation time. When complex periodic discontinuous
neurons (eg. sine, tangent, fractional parts) are augmented to arithmetic
networks, the resulting networks are computationally equivalent to
a massively parallel machine. Thus, this highly discontinuous network
can solve the presumably intractable class of PSPACE-complete problems
in polynomial time.
Download Compressed Postscript
|