Self-Attention Networks Can Process Bounded Hierarchical Languages

Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing, pages 3770–3785 August 1–6, 2021. ©2021 Association for Computational Linguistics 3770 Self-Attention Networks Can Process Bounded Hierarchical Languages Shunyu Yao† Binghui Peng‡ Christos Papadimitriou‡ Karthik Narasimhan† †Princeton University ‡Columbia University {shunyuy, karthikn}@princeton.edu {bp2601, christos}@columbia.edu Abstract Despite their impressive performance in NLP, self-attention networks were recently proved to be limited for processing formal languages with hierarchical structure, such as Dyckk, the language consisting of well-nested parenthe- ses of k types. This suggested that natural language can be approximated well with mod- els that are too weak for formal languages, or that the role of hierarchy and recursion in nat- ural language might be limited. We qualify this implication by proving that self-attention networks can process Dyckk,D, the subset of Dyckk with depth bounded by D, which ar- guably better captures the bounded hierarchi- cal structure of natural language. Specifically, we construct a hard-attention network with D + 1 layers and O(log k) memory size (per token per layer) that recognizes Dyckk,D, and a soft-attention network with two layers and O(log k) memory size that generates Dyckk,D. Experiments show that self-attention networks trained on Dyckk,D generalize to longer inputs with near-perfect accuracy, and also verify the theoretical memory advantage of self-attention networks over recurrent networks.1 1 Introduction Transformers (Vaswani et al., 2017) are now the undisputed champions across several benchmark leaderboards in NLP. The major innovation of this architecture, self-attention, processes input tokens in a distributed way, enabling efficient parallel com- putation as well as long-range dependency mod- elling. The empirical success of self-attention in NLP has led to a growing interest in studying its properties, with an eye towards a better understand- ing of the nature and characteristics of natural lan- guage (Tran et al., 2018; Papadimitriou and Juraf- sky, 2020). 1Code is available at https://github.com/ princeton-nlp/dyck-transformer. In particular, it was recently shown that self- attention networks cannot process various kinds of formal languages (Hahn, 2020; Bhattamishra et al., 2020a), among which particularly notable is Dyckk, the language of well-balanced brackets of k types. By the Chomsky-Schützenberger Theorem (Chom- sky and Schützenberger, 1959), any context-free language can be obtained from a Dyckk language through intersections with regular languages and homomorphisms. In other words, this simple lan- guage contains the essence of all context-free lan- guages, i.e. hierarchical structure, center embed- ding, and recursion – features which have been long claimed to be at the foundation of human language syntax (Chomsky, 1956). Consider for example the long-range and nested dependencies in English subject-verb agreement: (Laws (the lawmaker) [writes] [and revises]) [pass]. . . . The sentence structure is captured by Dyck2 string (()[][])[]. Given the state-of-the-art performance of Transformers in parsing natural language (Zhang et al., 2020; He and Choi, 2019), the Dyckk blind spot seems very suggestive. If the world’s best NLP models cannot deal with this simple language — generated by a grammar with k + 2 rules …

Content truncated to 500 words