Recurrent Neural Networks Can Learn to Implement Symbol-Sensitive Counting

Paul Rodríguez, Janet WilesNeurIPS 1997

Introduction

In the late 1990s, a major debate in cognitive science and artificial intelligence centered on whether neural networks could handle the recursive nature of human language. Formal languages are categorized by the complexity of the computational machinery required to recognize them. While simple languages only need a finite state machine, Context-Free Languages (CFLs)—such as palindromes or nested parentheses—require a stack, which is a memory structure that follows Last-In, First-Out (LIFO) logic.

While previous work demonstrated that Recurrent Neural Networks (RNNs) could learn simple counting (like $a^n b^n$), this research tackles a significantly harder challenge: symbol-sensitive counting. To recognize a complex palindrome like $a^n b^m B^m A^n$, a system cannot simply count the total number of symbols. It must remember exactly how many '$a$'s it observed, hold that information in memory while it counts a new sequence of '$b$'s, and then retrieve that stored count much later to verify the final '$A$'s.

This paper demonstrates that RNNs do not merely "memorize" sequences; they can self-organize into sophisticated dynamical systems to solve these complex linguistic tasks, effectively mimicking the behavior of a stack-based computer through the geometry of their internal phase space.

Methods and Training

The researchers utilized a standard discrete-time RNN with a 5-5-5 architecture (5 input units, 5 hidden units with recurrent connections, and 5 output units). The network was trained on a next-symbol prediction task using Back-Propagation Through Time (BPTT).

The training dataset consisted of synthetic "simple palindromes" structured as $w w^r$, specifically $a^n b^m B^m A^n$ (e.g., aaabbbBBBAAA). The training set contained 68 strings with a maximum length of 25 symbols. To test the network's ability to generalize the underlying grammatical rule rather than just memorizing examples, the testing set included much longer strings, up to 36 symbols in length.

Instead of treating the trained RNN as a black box, the authors employed Dynamical Systems Analysis. By calculating the Jacobian matrices at fixed points to find eigenvalues, they determined whether the system was "contracting" (counting up) or "expanding" (counting down) in specific dimensions of its internal state space.

Mechanisms of Symbol-Sensitive Counting

The dynamical systems analysis revealed several fascinating strategies the network self-discovered to process the context-free language:

The "Saddle Point" Trick

The network learned to count by "contracting" toward an attracting fixed point during the first half of a sequence. To "count down" or "pop" from its internal stack, it moved the state vector near a saddle point.

State space trajectories showing the network contracting and expanding to count symbols.

The rate at which the system expanded away from this saddle point was inversely proportional to the earlier contraction rate. This precise geometric relationship allowed the network to "undo" the count accurately.

Dimension Splitting

The network did not rely on a single, monolithic counter. Instead, it partitioned its hidden units. One unit tracked whether the sequence was in the first or second half of the string, while other units handled the $b \dots B$ and $a \dots A$ subsequences in separate dimensional subspaces.

Implicit Storage

Perhaps the most striking finding is how the network stores the initial count. The RNN lacks a discrete "memory register" for the count of '$a$'s. Instead, it stores this information implicitly in the starting position of the subsequent $b \dots B$ sequence.

Spatial offsets in the hidden unit space representing the implicit storage of the 'a' count.

Even as the network actively processes the '$b$'s, the "ghost" of the '$a$' count remains preserved as a spatial offset in the phase space. This offset is later recovered to accurately predict the final sequence of '$A$'s.

Results and Limitations

The network demonstrated strong generalization, successfully processing strings like $a^9 b^9 B^9 A^9$ (36 characters)—12 characters longer than any sequence it encountered during training. It proved its "symbol sensitivity" by maintaining one count (the '$a$'s) while actively performing a different counting task (the '$b$'s). Functionally, the RNN's self-organized solution mirrored hand-coded "dynamical recognizers" from theoretical analog computation, but achieved this entirely through learning.

However, the study notes several limitations:

  • Precision Limits: Because the network relies on real-valued distances in continuous space to count, it is fundamentally limited by numerical precision. For excessively long strings, the spatial differences between counts become too small to distinguish, leading to failure.
  • Training Difficulty: The learning process was unstable. Only about half of the simulations successfully learned the transitions, and none achieved perfect accuracy on the training set, despite generalizing well when successful.
  • Complexity Scaling: While the network handled a simple palindrome, "true" palindromes (where symbols can appear in any order, like abcba) require far more sophisticated state-space partitioning. Future work is needed to explore how these non-independent counting mechanisms scale to more complex formal languages.

Summary updated

BibTeX
@inproceedings{rodriguez1997recurrent,
  author = {Paul Rodríguez and Janet Wiles},
  title = {{Recurrent Neural Networks Can Learn to Implement Symbol-Sensitive Counting}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1997},
}
Figure