How Can Self-Attention Networks Recognize D yck-n Languages? (2020)

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 performance of two variants of SA, one with a starting symbol (SA+) and one without (SA-). Our results show that SA+ is able to generalize to longer sequences and deeper dependencies. 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 interpretation and compatible with a stack-based language recognizer. Surprisingly, the performance of SA networks is at par with LSTMs, which provides evidence on the ability of SA to learn hierarchies without recursion.

## introduction there is a growing interest in using formal languages to study fundamental properties of neural architectures, which has led to the extraction of interpretable models @xcite . recent work @xcite @xcite has explored the generalized dyck-n (d n ) languages, a subset of context-free languages. d n consists of "wellbalanced" strings of parentheses with n different types of bracket pairs, and it is the canonical formal language to study nested structures @xcite . @xcite show that lstms @xcite are a variant of the k-counter machine and can recognize d 1 languages. the dynamic counting mechanisms, however, are not sufficient for d @xmath0. @xcite shows that for a sufficiently large length, transformers @xcite will fail to transduce the d 2 language. t ( [ ] ) [ ( ( ) ) ] t ( [ ] ) [ ( ( ) ) ]  2 t ( < > [ { } ] < > ) t ( < > [ { } ] < > ) figure 1 : softmax attention scores of the second layer of a suffix-masked sa + , for a d 2 and a d 4 sequence. the rows and columns denote queries and keys, respectively. the layer produces virtually hard attentions, in which each symbol attends only to one preceding symbol 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 d n languages, and generalize to longer sequences, although not perfectly. 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 stack, then it attends to "(", the last unmatched symbol, which will determine the next valid closing bracket. the starting symbol (t) enables the model to learn the occurrence of the end of a clause or the end of the sequence, which can be regarded as a mechanism to represent an empty stack. our work is the first to perform an empirical exploration of sa on formal languages. we present detailed comparison between an sa which incorporates a starting symbol (sa + ), and one that does not (sa -), and demonstrate significant differences in their generalization across the length of sequences and the depth of dependencies. recent work has suggested that the ability of self-attention mechanisms to model hierarchical structures is limited. @xcite show that the performance of transformers on tasks such as logical inference @xcite and listops @xcite is either poor or worse than lstms. @xcite have also reported similar results on sa, concluding that recurrence is necessary to model hierarchical structures. in comparison, our results show that sa + outperforms lstm on d n languages except for d 2 on longer sequences. papadimitriou and jurafsky (2020) posit that the ability of neural models to learn hierarchical structures can be attributed to a "looking back" capability, rather than directly encoding hierarchies. our analysis sheds light on the ability of sa to learn hierarchical structures by elegantly attending to the correct preceding symbol. ## related work formal languages such as a n b n , a n b n c m d m (context-free) and a n b n c n , a n+m b n c m (contextsensitive) have been extensively studied and recognized using rnns @xcite @xcite . but the performance of same recurrent architectures on d n languages is poor and suffers from the lack of generalization. @xcite and @xcite study the capability of rnns to predict the next possible closing parenthesis at each position in the d n string and found that the generalization at higher recursion depths is poor. @xcite reported that stack-augmented lstms achieve better generalization on d n languages but the network computation does not emulate a stack. more recently, @xcite proposed memory-augmented recurrent neural networks and defined a sequence classification task for the recognition of d n languages. @xcite explored the use of attention-based seq2seq framework for d 2 languages and found that the generalization to sequences with higher depths is still lacking. besides empirical investigations, formal languages have been studied theoretically for understanding the complexity of neural networks @xcite , mostly under assumptions that cannot be met in an experimentinfinite precision or unbounded computation time. ## experiments we follow prior works @xcite , and formulate the recognition of d n languages as a transduction task: given a valid string, we ask the model to predict the next possible symbols auto-regressively. to illustrate, consider an input string "[ ( ) ] ( [" in the d 2 language, we seek to predict the set of next valid brackets in the string-(, [, or ]. we consider an input to be accurately recognized only if the model correctly predicts the set of all possible brackets at each position in the input sequence. throughout the paper, we refer to a clause as a substring, in which the number of closing and opening brackets of each type of bracket are equal. we train two multi-headed self-attention networks (i.e., only the encoder part of a transformer), one of which incorporates an additional starting symbol in the vocabulary (sa + ), and the other does not (sa -). for each model, the number of layers is 2, the number of attention heads @xmath1. we use learnable embeddings to convert each input symbol to a 256-dimensional vector. we also add residual connections around each layer followed by layer normalization, similar to the standard transformer @xcite . we train two unidirectional lstms, one with the starting symbol (lstm + ) and the other without it (lstm -). the lstms use 320-dimensional hidden states and a 320-dimensional vector for learned input embeddings. our sa and lstm variants all have around 1.6m parameters foot_0 . we use adam (kingma and ba, 2015) for optimization. for sa + and sa -, we vary the learning rate η as we re-generate the synthetic dataset for our experiments through the probabilistic context-free grammar (pcfg) already described in the existing literature @xcite . for instance, the pcfg for dyck-2 language can be defined as: (1) s -→ [s], (2) s -→ {s}, (3) s -→ ss, and (4) s -→ ε, each with probability @xmath2.25. for each d n language, we train on 32k sequences of length 2-50, validate on 3.2k sequences of length 52-74, and evaluate on 10k sequences divided equally over the length intervals 76-100 and 102-126. figure 2 shows the distribution of length and depth of d 2 sequences in training and evaluation. for higher dyck languages (d @xmath3, the training and evaluation datasets have similar depth and length distributions because the pcfg give equal probability to different pairs of parentheses and the total probability for rules of the form s -→ (s), s -→ [s], ... is 0.5. we perform experiments on d 1 , d 2 , d 3 , and d 4 languages. note that the number of pairs of parentheses cannot be increased arbitrarily without requiring modifications to the experimental setup: we varied the length of sequences during training from 2 to 50, which could contain at most 25 different pairs. in our sequence prediction task, the input vocabulary (v i n ) for a d n language consists of 2n+1 symbols: n pairs of brackets (or parentheses), and an additional starting symbol t whereas the output vocabulary (v o n ) does not include the starting symbol t. since there might exist multiple possibilities for the next bracket in a sequence, we adopt a multi-label classification approach wherein the outputs are encoded as a k-hot vector and the network is optimized using the binary cross-entropy loss function given by ## compatibility with a stack-based recognizer the ability of (memory-less) sa networks to recognize d @xmath4. in this section, we contrast second-layer attention maps produced by sa + and sa -, and provide insights into the underlying mechanism which leads to the success of sa + . we define compatibility as a quantitative measure for the alignment of the state of a stack-based language recognizer (m ) with the attention maps. m has access to the top of a hypothetical stack, and can push and pop depending on the opening and closing brackets, respectively. based on this analogy, all opening brackets should attend to themselves, and all closing brackets should first do a pop, and then attend to the last unmatched bracket. for example, the symbol "]" in the string "([])", will first pop "[" from the stack, then it attends to "(", the last unmatched symbol, which will determine the next valid closing bracket. if for every closing symbol in the sequence, the highest attention score of at least one of the heads points to the correct bracket, then we consider the sa compatible. furthermore, for a fair comparison between sa + and sa -, we do not push the starting symbol to the stack and only consider closing brackets which are not at the end of a clause. t ( [ ( [ ] ) ] ) t ( [ ( [ ] ) ] ) a) attention-map (head-1) t ( [ ( [ ] ) ] ) t ( [ ( [ ] ) ] ) b) attention-map (head-2) t ( [ ( [ ] ) ] ) t ( [ ( [ ] ) ] ) c) attention-map (head-3) t ( [ ( [ ] ) ] ) t ( [ ( [ ] ) ] ) d) attention-map (head-4) ( [ ( [ ] ) ] ) ( [ ( [ ] ) ] ) ( [ ( [ ] ) ] ) ( [ ( [ ] ) ] ) ( [ ( [ ] ) ] ) ( [ ( [ ] ) ] ) ( [ ( [ ] ) ] ) ( [ ( [ ] ) ] ) 0.0 0.2 0.4 0.6 0.8 1.0 versus sequence length. we find that sa -on d 2 has almost zero compatibility, even for sequence lengths seen during training (40-50), on which it achieves close-to-perfect accuracy. in comparison, sa + has perfect compatibility for sequence lengths seen during training, and maintains a high degree of compatibility for longer ones. further, perhaps not surprisingly, the pearson correlation between the distribution of accuracy and compatibility across lengths 50-100 is 90% for all sa + models. figure 4 shows the attention maps of all four heads of sa + and sa -for the d 2 sequence "([([])])". we observe that the third head of sa + matches our expectation of a stack-based recognizer. an important feature of the third head is that the last symbol attends to the starting symbol t. the starting symbol has enabled the model to learn the occurrence of the end of a clause and the end of the whole sequence. ## conclusion and future work we provide empirical evidence on the ability of self-attention (sa) networks to learn generalized d n languages. we compare the performance of two sa networks, sa + and sa -, which differ only in the inclusion of a starting symbol in their vocabulary. we demonstrate that a simple addition of the starting symbol helps sa + generalize to sequences that are longer and have higher depths. the competitive performance of sa (no-recurrence) against lstms might seem surprising, considering that the recognition of d n languages is an inherently hierarchical task. from our experiments, we conclude that recognizing dyck languages is not tied to recursion, but rather learning the right representations to look up the head token. further, we find that the representations learned by sa + are highly interpretable and the network performs computations similar to a stack automaton. our results suggest formal languages could be an interesting avenue to explore the interplay between performance and interpretability for sa. comparisons between sa and lstm reveal interesting contrast between the two architectures which calls for further investigation. recent work @xcite shows how to express the transformer as an rnn through linearization of the attention mechanism, which could lay grounds for more theoretical analysis of these neural architectures (e.g., inductive biases and complexity.)