Abstract
Traditional recurrent neural networks (RNNs) have a fixed, finite number of memory cells, which limits their formal language recognition power to regular languages. In practice, RNNs struggle to learn many context-free languages (CFLs). To expand their capabilities, prior work has augmented RNNs with nondeterministic stack data structures. This paper demonstrates that nondeterminism and the neural controller interact to produce two unexpected abilities: recognizing non-context-free languages and handling large alphabet sizes with minimal internal symbols. We also propose the Vector RNS-RNN, which simulates stacks of vectors to increase information capacity, showing improvements on the Penn Treebank benchmark.
Introduction
Recurrent Neural Networks (RNNs) like LSTMs and GRUs are fundamental to sequential data processing but face a theoretical "memory ceiling." Due to their fixed-size hidden state, they are mathematically equivalent to finite automata, making it difficult for them to learn hierarchical or recursive structures found in formal languages and natural language syntax.
To address this, researchers previously introduced "stacks" to RNNs, transforming them into neural versions of Pushdown Automata (PDAs). While deterministic stacks are useful, they cannot represent the ambiguity inherent in language. Nondeterministic stacks (NS-RNNs) were introduced to simulate all possible stack paths simultaneously. This paper investigates whether the interaction between a neural controller and a nondeterministic stack unlocks computational "superpowers" beyond the expected context-free language (CFL) completeness.
Architecture and Methods
The core of this research is the Renormalizing Nondeterministic Stack RNN (RNS-RNN). Unlike a standard PDA that follows a single path, the RNS-RNN utilizes dynamic programming to maintain a distribution over all possible stack configurations.
The authors introduce several key innovations:
- Theoretical Proofs: They demonstrate that RNS-RNNs can recognize the intersection of multiple CFLs, placing them in a higher complexity class than standard PDAs.
- Vector RNS-RNN (VRNS-RNN): This model augments discrete stack symbols with high-dimensional vectors (e.g., word embeddings). This allows the model to combine the structural rigor of nondeterministic logic with the representational power of continuous vectors.
- Efficiency: An optimized algorithm reduces the time complexity of stack operations, facilitating the training of larger models.
Experimental Evaluation
The models were evaluated on three types of challenges: synthetic non-context-free languages (like $w\#w$ and $w\#w^R\#w$), large alphabet tasks (Dyck language with up to 200 bracket types), and natural language modeling using the Penn Treebank (PTB) benchmark.
Key Results
- Beyond CFLs: The RNS-RNN was the only model capable of learning the $w\#w$ and $ww'$ languages without explicit input hints, outperforming deterministic multi-stack models.
- Alphabet Capacity: On the $w\#w^R$ task with an alphabet size of 200, the RNS-RNN with only 3 internal symbols achieved near-perfect performance. It achieves this by encoding symbols as specific probability distributions (points on a simplex) over its internal alphabet.
- Natural Language Modeling: The VRNS-RNN achieved a test perplexity of 120.12 on PTB, a significant improvement over the baseline LSTM (125.90) and previous stack-augmented models.
Discussion and Conclusion
This work reveals that nondeterminism in neural networks is more than a path-finding mechanism; the neural controller can use the entire distribution of paths as a rich, multi-dimensional state. This allows a single stack to coordinate different nondeterministic branches, effectively acting like multiple stacks.
While the RNS-RNN faces challenges with $O(n^2)$ or $O(n^3)$ time complexity relative to sequence length, it successfully bridges the gap between discrete structural logic and continuous vector representations. Future work may focus on linearizing these computational costs for broader industrial applications and exploring more complex linguistic dependencies.
Summary updated