RNNs can generate bounded hierarchical languages with optimal memory

Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, pages 1978–2010, November 16–20, 2020. c⃝2020 Association for Computational Linguistics 1978 RNNs can generate bounded hierarchical languages with optimal memory John Hewitt† Michael Hahn‡ Surya Ganguli∥ Percy Liang† Christopher D. Manning†‡ †Computer Science Department ‡Linguistics Department ∥Applied Physics Department Stanford University {johnhew,mhahn2,sganguli,pliang,manning}@stanford.edu Abstract Recurrent neural networks empirically gener- ate natural language with high syntactic fi- delity. However, their success is not well- understood theoretically. We provide theoreti- cal insight into this success, proving in a finite- precision setting that RNNs can efficiently generate bounded hierarchical languages that reflect the scaffolding of natural language syn- tax. We introduce Dyck-(k,m), the language of well-nested brackets (of k types) and m- bounded nesting depth, reflecting the bounded memory needs and long-distance dependen- cies of natural language syntax. The best known results use O(k m 2 ) memory (hidden units) to generate these languages. We prove that an RNN with O(m log k) hidden units suf- fices, an exponential reduction in memory, by an explicit construction. Finally, we show that no algorithm, even with unbounded computa- tion, can suffice with o(m log k) hidden units. 1 Introduction Recurrent neural networks (RNNs; Elman (1990)) trained on large datasets have demonstrated a grasp of natural language syntax (Karpathy et al., 2015; Kuncoro et al., 2018). While considerable empiri- cal work has studied RNN language models’ ability to capture syntactic properties of language (Linzen et al., 2016; Marvin and Linzen, 2018; Hewitt and Manning, 2019; van Schijndel and Linzen, 2018), their success is not well-understood theoretically. In this work, we provide theoretical insight into RNNs’ syntactic success, proving that they can ef- ficiently generate a family of bounded hierarchical languages. These languages form the scaffolding of natural language syntax. Hierarchical structure characterized by long dis- tance, nested dependencies, lies at the foundation of natural language syntax. This motivates, for ex- ample, context-free languages (Chomsky, 1956), a (2 (2 (1 (1 (1 (1 )1 )1 )1 )1 )2 )2 the lawmaker makes the reporter questions Laws and are the lawmaker makes the reporter questions laws and are They see that (2 )2 (2 )2 Figure 1: (Top) This string of well-nested brackets is a member of the Dyck-(2,4) language; triangles denote the scopes of nested hierarchical dependencies, mir- roring the core of hierarchical structure in natural lan- guages. (Bottom) A fragment in English with similar nested dependencies denoted by triangles. fundamental paradigm for describing natural lan- guage syntax. A canonical family of context-free languages (CFLs) is Dyck-k, the language of bal- anced brackets of k types, since any CFL can be constructed via some Dyck-k (Chomsky and Sch¨utzenberger, 1959). However, while context-free languages like Dyck-k describe arbitrarily deep nesting of hier- archical structure, in practice, natural languages exhibit bounded nesting. This is clear in, e.g., bounded center-embedding (Karlsson, 2007; Jin et al., 2018) (Figure 1). To reflect this, we intro- duce and study Dyck-(k,m), which adds a bound m on the number of unclosed open brackets …

Content truncated to 500 words