Finite State Automata and Simple Recurrent Networks

TLDR

Natural language embeddings retain some dependence on earlier information, suggesting that recurrent networks might capture long‑distance dependencies despite initial doubts about their relevance. The study investigates whether an Elman recurrent network can learn finite‑state grammars and retain distant sequential contingencies across intervening elements. Using an Elman architecture, the network predicts the next element from the current input and the hidden activations of the previous time step. The network learns to perfectly recognize a finite‑state grammar, with hidden unit patterns aligning with grammar nodes when few units are used, and it can encode long‑distance contingencies when intermediate steps depend on early information, even if only subtle statistical cues are present.

Abstract

We explore a network architecture introduced by Elman (1988) for predicting successive elements of a sequence. The network uses the pattern of activation over a set of hidden units from time-step t−1, together with element t, to predict element t + 1. When the network is trained with strings from a particular finite-state grammar, it can learn to be a perfect finite-state recognizer for the grammar. When the network has a minimal number of hidden units, patterns on the hidden units come to correspond to the nodes of the grammar, although this correspondence is not necessary for the network to act as a perfect finite-state recognizer. We explore the conditions under which the network can carry information about distant sequential contingencies across intervening elements. Such information is maintained with relative ease if it is relevant at each intermediate step; it tends to be lost when intervening elements do not depend on it. At first glance this may suggest that such networks are not relevant to natural language, in which dependencies may span indefinite distances. However, embeddings in natural language are not completely independent of earlier information. The final simulation shows that long distance sequential contingencies can be encoded by the network even if only subtle statistical properties of embedded strings depend on the early information.