Can Recurrent Neural Networks Learn Nested Recursion?

LiLT volume 16, issue (1) July 2018 Can Recurrent Neural Networks Learn Nested Recursion? JEAN-PHILIPPE BERNARDY, Centre for Linguistic Theory and Studies in Probability (CLASP), Department of Philosophy, Linguistics and Theory of Science, University of Gothenburg. 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 recur- rent 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 per- fect. Additionally, we propose some non-standard stack-based models which can approach perfect accuracy, at the cost of robustness. 1 2 / LILT VOLUME 16, ISSUE (1) JULY 2018 1 Introduction In many settings, Recurrent Neural Networks (RNNs) act as generative lan- guage 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 de- scent. 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 pa- rameters are also linearly dependent on the error in the output. RNNs need non-linear components as well, which allows them to model complex (non- linear) relations between inputs and outputs. Popular RNNs functioning on these principles include the long short-term memory (LSTM) (Hochreiter and Schmidhuber, 1997), and the gated recurrent unit (GRU) (Cho et al., 2014). Thanks to their versatility, relative ease of training and ability to model long-term dependencies, RNNs have become the leading tool for natural lan- guage processing. For example, Karpathy et al. (2015) and Karpathy (2016) show that RNNs can model Shakespeare plays, Wikipedia articles, algebraic geometry papers and modules …

Content truncated to 500 words