On the Practical Ability of Recurrent Neural Networks to Recognize Hierarchical Languages (2020)

Abstract: While recurrent models have been effective in NLP tasks, their performance on context-free languages (CFLs) has been found to be quite weak. Given that CFLs are believed to capture important phenomena such as hierarchical structure in natural languages, this discrepancy in performance calls for an explanation. We study the performance of recurrent models on Dyck-n languages, a particularly important and well-studied class of CFLs. We find that while recurrent models generalize nearly perfectly if the lengths of the training and test strings are from the same range, they perform poorly if the test strings are longer. At the same time, we observe that RNNs are expressive enough to recognize Dyck words of arbitrary lengths in finite precision if their depths are bounded. Hence, we evaluate our models on samples generated from Dyck languages with bounded depth and find that they are indeed able to generalize to much higher lengths. Since natural language datasets have nested dependencies of bounded depth, this may help explain why they perform well in modeling hierarchical dependencies in natural language data despite prior works indicating poor generalization performance on Dyck languages. We perform probing studies to support our results and provide comparisons with Transformers.

## introduction recurrent models (rnns and more specifically lstms) have been used extensively across several nlp tasks such as machine translation @xcite , language modeling @xcite and question answering @xcite . natural languages involve phenomena such as hierarchical and long-distance dependencies. although rnns are known to be turing-complete @xcite given unbounded precision, their practical ability to model such phenomena remains unclear. recently, several works @xcite @xcite ) have attempted to understand the capabilities of lstms by empirically analyzing them on different types of formal languages. natural languages, for the most part, can be modeled by context-free languages @xcite and their hierarchical structure has been emphasized by @xcite . thus studying the capabilities of rnns in recognizing context-free languages (cfls) can shed light on how well they can model hierarchical structures. an important family of context-free languages is the dyck-n language 1 . previous works @xcite @xcite showed that lstms achieve limited generalization performance on recognizing dyck-2. this prompted the development of memory-augmented variants @xcite of lstms which generalize well on dyck languages but are notoriously hard to train and fail to perform well on practical nlp tasks @xcite . on the other hand, despite the limited performance of lstms on dyck languages, several studies @xcite have found that lstms perform well in modeling hierarchical structure in natural language data. in this work, we take a step towards bridging this gap. they say all the prayers those priests preach, and the boy hears were written centuries ago. ## preliminaries and motivation the language dyck-n parameterized by @xmath0. its derivation rules are: @xmath1, @xmath2, @xmath3, . . . , n}. dyck-n is context-free for every n, dyck-2 being crucial among them, since all dyck-n for @xmath4. for words in dyck-n, the required depth of the stack in its underlying pda is the maximum number of unbalanced parentheses in a prefix. for instance, the word ( [ ( ) ] ) [ ] in dyck-2 has maximum depth of 3 corrsponding to the prefix ( [ (. rnns. rnns are defined by the update rule h @xmath5, x t ), where the function f could be a feedforward network, h t is the model's memory vector usually referred to as the hidden state vector and x t denotes the input vector at the t-th step. in practice, f is usually a single layer feedforward network with tanh or relu activation. to mitigate the vanishing gradients problem, lstms @xcite , a variant of rnns with additional gates, is most commonly used in practice. in our experiments, we will primarily work with lstms. ## discussion lstms and transformers have been effective on language modeling tasks. in practice, during language modeling on a natural language corpus, the entire input is fed sequentially to the lstm. hence, the length of the input processed by the lstm is bound to be large, requiring it to model a number of figure 3 nested dependencies. prior works in psycholinguistics @xcite have pointed out that given limited working memory of humans, natural language as used in practice should have nested dependencies of bounded depth. some works @xcite have even sought to build parsers for natural language with depth-bounded pcfgs. our generalization results for lstms on depth-bounded cfgs could help explain why they perform well on modeling hierarchical dependencies in natural language datasets. for transformer, although it did not generalize to higher lengths, but in practice transformers (as used in bert and gpt) process inputs in a fixed-length context window. our results indicate that it does not have trouble in generalizing when the train and validation sets contain inputs of the same lengths. our experiments also demonstrate that the limiting factor in lstms is in generalizing to higher depths as opposed to its memory-augmented variants. the exact mechanism with which trained lstms perform the task is not entirely clear. the limited performance of lstms could be due to precision issues or unstable stack encoding mechanism @xcite . however, given that natural language datasets are likely to have nested dependencies of bounded depth, this limitation may not play a significant role and may help explain why prior works @xcite have found lstms to perform well in modeling hierarchical structure on natural language datasets.