Can Recurrent Neural Networks Learn Nested Recursion? (2018)

Abstract: Context-free grammars (CFG) were one of the first formal tools used to model natural languages, and they remain relevant today as the basis of several frameworks. A key ingredient of CFG is the presence of nested recursion. In this paper, we investigate experimentally the capability of several recurrent neural networks (RNNs) to learn nested recursion. More precisely, we measure an upper bound of their capability to do so, by simplifying the task to learning a generalized Dyck language, namely one composed of matching parentheses of various kinds. To do so, we present the RNNs with a set of random strings having a given maximum nesting depth and test its ability to predict the kind of closing parenthesis when facing deeper nested strings. We report mixed results: when generalizing to deeper nesting levels, the accuracy of standard RNNs is significantly higher than random, but still far from perfect. Additionally, we propose some non-standard stack-based models which can approach perfect accuracy, at the cost of robustness.

## introduction in many settings, recurrent neural networks (rnns) act as generative language models. that is, given a prefix, they predict the likelihood of the next symbol. this probability is expressed as a continuous function of parameters (typically millions), which can be optimized (or trained) using gradient descent. by definition, rnns are constructed by repeating a simple component, often called a cell, each cell taking care of one time-step. additionally each cell passes some information to the cell at the next timestep. this information can be understood as an internal (so called "hidden") state, which can be used by the rnn to represent the input seen so far. rnns can additionally be used for a variety of tasks such as input classification (e.g. sentiment analysis) or translation tasks. the key ingredient to well-performing rnns is to have each cell update the state by using a linear combination of the previous state and a new value. this linearity means that the current timestep depends linearly on symbols which occur much earlier in the input, and, in turn, the gradients of the parameters are also linearly dependent on the error in the output. rnns need non-linear components as well, which allows them to model complex @xcite relations between inputs and outputs. popular rnns functioning on these principles include the long short-term memory (lstm) @xcite , and the gated recurrent unit (gru) @xcite . thanks to their versatility, relative ease of training and ability to model long-term dependencies, rnns have become the leading tool for natural language processing. for example, @xcite and @xcite show that rnns can model shakespeare plays, wikipedia articles, algebraic geometry papers and modules of the linux source code. while experts in either domain will quickly recognize the generated samples as nonsense, they nonetheless broadly exhibit the syntactic structure that one would expect, both for small-scale (words, function names) and large-scale elements (e.g. stanzas, complex c-code statements). yet understanding how precisely they learn how to generalize is an open question. even experienced computational linguists use words such as "amazing" or even "magic" to describe them, betraying that it remains mysterious how, simply by performing arithmetic operations, the rnn can effectively mimic human linguistic production @xcite . unfortunately this combination of poor understanding and enthusiasm may lead less experienced researchers into believing that the capabilities of lstm rnns are limitless, and that, with enough data, they can model any language you throw at them. in particular, because @xcite shows that their models can generate text which appears to adhere to the rules of a context-free grammar, one might draw the conclusion that lstm rnns are in fact suitable to learn context-free languages from a set of real-world examples. but can they? unfortunately, the generated samples only show display shallow recursion depths, so one cannot conclude that they model nested recursion -which is one of the defining features of the venerable context-free grammars (cfg). (whether or not nested recursion is a fundamental feature of natural languages has been the subject of a fierce debate. while we do not wish to take sides in that debate, we do acknowledge the importance of recursion when modeling syntax.) in this paper we measure an upper bound on the capability of various rnns to learn nested recursion, by focusing on a simpler problem than that of learning context-free languages. more precisely, we investigate experimentally the ability of rnns to learn a nested recursion in a language composed of balanced parentheses of various kinds. thus, the results presented here apply directly to formal languages rather than natural languages. the present work is part of an effort in the computational linguistic community to understand the capabilities of neural networks. we discuss previous work, including that of @xcite , in section 6. we test the lstm, gru, and a special purpose recurrent unit with a stack-like state (hereafter referred to as russ), and combinations thereof (section 2). we test the ability to learn both the plain dyck language (with a kind pair of parentheses, see section 4) and a generalization of it, with several kinds of parentheses (section 5) -the precise definition of the language can be found in section 3. ## models we experiment with lstms, grus and russs, sometimes in combination. in this section we give the precise definition of each of the components. ## generalized-dyck language let us define the language d p as the set of strings generated by the following context-free rules, dependent on a set p of matching parenthesis pairs. s ::= e# e ::= oec for every (o, c) 2 p e ::= ee e ::= " let us further call d n p the subset of d p composed of strings of length n + 1 (adding one to account for the termination character (#)), and d (n) p the the subset of d composed of strings of length n + 1 or less. we start by checking that rnns can learn recursion in a dyck language with a single pair of parentheses. thus we let p be {(, )}. in this experiment, we train rnns on strings in d 14 p and test it on all strings in d 18 p . the training set is a subset of 512 strings picked at random in d 14 p . (#d 14 @xmath0.) while it is customary to select a large training set and a small test set, we do the opposite here because 1. the language is small enough to test in its entirety and 2. we want to train our model on a data set which does not cover the whole language. recall that rnns predict the probability of any given character, knowing the previous characters in the string. however, in a dyck language with a single pair of possible parentheses, the next character is only restricted in the situation when all opening parentheses have been closed -in which case the general trends). because using embeddings has little to no impact on the complexity of the models, we stuck to this choice in the reported experiments.