Learning Context-Free Languages with Nondeterministic Stack RNNs
We present a differentiable stack data structure that simultaneously and tractably encodes an exponential number of stack configurations, based on Lang's algorithm for simulating nondeterministic pushdown automata. We call the combination of this data structure with a recurrent neural network (RNN) controller a Nondeterministic Stack RNN. We compare our model against existing stack RNNs on various formal languages, demonstrating that our model converges more reliably to algorithmic behavior on deterministic tasks, and achieves lower cross-entropy on inherently nondeterministic tasks.
Code (1)
Similar Papers 제목 키워드 기반
The Surprising Computational Power of Nondeterministic Stack RNNs
Traditional recurrent neural networks (RNNs) have a fixed, finite number of memory cells. In theory (assuming bounded range and precision), this limits their formal language recognition power to regular languages, and in…
Language ModelingLanguage ModellingNondeterministic Stacks in Neural Networks
Human language is full of compositional syntactic structures, and although neural networks have contributed to groundbreaking improvements in computer systems that process language, widely-used neural network architectur…
Language ModelingLanguage ModellingLearning Hierarchical Structures with Differentiable Nondeterministic Stacks
Learning hierarchical structures in sequential data -- from simple algorithmic patterns to natural language -- in a reliable, generalizable way remains a challenging problem for neural language models. Past work has show…
Inductive BiasLanguage ModelingLanguage ModellingContext-Free Transductions with Neural Stacks
This paper analyzes the behavior of stack-augmented recurrent neural network (RNN) models. Due to the architectural similarity between stack RNNs and pushdown transducers, we train stack RNN models on a number of tasks, …
Language ModellingStack Attention: Improving the Ability of Transformers to Model Hierarchical Patterns
Attention, specifically scaled dot-product attention, has proven effective for natural language, but it does not have a mechanism for handling hierarchical patterns of arbitrary nesting depth, which limits its ability to…
Language ModelingLanguage ModellingMachine Translation