Evaluating the Ability of LSTMs to Learn Context-Free Grammars

Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 115–124 Brussels, Belgium, November 1, 2018. c⃝2018 Association for Computational Linguistics 115 Evaluating the Ability of LSTMs to Learn Context-Free Grammars Luzi Sennhauser Federal Institute of Technology Zurich, Switzerland Massachusetts Institute of Technology Cambridge, MA, USA luzis@student.ethz.ch Robert C. Berwick LIDS, Room 32-D728 Massachusetts Institute of Technology Cambridge, MA, USA berwick@csail.mit.edu Abstract While long short-term memory (LSTM) neu- ral net architectures are designed to capture se- quence information, human language is gener- ally composed of hierarchical structures. This raises the question as to whether LSTMs can learn hierarchical structures. We explore this question with a well-formed bracket prediction task using two types of brackets modeled by an LSTM. Demonstrating that such a system is learnable by an LSTM is the first step in demonstrating that the entire class of CFLs is also learnable. We observe that the model requires exponen- tial memory in terms of the number of charac- ters and embedded depth, where a sub-linear memory should suffice. Still, the model does more than memorize the training input. It learns how to distinguish be- tween relevant and irrelevant information. On the other hand, we also observe that the model does not generalize well. We conclude that LSTMs do not learn the rele- vant underlying context-free rules, suggesting the good overall performance is attained rather by an efficient way of evaluating nuisance vari- ables. LSTMs are a way to quickly reach good results for many natural language tasks, but to understand and generate natural language one has to investigate other concepts that can make more direct use of natural language’s structural nature. 1 Introduction Composing hierarchical structure for natural lan- guage is an extremely powerful tool for human language generation. These structures are of great importance in order to extract semantic interpreta- tion (Berwick and Chomsky, 2016) and enable us to produce a vast repertoire of sentences via a very small set of rules. Having acquired such a set of rules, it is easy to construct new structures without having previously seen similar examples. For purposes of external communication, the syntactic structures generated by grammars must be “flattened” or linearized into a sequential out- put form (e.g. written, signed, or spoken). When reading such a (linearized) text, hearing a spoken sentence or observing a signed language, the struc- ture has to be recovered implicitly to recover the original meaning (i.e., parsing). In this study, we investigate whether Long Short-Term Memory (LSTM) models (Hochreiter and Schmidhuber, 1997) possess this same ability as humans do: inferring rule-based structure from a linear representation. Everaert et al. (2015) show clearly that there are phenomena in human lan- guage that can only be understood by taking the underlying hierarchical structure into account. For neural networks to do the same, it is therefore es- sential to acquire the underlying structure of sen- tences. Recurrent neural networks are often used for tasks like language modeling (Mikolov et al., 2010; Sundermeyer et al., …

Content truncated to 500 words