Paper Info
Title
Stochastic analog networks and computational complexity
Abstract
The model of analog recurrent neural networks (ARNN) is typically perceived as based on either the practical powerful tool of automatic learning or on biological metaphors, yet it constitutes an appealing model of computation. This paper provides rigorous foundations for ARNN, when they are allowed to exhibit stochastic and random behavior of discrete nature. Our model is an extension of the von Neumann model of unreliable interconnection of components and incor- porates a generalization of Shannon's random-noise philosophy. In the general case the computational class (Ppoly) is associated with both deterministic and stochastic networks. However, when the weights are restricted to rational numbers, stochasticity adds power to the computation. As part of the proof, we show that probabilistic Turing machines that use a coin with a real probability rather than an exactly random ( 1 2) coin, compute the nonuniform version BPPlog* instead of the recursive class BPP. We also show that in the case of real probabilities only their first logarithmic number of bits are relevant for the computation. 1999 Academic Press
Year
DOI
Venue
1999
10.1006/jcom.1999.0505
J. Complexity
Keywords
DocType
Volume
stochastic analog network,computational complexity
Journal
15
Issue
ISSN
Citations 
4
Journal of Complexity
6
PageRank 
References 
Authors
1.45
14
1
Name
Order
Citations
PageRank
Hava T. Siegelmann1980145.09