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

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