RNN s can generate bounded hierarchical languages with optimal memory (2020)

Abstract: Recurrent neural networks empirically generate natural language with high syntactic fidelity. However, their success is not well-understood theoretically. We provide theoretical 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 syntax. 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 dependencies of natural language syntax. The best known results use O(k^{\frac{m}{2}}) memory (hidden units) to generate these languages. We prove that an RNN with O(m \log k) hidden units suffices, an exponential reduction in memory, by an explicit construction. Finally, we show that no algorithm, even with unbounded computation, can suffice with o(m \log k) hidden units.

## 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 empirical 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 efficiently generate a family of bounded hierarchical languages. these languages form the scaffolding of natural language syntax. hierarchical structure characterized by long distance, nested dependencies, lies at the foundation of natural language syntax. this motivates, for example, context-free languages (chomsky, 1956), a fundamental paradigm for describing natural language syntax. a canonical family of context-free languages (cfls) is dyck-k, the language of balanced brackets of k types, since any cfl can be constructed via some dyck-k (chomsky and schützenberger, 1959). however, while context-free languages like dyck-k describe arbitrarily deep nesting of hierarchical 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 introduce and study dyck-(k,m), which adds a bound m on the number of unclosed open brackets at any time. informally, the ability to efficiently generate dyck-(k,m) suggests the foundation of the ability to efficiently generate languages with the syntactic properties of natural language. see §(1.1) for further motivation for bounded hierarchical structure. in our main contribution, we prove that rnns are able to generate dyck-(k,m) as memory-efficiently as any model, up to constant factors. since dyck-(k,m) is a regular (finite-state) language, the application of general-purpose rnn constructions trivially proves that rnns can generate the language (merrill, 2019). however, the best construction we are aware of uses o(k m foot_0 ) hidden units (horne and hush, 1994; indyk, 1995), where k is the vocabulary size and m is the nesting depth, which is exponential. @xcite we provide an explicit construction proving that a simple (elman; elman (1990)) rnn can generate any dyck-(k,m) using only 6m log k -2m = o(m log k) hidden units, an exponential improvement. this is not just a strong result relative to rnns' general capacity; we prove that even computationally unbounded models generating dyck-(k,m) require ω(m log k) hidden units, via a simple communication complexity argument. our proofs provide two explicit constructions, one for the simple rnn and one for the lstm, which detail how these networks can use their hidden states to simulate stacks in order to efficiently generate dyck-(k,m). the differences between the constructions exemplify how lstms can use exclusively their gates, ignoring their simple rnn subcomponent entirely, to reduce the memory by a factor of 2 compared to the simple rnn. @xcite we prove these results under a theoretical setting that aims to reflect the realistic settings in which rnns have excelled in nlp. first, we assume finite precision; the value of each hidden unit is represented by @xmath0. this has drastic implications compared to existing work (siegelmann and sontag, 1992; weiss et al., 2018; merrill, 2019; merrill et al., 2020). it implies that only regular languages can be generated by any machine with d hidden units, since they can take on only 2 pd states (korsky and berwick, 2019). this points us to focus on whether languages can be implemented memory-efficiently. second, we consider networks as language generators, not acceptors; foot_1 informally, rnns' practical successes have been primarily as generators, like in language modeling and machine translation (karpathy et al., 2015; wu et al., 2016). finally, we include a preliminary study in learn- @xcite for hard-threshold neural networks, the lower-bound would be ω(k m ing dyck-(k,m) with lstm lms from finite samples, finding for a range of k and m that learned lstm lms extrapolate well given the hidden sizes predicted by our theory. in summary, we prove that rnns are memory optimal in generating a family of bounded hierarchical languages that forms the scaffolding of natural language syntax by describing mechanisms that allow them to do so; this provides theoretical insight into their empirical success. ## formal results we now state our results. we provide intuitive proof sketches in the next section, and leave the full proofs to the appendix. we start with an application of known work to prove that dyck-(k,m) can be generated by rnns. theorem 1 (naive generation of dyck-(k,m)). for any k, @xmath1, there exists a simple rnn f θ with o(k m+1 ) hidden units that generates dyck-(k,m). the proof follows by first recognizing that there exists a deterministic finite automaton (dfa) with o(k m+1 ) states that generates dyck-(k,m). each state of the dfa is a sequence of up to m unclosed brackets (of k possible types), implying k m+1 -1 total states. then, one applies a general-purpose algorithm for implementing dfas with |q| states using an rnn with o(|q|) hidden units (omlin and giles, 1996; merrill, 2019). intuitively, this construction assigns a separate hidden unit to each state. @xcite for our results, we first present two theorems for the simple rnn and lstm that use o(mk) hidden units by simulating a stack of m o(k)dimensional vectors, which are useful for discussing the constructions. then we show how to reduce to o(m log k) via an efficient encoding of k symbols in o(log k) space. theorem 2. for any k, @xmath2, there exists a simple rnn f θ with 2mk hidden units that generates dyck-(k,m). we state 2mk exactly instead of o(mk) because this exactness is interesting and the constant is small; further, we find that the modeling power of the lstm leads to a factor of 2 improvement: theorem 3. for any k, @xmath3, there exists a lstm f θ with mk hidden units and w @xmath4,m). we point out the added property that w @xmath5, informally, this matrix corresponds to the recurrent matrix w of the simple rnn; it's the only matrix operating on lstm's memory that isn't used in computing a gate. thus, the lstm we provide as proof uses only its gates. using the same mechanisms as in the proofs above but using an efficient encoding of each stack element in o(log k) units, we achieve the following. theorem 4. for any k, @xmath6, where @xmath7, there exists a simple rnn f θ with 6m log k -2m hidden units that generates dyck-(k,m). likewise, for lstms, we achieve a more memory-efficient generator. @xcite the construction of indyk (1995) may achieve o( |q|) in this case (they do not discuss how vocabulary size affects construction size), but this is still o(k m 2 ) and thus intractable. theorem 5. for any k, @xmath8, where @xmath9, there exists an lstm f θ with 3m log k -m hidden units and w @xmath10,m). ## stack constructions in simple rnns the memory needed to close all the brackets in a dyck-(k,m) prefix w 1:t can be represented as a stack of (yet unclosed) open brackets [ i 1 , . . . , i m ], @xmath11; reading each new parenthesis either pushes or pops from this stack. informally, all of our efficient rnn constructions generate dyck-(k,m) by writing to and reading from an implicit stack that they encode in their hidden states. in this section, we present some challenges in a naive approach, and then describe a construction to solve these challenges. we provide only the high-level intuition; rigorous proofs are provided in the appendix. ## stack construction in lstms we could implement our 2mk simple rnn construction in an lstm, but its gating functions suggest more flexibility in memory management, and levy et al. (2018) claim that the lstm's modeling power stems from its gates. with an lstm, we achieve the mk of the oracle we described, all while exclusively using its gates. ## experiments our proofs have concerned constructing rnns that generate dyck-(k,m); now we present a short study connecting our theory to learning dyck-(k,m) from finite samples. in particular, for @xmath12, 8, 32, 128} and @xmath13, 5}, we use our theory to set the hidden dimensionality of lstms to 3m log k -m, and train them as lms on samples from a distribution 17 over dyck-(k,m). for space, we provide an overview of the experiments, with details in the appendix. we evaluate the models' abilities to extrapolate to unseen lengths by setting a maximum length of 84 for @xmath14, and 180 for @xmath15, and testing on sequences longer than those seen at training time. @xcite for our evaluation metric, let p j be the probability that the model predicts the correct closing bracket given that j tokens separate it from its open bracket. we report mean j p j , to evaluate the model's bracket-closing memory. for all configurations, we find that the lstms using our memory limit achieve error less than 10 -4 when trained on 20 million tokens. strikingly, this is despite the fact that for large m and k, a small fraction of the possible stack states is seen at training time; 19 this shows that the lstms are not simply learning k m structureless dfa states. learning curves are provided in figure 3 . ## discussion and conclusion we proved that finite-precision rnns can generate dyck-(k,m), a canonical family of bounded-depth hierarchical languages, in o(m log k) memory, a result we also prove is tight. our constructions provide insight into the mechanisms that rnns and lstms can implement. the chomsky hierarchy puts all finite memory languages in the single category of regular languages. but humans generating natural language have finite memory, and context-free languages are known to be both too expressive and not expressive enough (chomsky, 1959; joshi et al., 1990). we thus suggest the further study of what structure networks can encode in their memory (here, stack-like) as opposed to ( just