Neural Computation, Vol 8, 1135-1178, Copyright © 1996 by The MIT Press

ARTICLES

The dynamics of discrete-time computation, with application to recurrent neural networks and finite state machine extraction

M Casey
Department of Mathematics, University of California, San Diego, La Jolla 92093, USA.

Recurrent neural networks (RNNs) can learn to perform finite state computations. It is shown that an RNN performing a finite state computation must organize its state space to mimic the states in the minimal deterministic finite state machine that can perform that computation, and a precise description of the attractor structure of such systems is given. This knowledge effectively predicts activation space dynamics, which allows one to understand RNN computation dynamics in spite of complexity in activation dynamics. This theory provides a theoretical framework for understanding finite state machine (FSM) extraction techniques and can be used to improve training methods for RNNs performing FSM computations. This provides an example of a successful approach to understanding a general class of complex systems that has not been explicitly designed, e.g., systems that have evolved or learned their internal structure.

This article has been cited by other articles:

				E. Izquierdo, I. Harvey, and R. D. Beer Associative Learning on a Continuum in Evolved Dynamical Neural Networks Adaptive Behavior, December 1, 2008; 16(6): 361 - 384. [Abstract] [PDF]

				P. Phattanasri, H. J. Chiel, and R. D. Beer The Dynamics of Associative Learning in Evolved Model Circuits Adaptive Behavior, December 1, 2007; 15(4): 377 - 396. [Abstract] [PDF]

				H. Jacobsson The Crystallizing Substochastic Sequential Machine Extractor: CrySSMEx. Neural Comput., September 1, 2006; 18(9): 2211 - 2255. [Abstract] [Full Text] [PDF]

				P. Tino and A. J. S. Mills Learning beyond finite memory in recurrent networks of spiking neurons. Neural Comput., March 1, 2006; 18(3): 591 - 613. [Abstract] [Full Text] [PDF]

				H. Jacobsson Rule Extraction from Recurrent Neural Networks: A Taxonomy and Review Neural Comput., June 1, 2005; 17(6): 1223 - 1263. [Abstract] [Full Text] [PDF]

				A. Vahed and C.W. Omlin A Machine Learning Method for Extracting Symbolic Knowledge from Recurrent Neural Networks Neural Comput., January 1, 2004; 16(1): 59 - 71. [Abstract] [Full Text] [PDF]

				J. Sima and P. Orponen General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results Neural Comput., December 1, 2003; 15(12): 2727 - 2778. [Abstract] [Full Text] [PDF]

				P. Tino and B. Hammer Architectural Bias in Recurrent Neural Networks: Fractal Analysis Neural Comput., August 1, 2003; 15(8): 1931 - 1957. [Abstract] [Full Text]

				J. Sima and P. Orponen Continuous-Time Symmetric Hopfield Nets Are Computationally Universal Neural Comput., March 1, 2003; 15(3): 693 - 733. [Abstract] [Full Text] [PDF]

				S. J. Hanson and M. Negishi On the Emergence of Rules in Neural Networks Neural Comput., September 1, 2002; 14(9): 2245 - 2268. [Abstract] [Full Text] [PDF]

				P. Rodriguez Simple Recurrent Networks Learn Context-Free and Context-Sensitive Languages by Counting Neural Comput., September 1, 2001; 13(9): 2093 - 2118. [Abstract] [Full Text] [PDF]

				P. Tino, B. G. Horne, and C. L. Giles Attractive Periodic Sets in Discrete-Time Recurrent Networks (with Emphasis on Fixed-Point Stability and Bifurcations in Two-Neuron Networks) Neural Comput., June 1, 2001; 13(6): 1379 - 1414. [Abstract] [Full Text] [PDF]

				J. Síma, P. Orponen, and T. Antti-Poika On the Computational Complexity of Binary and Analog Symmetric Hopfield Nets Neural Comput., December 1, 2000; 12(12): 2965 - 2989. [Abstract] [Full Text]

				R. C. Carrasco, M. L. Forcada, M. A. Valdés-Muñoz, and R. P. Ñeco Stable Encoding of Finite-State Machines in Discrete-Time Recurrent Neural Nets with Sigmoid Units Neural Comput., September 1, 2000; 12(9): 2129 - 2174. [Abstract] [Full Text]