Learning Context-free Languages with Nondeterministic Stack RNNs

Proceedings of the 24th Conference on Computational Natural Language Learning, pages 507–519 Online, November 19-20, 2020. c⃝2020 Association for Computational Linguistics https://doi.org/10.18653/v1/P17 507 Learning Context-Free Languages with Nondeterministic Stack RNNs Brian DuSell University of Notre Dame bdusell1@nd.edu David Chiang University of Notre Dame dchiang@nd.edu Abstract We present a differentiable stack data struc- ture that simultaneously and tractably encodes an exponential number of stack configurations, based on Lang’s algorithm for simulating non- deterministic pushdown automata. We call the combination of this data structure with a recur- rent neural network (RNN) controller a Non- deterministic Stack RNN. We compare our model against existing stack RNNs on vari- ous formal languages, demonstrating that our model converges more reliably to algorithmic behavior on deterministic tasks, and achieves lower cross-entropy on inherently nondeter- ministic tasks. 1 Introduction Although recent neural models of language have made advances in learning syntactic behavior, re- search continues to suggest that inductive bias plays a key role in data efficiency and human-like syntactic generalization (van Schijndel et al., 2019; Hu et al., 2020). Based on the long-held observa- tion that language exhibits hierarchical structure, previous work has proposed coupling recurrent neu- ral networks (RNNs) with differentiable stack data structures (Joulin and Mikolov, 2015; Grefenstette et al., 2015) to give them some of the computa- tional power of pushdown automata (PDAs), the class of automata that recognize context-free lan- guages (CFLs). However, previously proposed dif- ferentiable stack data structures only model deter- ministic stacks, which store only one version of the stack contents at a time, theoretically limiting the power of these stack RNNs to the determinis- tic CFLs. A sentence’s syntactic structure often cannot be fully resolved until its conclusion (if ever), requir- ing a human listener to track multiple possibilities while hearing the sentence. Past work in psycholin- guistics has suggested that models that keep multi- ple candidate parses in memory at once can explain human reading times better than models which as- sume harsher computational constraints. This abil- ity also plays an important role in calculating ex- pectations that facilitate more efficient language processing (Levy, 2008). Current neural language models do not track multiple parses, if they learn syntax generalizations at all (Futrell et al., 2019; Wilcox et al., 2019; McCoy et al., 2020). We propose a new differentiable stack data struc- ture that explicitly models a nondeterministic PDA, adapting an algorithm by Lang (1974) and refor- mulating it in terms of tensor operations. The algo- rithm is able to represent an exponential number of stack configurations at once using cubic time and quadratic space complexity. As with existing stack RNN architectures, we combine this data structure with an RNN controller, and we call the resulting model a Nondeterministic Stack RNN (NS-RNN). We predict that nondeterminism can help lan- guage processing in two ways. First, it will im- prove trainability, since all possible sequences of stack operations contribute to the objective func- tion, not just the sequence used by the current model. Second, it will improve expressivity, as …

Content truncated to 500 words