TR: Unreliable Neurons and Asynchronous Recurrent Nets

[Siegelmann Hava]

FTP-host: archive.cis.ohio-state.edu
FTP-filename: /pub/neuroprose/siegelmann.prob.ps.Z

The file siegelmann.prob.ps.Z is now available for copying from the
Neuroprose repository:

=============================================================================

ON THE COMPUTATIONAL POWER OF FAULTY AND ASYNCHRONOUS NEURAL NETWORKS (28 pages)
                           Hava Siegelmann
                         Bar-Ilan University

ABSTRACT
========

This paper deals with finite size recurrent neural networks which consist
of general (possibly with cycles) interconnections of
evolving processors.
Each neuron may assume real activation value.
We provide the first rigorous foundations for {\it recurrent}
networks which are built of
unreliable {\it analog} devices and present asynchronicity in their updates.

The first model considered incorporates unreliable devices (either neurons
or the connections between them) which assume fixed error probabilities,
independent of the history and the global state of the network.
The model corresponds to the random-noise philosophy of Shannon.
Another model allows the error probabilities to depend both on the global
state and the history.

Next, we change the various faulty nets to update in a total asynchronity.
We prove all the above models to be computationally equivalent
and we express their power. In particular, we see that for some constrained
models of networks, the random behavior adds nonunifromity to the computation.
However, the general simple  model of networks is robust to probabilistic 
failures and asynchronous behavior.

Nondeterministic unreliable nets are defined, and we show that in the
faulty model the equality P = NP holds.

=======================================================================

    Hope you find it interesting,  Hava