CRL Newsletter

Vol. 10, No. 1

October 1995

Technical Report

Representing the Structure of a Simple Context-Free Language in a Recurrent Neural Network: A Dynamical Systems Approach

Paul Rodriguez

Department of Cognitive Science, UCSD

ABSTRACT

Parallel Distributed Processing (PDP) architectures demonstrate a potentially radical alternative to the traditional theories of language processing that are based on serial computational models.  However, learning complex structural relationships in temporal data presents a serious challenge to PDP systems. For example, automata theory dictates that processing strings from a simple Context-Free Language(CFL) requires a memory device. This project will employ standard backpropagation training techniques for a Recurrent Neural Network (RNN) in the task of learning a simple CFL.

I will show that a RNN can learn to recognize the structure of a simple CFL; and using Dynamical Systems Theory, one can correctly identify how network states reflect that structure. An important question that arises is whether or not the RNN performs similarly or not to discrete automata.

1. INTRODUCTION

It is well established that sentences of natural language are more than just a linear arrangement of words. Sentences have complex temporal structures that are often characterized syntactically, such as phrase structures, subject-verb agreement, and relative-clauses. Representing and processing such structure presents a critical challenge to mechanisms of natural language processing (NLP), both as a gauge of their theoretic capability and their potential to provide a pyschological account of natural language parsing. Ideally, a mechanism should reflect the nature of the process as well as how it is implemented.

A traditional view of NLP is based on mechanisms of discrete finite automata. Automata theory states that a regular language can be processed by a Finite State Machine (FSM). However, if a language has center-embedding, then that language is a Context-Free Language(CFL) which requires a Push-Down Automata(PDA). Importantly, a PDA is a FSM with an additional resource of a memory-like device that is a "stack" or "counter" in order to keep track of the embeddings (figure 1).

Parallel Distributed Processing (PDP) architectures demonstrate a potentially radical alternative to the traditional theories of language processing. However, learning complex structural relationships in temporal data presents a serious challenge to PDP systems. Here I show that a Recurrent Neural Network (RNN) can learn a simple CFL. Furthermore, I use Dynamical Systems Theory to demonstrate how the RNN reflects the functional requirements of a CFL. In particular, the net can organize resources in order to keep track of input and maintain informational states that reflect the temporal structure of the input. The analysis enables a rough comparison to PDA. This work is complementary to theoretic analysis of RNN capabilities (e.g. Siegelmann) yet original in its specific identification of dynamic properties involved. The work is distinct to other proposed modelling of CFL, such as sequential recursive auto-associative memory (RAAM, e.g. Kwasny and Kalman, 1995), in that I am not directly attempting to represent constituent structures. An important question that arises is: How does a RNN compare to a PDA?

2. RECURRENT NEURAL NETWORKS

2.1 Description

Neural network architectures demonstrate a potentially radical alternative to the traditional discrete automata. A neural network system has no explicit state definitions nor explicit memory stores, but rather consist of simple neuron-like nodes (or units) which are linked together via weighted-connections so that the activation value of a node is a function of weights and activation values from nodes that are directly connected to it. Weights can be adjusted through an error correction procedure (backpropagation) which allows the network to learn input-output mappings (Rumelhart, Hinton, and Williams, 1986).

A recurrent neural network (RNN) architecture contains feedback connections which allow the system to have node activation values at one time step affect the same node activation values at the next time step, thereby reflecting temporal processing. Figure 2 presents a typical RNN architecture with two binary-valued input nodes,(shown as input lines), two hidden nodes, two output nodes, and one bias node. The feedback connections are implemented through copy units and the weights can also be updated through appropriate error correction procedures (Elman, 1991; St. John, 1992).

2.2 RNN and Language

Empirical investigations using RNNs with simple artificial grammars have shown that a RNN can learn to recognize strings from a RG (Giles et al., 1992; Giles et al., 1993; Waltrous and Kuhn, 1992; Servan-Shrieber, et al., 1989; Smith and Zipser, 1989). However, relatively little conclusive work has been done using RNNs with artificial CFGs, nor has it been shown how a RNN might perform the same functions as a PDA in processing strings from a CFG. A sequential version of the RAAM model was shown to have compositional structure yet it was not shown how it might generalize on long input strings (Kwasny and Kalman, 1995). Recently, it was shown that a RNN can perform recognition of strings from a CFG, but the network could not generalize properly (Batali, 1994).

Empirical investigations using natural language input have not demonstrated conclusive results on sentence processing capabilities of RNNs.1 For example, Elman reports a RNN that can learn up to three levels of center-embeddings (Elman, 1991). Stolke reports a RNN that can learn up to two levels of center-embeddings, and up to five levels for tail-recursion (Stolke, 1990). Other work has shown that a RNN can process temporal semantic cues within sentences and reflect semantic constraints and associations (St. John, 1990).

Interestingly, it has been shown that a RNN can handle more levels of embedding if there are additional semantic constraints (Weckerley and Elman, 1992). The authors suggest that the RNN is a mechanism that reflects performance. However, in all these latter studies it may be the case that the RNN is performing the functional equivalent of a FSM. In other words the RNN may not appropriately reflect syntactic structure of complex sentences as does a PDA. Perhaps RNN capabilities are inherently limited such that performance is only reflected gratuitously. The current state of affairs presents a dilemma for RNN enthusiasts - they have a mechanism that reflects some aspects of performance, but they do not yet have a theory about the "nature of the solution".

3. THE EXPERIMENT

3.1 Issues

The broader question that situates my research is the issue of how a RNN may suggest an alternative psychological description of syntactic processing tasks. However, I will not directly address this question. Rather I will be addressing two related questions that work toward the bigger issue:

• Can a RNN learn to process a simple CFL?
• What are the states and resources employed by the RNN?

The first question demands that a RNN learn to process a simple CFL so that it generalizes beyond those input/output mappings presented in training. In other words, the performance of the RNN must somehow reflect the structure of the input. The second question demands a functional description of how the RNN reflects the structure of the input. Ideally, one should ground the functional description of states and resources on a formal analysis of the RNN dynamics. Next I will describe the RNN experiment and later I will introduce concepts from Dynamical Systems Theory as the method of analysis.

3.2 RNN Experiment

The input stimuli is a very simple CFL that uses only two symbols, {a, b}, and consists of strings of the form a^n b^n, in which "n" is an integer greater than 0. The training set consists of all strings of total length up to 22, or n=11, which means 11 a's followed by 11 b's. There are more proportionately more short strings than long strings in a ratio of 10 to 1 of shortest to longest. A network that properly generalizes will correctly process strings beyond length n=11.

The architecture for the experiment will be a RNN with 2 input units, 2 hidden units, 2 copy units, 2 output units, 1 bias unit (see figure 2). In one time step the hidden unit activation values and then output unit activation values will be updated. The copy units will hold the hidden unit values in preparation for the next time step.

The RNN will be trained to predict the next input such that if a network makes all the right predictions possible then the network is correctly processing the input. Elman points out several advantages in the prediction task; for one it requires minimal commitment to defining the role of an external teacher, and more importantly it is psychologically motivated by the observation that humans use prediction and anticipation in language processing (Elman, 1991).

For the simple CFL input a^n b^n, when the network has "a" input, it will not be able to accurately predict the next symbol because the next symbol can be another "a" or the first "b" in the sequence. On the other hand, when the network has a "b" input, it could accurately predict the number of "b" symbols that match the number of "a" input, and then also predict the end of the string (Batali, 1994). Correct processing of a string is defined as follows:

• A) "b" input => predict only "b" symbols, except for B).
• B) last "b" input => predict end of the string (or beginning of the next string).

(Since the network outputs values are continuous, I will use a cut off value at .5.)

3.3 Overall Results

I will present two cases of the RNN training results. Both cases use the same network architecture and training set, different sets of initial weights, and were trained to the point of best performance. The first network learned proper predictions for n=8 and the second learned proper predictions for n=16, for a total string length of 32. I claim that the first case attempts to solve the problem in an intuitive way, although it fails. The second case found a solution that does generalize, although the solution will be non-intuitive and will require a dynamical systems analysis. Consequently, before I present the results in detail, in the next section I will introduce the concepts and formalisms of dynamical systems theory.

4. METHOD OF ANALYSIS

4.1 Dynamical Systems Theory as Method

How does one compare and contrast a RNN to finite automata, such as FSM or PDA? The difficulty of the question stems from the fact that a RNN contains node activations that consist of a real number between 0 and 1, whose value is a function of previous node activations and current inputs. In fact, the set of values represent a coordinate point in a high-dimensional vector space defined over real numbers, which implies that two sets of node values have some meaningful measure of distance. On the other hand, in finite automata, such as a FSM or PDA, there exists a predefined set of discrete states and a transition functions which maps current states and current input into a next state. The states have no topological meaning and there is no middle ground between them. Recent work has formally compared a RNN to a FSM by analyzing the RNN performance using mathematical techniques from dynamical systems theory (Casey, 1995; also Tino, Horne, and Giles, 1995). In a similar vein, I will use dynamical systems theory techniques to evaluate a RNN and draw comparisons to PDA.

4.2 Dynamical Systems Overview

A dynamical system is often used to describe real physical systems in which the state of the system at some time depends on the state at a previous time. Many concepts can be introduced by describing some simple physical systems. For example consider a ball placed on a 3-D landscape (figure 3). Depending on where the ball is initially placed, the ball will roll around to some lowest point that it can reach. The position of the ball at some time depends on the position of the ball at some previous time. If the ball is at rest then it is at a "fixed point". If the fixed point is at the bottom of a valley then it is called an attracting fixed point. If the fixed point is at the top of a hill then it is called a repelling fixed point because with a slight perturbation the ball will roll away. The path that the ball takes is called a trajectory.

The 3-D physical landscape can be characterized by a vector flow field in a phase space diagram. The vector flow field represents the set of possible trajectories and the phase space diagram coordinate axis that represent the state variables of the system.2 In this example the state variables are the {x, y} coordinate point of the ball position. For each position on the landscape, the vector flows describe the change of position. In fact, the entire trajectory of the ball can be roughly plotted out in the phase space diagram.

4.3 A RNN is a Dynamical System

A RNN is a system that can be characterized as a discrete-time dynamical system. Since the weight parameters are held constant after training, if the input values are held constant for several time steps, then the hidden unit activation values are the state variables in a phase space diagram. The coordinate system of the phase space diagram would be the pair {hidden unit 1, hidden unit 2} and the vector flow field would give a qualitative description of the change in activation values over several time steps (i.e. a trajectory). Note that for each input there will be a different set of dynamics. Hence for my experiment, there will be one phase space diagram for "a" input, and one diagram for "b" input.

Since the output units are a function of the hidden unit values it will be informative to draw a contour plot on the phase space diagram for each output unit. I will draw a one-line contour plot which cuts up the phase space such that for all {hidden unit 1,hidden unit 2} values on one side of the line the output unit is > .5 or .5 (threshold value).

4.4 Dynamical Systems Analysis

For a discrete-time dynamical system one can use a standard technique ("linearization") for analyzing the behavior near a fixed point. The technique produces a linear system for which the eigenvalues3 govern how the trajectories are contracting or expanding. The eigenvalues give the rate of contraction or expansion and the eigenvectors give the axis along which the system contracts or expands. For example:

• a) eigenvalues > 1 or -1 => system is expanding and the fixed point is repelling,
• b) eigenvalues 1 and > -1 =>system is contracting and the fixed point is attracting,
• c) at least one eigenvalue > 1 or -1 => system is expanding in the direction of the eigenvector that corresponds to that eigenvalue and the fixed point is also a repelling point specifically referred to as a saddle point.

5. RESULTS

I will present two cases of the RNN training results. Case 1 learned the training set only for n=8; case 2 learned the training set completely and generalized for n=16. I will present first a graphical analysis of network performance using vector flow fields and graphing the trajectories (all diagrams are attached at the end). The graphical analysis will only provide a qualitative description of the network dynamics and provide some insights into the mathematical analysis that follows later.

5.1 Case 1

The output units cut up the phase space evenly along a nearly vertical line, such that all {HU1, HU2} (where HU is abbreviation for hidden unit) values to the left of the line predict an "a", and all {HU1,HU2} values to the right predict a "b". Most networks independent of overall performance divided the phase space evenly, although not necessarily vertically. This will be shown on trajectory diagrams below as a line in diagram.

Figure 4 shows the vector flow field for the two input conditions. Note that the vectors are scaled from their true magnitude, but the relative vector size still reflects relative change in {HU1, HU2}. " Fa" and "Fb" represent the dynamics for the "a" input condition and "b" input condition respectively. Note that Fa has an attracting point near (0,.35), and Fb has an attracting point near (0,1). In the physical metaphor the Fa landscape has a valley that slopes down to (0,.35), and Fb has a valley that slopes down to (0,1). One can imagine placing a ball on the Fa hill, letting it roll for a while, and then holding the ball steady at some location while the landscape is instantaneously switched to Fb. Now the ball will change directions and roll around to the other attracting point. This is exactly analogous to feeding the network some strings of the form "aa...aabb...bb".

The landscape analogy has at least one caveat. In real landscapes a ball will roll quickly down from a hilltop and perhaps roll past a small valley, depending on speed, momentum, etc.. However, in the RNN dynamics there is an important rule of thumb: the trajectory will always have small changes near a fixed point - for both attracting and repelling points.

Figure 5 shows the trajectory for some short strings, n=2 and n=3. Each arrow represents 1 time step, hence 1 input. The tail of the arrow is the value of {HU1, HU2} before the time step (i.e. the copy units) and the head represents the updated value of {HU1, HU2} after applying the activation functions. Note that the initial value was chosen by allowing the network to run for one or two short strings. Importantly, the last "b" input results in a change in {HU1, HU2} that crosses over to the left of the dividing line, hence the network properly predicts an "a" when the last "b" is input. Not surprisingly the last {HU1, HU2} value is near the initial starting value.

Figure 6 shows the trajectories for longer strings: n=4 and n=5. As above, the network trajectory correctly crosses the dividing line on the last "b" input. Figure 7 shows the trajectories for n=8 and n=9. Note how the network arrows are increasingly shorter near the Fa attracting fixed point. Also, the first "b" input cause a transition to a region of phase space where the arrows can take smaller step sizes as well. However, for n=9 the network crosses the dividing line on the 8th "b", suggesting that perhaps the step sizes are not properly matched.

One important feature is that the case 1 network performed most of the processing of "a" input along the HU2 axis, and most of the processing for "b" input along the HU1 axis. In fact, Fa monotonically decreased in HU2, and Fb monotonically decreased in HU1, which intuitively suggests that the network is "counting a's" and then "counting b's", with a transition from "a" to "b" that attempts to set up a proper "b" starting point.

5.2 Case 2

The case 2 network also has output values that divide the phase space along a nearly vertical line (but not all networks have vertical dividing lines). The flow fields in figure 8 show that Fa has an attracting point near (0,.85). The Fb also seems to have an attracting point near (.4,.8), however, the dynamics for Fb turn out to be more complicated. In fact, with simple computer iteration of the network activation functions it was determined that Fb will eventually settle into a periodic-2 fixed point. Therefore in figure 9 I show the dynamics for Fb and for Fb^2, (the composite of Fb with itself). One can now see that Fb^2 has 2 fixed points, near (0,.4) and (1,1). Since, a fixed point for Fb^2 is a periodic point for Fb, we can see that the Fb vector flow field shows not an attracting point but actually a repelling point. The trajectories will show that the network oscillates around the repelling point and eventually settles into the periodic 2 fixed point. The oscillations are the reason that the vectors point toward the repelling point in the Fb dynamics in figure 8. The landscape metaphor would be a large hill with a valley below it, but the valley has a smaller hill in the middle of it such that a ball will roll down the hill towards the small hill but then roll towards the lower points in the valley.

Figure 10 shows the trajectories for short strings, n=2 and n=3. Again the arrows represent 1 time step, hence 1 input. In the next figure, n=4 and n=5, one can see that the trajectories are actually oscillating around both the attracting point and the repelling point. Figure 12 confirms that the oscillations are somehow matched up for longer strings. In other words, if the last "a" input ends up a little higher(or lower) than the attracting fixed point, then the "b" input must transition to a coordinate point that is also higher (or lower) than the repelling fixed point. Also, the smaller arrows of Fa must be matched by small arrow of Fb. As the Fb trajectory steps expand around the repelling point, the network will cross the dividing line on the last expanding step after taking the correct number of total smaller steps. I will refer to such complementary dynamics as coordinated trajectories.

5.3 Analysis Results

In this section I will develop a deeper analysis of the networks and establish some informal criteria that explain how a network is successful. The analysis employs a standard technique of 'linearization' around the fixed point for each input condition. I will be using this technique to compare the trajectory for Fa and Fb. Since the graphs show that the interesting dynamics occur in the neighborhoods around the attracting point for Fa and the saddle point for Fb, I will use these two points as the fixed points in the linearization method.4 In the physical metaphor these points correspond to a valley in the Fa landscape, and a hilltop in the Fb landscape.

The results in table 1 summarize my findings. I have added two other cases of networks with the same architecture trained on the same task, although with different combinations of initial seed, training set, and eta values. Case 3 is a network that had dynamics similar to case 1.5 Case 4 is a network with dynamics similar to my case 2, which was found by Janet Wiles in related work.

             CASE     max n learned      Fa       Fb      1/Fa
             ----     -------------   ------   --------  --------
               1           8           .408      .832     2.45
               2          16          -.7095   -1.455*   -1.409*
               3           7           .242     1.29      4.136
               4          25          -.637    -1.536**  -1.57**

Table 1. A comparison of largest eigenvalues at the attracting fixed point of Fa and repelling fixed point of Fb. The successful networks have eigenvalues that are inversely proportional to each other. The starred values indicate which values are proportional.

The table compares the largest eigenvalues of the Fa system with the largest eigenvalue of the Fb system. These eigenvalues are associated with the eigenvectors that correspond to the axis of contraction under Fa, and the axis of expansion Fb.6 The contraction and expansion rates, which are given by the eigenvalues, indicate the change in hidden units values from one time step to the next. In other words, the size of the trajectory step, as seen in the graphical analysis, is completely determined by the eigenvalues. If the eigenvalues are inversely proportional, then step sizes for "a" input will be matched by step sizes for "b" input. In the landscape metaphor, if the eigenvalues of Fa and Fb are exactly proportional to each other, then the upward slope of the valley in the Fa landscape matches the downward slope of the hilltop in the Fb landscape.

Based on the results in the table I can state the first attempt at a criterion for success as the following:

• C1) If the rates of contraction for Fa around the attracting point and the rate of expansion for Fb around the saddle point are inversely proportional to each other, then a RNN can process the a^n b^n language by matching step sizes for "a" input and "b" input.

The above criterion explained how trajectory steps match in size, which helps explain how the network predicts the transition at the end of the string. However, it does not explain how a network can organize itself to so that the transition from the last "a" to the first "b" in an input sequence will put the network in a region of phase space such that the step sizes will match. I will explain this by looking at the eigenvectors at the saddle point.

Figure 13 replicates the vector flow field for Fb and Fb^2. I have also drawn in the lines in the direction of the eigenvectors, which intersect at the location of the saddle point. The line that crosses the HU2 axis near (0,.85) is the stable eigenvector line; and the line that crosses the HU2 axis near (0,.65) is the unstable eigenvector line. Values of {HU1,HU2} near the stable eigenvector get contracted in towards the saddle point before moving towards the periodic 2 fixed point. Notice that the attracting point for the Fa dynamics (see figure 12) nearly falls on the stable eigenvector line of the saddle point for the Fb dynamics. The full criterion can now be stated as follows:

• C2) If "C1)" above is satisfied, and if the attracting point of Fa lies on the stable eigenvector of the saddle point for Fb then a RNN can process the a^n b^n language.

These criteria describe coordinated trajectories.

6. CONCLUSION

The case 2 network generalized for n=16, which is 10 characters more in total string length than presented in training. The ability of the network to perform the task is manifested in the weight parameters of the output units and the dynamics of the hidden units. Although, the network did not generalize to an infinite length string, one can comfortably conjecture based on the analysis that the network dynamics reflect the structure of the input/output task.

In fact one can draw functional correspondences between the behavior of the network and the behavior of the PDA as follows:

          PDA:			RNN:
          stack/counter 		~ coordinated trajectories
          state 			~ region of activation values
          transition 		~ a change in activation values

I am not implying that a RNN is equivalent to a PDA; the coordinated trajectory concept I introduce is neither a stack nor a counter. However, in the context of the task domain and network architecture the hidden node dynamics realize an equivalent functional and informational content as that provided by a stack or counter in the context of a PDA. Also, the dynamical systems interpretation provides the correct functional description (as well as the mathematical analysis) of the resources employed by a RNN. In particular, a coordinated trajectory is composed of the following resources in the a^n b^n task domain: 1) the contracting dynamics of the attracting point under "a" input condition matches the expanding dynamics of the repelling point under the "b" input condition and 2) the attracting point under "a" input condition lies near the axis of convergence of the saddle point.

In conclusion, I can address the two questions I presented earlier: first, a RNN can learn to process a simple CFL; secondly the states and resources employed are correctly identified by a dynamical systems interpretation. A RNN can employ its resources to behave functionally as a stack/counter. However, there are important differences which may not correspond to a PDA. In the case of a PDA the states of the system that control the stack or counter is literally disconnected from the stack or counter device. In the case of a RNN one cannot decouple the coordinated trajectory from the states of the system. In fact, the trajectory is the state of activation values and the change of activation values.7

7. DISCUSSION

7.1 Overview

The work here has implications for a variety of issues. In this section I would like to briefly discuss some of these. My purpose is not to postulate any answers but rather point out that the work here adds a building block to the connectionist framework and perhaps new background information with which to frame some language processing questions.

7.2 The Psychological Account

An important question surrounding this work is the following: Does a RNN provide an alternative account of psychological data on human language processing than discrete automata? For example, a PDA with limitations on the stack depth can account for human performance limits on processing center-embedded sentences (Barton, et al. 1987). However, experiments have shown that semantic information might aid the processing of center-embedded sentences (Stolz, 1967). In a PDA framework this is problematic because syntactic processing constraints on the stack device must somehow depend on semantic constraints as well (Marcus, 1980). On the other hand, Weckerly and Elman (1992) have demonstrated that a RNN can learn to process center-embedded sentences with semantically biased verbs better than semantically unbiased verbs, suggesting that a RNN mechanism reflects some aspects of performance more seamlessly.

The work presented here suggests a related question that one can now ask: How does content affect trajectories? In other words, since we have some characterization of the resources involved in trajectories, we can begin to understand how different task domains, including ones that use semantic input, affects those resources. The affects could arise from precision, location of fixed points, rates of contraction/expansion, the topographical relationships of those axis of contraction/expansion, the ability of output units to "cut up" the phase space, etc.. The dynamical systems analysis presented here provides insight on some performance issues for RNN models of language processing, but by no means does it exhaust the possibilities.

7.3 Other Counters

Recently, Siegelmann has proved that one can construct a RNN to perform as counters (Siegelmann, 1993). Each counter consists of one linear node with only one recurrent connection to itself and the connections between nodes are laid out such that they only have limited interaction.

In my case 2 network the "counting up" values oscillate and converge around a fixed point, the "counting down" values oscillate and expand around a repelling fixed point. More importantly my network learned the solution, with hidden units that were fully connected to each other. The axis of expansion in case 2 contained components of both hidden units which suggests a solution that was distributed among units. The output units were not specially constructed but rather developed their own connection weights to cut up the hidden unit phase space as appropriate. In fact, since the output units were not connected to the input units the hidden layer was forced to find a solution that "counts up and down" in two different regions of phase space. Essentially, the case 2 network realizes a distributed solution for the task at hand.

7.4 What other CFLs can a RNN learn?

The possibility exists that the network dynamics are particular to the specific task and do not reflect the kind of dynamics needed for CFLs in general. For example, a more complicated CFL is the balanced parenthesis language.8 This language consists of some number of "a" and the same number of "b", but a "b" can be placed anywhere in the string such that it matches some previous "a". In other words, the "ab" can be embedding anywhere in the string. For this task the network can only correctly predict the end of the string.

Further testing of the case 2 network with strings from the balanced parenthesis language confirms that coordinated trajectories are sufficient to process other CFLs. For example, the case 2 network will correctly predict the transition at the end of strings such as "aabaabbb" and "aabaabaabbb". This result is striking because the network was never trained on any strings from the balanced parenthesis problem. The conditions to process this language are related to those for a^n b^n language. Future work will investigate whether or not a RNN can learn other CFLs. It is possible that the solution may involve a different set of dynamics or just dynamics that are more complex.

7.5 Constituent Structure

It is premature to fully compare a RNN with a PDA because a PDA is capable of producing output in the form of constituent-tree structure, which represents a hierarchical relationship of syntactic structure. A RNN trained on the prediction task can reflect structure of the input strings but it does not develop constituent structure representations. However, an appreciation of the RNN capabilities and limitations directed at addressing such issues will contribute to an understanding of possible syntactic machineries necessary to support the production and comprehension of language. This work has demonstrated that under some configuration of dynamics a RNN has capabilities that reflect the structure of the input, independent of string length.

ACKNOWLEDGEMENTS

I would like to thank Jeffrey Elman for excellent guidance and insightful discussions about everything herein, and Janet Wiles for providing some of her sample work and engaging discussions. Also, I benefited from very helpful feedback from John Batali, Michael Casey, Paul Minero, Mark St. John, and David Zipser.

BIBLIOGRAPHY

Batali, John (1994). "Innate Biases and Critical Periods: Combining Evolution and Learning in the Acquisition of Syntax". Proceedings of the Fourth Artificial Life Workshop, Cambridge, MA.

Casey, Michael Patrick (1995). Computation in Discrete-Time Dynamical Systems, Ph.D. dissertation, unpublished, University of California at San Diego.

Chalmers, David (1992). "Syntactic Transformations on Distributed Representations", in Connectionist Natural Language Processing, ed. Noel Sharkey, Kluwer Academic.

Elman, Jeffrey L. (1990). "Finding Structure in Time", in Cognitive Science 14, Ablex.

Elman, Jeffrey L. (1991). "Distributed Representations, Simple Recurrent Networks, and Grammatical Structure" in Machine Learning 7, Kluwer Academic.

Giles, C.L., Sun, G.Z., Chen, H.H., Lee, Y.C., Chen, D. (1992) "Extracting and Learning and Unknown Grammar with Recurrent Neural Networks" in Advances in Information Processing 4, J.E. Moody, S.J. Hanson and R.P. Lippmann (eds), Morgan Kaufman, San Mateo, Ca.

Giles, C. Lee, and Omlin, Christian W. (1993). "Extraction, Insertion and Refinement of Symbolic Rules in Dynamically Driven Recurrent Neural Networks", in Connection Science, Vol5, Nos. 3 and 4.

Hopcroft, John E., and Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation, Addison-Wesley.

Kwasny, Stan C., and Kalman, Barry L. (1995). "Tail-recursive Distributed Representations and Simple Recurrent Networks", in Connection Science, Vol7, No 1.

Lucas, S. M., Damper, R. I. (1992). "Syntactic Neural Networks", in Connectionist Natural Language Processing, ed. Noel Sharkey, Kluwer Academic.

Marcus, Mitchell P., (1980). A Theory of Syntactic Recognition for Natural Language, MIT Press, Cambridge, Mass..

Miikulainen, Risto (1992). "Script Recognition with Hierarchical Feature Maps", in Connectionist Natural Language Processing, ed. Noel Sharkey, Kluwer Academic.

Maskara, Arun and Noetzel, Andrew (1992) "Sequence Recogntion withRecurrent Neural Networks", Technical Report, New Jersey Institute of Technology.

McClelland, James L., and Kawamoto, Alan H. (1986). "Mechanisms of Sentence Processing: Assigning Roles to Constituents", in Parallel Distributed Processing Vol. 1, MIT Press.

Rumelhart, D. E., Hinton, G.E., Williams, R.J. (1987). "Learning Internal Representations by Error Propagation", in Parallel Distributed Processing Vol. 1, MIT Press.

Servan-Schreiber, David, Cleermans, Axel, and McClelland, James L. (1988) "Encoding Sequential Structure in Simple Recurrent Networks", CMU Technical Report CS-88-183.

Siegelmann, Hava Tova (1993). Foundations of Recurrent Neural Networks, Ph.D. dissertation, unpublished. New Brunswick Rutgers, The State University of New Jersey.

Smith, Anthony W. and Zipser, David (1989). "Learning Sequential Structure with the Real-Time Recurrent Learning Algorithm", International Journal of Neural Systems, Vol.1, No. 2.

St John, Mark (1992). "The Story Gestalt: A Model of Knowledge-Intensive Processes in Text Comprehension", Cognitive Science, 16.

Stolcke, Andreas (1990). "Learning Feature-Based Semantics with Simple Recurrent Networks", Technical Report, ICSI, UC Berkeley.

Stolz, W.S. (1967). "A Study of the Ability to Decode Grammatically Novel Sentences", in Journal of Learning and Verbal Behavior, Vol. 6.

Sun, G.Z., Chen, H.H., Giles, C.L., Lee, Y.C., Chen, D. (1990). "Connectionist Pushdown Automata That Learn Context-Free Grammars", in IJCNN, Washington D.C.

Tino, Peter, Horne, Bill, and Giles, Lee (1995). "Finite State Machines and RecurrentNeural Networks - Automata and Dynamical Systems Approaches", Technical Report-UMCP-CSD:CS-TR-3396, University of Maryland, College Park.

Watrous, Raymond L., and Kuhn, Gary M. (1992). "Induction of Finite-State Automata Using Second Order Recurrent Networks" in Advances in Information Processing 4, J.E. Moody, S.J. Hanson and R.P. Lippmann (eds), Morgan Kaufman, San Mateo, Ca.

Weckerley, Jill and Elman, Jeffrey L. (1992). "A PDP Approach to Processing Center-Embedded Sentences", in Proceedings of the Fourteenth Annual Conference of the Cognitive Science Society, Indiana University, Bloomington, Lawrence Erlbaum Associates, Hillsdale, N.J.

Williams, Ronald J., and Zipser, David (1989). "Experimental Analysis of the Real-Time Recurrent Learning Algorithm", in Connection Science, Vol. 1, No. 1.

1 Several works have demonstrated that feed-forward networks are capable of representing complex structural relationships, such as the RAAM model (e.g. Chalmers, 1992). Also, there have been other works showing that feed-forward networks are capable of performing semantic processes, such as assigning thematic role information (McClelland and Kawamoto, 1986; Miikkulainen, 1992). Some researches have built networks to handle temporal structure by using special delay lines or hierarchical structure (Lucas and Damper, 1992). My emphasis here is on networks that attempt to organize itself to match the temporal structure of the language task.

2 Note that the phase space diagram does not include an axis for time.

3 An eigenvalue is a scalar (, and an eigenvector is a vector v, such that for a system of equations F, Fv=(v.

4 The case 1 network did not actually have a repelling point, however, I used the point that had the smallest change in activation values, which still allows one to make a rough comparison of dynamics.

5 Case 3 had dynamics that monotonically increase for 1 hidden unit in Fa, then monotonically decreased for the other hidden unit in Fb, but in this case the dynamics have a repelling point.

6 The other eigenvalues are only important in the sense that they are small enough so that the larger eigenvalues "dominate" the action.

7 This claim is supported by formal definitions. In the set theoretic language of automata the stack or counter is a discrete set distinct from the set of control states. In the set theoretic language of dynamical systems a trajectory (or orbit) is the real-valued set of state variables through time.

8 In fact the language a^n b^n is a subset of the balanced parenthesis language.