Self-attentive Biaffine Dependency Parsing

1 Introduction

As a fundamental task in NLP, dependency parsing has attracted a lot of research interest during the past decades due to its simplicity and multi-lingual applicability in capturing both syntactic and semantic information. Given an input sentence s = w0w1 . . . wn, a dependency tree, as depicted in Figure 1, is defined as d = {(h, m, l), 0 ≤ h ≤ n, 1 ≤ m ≤ n, l ∈ L}, where (h, m, l) is a dependency from the head word wh to the modifier word wm with the relation label l ∈ L, and w0 is a pseudo word that points to the root word.

In recent years, neural network based approaches have achieved remarkable improvement and outperformed the traditional discrete-feature based approaches in dependency parsing by a large margin [Chen and Manning, 2014; Dyer et al., 2015]. Most remarkably, Kiperwasser and Goldberg [2016] utilize BiLSTM as an encoder and achieve excellent results in both graph-based and transfer-based parsers. Based on this work, Dozat and Manning [2017] propose a simple yet effective deep biaffine graph-based parser and achieve the state-of-the-art accuracy on a variety of datasets and languages. The key of the biaffine parser is the use of multilayer BiLSTMs to fully and globally encode the input sentence, along with reasonable design of scoring architecture and good settings of hyperparameters such as dropouts and initialization choices.

∗Corresponding author

As an alternative for encoding input sequences, the selfattention mechanism has proven to be especially effective and achieved much higher performance on machine translation [Vaswani et al., 2017], known as the transformer. Intuitively, the self-attention mechanism is more suitable for capturing long-distance dependencies due to its capability of directly building connections between distant word pairs via attending. By contrast, the long-distance information may fade in the encoding process of BiLSTM. From another perspective, self-attention is also more efficient than the sequential BiLSTM since the attention computations of different tokens are independent and thus parallelizable.

In this work, we for the first time apply the self-attentionbased encoder to dependency parsing as the replacement of BiLSTMs and make an in-depth study on the the differences between the two techniques. Our experiments on both the English and Chinese datasets demonstrate that the two encoders achieve similar overall performance, but further detailed analysis reveals a lot of local divergence with regard to dependency distances.

We then employ model ensemble to combine the power of the self-attention and BiLSTM encoders, leading to consistent improvements over the homogeneous ensembles, which indicates that the two encoders are complementary in capturing contextual information.

Finally, we further improve parsing performance by making good use of external contextualized word representations (ELMo & BERT), and the new state-of-the-art parsing accuracy of 95.22 on English and 89.90 on Chinese.

2 The Biaffine Parser

Given an input sentence s = w0w1 . . .wn, where w0 is a pseudo word that represents the root node of the parse tree. The goal of dependency parsing is to find the highest-scoring dependency tree d∗ .

There exist two paradigms of dependency parsing, i.e., graph-based and transition-based approaches, depending on the definition of the scoring function score(s, d). In this work, we adopt the state-of-the-art deep biaffine parser as our basic parsing framework, which belongs to the graph-based paradigm and is proposed by Dozat and Manning [2017].

2.1 The Neural Network Architecture

Figure 2 shows the basic framework of the biaffine parser. The input layer maps each input word wi into a dense vector representation xi. In the original biaffine parser, xi is the concatenation of the word and the POS-tag embedding.

where embword wi is the pre-trained word embedding and embtag ti is the randomly initialized POS-tag embedding, which are both fine-tuned during training.

The encoder layer takes x0x1...xn as the input dense vectors, and produces context-aware word representations hi of all positions 0 ≤ i ≤ n. Presumably, the produced representation hi retains task-related sentence-level information and long-distance dependencies for word wi after proper training.

The biaffine parser of Dozat and Manning [2017] employs a multi-layer BiLSTM encoder. The first-layer BiLSTM sequentially encodes the input x0x1...xn in two independent directions, and the concatenated outputs of both directions are used as input for the second-layer BiLSTM, and so on. Finally, the outputs of the top-layer BiLSTM are used as the context-aware word representations hi. We omit the detailed equations of BiLSTMs due to space limitation.

In this work, we propose to employ the self-attention-based encoder instead of BiLSTMs, which will be introduced in Section 3.1 in detail.

The MLP representation layer takes the context-aware word representation hi as input, and use two separate MLPs to get two lower-dimensional representation vectors for each position 0 ≤ i ≤ n.

where rHi is the representation vector of wi as a head word, and rDi as a dependent. The MLP layer on the one hand reduces the dimension of hi, and more importantly on the other hand detains only syntax-related information in ri.

The biaffine scoring layer computes scores of all dependencies via a biaffine operation.

where score(i ← j) is the score of the dependency (j, i) and the matrix Wb is a biaffine parameter. Please note that scores of all dependencies can be efficiently computed at the same time in the matrix form.

2.2 Cross-entropy Training Loss

The parser defines a local cross-entropy loss for each position i. Assuming wj is the gold-standard head of wi, the corresponding loss is

2.3 Viterbi Decoding

Given the scores of all dependencies, the arc-factorization score of a dependency tree is

The highest-scoring tree d∗ can be decoded with the dynamic programming algorithm known as maximum spanning tree [McDonald et al., 2005].

2.4 Dependency Label Handling

The biaffine parser treats the classification of dependency labels as a separate task after finding d∗ . We denote the score of assigning a label l to a dependency i ← j as score(i ← j, l), which is also computed with biaffine operations. The unlabeled parsing task and the label classification task share most parameters except for the MLPs and biaffines.

3 Our Approach

In this work, we first propose to use the self-attention mechanism as the replacement of the BiLSTM-based encoder in dependency parsing. Then we explore the encoding capacity of both by model ensembles. Furthermore, we make in-depth empirical study on the use of the recently proposed contextualized word representations.

3.1 Self-Attention Encoder

As an encoding mechanism, self-attention has been successfully applied in several tasks. This work aims to make full investigation on how to effectively use self-attention in dependency parsing.

Similar to BiLSTM, the self-attention-based encoder takes x0x1...xn as the inputs, and produces context-aware word representations ri of all positions 0 ≤ i ≤ n. We employ a stack of N identical self-attention layers, each having independent parameters. Figure 3 illustrates the structure of an N-layered self-attention-based encoder. Each layer is composed of a multi-head attention sublayer and a feed-forward sublayer. Residual connection and layer normalization are applied to the outputs of the two sublayers.

In the following, we illustrate the first layer of the selfattention-based encoder in detail:

Position Embedding as Extra Input

Unlike BiLSTMs, the self-attention mechanism need to use an extra position embedding embpos i , in order to inject relative or absolute position information.

where embpos i is called the position embedding of the i-th position. We follow Vaswani et al. [2017] and use the sine and cosine functions of different frequencies to compose position embeddings.

where 2j and 2j + 1 are the even and odd indices of the position embedding, and dmodel is the dimension of embpos i . 1 In this way, each dimension of the positional encoding corresponds to a sinusoid, allowing the model to easily learn to attend to relative positions.

Multi-Head Attention Sublayer

The inputs xi (0 ≤ i ≤ n) are then fed into a multi-head attention layer. We use X ∈ R(n+1)×dmodel to represent the inputs in the matrix form.

1 We have also tried using a learned table of position embeddings as Kitaev and Klein [2018] did, but found a slight accuracy drop.

The basic idea of the self-attention mechanism is to reconstruct a representation vector for each position by attending to and aggregating the inputs of all positions. To be clearer, we begin with the single-head attention mechanism.

First, each input xi is mapped into three vectors.

The resulting three vectors are called query, key, value vectors respectively, and have the same dimension (denoted as dhead).

Then, the query vector of the focused position i attends to the key vectors of all positions, and the value vectors of all positions are aggregated according to normalized attention weights, producing the single-head representation of i (of dimension dhead).

where Z = ∑nj=0 eqi·kj/√dhead is the normalization factor, also known as a softmax process.

Multi-head attention uses m separate sets of projection matrices W1..m q/k/v to produce m independent representations, which are then concatenated as the representation of i.

Compared with single-head attention, multi-head attention is proven to be more effective due to the capability of representing the same position from different perspectives. Then, a linear map is used to mix different channels from different heads for each position i, following Tan et al. [2018].

Finally, residual connection and layer normalization [Ba et al., 2016] are performed.

Position-Wise Feed-Forward Sublayer

The outputs of the multi-head attention sublayer are then fed into a fully connected feed-forward network for each position i.

where W1 ∈ Rdff×dmodel , W2 ∈ Rdmodel×dff , b1 ∈ Rdff , and b2 ∈ Rdmodel are the parameters.

Similar to the multi-head attention sublayer, residual connection and layer normalization are also performed.

3.2 Model Ensemble

Model ensemble has been extensively adopted in real-life applications and shared task competitions [Petrov and McDonald, 2012; Zeman et al., 2018]. In this work, we employ ensemble to combine the power of both self-attention- and BiLSTM-based encoders due to their divergent but complementary capability of capturing contextual information.

In particular, we use the product of experts approach [Hinton, 2002] to combine predictions of 6 models. First, we separately train 6 parsers in the n-fold jack-knifing way, where each parser is trained on a 5/6 subset of the whole training data. During evaluation, we employ the 6 parsers to independently produce a probability for each dependency. We then use the averaged probability as the final probability of a dependency. Finally, we employ Viterbi decoding to produce the optimal tree according to the aggregated probabilities.

3.3 ContextualizedWord Representations

Recently proposed contextualized word representations, such as ELMo [Peters et al., 2018] and BERT [Devlin et al., 2018], have been shown to be extremely helpful in a variety of NLP tasks. The basic idea is to train a multi-layer LSTM- or selfattention-based encoder on large-scale unlabeled texts with the natural language model (or next-sentence prediction) loss.

In this work, we replace the word embeddings with the contextualized word representations as extra features without fine-tuning. We make a thorough comparison between ELMo and BERT for dependency parsing, and also experiment with different ways to combine the different encoder layers.

4 Experiments

We conduct experiments on the English Penn Treebank (PTB) dataset with Stanford dependencies and the Chinese dataset of the 2009 CoNLL shared task. For PTB, we directly use the data of Chen and Manning [2014], and they use the Stanford POS tagger. For Chinese CoNLL-2009, we use the data split and POS tags provided by the organizers [Hajic et al., 2009].

For evaluation metrics, we use the standard labeled attachment score (LAS, percent of words that receives correct heads and labels) and unlabeled attachment score (UAS, ignoring labels). Following previous work [Dozat and Manning, 2017], we ignore all punctuation marks for PTB and keep them for the Chinese CoNLL-2009 dataset.

Each parser is trained for at most 1, 000 iterations, and the performance is evaluated on the dev data after each iteration for model selection. We stop the training if the peak performance does not increase in 100 consecutive iterations.

For pre-trained word embeddings, we directly adopt the GloVe embeddings released by Stanford for English 2 , and train word2vec embeddings on Chinese Gigaword Third Edition for Chinese.

We directly use the English ELMo model released by AllenNLP 3 . For Chinese, we train ELMo for 10 iterations on the Chinese Gigaword Third Edition, consisting of about 1.2 million sentences. It takes about 7 days using 6 GPU nodes (GTX 1080Ti). For BERT, we use the released BERT-Base models for English (uncased) and Chinese. 4

2 https://nlp.stanford.edu/projects/glove/

3 https://github.com/allenai/allennlp/blob/master/tutorials/ how to/elmo.md

4 https://github.com/google-research/bert

4.1 Hyperparameter Choices

We mainly follow the work of Dozat and Manning [2017] for most of the hyperparameter settings, which uses three BiLSTM layers as the encoder. The dimensions of the word/tag/position embeddings are 100/100/200; dmodel is 200; dff is 800; head number m is 8, and thus dhead is 25; dropout ratio before residual connection is 0.2; dropout ratios before entering multi-head attention and feed-forward are both 0.1; all other dropout ratios are 0.33; β1 = 0.9, β2 = 0.98 and ϵ = 10-6 for the Adam optimizer.

Preliminary experiments show that the our parser using the self-attention encoder is insensitive to most of the above parameters, while the number of self-attention layers and the learning rate have larger impact on the performance as shown in the following results.

Depth of the Self-attention Encoder (N)

Table 1 shows the results with different numbers of selfattention layers on the dev data. Increasing the self-attention layer number from 4 to 8 consistently improves the performance on both English and Chinese datasets. The performance drops slightly when using 10 self-attention layers. These results indicate that the use of more self-attention layers increases the complexity of the model, allowing it to capture richer contextual information, but also makes the model prone to overfit the training data, which is consistent with previous findings [Vaswani et al., 2017; Tan et al., 2018].

Learning Rate

The results on the dev data with different learning rates are shown in Table 2. When we use the same learning rate 0.002 (or larger) as the original biaffine parser of Dozat and Manning [2017], the model converges quickly but achieves unsatisfactory performance. Reducing the value to certain extent improves the parsing accuracy. Based on the results, we set the learning rate to 0.0012 for English and 0.0011 for Chinese afterwards.

4.2 ContextualizedWord Representations

Instead of using the pretrained word embedding, we also experiment with contextualized word representations from both ELMo and BERT.

The results of ELMo are shown in Table 3. We can see that it leads to much better performance using only the third (top) layer outputs of ELMo than the first (bottom) layer outputs. We then use the weighted sum of all three layers, with the weight values learned during training, leading to further improvement on both English and Chinese. However, it is interesting to see that the simple averaged sum even slightly outperforms the weighted sum.

Table 3: Results of the self-attentive parser on the dev data regarding the different ways to use ELMo/BERT outputs.

Instead of replacing word embeddings with ELMo outputs, we also try to directly combine them, which decreases the performance, especially for Chinese. The reason may be that it is difficult for the model to reach a balance between word embeddings as shallow and context-free representations and ELMo outputs as deep and contextualized representations.

For BERT, We conduct the same experiments and find the trends are similar: using the averaged sum of the top-4 layer outputs is the best. We can see that BERT can greatly boost parsing accuracy over ELMo by about 2% for Chinese. The gain is much smaller (about 0.1-0.2%) for English since the performance is already at a high level.

4.3 Model Ensemble

The results for the model ensemble experiments are shown in Table 4. 3×SelfAtt+3×BiLSTM means among six training data folds, three are used to train three parsers with the selfattention encoder, and the remaining three are for those with the BiLSTM encoder.

First, compared with the results of single self-attentive parsers in Table 3, model ensemble can consistently improve parsing accuracy on both languages. For example, 6×SelfAtt with BERT outperforms the single self-attentive parser with BERT by 0.18 (94.87 vs. 94.69) on English and 0.53 (89.73 vs. 89.20) on Chinese in LAS.

Second, we can see that the 6×SelfAtt parsers achieve very similar results (slightly higher in most cases) compared with the 6×BiLSTM, showing that the two frameworks have similar power of encoding contextual information.

Finally and most importantly, we find that the hybrid 3×SelfAtt+3×BiLSTM ensembles achieve consistently higher accuracy than the homogeneous 6×SelfAtt/BiLSTM ensembles. This clearly demonstrates that the two encoding techniques are complementary and can certainly benefit from each other.

4.4 Final Results on the Test Data

Table 5 shows the final results and makes comparison with previous works on the test data. Our implemented biaffine parser with the BiLSTM-based encoder achieves slightly higher performance than the original results reported in Dozat and Manning [2017], and our proposed self-attentive parser outperforms our BiLSTM parser by small margin. In the ensemble setting (3×SelfAtt+3×BiLSTM), the ensemble models with BERT achieve the best performance, leading to new state-of-the-art results on both languages.

4.5 Analysis

Although the self-attention and BiLSTM encoders achieve very close overall parsing accuracy, we conduct more detailed analysis in order to gain more insights on the differences between them. We divide the gold-standard dependencies into seven subsets according to the absolute distance between the two words, and calculate the accuracy for each subset. Figure 4 compares the accuracy curves of the two single parsers with the self-attention or BiLSTM encoder with regard to the dependency distance on the test data. On the one hand, we can see that the two encoders actually exhibit divergent encoding power for dependencies of different distances. On the other hand, there seems no clear pattern on the wins and loses, indicating that self-attention and BiLSTM, as two different encoders, both have the competitive capability of capturing short- and long-range dependencies.

5 RelatedWork

LSTM, as the mainstream encoding technique, has been extensively used in many NLP tasks including parsing. Dyer et al. [2015] first apply LSTMs to encode history actions and partially built trees in a transition-based dependency parser. Kiperwasser and Goldberg [2016] utilize BiLSTM to encode the input sentence for both transition-based and graph-based dependency parsing. As the baseline of this work, Dozat and Manning [2017] propose a graph-based biaffine dependency parser which largely relies on a multi-layer BiLSTM encoder.

Self-attention has been successfully applied to neural machine translation by Vaswani et al. [2017], leading to large improvement on translation quality, known as the transformer. Foster et al. [2018] extend the transformer for machine translation by combining BiLSTM and self-attention encoders in a cascaded stacking architecture. In this work, we have also tried their method in dependency parsing, but found little improvement. So far, self-attention has been successfully applied to a variety of NLP tasks, such as language understanding [Shen et al., 2018] and semantic role labeling [Tan et al., 2018]. Most closely related to this work, Kitaev and Klein [2018] replace BiLSTM with self-attention in the constituent parser of Stern et al. [2017]. They propose two useful techniques to improve parsing performance, i.e., factored content and position attention and replacing POS-tag embeddings with CharLSTM word representations. In this work, we have also implemented the two techniques of Kitaev and Klein [2018], but our preliminary experiments show they are not helpful for dependency parsing.

Contextualized word representations are first proposed by Peters et al. [2018]. They train LSTM encoders on largescale unlabeled data with language model loss to obtain context-aware word representations, known as ELMo, which is shown to be extensively helpful for many NLP tasks. Radford et al. [2018] propose to pre-train transformer instead of the LSTM encoder on large-scale unlabeled corpus with language model loss, and finetune the model on the labeled data of the focused task, known as GPT. Devlin et al. [2018] further extend the idea of ELMo and GPT by 1) replacing the less efficient BiLSTM with self-attention, 2) using both bidirectional masked language model loss and next-sentence prediction loss, and 3) using a larger model and much more data. As another interesting direction, Clark et al. [2018] propose a semi-supervised learning framework to learn from both labeled and unlabeled data by designing clever auxiliary tasks, instead of using language model loss, leading to very promising performance on English dependency parsing.

Model ensemble is a commonly used strategy to integrate different parsing models in traditional discrete-feature dependency parsing [Nivre and McDonald, 2008]. Kuncoro et al. [2016] propose an knowledge distilling approach to train a graph-based neural parser on the voting results of many transition-based neural parsers trained with different initialization starts. Liu et al. [2018] propose to distill knowledge from the local classifiers employed by the transition-based parser.

6 Conclusions

This work for the first time applies the self-attention encoder to dependency parsing under the state-of-the-art graphbased biaffine parsing framework, obtaining competitive performance on both English and Chinese benchmark data. The comparative analysis shows that in spite of local divergences, the two encoders actually both have the power of modeling short- or long-range dependencies, which motivates us to extend our experiments into model ensembles. The hybrid ensemble models achieve consistently higher performance than the homogeneous ensemble ones, demonstrating that selfattention and BiLSTM are complementary in encoding contextual information. Furthermore, we find that proper utilization of the contextualized word representations substantially improves parsing accuracy, leading to new state-of-theart parsing performance.

Acknowledgments

We thank our anonymous reviewers for their helpful comments. This work was supported by National Natural Science Foundation of China (Grant No. 61525205, 61876116, 61432013), and was partially supported by the joint research project of Alibaba and Soochow University.