Can the Transformer Learn Nested Recursion with Symbol Masking?

Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021, pages 753–760 August 1–6, 2021. ©2021 Association for Computational Linguistics 753 Can the Transformer Learn Nested Recursion with Symbol Masking? Jean-Philippe Bernardy Adam Ek Vladislav Maraev Centre for Linguistic Theory and Studies in Probability Department of Philosophy, Linguistics and Theory of Science University of Gothenburg firstname.lastname@gu.se Abstract We investigate if, given a simple symbol mask- ing strategy, self-attention models are capable of learning nested structures and generalise over their depth. We do so in the simplest set- ting possible, namely languages consisting of nested parentheses of several kinds. We use encoder-only models, which we train to pre- dict randomly masked symbols, in a BERT- like fashion. We find that the accuracy is well above random baseline, with accuracy consis- tently above 50% both when increasing nest- ing depth and distances between training and testing. However, we find that the predic- tions made correspond to a simple parenthesis counting strategy, rather than a push-down au- tomaton. This suggests that self-attention mod- els are not suitable for tasks which require gen- eralisation to more complex instances of recur- sive structures than those found in the training set. 1 Introduction Self-attention models (Vaswani et al., 2017) enjoy broad use in NLP tasks. The best attention-based models can tackle several tasks using a unified sen- tence encoding (and perhaps decoding) module (Raffel et al., 2020), with applications ranging from classification to inference and generation. They provide state of the art results for all such tasks, displacing the already very successful recurrent neural networks, in particular the LSTM and its variants. The availability of large pretrained mod- els (Devlin et al., 2019) is another strong point in their favour. However, the generalisation capabilities of self- attention models are still not well understood, and the present work is part of an ongoing effort to un- derstand their capabilities. We study in particular their ability to learn context-free languages, which are characterised by the nested structures. For this purpose, we control the inputs to the model to the maximum, while focusing on the defining charac- teristic of context-free languages, namely matching opening and closing brackets. This corresponds to learning generalised Dyck languages (see table 2). In particular, we investigate the following ques- tions: 1. Can self-attention generalise to matching open/close parenthesis at longer distances? 2. Can self-attention generalise to matching open/close parenthesis at deeper nesting levels distances? There is a already a small body of work dealing with this question (see sec. 5), but our contribu- tion is specific in the following two respects: i) We use the popular BERT-like training regime (pre- dict a percentage of randomly masked tokens), ii) We concentrate on generalising to (much) deeper nesting. Beyond theoretical considerations, matching brackets have applications in the NLP-style treat- ment of constructed languages (in particular) pro- gramming languages, for example translating be- tween programs and their natural language descrip- tions. 2 Data Sets We define the language Dn as the set of strings gen- erated by the …

Content truncated to 500 words