Title: DEEP BIAFFINE ATTENTION FOR NEURAL DEPENDENCY PARSING

Abstract: This paper builds off recent work from Kiperwasser & Goldberg (2016) using neural attention in a simple graph-based dependency parser. We use a larger but more thoroughly regularized parser than other recent BiLSTM-based approaches, with biaffine classifiers to predict arcs and labels. Our parser gets state of the art or near state of the art performance on standard treebanks for six different languages, achieving 95.7% UAS and 94.1% LAS on the most popular English PTB dataset. This makes it the highest-performing graph-based parser on this benchmarkoutperforming Kiperwasser & Goldberg (2016) by 1.8% and 2.2%-and comparable to the highest performing transition-based parser (Kuncoro et al., 2016) , which achieves 95.8% UAS and 94.6% LAS. We also show which hyperparameter choices had a significant effect on parsing accuracy, allowing us to achieve large gains over other graph-based approaches.

1. INTRODUCTION:

Dependency parsers-which annotate sentences in a way designed to be easy for humans and computers alike to understand-have been found to be extremely useful for a sizable number of NLP tasks, especially those involving natural language understanding in some way (Bowman et al., 2016; Angeli et al., 2015; Levy & Goldberg, 2014; Toutanova et al., 2016; Parikh et al., 2015) . However, frequent incorrect parses can severely inhibit final performance, so improving the quality of dependency parsers is needed for the improvement and success of these downstream tasks.

The current state-of-the-art transition-based neural dependency parser (Kuncoro et al., 2016) substantially outperforms many much simpler neural graph-based parsers. We modify the neural graphbased approach first proposed by Kiperwasser & Goldberg (2016) in a few ways to achieve competitive performance: we build a network that's larger but uses more regularization; we replace the traditional MLP-based attention mechanism and affine label classifier with biaffine ones; and rather than using the top recurrent states of the LSTM in the biaffine transformations, we first put them through MLP operations that reduce their dimensionality. Furthermore, we compare models trained with different architectures and hyperparameters to motivate our approach empirically. The resulting parser maintains most of the simplicity of neural graph-based approaches while approaching the performance of the SOTA transition-based one.

2. BACKGROUND AND RELATED WORK:

Transition-based parsers-such as shift-reduce parsers-parse sentences from left to right, maintaining a "buffer" of words that have not yet been parsed and a "stack" of words whose head has not been seen or whose dependents have not all been fully parsed. At each step, transition-based parsers can access and manipulate the stack and buffer and assign arcs from one word to another. One can then train any multi-class machine learning classifier on features extracted from the stack, buffer, and previous arc actions in order to predict the next action.

Chen & Manning (2014) make the first successful attempt at incorporating deep learning into a transition-based dependency parser. At each step, the (feedforward) network assigns a probability to each action the parser can take based on word, tag, and label embeddings from certain words on the (2015) and Andor et al. (2016) augment it with a beam search and a conditional random field loss objective to allow the parser to "undo" previous actions once it finds evidence that they may have been incorrect; and Dyer et al. (2015) and (Kuncoro et al., 2016) instead use LSTMs to represent the stack and buffer, getting state-of-the-art performance by building in a way of composing parsed phrases together.

Transition-based parsing processes a sentence sequentially to build up a parse tree one arc at a time. Consequently, these parsers don't use machine learning for directly predicting edges; they use it for predicting the operations of the transition algorithm. Graph-based parsers, by contrast, use machine learning to assign a weight or probability to each possible edge and then construct a maximum spaning tree (MST) from these weighted edges. Kiperwasser & Goldberg (2016) present a neural graph-based parser (in addition to a transition-based one) that uses the same kind of attention mechanism as Bahdanau et al. (2014) for machine translation. In Kiperwasser & Goldberg's 2016 model, the (bidirectional) LSTM's recurrent output vector for each word is concatenated with each possible head's recurrent vector, and the result is used as input to an MLP that scores each resulting arc. The predicted tree structure at training time is the one where each word depends on its highestscoring head. Labels are generated analogously, with each word's recurrent output vector and its gold or predicted head word's recurrent vector being used in a multi-class MLP.

Similarly, Hashimoto et al. (2016) include a graph-based dependency parser in their multi-task neural model. In addition to training the model with multiple distinct objectives, they replace the traditional MLP-based attention mechanism that Kiperwasser & Goldberg (2016) use with a bilinear one (but still using an MLP label classifier). This makes it analogous to Luong et al.'s 2015 proposed attention mechanism for neural machine translation. Cheng et al. (2016) likewise propose a graph-based neural dependency parser, but in a way that attempts to circumvent the limitation of other neural graph-based parsers being unable to condition the scores of each possible arc on previous parsing decisions. In addition to having one bidirectional recurrent network that computes a recurrent hidden vector for each word, they have additional, unidirectional recurrent networks (leftto-right and right-to-left) that keep track of the probabilities of each previous arc, and use these together to predict the scores for the next arc.

3. PROPOSED DEPENDENCY PARSER:



3.1. DEEP BIAFFINE ATTENTION:

We make a few modifications to the graph-based architectures of Kiperwasser & Goldberg (2016) , Hashimoto et al. (2016), and Cheng et al. (2016) , shown in Figure 2 : we use biaffine attention instead of bilinear or traditional MLP-based attention; we use a biaffine dependency label classifier; and we apply dimension-reducing MLPs to each recurrent output vector r i before applying the biaffine transformation. 1 The choice of biaffine rather than bilinear or MLP mechanisms makes the classifiers in our model analogous to traditional affine classifiers, which use an affine transformation over a single LSTM output state r i (or other vector input) to predict the vector of scores s i for all classes (1). We can think of the proposed biaffine attention mechanism as being a traditional affine . . .

root ROOT Kim NNP 1 1 1 1 • • = BiLSTM: r i Embeddings: x i MLP: h (arc-dep) i , h (arc-head) i H (arc-dep) ⊕ 1 U (arc) H (arc-head) S (arc)

Figure 2 : BiLSTM with deep biaffine attention to score each possible head for each dependent, applied to the sentence "Casey hugged Kim". We reverse the order of the biaffine transformation here for clarity.

classifier, but using a (d × d) linear transformation of the stacked LSTM output RU (1) in place of the weight matrix W and a (d × 1) transformation Ru (2) for the bias term b (2).

EQUATION

In addition to being arguably simpler than the MLP-based approach (involving one bilinear layer rather than two linear layers and a nonlinearity), this has the conceptual advantage of directly modeling both the prior probability of a word j receiving any dependents in the term r j u (2) and the likelihood of j receiving a specific dependent i in the term r j U (1) r i . Analogously, we also use a biaffine classifier to predict dependency labels given the gold or predicted head y i (3).

s (label) i = r yi U (1) r i + (r yi ⊕ r i ) U (2) + b Fixed-class biaffine classifier (3)

This likewise directly models each of the prior probability of each class, the likelihood of a class given just word i (how probable a word is to take a particular label), the likelihood of a class given just the head word y i (how probable a word is to take dependents with a particular label), and the likelihood of a class given both word i and its head (how probable a word is to take a particular label given that word's head).

Applying smaller MLPs to the recurrent output states before the biaffine classifier has the advantage of stripping away information not relevant to the current decision. That is, every top recurrent state r i will need to carry enough information to identify word i's head, find all its dependents, exclude all its non-dependents, assign itself the correct label, and assign all its dependents their correct labels, as well as transfer any relevant information to the recurrent states of words before and after it. Thus r i necessarily contains significantly more information than is needed to compute any individual score, and training on this superfluous information needlessly reduces parsing speed and increases the risk of overfitting. Reducing dimensionality and applying a nonlinearity (4 -6) addresses both of these problems. We call this a deep bilinear attention mechanism, as opposed to shallow bilinear attention, which uses the recurrent states directly.

h (arc-dep) i = MLP (arc-dep) (r i ) (4) h (arc-head) j = MLP (arc-head) (r j ) (5) s (arc) i = H (arc-head) U (1) h (arc-dep) i (6) + H (arc-head) u (2)

We apply MLPs to the recurrent states before using them in the label classifier as well. As with other graph-based models, the predicted tree at training time is the one where each word is a dependent of its highest scoring head (although at test time we ensure that the parse is a well-formed tree via the MST algorithm). Aside from architectural differences between ours and the other graph-based parsers, we make a number of hyperparameter choices that allow us to outperform theirs, laid out in Table 1 . We use 100-dimensional uncased word vectors2 and POS tag vectors; three BiLSTM layers (400 dimensions in each direction); and 500-and 100-dimensional ReLU MLP layers. We also apply dropout at every stage of the model: we drop words and tags (independently); we drop nodes in the LSTM layers (input and recurrent connections), applying the same dropout mask at every recurrent timestep (cf. the Bayesian dropout of Gal & Ghahramani (2015) ); and we drop nodes in the MLP layers and classifiers, likewise applying the same dropout mask at every timestep. We optimize the network with annealed Adam (Kingma & Ba, 2014) for about 50,000 steps, rounded up to the nearest epoch.

3.2. HYPERPARAMETER CONFIGURATION:



Param:



4. EXPERIMENTS & RESULTS:



4.1. DATASETS:

We show test results for the proposed model on the English Penn Treebank, converted into Stanford Dependencies using both version 3.3.0 and version 3.5.0 of the Stanford Dependency converter (PTB-SD 3.3.0 and PTB-SD 3.5.0); the Chinese Penn Treebank; and the CoNLL 09 shared task dataset,3 following standard practices for each dataset. We omit punctuation from evaluation only for the PTB-SD and CTB. For the English PTB-SD datasets, we use POS tags generated from the Stanford POS tagger (Toutanova et al., 2003) ; for the Chinese PTB dataset we use gold tags; and for the CoNLL 09 dataset we use the provided predicted tags. Our hyperparameter search was done with the PTB-SD 3.5.0 validation dataset in order to minimize overfitting to the more popular PTB-SD 3.3.0 benchmark, and in our hyperparameter analysis in the following section we report performance on the PTB-SD 3.5.0 test set, shown in Tables 2 and 3 .

4.2. HYPERPARAMETER CHOICES:



4.2.1. ATTENTION MECHANISM:

We examined the effect of different classifier architectures on accuracy and performance. What we see is that the deep bilinear model outperforms the others with respect to both speed and accuracy.

The model with shallow bilinear arc and label classifiers gets the same unlabeled performance as the deep model with the same settings, but because the label classifier is much larger ((801 × c × 801) as opposed to (101 × c × 101)), it runs much slower and overfits. One way to decrease this overfitting is by increasing the MLP dropout, but that of course doesn't change parsing speed; another way is to decrease the recurrent size to 300, but this hinders unlabeled accuracy without increasing parsing speed up to the same levels as our deeper model. We also implemented the MLP-based approach to attention and classification used in Kiperwasser & Goldberg (2016) . 4 We found this version to likewise be somewhat slower and significantly underperform the deep biaffine approach in both labeled and unlabeled accuracy.

4.2.2. NETWORK SIZE:

We also examine more closely how network size influences speed and accuracy. In Kiperwasser & Goldberg's 2016 model, the network uses 2 layers of 125-dimensional bidirectional LSTMs; in Hashimoto et al.'s 2016 model, it has one layer of 100-dimensional bidirectional LSTMs dedicated to parsing (two lower layers are also trained on other objectives); and Cheng et al.'s 2016 model has one layer of 368-dimensional GRU cells. We find that using three or four layers gets significantly better performance than two layers, and increasing the LSTM sizes from 200 to 300 or 400 dimensions likewise signficantly improves performance.5 

4.2.3. RECURRENT CELL:

GRU cells have been promoted as a faster and simpler alternative to LSTM cells, and are used in the approach of Cheng et al. (2016) ; however, in our model they drastically underperformed LSTM cells. We also implemented the coupled input-forget gate LSTM cells (Cif-LSTM) suggested by Greff et al. (2015) ,6 finding that while the resulting model still slightly underperforms the more popular LSTM cells, the difference between the two is much smaller. Additionally, because the gate and candidate cell activations can be computed simultaneously with one matrix multiplication, the Cif-LSTM model is faster than the GRU version even though they have the same number of parameters. We hypothesize that the output gate in the Cif-LSTM model allows it to maintain a sparse recurrent output state, which helps it adapt to the high levels of dropout needed to prevent overfitting in a way that GRU cells are unable to do. Because we increase the parser's power, we also have to increase its regularization. In addition to using relatively extreme dropout in the recurrent and MLP layers mentioned in Table 1 , we also regularize the input layer. We drop 33% of words and 33% of tags during training: when one is dropped the other is scaled by a factor of two to compensate, and when both are dropped together, the model simply gets an input of zeros. Models trained with only word or tag dropout but not both wind up signficantly overfitting, hindering label accuracy and-in the latter case-attachment accuracy. Interestingly, not using any tags at all actually results in better performance than using tags without dropout.

4.2.5. OPTIMIZER:

We choose to optimize with Adam (Kingma & Ba, 2014) , which (among other things) keeps a moving average of the L 2 norm of the gradient for each parameter throughout training and divides the gradient for each parameter by this moving average, ensuring that the magnitude of the gradients will on average be close to one. However, we find that the value for β 2 recommended by Kingma & Ba-which controls the decay rate for this moving average-is too high for this task (and we suspect more generally). When this value is very large, the magnitude of the current update is heavily influenced by the larger magnitude of gradients very far in the past, with the effect that the optimizer can't adapt quickly to recent changes in the model. Thus we find that setting β 2 to .9 instead of .999 makes a large positive impact on final performance.

4.3. RESULTS:

Our model gets nearly the same UAS performance on PTB-SD 3.3.0 as the current SOTA model from Kuncoro et al. (2016) in spite of its substantially simpler architecture, and gets SOTA UAS performance on CTB 5.17 as well as SOTA performance on all CoNLL 09 languages. It is worth noting that the CoNLL 09 datasets contain many non-projective dependencies, which are difficult or impossible for transition-based-but not graph-based-parsers to predict. This may account for some of the large, consistent difference between our model and Andor et al.'s 2016 transition-based model applied to these datasets.

Where our model appears to lag behind the SOTA model is in LAS, indicating one of a few possibilities. Firstly, it may be the result of inefficiencies or errors in the GloVe embeddings or POS tagger, in which case using alternative pretrained embeddings or a more accurate tagger might improve label classification. Secondly, the SOTA model is specifically designed to capture phrasal compositionality; so another possibility is that ours doesn't capture this compositionality as effectively, and that this results in a worse label score. Similarly, it may be the result of a more general limitation of graph-based parsers, which have access to less explicit syntactic information than transition-based parsers when making decisions. Addressing these latter two limitations would require a more innovative architecture than the relatively simple one used in current neural graph-based parsers.

5. CONCLUSION:

In this paper we proposed using a modified version of bilinear attention in a neural dependency parser that increases parsing speed without hurting performance. We showed that our larger but more regularized network outperforms other neural graph-based parsers and gets comparable performance to the current SOTA transition-based parser. We also provided empirical motivation for the proposed architecture and configuration over similar ones in the existing literature. Future work will involve exploring ways of bridging the gap between labeled and unlabeled accuracy and augment the parser with a smarter way of handling out-of-vocabulary tokens for morphologically richer languages.

:

In this paper we follow the convention of using lowercase italic letters for scalars and indices, lowercase bold letters for vectors, uppercase italic letters for matrices, uppercase bold letters for higher order tensors. We also maintain this notation when indexing; so row i of matrix R would be represented as ri.

We compute a "trained" embedding matrix composed of words that occur at least twice in the training dataset and add these embeddings to their corresponding pretrained embeddings. Any words that don't occur in either embedding matrix are replaced with a separate OOV token.

We exclude the Japanese dataset from our evaluation because we do not have access to it.

In the version of TensorFlow we used, the model's memory requirements during training exceeded the available memory on a single GPU when default settings were used, so we reduced the MLP hidden size to 200

The model with 400-dimensional recurrent states significantly outperforms the 300-dimensional one on the validation set, but not on the test set

In addition to using a coupled input-forget gate, we remove the first tanh nonlinearity, which is no longer needed when using a coupled gate

We'd like to thank Zhiyang Teng for finding a bug in the original code that affected the CTB 5.1 dataset

Figures and Tables:

Figure1: A dependency tree parse for Casey hugged Kim, including part-of-speech tags and a special root token. Directed edges (or arcs) with labels (or relations) connect the verb to the root and the arguments to the verb head.

Model hyperparameters

Table content: <table><tr><td/><td colspan="2">Value</td><td>Param</td><td>Value</td></tr><tr><td colspan="3">Embedding size 100</td><td colspan="2">Embedding dropout 33%</td></tr><tr><td>LSTM size</td><td colspan="2">400</td><td>LSTM dropout</td><td>33%</td></tr><tr><td>Arc MLP size</td><td colspan="2">500</td><td>Arc MLP dropout</td><td>33%</td></tr><tr><td colspan="3">Label MLP size 100</td><td colspan="2">Label MLP dropout 33%</td></tr><tr><td>LSTM depth</td><td>3</td><td/><td>MLP depth</td><td>1</td></tr><tr><td>α</td><td colspan="2">2e -3</td><td>β1,β2</td><td>.9</td></tr><tr><td>Annealing</td><td>.75</td><td>t 5000</td><td>tmax</td><td>50,000</td></tr></table>

Test accuracy and speed on PTB-SD 3.5.0. Statistically significant differences are marked with an asterisk.

Table content: <table><tr><td/><td colspan="2">Classifier</td><td/><td/><td colspan="2">Size</td><td/></tr><tr><td>Model</td><td>UAS</td><td>LAS</td><td>Sents/sec</td><td>Model</td><td>UAS</td><td>LAS</td><td>Sents/sec</td></tr><tr><td>Deep</td><td>95.75</td><td>94.22</td><td>410.91</td><td colspan="2">3 layers, 400d 95.75</td><td>94.22</td><td>410.91</td></tr><tr><td>Shallow</td><td>95.74</td><td colspan="2">94.00* 298.99</td><td colspan="2">3 layers, 300d 95.82</td><td>94.24</td><td>460.01</td></tr><tr><td colspan="2">Shallow, 50% drop 95.73</td><td colspan="2">94.05* 300.04</td><td colspan="4">3 layers, 200d 95.55* 93.89* 469.45</td></tr><tr><td>Shallow, 300d</td><td colspan="3">95.63* 93.86* 373.24</td><td colspan="4">2 layers, 400d 95.62* 93.98* 497.99</td></tr><tr><td>MLP</td><td colspan="3">95.53* 93.91* 367.44</td><td colspan="2">4 layers, 400d 95.83</td><td>94.22</td><td>362.09</td></tr><tr><td/><td colspan="2">Recurrent Cell</td><td/><td/><td/><td/><td/></tr><tr><td>Model</td><td>UAS</td><td>LAS</td><td>Sents/sec</td><td/><td/><td/><td/></tr><tr><td>LSTM</td><td>95.75</td><td>94.22</td><td>410.91</td><td/><td/><td/><td/></tr><tr><td>GRU</td><td colspan="3">93.18* 91.08* 435.32</td><td/><td/><td/><td/></tr><tr><td>Cif-LSTM</td><td>95.67</td><td colspan="2">94.06* 463.25</td><td/><td/><td/><td/></tr><tr><td/><td colspan="3">Input Dropout</td><td/><td>Adam</td><td/><td/></tr><tr><td/><td>Model</td><td>UAS</td><td>LAS</td><td>Model</td><td>UAS</td><td>LAS</td><td/></tr><tr><td/><td>Default</td><td>95.75</td><td>94.22</td><td>β2 = .9</td><td>95.75</td><td>94.22</td><td/></tr><tr><td/><td colspan="2">No word dropout 95.74</td><td>94.08*</td><td colspan="3">β2 = .999 95.53* 93.91*</td><td/></tr><tr><td/><td>No tag dropout</td><td colspan="2">95.28* 93.60*</td><td/><td/><td/><td/></tr><tr><td/><td>No tags</td><td>95.77</td><td>93.91*</td><td/><td/><td/><td/></tr></table>

Test Accuracy on PTB-SD 3.5.0. Statistically significant differences are marked with an asterisk.

Table content: <table/>

Results on the English PTB and Chinese PTB parsing datasets

Table content: <table><tr><td>English PTB-SD 3.3.0 Chinese PTB 5.1</td></tr></table>

Results on the CoNLL '09 shared task datasets 4.2.4 EMBEDDING DROPOUT

Table content: <table/>

Peer review (iclr2017):
The paper brings the new STOA in PTB dependency parsing. The numbers are very impressive. Built upon the framework of K&G parser, this improvement is achieved by mainly two things -- (1) the paper replace the original scorer using bilinear scorer and make a difference between the head of modifier representation (2) the hyperparameter tuning in the ADAM trainer. Although I think the bilinear modification make some sense intuitively, I don*t think this contribution alone is strong enough for a conference publication. The authors did not show a good explanation of why this approach works better in this case nor did the author show this modification is generally applicable in any other tasks.