On the Ability and Limitations of Transformers to Recognize Formal Languages

Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, pages 7096–7116, November 16–20, 2020. c⃝2020 Association for Computational Linguistics 7096 On the Ability and Limitations of Transformers to Recognize Formal Languages Satwik Bhattamishra♠ Kabir Ahuja♦∗ Navin Goyal♠ ♠ Microsoft Research India ♦ Udaan.com {t-satbh,navingo}@microsoft.com kabir.ahuja@udaan.com Abstract Transformers have supplanted recurrent mod- els in a large number of NLP tasks. However, the differences in their abilities to model dif- ferent syntactic properties remain largely un- known. Past works suggest that LSTMs gener- alize very well on regular languages and have close connections with counter languages. In this work, we systematically study the ability of Transformers to model such languages as well as the role of its individual components in doing so. We first provide a construction of Transformers for a subclass of counter lan- guages, including well-studied languages such as n-ary Boolean Expressions, Dyck-1, and its generalizations. In experiments, we find that Transformers do well on this subclass, and their learned mechanism strongly corre- lates with our construction. Perhaps surpris- ingly, in contrast to LSTMs, Transformers do well only on a subset of regular languages with degrading performance as we make languages more complex according to a well-known mea- sure of complexity. Our analysis also provides insights on the role of self-attention mecha- nism in modeling certain behaviors and the influence of positional encoding schemes on the learning and generalization abilities of the model. 1 Introduction Transformer (Vaswani et al., 2017) is a self- attention based architecture which has led to state- of-the-art results across various NLP tasks (Devlin et al., 2019; Liu et al., 2019; Radford et al., 2018). Much effort has been devoted to understand the inner workings and intermediate representations of pre-trained models; Rogers et al. (2020) is a recent survey. However, our understanding of their practi- cal ability to model different behaviors relevant to sequence modeling is still nascent. ∗This research was conducted during the author’s intern- ship at Microsoft Research. Regular Context-Free Context-Sensitive Recursively�Enumerable Counter Figure 1: Counter languages form a strict superset of regular languages, and are a strict subset of context- sensitive languages. Counter and context-free lan- guages have a nonempty intersection and neither set is contained in the other. On the other hand, a long line of research has sought to understand the capabilities of recurrent neural models such as the LSTMs (Hochreiter and Schmidhuber, 1997) . Recently, Weiss et al. (2018), Suzgun et al. (2019a) showed that LSTMs are ca- pable of recognizing counter languages such as Dyck-1 and anbn by learning to perform counting like behavior. Suzgun et al. (2019a) showed that LSTMs can recognize shuffles of multiple Dyck- 1 languages, also known as Shuffle-Dyck. Since Transformer based models (e.g., GPT-2 and BERT) are not equipped with recurrence and start compu- tation from scratch at each step, they are incapable of directly maintaining a counter. Moreover, it is known that theoretically RNNs can recognize any regular language in finite precision, and LSTMs work well for this task in …

Content truncated to 500 words