Finite State Machines and Recurrent Neural Networks -- Automata and Dynamical Systems Approaches

Abstract

We present two approaches to the analysis of the relationship between a recurrent neural network (RNN) and the finite state machine \( {\cal M} \) the network is able to exactly mimic. First, the network is treated as a state machine and the relationship between the RNN and \( {\cal M} \) is established in the context of algebraic theory of automata. In the second approach, the RNN is viewed as a set of discrete-time dynamical systems associated with input symbols of \( {\cal M} \). In particular, issues concerning network representation of loops and cycles in the state transition diagram of \( {\cal M} \) are shown to provide a basis for the interpretation of learning process from the point of view of bifurcation analysis. The circumstances under which a loop corresponding to an input symbol \( x \) is represented by an attractive fixed point of the underlying dynamical system associated with \( x \) are investigated. For the case of two recurrent neurons, under some assumptions on weight values, bifurcations can be understood in the geometrical context of intersection of increasing and decreasing parts of curves defining fixed points. The most typical bifurcation responsible for the creation of a new fixed point is the saddle node bifurcation. (Also cross-referenced as UMIACS-TR-95-1)