- ▪B. DasGupta, H.T. Siegelmann, E.D. Sontag, "On the complexity of training neural networks with continuous activation functions", IEEE Trans.\ Neural Networks, vol. 6, pp. 1490–1504, 1995. pdfanalog computing · theory of computing · neural networks · computational complexity · machine learning
Abstract
Blum and Rivest showed that any possible neural net learning algorithm based on fixed architectures faces severe computational barriers. This paper extends their NP-completeness result, which applied only to nets based on hard threshold activations, to nets that employ a particular continuous activation. In view of neural network practice, this is a more relevant result to understanding the limitations of backpropagation and related techniques.
- ▪H. T. Siegelmann, E.D. Sontag, "On the computational power of neural nets", J. Computer System Sciences, vol. 50, no. 1, pp. 132–150, 1995. doipdfmachine learning · analog computing · theory of computing · neural networks · computational complexity · super-Turing computation
Abstract
This paper deals with finite size networks which consist of interconnections of synchronously evolving processors. Each processor updates its state by applying a "sigmoidal" function to a rational-coefficient linear combination of the previous states of all units. We prove that one may simulate all Turing Machines by such nets. In particular, one can simulate any multi-stack Turing Machine in real time, and there is a net made up of 886 processors which computes a universal partial-recursive function. Products (high order nets) are not required, contrary to what had been stated in the literature. Non-deterministic Turing Machines can be simulated by non-deterministic rational nets, also in real time. The simulation result has many consequences regarding the decidability, or more generally the complexity, of questions about recursive nets.
- ▪B. DasGupta, H. T. Siegelmann, E.D. Sontag, "On a learnability question associated to neural networks with continuous activations (extended abstract)", In COLT '94: Proceedings of the seventh annual conference on Computational learning theory, pp. 47–56, 1994. doi
- ▪B. DasGupta, H.T. Siegelmann, E.D. Sontag, "On the Intractability of Loading Neural Networks", In Theoretical Advances in Neural Computation and Learning\/, pp. 357–389, 1994. pdf
- ▪H.T. Siegelmann, E.D. Sontag, "Analog computation via neural networks", In Proc.\ 2nd Israel Symposium on Theory of Computing and Systems (ISTCS93)\/, IEEE Computer Society Press, 1993, 1993.
- ▪H.T. Siegelmann, E.D. Sontag, "On the computational power of neural nets", In COLT '92: Proceedings of the fifth annual workshop on Computational learning theory, pp. 440–449, 1992. doi
- ▪H.T. Siegelmann, E.D. Sontag, "Some results on computing with neural nets", In Proc.\ IEEE Conf.\ Decision and Control, Tucson, Dec.\ 1992, IEEE Publications, 1992, pp. 1476–1481, 1992.