Learning Context-free Languages with Nondeterministic Stack RNN s (2020)

Abstract: 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.

## introduction although recent neural models of language have made advances in learning syntactic behavior, research continues to suggest that inductive bias plays a key role in data efficiency and human-like syntactic generalization @xcite . based on the long-held observation that language exhibits hierarchical structure, previous work has proposed coupling recurrent neural networks (rnns) with differentiable stack data structures @xcite to give them some of the computational power of pushdown automata (pdas), the class of automata that recognize context-free languages (cfls). however, previously proposed differentiable stack data structures only model deterministic stacks, which store only one version of the stack contents at a time, theoretically limiting the power of these stack rnns to the deterministic cfls. a sentence's syntactic structure often cannot be fully resolved until its conclusion (if ever), requiring a human listener to track multiple possibilities while hearing the sentence. past work in psycholinguistics has suggested that models that keep multiple candidate parses in memory at once can explain human reading times better than models which assume harsher computational constraints. this ability also plays an important role in calculating expectations that facilitate more efficient language processing @xcite . current neural language models do not track multiple parses, if they learn syntax generalizations at all @xcite @xcite . we propose a new differentiable stack data structure that explicitly models a nondeterministic pda, adapting an algorithm by @xcite and reformulating it in terms of tensor operations. the algorithm 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 language processing in two ways. first, it will improve trainability, since all possible sequences of stack operations contribute to the objective function, not just the sequence used by the current model. second, it will improve expressivity, as it is able to model concurrent parses in ways that a deterministic stack cannot. we demonstrate these claims by comparing the ns-rnn to deterministic stack rnns on formal language modeling tasks of varying complexity. to show that nondeterminism aids training, we show that the ns-rnn achieves lower cross-entropy, in fewer parameter updates, on some deterministic cfls. to show that nondeterminism improves expressivity, we show that the ns-rnn achieves lower crossentropy on nondeterministic cfls, including the "hardest context-free language" @xcite , a language which is at least as difficult to parse as any other cfl and inherently requires nondeterminism. our code is available at https://github. com/bdusell/nondeterministic-stack-rnn . ## 2 background and motivation in all differentiable stack-augmented networks that we are aware of (including ours), a network called the controller, which is some kind of rnn (typically an lstm), is augmented with a differentiable stack, which has no parameters of its own. at each time step, the controller emits weights for various stack operations, which at minimum include push and pop. to maintain differentiability, the weights need to be continuous; different designs for the stack interpret fractionally-weighted operations differently. the stack then executes the fractional operations and produces a stack reading, which is a vector that represents the top of the updated stack. the stack reading is used as an extra input to the next hidden state update. designs for differentiable stacks have proceeded generally along two lines. one approach, which we call superposition @xcite , treats fractional weights as probabilities. the other, which we call stratification @xcite , treats fractional weights as "thicknesses." superposition in the model of @xcite , the controller emits at each time step a probability distribution over three stack operations: push a new vector, pop the top vector, and no-op. the stack simulates all three operations at once, setting each stack element to the weighted interpolation of the elements above, at, and below it in the previous time step, weighted by push, noop, and pop probabilities respectively. thus, each stack element is a superposition of possible values for that element. because stack elements depend only on a fixed number of elements from the previous time step, the stack update can largely be parallelized. @xcite developed an extension to this model that allows a variable number of pops per time step, up to a fixed limit k. suzgun et al. (2019) stratification the model proposed by @xcite and later studied by @xcite takes a different approach, assigning a strength between 0 and 1 to each stack element. if the stack elements were the layers of a cake, then the strengths would represent the thickness of each layer. at each time step, the controller emits a push weight between 0 and 1 which determines the strength of a new vector pushed onto the stack, and a pop weight between 0 and 1 which determines how much to slice off the top of the stack. the stack reading is computed by examining the top layer of unit thickness and interpolating the vectors proportional to their strengths. this relies on min and max operations, which can have zero gradients. in practice, the model can get trapped in local optima and requires random restarts @xcite . this model also affords less opportunity for parallelization because of the interdependence of stack elements within the same time step. @xcite proposed an extension that uses memory buffers to allow variable-length transductions. nondeterminism in all the above models, the stack is essentially deterministic in design. in order to recognize a nondeterministic cfl like {ww r } from left to right, it must be possible, at each time step, for the stack to track all prefixes of the input string read so far. none of the foregoing models, to our knowledge, can represent a set of possiblities like this. even for deterministic cfls, this has consequences for trainability; at each time step, training can only update the model from the vantage point of a single stack configuration, making the model prone to getting stuck in local minima. to overcome this weakness, we propose incorporating a nondeterministic stack, which affords the model a global view of the space of possible ways to use the stack. our controller emits a probability distribution over stack operations, as in the superposition approach. however, whereas superposition only maintains the per-element marginal distributions over the stack elements, we propose to maintain the full distribution over the whole stack contents. we marginalize the distribution as late as possible, when the controller queries the stack for the current top stack symbol. in the following sections, we explain our model and compare it against those of @xcite and @xcite . despite taking longer in wall-clock time to train, our model learns to solve the tasks optimally with a higher rate of success. ## pushdown automata in this section, we give a definition of nondeterministic pdas ( §3.2), describe how to process strings with nondeterministic pdas in cubic time ( §3.3), and reformulate this algorithm in terms of tensor operations ( §3.4). ## neural pushdown automata now we couple the tensor formulation of lang's algorithm for nondeterministic pdas with an rnn controller. ## experiments in this section, we describe our experiments comparing our ns-rnn and three baseline language models on several formal languages. ## results we show plots of the difference in cross entropy on the validation set between each model and the source distribution in figure 4 . for all tasks, stackbased models outperform the lstm baseline, indicating that the tasks are effective benchmarks for differentiable stacks. for the marked reversal, unmarked reversal, and hardest cfl tasks, our model consistently achieves cross-entropy closer to the source distribution than any other model. even for the marked reversal task, which can be solved deterministically, the ns-rnn, besides achieving lower cross-entropy on average, learns to solve the task in fewer updates and with much higher reliability across random restarts. in the case of the mildly nondeterministic unmarked reversal and highly nondeterministic hardest cfl tasks, the ns-rnn converges on the lowest validation crossentropy. on the dyck language, which is a deterministic task, all stack models converge quickly on the source distribution. we hypothesize that this is because the dyck language represents a case where stack usage is locally advantageous everywhere, so it is particularly conducive for learning stack-like behavior. on the other hand, we note that our model struggles on padded reversal, in which stack-friendly signals are intentionally made very distant. although the ns-rnn outperforms the lstm baseline, the jm model solves the task most effectively, though still imperfectly. in order to show how each model performs when evaluated on strings longer than those seen during training, in figure 5 , we show cross-entropy on separately sampled test data as a function of string length. all test sets are identical across models and random restarts, and there are 100 samples per length. the ns-rnn consistently does well on string lengths it was trained on, but it is sometimes surpassed by other stack models on strings that are outside the distribution of lengths it was trained on. this suggests that the ns-rnn conforms more tightly to the real distribution seen during training. ## conclusion we presented the ns-rnn, a neural language model with a differentiable stack that explicitly models nondeterminism. we showed that it offers improved trainability and modeling power over previous stack-based neural language models; the ns-rnn learns to solve some deterministic tasks more effectively than other stack-lstms, and achieves the best results on a challenging nondeterministic context-free language. however, we note that the ns-rnn struggled on a task where signals in the data were distant, and did not generalize to longer lengths as well as other stack-lstms; we hope to address these shortcomings in future work. we believe that the ns-rnn will prove to be a powerful tool for learning and modeling ambiguous syntax in natural language.