Context-Free Transductions with Neural Stacks

Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 306–315 Brussels, Belgium, November 1, 2018. c⃝2018 Association for Computational Linguistics 306 Context-Free Transductions with Neural Stacks Yiding Hao,∗William Merrill,∗Dana Angluin, Robert Frank, Noah Amsel, Andrew Benz, and Simon Mendelsohn Department of Linguistics, Yale University Department of Computer Science, Yale University firstname.lastname@yale.edu Abstract This paper analyzes the behavior of stack- augmented recurrent neural network (RNN) models. Due to the architectural similarity be- tween stack RNNs and pushdown transduc- ers, we train stack RNN models on a num- ber of tasks, including string reversal, context- free language modelling, and cumulative XOR evaluation. Examining the behavior of our net- works, we show that stack-augmented RNNs can discover intuitive stack-based strategies for solving our tasks. However, stack RNNs are more difficult to train than classical ar- chitectures such as LSTMs. Rather than em- ploy stack-based strategies, more complex net- works often find approximate solutions by us- ing the stack as unstructured memory. 1 Introduction Recent work on recurrent neural network (RNN) architectures has introduced a number of models that enhance traditional networks with differen- tiable implementations of common data structures. Appealing to their Turing-completeness (Siegel- mann and Sontag, 1995), Graves et al. (2014) view RNNs as computational devices that learn trans- duction algorithms, and develop a trainable model of random-access memory that can simulate Tur- ing machine computations. In the domain of natu- ral language processing, the prevalence of context- free models of natural language syntax has mo- tivated stack-based architectures such as those of Grefenstette et al. (2015) and Joulin and Mikolov (2015). By analogy to Graves et al.’s Neural Tur- ing Machines, these stack-based models are de- signed to simulate pushdown transducer compu- tations. From a practical standpoint, stack-based mod- els may be seen as a way to optimize networks for discovering dependencies of a hierarchical ∗Equal contribution. nature. Additionally, stack-based models could potentially facilitate interpretability by imposing structure upon the recurrent state of an RNN. Classical architectures such as Simple RNNs (El- man, 1990), Long Short-Term Memory networks (LSTM, Hochreiter and Schmidhuber, 1997), and Gated Recurrent Unit networks (GRU, Cho et al., 2014) represent state as black-box vectors. In cer- tain cases, these models can learn to implement classical data structures using state vectors (Kirov and Frank, 2011). However, because state vec- tors are fixed in size, the inferred data structures must be represented in a fractal encoding requir- ing arbitrary position. On the other hand, differ- entiable stacks typically increase in size through- out the course of the computation, so their per- formance may better scale to larger inputs. Since the ability of a differentiable stack to function cor- rectly intrinsically requires that the information it contains be represented in the proper format, ex- amining the contents of a network’s stack through- out the course of its computation could reveal hi- erarchical patterns that the network has discovered in its training data. This paper systematically explores the behav- ior of stack-augmented RNNs on simple …

Content truncated to 500 words