How Can Self-Attention Networks Recognize Dyck-n Languages?

Findings of the Association for Computational Linguistics: EMNLP 2020, pages 4301–4306 November 16 - 20, 2020. c⃝2020 Association for Computational Linguistics 4301 How Can Self-Attention Networks Recognize Dyck-n Languages? Javid Ebrahimi, Dhruv Gelda, Wei Zhang Visa Research, Palo Alto, USA {jebrahim,dhgelda,wzhan}@visa.com Abstract We focus on the recognition of Dyck-n (Dn) languages with self-attention (SA) networks, which has been deemed to be a difficult task for these networks. We compare the perfor- mance of two variants of SA, one with a start- ing symbol (SA+) and one without (SA−). Our results show that SA+ is able to general- ize to longer sequences and deeper dependen- cies. For D2, we find that SA− completely breaks down on long sequences whereas the accuracy of SA+ is 58.82%. We find attention maps learned by SA+ to be amenable to in- terpretation and compatible with a stack-based language recognizer. Surprisingly, the perfor- mance of SA networks is at par with LSTMs, which provides evidence on the ability of SA to learn hierarchies without recursion. 1 Introduction There is a growing interest in using formal lan- guages to study fundamental properties of neural architectures, which has led to the extraction of in- terpretable models (Weiss et al., 2018; Merrill et al., 2020). Recent work (Hao et al., 2018; Suzgun et al., 2019; Skachkova et al., 2018) has explored the generalized Dyck-n (Dn) languages, a subset of context-free languages. Dn consists of “well- balanced” strings of parentheses with n different types of bracket pairs, and it is the canonical formal language to study nested structures (Chomsky and Sch¨utzenberger, 1959). Weiss et al. (2018) show that LSTMs (Hochreiter and Schmidhuber, 1997) are a variant of the k-counter machine and can rec- ognize D1 languages. The dynamic counting mech- anisms, however, are not sufficient for Dn>1 as it requires emulating a pushdown automata. Hahn (2020) shows that for a sufficiently large length, Transformers (Vaswani et al., 2017) will fail to transduce the D2 language. We empirically show that with the addition of T ( [ ] ) [ ( ( ) ) ] ))(([)][(T ] 2 T ( < > [ { } ] < > ) <(T > <]}{[ > ) 4 Figure 1: Softmax attention scores of the second layer of a suffix-masked SA+, for a D2 and a D4 sequence. The rows and columns denote queries and keys, respec- tively. The layer produces virtually hard attentions, in which each symbol attends only to one preceding sym- bol or itself. The attended symbol is either the starting symbol (T) or the last unmatched opening bracket. a starting symbol to the vocabulary, a two-layer multi-headed SA network (i.e., the encoder of a Transformer) is able to learn Dn languages, and generalize to longer sequences, although not per- fectly. As shown in Figure 1, the network is able to identify the corresponding closing bracket for an opening bracket, in what resembles a stack-based automaton. For example, the symbol “]” in the string “([])”, will first pop “[” from the …

Content truncated to 500 words