On the Effect of Analog Noise in Discrete-Time Analog Computations
- 1 July 1998
- journal article
- Published by MIT Press in Neural Computation
- Vol. 10 (5) , 1071-1095
- https://doi.org/10.1162/089976698300017359
Abstract
We introduce a model for analog computation with discrete time in the presence of analog noise that is flexible enough to cover the most important concrete cases, such as noisy analog neural nets and networks of spiking neurons. This model subsumes the classical model for digital computation in the presence of noise. We show that the presence of arbitrarily small amounts of analog noise reduces the power of analog computational models to that of finite automata, and we also prove a new type of upper bound for the VC-dimension of computational models with analog noise.Keywords
This publication has 19 references indexed in Scilit:
- Polynomial Bounds for VC Dimension of Sigmoidal and General Pfaffian Neural NetworksJournal of Computer and System Sciences, 1997
- The Dynamics of Discrete-Time Computation, with Application to Recurrent Neural Networks and Finite State Machine ExtractionNeural Computation, 1996
- Representation of finite state automata in Recurrent Radial Basis Function networksMachine Learning, 1996
- Bounds on the complexity of recurrent neural network implementations of finite state machinesNeural Networks, 1996
- Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbersMachine Learning, 1995
- Computability with low-dimensional dynamical systemsTheoretical Computer Science, 1994
- Decision theoretic generalizations of the PAC model for neural net and other learning applicationsInformation and Computation, 1992
- Efficient simulation of finite automata by neural netsJournal of the ACM, 1991
- Learnability and the Vapnik-Chervonenkis dimensionJournal of the ACM, 1989
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machinesBulletin of the American Mathematical Society, 1989