Learning Context-Free Languages with Nondeterministic Stack RNNs
This addresses the challenge of modeling nondeterministic formal languages for computational linguistics and AI, representing an incremental improvement over prior stack RNN methods.
The paper tackled the problem of learning context-free languages by introducing a differentiable stack data structure that encodes multiple stack configurations, combined with an RNN controller. The result showed more reliable convergence on deterministic tasks and lower cross-entropy on nondeterministic tasks compared to existing 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.