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

Proceedings of the 28th International Conference on Computational Linguistics, pages 1481–1494 Barcelona, Spain (Online), December 8-13, 2020 1481 On the Practical Ability of Recurrent Neural Networks to Recognize Hierarchical Languages Satwik Bhattamishra♠ Kabir Ahuja♦∗ Navin Goyal♠ ♠ Microsoft Research India ♦ Udaan.com {t-satbh,navingo}@microsoft.com kabir.ahuja@udaan.com 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 recurrent models 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. 1 Introduction Recurrent models (RNNs and more specifically LSTMs) have been used extensively across several NLP tasks such as machine translation (Sutskever et al., 2014), language modeling (Melis et al., 2017) and question answering (Seo et al., 2016). Natural languages involve phenomena such as hierarchical and long-distance dependencies. Although RNNs are known to be Turing-complete (Siegelmann and Sontag, 1992) given unbounded precision, their practical ability to model such phenomena remains unclear. Recently, several works (Weiss et al., 2018; Sennhauser and Berwick, 2018; Skachkova et al., 2018) 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 (Jger and Rogers, 2012) and their hierarchical structure has been emphasized by Chomsky (2002). 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 language1. Previous works (Suzgun et al., 2019a; Suzgun et al., 2019c; Yu et al., 2019) showed that LSTMs achieve limited generalization performance on recognizing Dyck-2. This prompted the development of memory-augmented variants (Joulin and Mikolov, 2015; Suzgun et al., 2019c) of LSTMs which generalize well on Dyck languages but are notoriously hard to train and fail to perform well on practical NLP tasks (Shen et al., 2019). On the other hand, despite the limited performance of LSTMs on Dyck languages, several studies (Gulordava et al., 2018; Tran et al., 2018) have found that LSTMs perform …

Content truncated to 500 words