Global Greedy Dependency Parsing

Abstract: Most syntactic dependency parsing models may fall into one of two categories: transition- and graph-based models. The former models enjoy high inference efficiency with linear time complexity, but they rely on the stacking or re-ranking of partially-built parse trees to build a complete parse tree and are stuck with slower training for the necessity of dynamic oracle training. The latter, graph-based models, may boast better performance but are unfortunately marred by polynomial time inference. In this paper, we propose a novel parsing order objective, resulting in a novel dependency parsing model capable of both global (in sentence scope) feature extraction as in graph models and linear time inference as in transitional models. The proposed global greedy parser only uses two arc-building actions, left and right arcs, for projective parsing. When equipped with two extra non-projective arc-building actions, the proposed parser may also smoothly support non-projective parsing. Using multiple benchmark treebanks, including the Penn Treebank (PTB), the CoNLL-X treebanks, and the Universal Dependency Treebanks, we evaluate our parser and demonstrate that the proposed novel parser achieves good performance with faster training and decoding.

Dependency parsing predicts the existence and type of linguistic dependency relations between words (as shown in Figure FIGREF1), which is a critical step in accomplishing deep natural language processing. Dependency parsing has been well developed BIBREF0, BIBREF1, and it generally relies on two types of parsing models: transition-based models and graph-based models. The former BIBREF2, BIBREF3, BIBREF4, BIBREF5, BIBREF4 traditionally apply local and greedy transition-based algorithms, while the latter BIBREF6, BIBREF7, BIBREF8, BIBREF9, BIBREF10, BIBREF11, BIBREF12 apply globally optimized graph-based algorithms.
A transition-based dependency parser processes the sentence word-by-word, commonly from left to right, and forms a dependency tree incrementally from the operations predicted. This method is advantageous in that inference on the projective dependency tree is linear in time complexity with respect to sentence length; however, it has several obvious disadvantages. Because the decision-making of each step is based on partially-built parse trees, special training methods are required, which results in slow training and error propagation, as well as weak long-distance dependence processing BIBREF13.
Graph-based parsers learn scoring functions in one-shot and then perform an exhaustive search over the entire tree space for the highest-scoring tree. This improves the performances of the parsers, particularly the long-distance dependency processing, but these models usually have slow inference speed to encourage higher accuracy.
The easy-first parsing approach BIBREF14, BIBREF15 was designed to integrate the advantages of graph-based parsers’ better-performing trees and transition-based parsers’ linear decoding complexity. By processing the input tokens in a stepwise easy-to-hard order, the algorithm makes use of structured information on partially-built parse trees. Because of the presence of rich, structured information, exhaustive inference is not an optimal solution - we can leverage this information to conduct inference much more quickly. As an alternative to exhaustive inference, easy-first chooses to use an approximated greedy search that only explores a tiny fraction of the search space. Compared to graph-based parsers, however, easy-first parsers have two apparent weaknesses: slower training and worse performance. According to our preliminary studies, with the current state-of-the-art systems, we must either sacrifice training complexity for decoding speed, or sacrifice decoding speed for higher accuracy.
In this paper, we propose a novel Global (featuring) Greedy (inference) parsing architecture that achieves fast training, high decoding speed and good performance. With our approach, we use the one-shot arc scoring scheme as in the graph-based parser instead of the stepwise local scoring in transition-based. This is essential for achieving competitive performance, efficient training, and fast decoding. Since, to preserve linear time decoding, we chose a greedy algorithm, we introduce a parsing order scoring scheme to retain the decoding order in inference to achieve the highest accuracy possible. Just as with one-shot scoring in graph-based parsers, our proposed parser will perform arc-attachment scoring, parsing order scoring, and decoding simultaneously in an incremental, deterministic fashion just as transition-based parsers do.
We evaluated our models on the common benchmark treebanks PTB and CTB, as well as on the multilingual CoNLL and the Universal Dependency treebanks. From the evaluation results on the benchmark treebanks, our proposed model gives significant improvements when compared to the baseline parser. In summary, our contributions are thus:
$\bullet $ We integrate the arc scoring mechanism of graph-based parsers and the linear time complexity inference approach of transition parsing models, which, by replacing stepwise local feature scoring, significantly alleviates the drawbacks of these models, improving their moderate performance caused by error propagation and increasing their training speeds resulting from their lack of parallelism.
$\bullet $ Empirical evaluations on benchmark and multilingual treebanks show that our method achieves state-of-the-art or comparable performance, indicating that our novel neural network architecture for dependency parsing is simple, effective, and efficient.
$\bullet $ Our work shows that using neural networks’ excellent learning ability, we can simultaneously achieve both improved accuracy and speed.
The global greedy parser will build its dependency trees in a stepwise manner without backtracking, which takes a general greedy decoding algorithm as in easy-first parsers.
Using easy-first parsing's notation, we describe the decoding in our global greedy parsing. As both easy-first and global greedy parsing rely on a series of deterministic parsing actions in a general parsing order (unlike the fixed left-to-right order of standard transitional parsers), they need a specific data structure which consists of a list of unattached nodes (including their partial structures) referred to as “pending". At each step, the parser chooses a specific action $\hat{a}$ on position $i$ with the given arc score score($\cdot $), which is generated by an arc scorer in the parser. Given an intermediate state of parsing with pending $P=\lbrace p_0, p_1, p_2, \cdots , p_N\rbrace $, the attachment action is determined as follows:
where $\mathcal {A}$ denotes the set of the allowed actions, and $i$ is the index of the node in pending. In addition to distinguishing the correct attachments from the incorrect ones, the arc scorer also assigns the highest scores to the easiest attachment decisions and lower scores to the harder decisions, thus determining the parsing order of an input sentence.
For projective parsing, there are exactly two types of actions in the allowed action set: ATTACHLEFT($i$) and ATTACHRIGHT($i$). Let $p_i$ refer to $i$-th element in pending, then the allowed actions can be formally defined as follows:
$\bullet $ ATTACHLEFT($i$): attaches $p_{i+1}$ to $p_i$ , which results in an arc ($p_i$, $p_{i+1}$) headed by $p_i$, and removes $p_{i+1}$ from pending.
$\bullet $ ATTACHRIGHT($i$): attaches $p_i$ to $p_{i+1}$ , which results in an arc ($p_{i+1}$, $p_i$) headed by $p_{i+1}$, and removes $p_i$ from pending.
Our proposed global greedy model contains three components: (1) an encoder that processes the input sentence and maps it into hidden states that lie in a low dimensional vector space $h_i$ and feeds it into a specific representation layer to strip away irrelevant information, (2) a modified scorer with a parsing order objective, and (3) a greedy inference module that generates the dependency tree.
We employ a bi-directional LSTM-CNN architecture (BiLSTM-CNN) to encode the context in which convolutional neural networks (CNNs) learn character-level information $e_{char}$ to better handle out-of-vocabulary words. We then combine these words' character level embeddings with their word embedding $e_{word}$ and POS embedding $e_{pos}$ to create a context-independent representation, which we then feed into the BiLSTM to create word-level context-dependent representations. To further enhance the word-level representation, we leverage an external fixed representation $e_{lm}$ from pre-trained ELMo BIBREF16 or BERT BIBREF17 layer features. Finally, the encoder outputs a sequence of contextualized representations $h_i$.
Because the contextualized representations will be used for several different purposes in the following scorers, it is necessary to specify a representation for each purpose. As shown in BIBREF18, applying a multi-layer perceptron (MLP) to the recurrent output states before the classifier strips away irrelevant information for the current decision, reducing both the dimensionality and the risk of model overfitting. Therefore, in order to distinguish the biaffine scorer's head and dependent representations and the parsing order scorer's representations, we add a separate contextualized representation layer with ReLU as its activation function for each syntax head $h^{head}_i \in H_{head}$ specific representations, dependent $h^{dep}_i \in H_{dep}$ specific representations, and parsing order $h^{order}_i \in H_{order}$:
The traditional easy-first model relies on an incremental tree scoring process with stepwise loss backpropagation and sub-tree removal facilitated by local scoring, relying on the scorer and loss backpropagation to hopefully obtain the parsing order. Communicating the information from the scorer and the loss requires training a dynamic oracle, which exposes the model to the configurations resulting from erroneous decisions. This training process is done at the token level, not the sentence level, which unfortunately means incremental scoring prevents parallelized training and causes error propagation. We thus forego incremental local scoring, and, inspired by the design of graph-based parsing models, we instead choose to score all of the syntactic arc candidates in one-shot, which allows for global featuring at a sentence level; however, the introduction of one-shot scoring brings new problems. Since the graph-based method relies on a tree space search algorithm to find the tree with the highest score, the parsing order is not important at all. If we apply one-shot scoring to greedy parsing, we need a mechanism like a stack (as is used in transition-based parsing) to preserve the parsing order.
Both transition-based and easy-first parsers build parse trees in an incremental style, which forces tree formation to follow an order starting from either the root and working towards the leaf nodes or vice versa. When a parser builds an arc that skips any layer, certain errors will exist that it will be impossible for the parent node to find. We thus implement a parsing order prediction module to learn a parsing order objective that outputs a parsing order score addition to the arc score to ensure that each pending node is attached to its parent only after all (or at least as many as possible) of its children have been collected.
Our scorer consists of two parts: a biaffine scorer for one-shot scoring and a parsing order scorer for parsing order guiding. For the biaffine scorer, we adopt the biaffine attention mechanism BIBREF18 to score all possible head-dependent pairs:
where $\textbf {W}_{arc}$, $\textbf {U}_{arc}$, $\textbf {V}_{arc}$, $\textbf {b}_{arc}$ are the weight matrix of the bi-linear term, the two weight vectors of the linear terms, and the bias vector, respectively.
If we perform greedy inference only on the $s_{arc}$ directly, as in Figure FIGREF6, at step $i$, the decoder tests every pair in the pending list, and although the current score fits the correct tree structure for this example, because backtracking is not allowed in the deterministic greedy inference, according to the maximum score $s_{arc}$, the edge selected in step $i$+1 is “root"$\rightarrow $“come". This prevents the child nodes (“today" and “.") from finding the correct parent node in the subsequent step. Thus, the decoder is stuck with this error. This problem can be solved or mitigated by using a max spanning tree (MST) decoder or by adding beam search method to the inference, but neither guarantees maintaining linear time decoding. Therefore, we propose a new scorer for parsing order $s_{order}$. In the scoring stage, the parsing order score is passed to the decoder to guide it and prevent (as much as possible) resorting to erroneous choices.
We formally define the parsing order score for decoding. To decode the nodes at the bottom of the syntax tree first, we define the the parsing order priority as the layer “level" or “position" in the tree. The biaffine output score is the probability of edge (dependency) existence, between 0 and 1, so the greater the probability, the more likely an edge is to exist. Thus, our parsing order scorer gives a layer score for a node, and then, we add this layer score to the biaffine score. Consequently, the relative score of the same layer can be kept unchanged, and the higher the score of a node in the bottom layer, the higher its decoding priority will be. We therefore define $s_{order}$ as:
where $\textbf {W}_{order}$ and $\textbf {b}_{order} $ are parameters for the parsing order scorer. Finally, the one-shot arc score is:
Similarly, we use the biaffine scorer for dependency label classification. We apply MLPs to the contextualized representations before using them in the label classifier as well. As with other graph-based models, the predicted tree at training time has each word as a dependent of its highest-scoring head (although at test time we ensure that the parse is a well-formed tree via the greedy parsing algorithm).
To parse the syntax tree $y$ for a sentence $x$ with length $l$, the easy-first model relies on an action-by-action process performed on pending. In the training stage, the loss is accumulated once per step (action), and the model is updated by gradient backpropagation according to a preset frequency. This prohibits parallelism during model training lack between and within sentences. Therefore, the traditional easy-first model was trained to maximize following probability:
where $\emph {pending}_i$ is the pending list state at step $i$.
While for our proposed model, it uses the training method similar to that of graph-based models, in which the arc scores are all obtained in one-shot. Consequently, it does not rely on the pending list in the training phase and only uses the pending list to promote the process of linear parsing in the inference stage. Our model is trained to optimize the probability of the dependency tree $y$ when given a sentence $x$: $P_\theta (y|x)$, which can be factorized as:
where $\theta $ represents learnable parameters, $l$ denotes the length of the processing sentence, and $y^{arc}_i$, $y^{rel}_i$ denote the highest-scoring head and dependency relation for node $x_i$. Thus, our model factors the distribution according to a bottom-up tree structure.
Corresponding to multiple objectives, several parts compose the loss of our model. The overall training loss is the sum of three objectives:
where the loss for arc prediction $\mathcal {L}^{arc}$ is the negative log-likelihood loss of the golden structure $y^{arc}$:
the loss for relation prediction $\mathcal {L}^{rel}$ is implemented as the negative log-likelihood loss of the golden relation $y^{rel}$ with the golden structure $y^{arc}$,
and the loss for parsing order prediction $\mathcal {L}^{order}$:
Because the parsing order score of each layer in the tree increases by 1, we frame it as a classification problem and therefore add a multi-class classifier module as the order scorer.
For non-projective inference, we introduce two additional arc-building actions as follows.
$\bullet $ NP-ATTACHLEFT($i$): attaches $p_{j}$ to $p_i$ where $j > i$, which builds an arc ($p_i$, $p_{j}$) headed by $p_i$, and removes $p_{j}$ from pending.
$\bullet $ NP-ATTACHRIGHT($i$): attaches $p_{j}$ to $p_i$ where $j < i$ which builds an arc ($p_i$, $p_j$) headed by $p_i$, and removes $p_j$ from pending.
If we use the two arc-building actions for non-projective dependency trees directly on $s_{final}$, the time complexity will become $O(n^3)$, so we need to modify this algorithm to accommodate the non-projective dependency trees. Specifically, we no longer use $s_{final}$ directly for greedy search but instead divide each decision into two steps. The first step is to use the order score $s_{order}$ to sort the pending list in descending order. Then, the second step is to find the edge with the largest arc score $s_{arc}$ for this node in the first position of the pending list.
The number of decoding steps to build a parse tree for a sentence is the same as its length, $n$. Combining this with the searching in the pending list (at each step, we need to find the highest-scoring pair in the pending list to attach. This has a runtime of $O(n)$. The time complexity of a full decoding is $O(n^2)$, which is equal to 1st-order non-projective graph-based parsing but more efficient than 1st-order projective parsing with $O(n^3)$ and other higher order graph parsing models. Compared with the current state-of-the-art transition-based parser STACKPTR BIBREF23, with the same decoding time complexity as ours, since our number of decoding takes $n$ steps while STACKPTR takes $2n-1$ steps for decoding and needs to compute the attention vector at each step, our model actually would be much faster than STACKPTR in decoding.
For the non-projective inference in our model, the complexity is still $O(n^2)$. Since the order score and the arc score are two parts that do not affect each other, we can sort the order scores with time complexity of $O$($n$log$n$) and then iterate in this descending order. The iteration time complexity is $O(n)$ and determining the arc is also $O(n)$, so the overall time complexity is $O$($n$log$n$) $+$ $O(n^2)$, simplifying to $O(n^2)$.
We evaluate our parsing model on the English Penn Treebank (PTB), the Chinese Penn Treebank (CTB), treebanks from two CoNLL shared tasks and the Universal Dependency (UD) Treebanks, using unlabeled attachment scores (UAS) and labeled attachment scores (LAS) as the metrics. Punctuation is ignored as in previous work BIBREF18. For English and Chinese, we use the projective inference, while for other languages, we use the non-projective one.
For English, we use the Stanford Dependency (SD 3.3.0) BIBREF37 conversion of the Penn Treebank BIBREF38, and follow the standard splitting convention for PTB, using sections 2-21 for training, section 22 as a development set and section 23 as a test set. We use the Stanford POS tagger BIBREF39 generate predicted POS tags.
For Chinese, we adopt the splitting convention for CTB BIBREF40 described in BIBREF19. The dependencies are converted with the Penn2Malt converter. Gold segmentation and POS tags are used as in previous work BIBREF19.
For the CoNLL Treebanks, we use the English treebank from the CoNLL-2008 shared task BIBREF41 and all 13 treebanks from the CoNLL-X shared task BIBREF42. The experimental settings are the same as BIBREF43.
For UD Treebanks, following the selection of BIBREF23, we take 12 treebanks from UD version 2.1 (Nivre et al. 2017): Bulgarian (bg), Catalan (ca), Czech (cs), Dutch (nl), English (en), French (fr), German (de), Italian (it), Norwegian (no), Romanian (ro), Russian (ru) and Spanish (es). We adopt the standard training/dev/test splits and use the universal POS tags provided in each treebank for all the languages.
We use the GloVe BIBREF44 trained on Wikipedia and Gigaword as external embeddings for English parsing. For other languages, we use the word vectors from 157 languages trained on Wikipedia and Crawl using fastText BIBREF45. We use the extracted BERT layer features to enhance the performance on CoNLL-X and UD treebanks.
The character embeddings are 8-dimensional and randomly initialized. In the character CNN, the convolutions have a window size of 3 and consist of 50 filters. We use 3 stacked bidirectional LSTMs with 512-dimensional hidden states each. The outputs of the BiLSTM employ a 512-dimensional MLP layer for the arc scorer, a 128-dimensional MLP layer for the relation scorer, and a 128-dimensional MLP layer for the parsing order scorer, with all using ReLU as the activation function. Additionally, for parsing the order score, since considering it a classification problem over parse tree layers, we set its range to $[0, 1, ..., 32]$.
Parameter optimization is performed with the Adam optimizer with $\beta _1$ = $\beta _2$ = 0.9. We choose an initial learning rate of $\eta _0$ = 0.001. The learning rate $\eta $ is annealed by multiplying a fixed decay rate $\rho $ = 0.75 when parsing performance stops increasing on validation sets. To reduce the effects of an exploding gradient, we use a gradient clipping of 5.0. For the BiLSTM, we use recurrent dropout with a drop rate of 0.33 between hidden states and 0.33 between layers. Following BIBREF18, we also use embedding dropout with a rate of 0.33 on all word, character, and POS tag embeddings.
We now compare our model with several other recently proposed parsers as shown in Table TABREF9. Our global greedy parser significantly outperforms the easy-first parser in BIBREF14 (HT-LSTM) on both PTB and CTB. Compared with other graph- and transition-based parsers, our model is also competitive with the state-of-the-art on PTB when considering the UAS metric. Compared to state-of-the-art parsers in transition and graph types, BIAF and STACKPTR, respectively, our model gives better or comparable results but with much faster training and decoding. Additionally, with the help of pre-trained language models, ELMo or BERT, our model can achieve even greater results.
In order to explore the impact of the parsing order objective on the parsing performance, we replace the greedy inference with the traditional MST parsing algorithm (i.e., BIAF + parsing order objective), and the result is shown as “This work (MST)", giving slight performance improvement compared to the greedy inference, which shows globally optimized decoding of graph model still takes its advantage. Besides, compared to the standard training objective for graph model based parser, the performance improvement is slight but still shows the proposed parsing order objective is indeed helpful.
Table TABREF11 presents the results on 14 treebanks from the CoNLL shared tasks. Our model yields the best results on both UAS and LAS metrics of all languages except the Japanese. As for Japanese, our model gives unsatisfactory results because the original treebank was written in Roman phonetic characters instead of hiragana, which is used by both common Japanese writing and our pre-trained embeddings. Despite this, our model overall still gives 1.0% higher average UAS and LAS than the previous best parser, BIAF.
Following BIBREF23, we report results on the test sets of 12 different languages from the UD treebanks along with the current state-of-the-art: BIAF and STACKPTR. Although both BIAF and STACKPTR parsers have achieved relatively high parsing accuracies on the 12 languages and have all UAS higher than 90%, our model achieves state-of-the-art results in all languages for both UAS and LAS. Overall, our model reports more than 1.0% higher average UAS than STACKPTR and 0.3% higher than BIAF.
In order to verify the time complexity analysis of our model, we measured the running time and speed of BIAF, STACKPTR and our model on PTB training and development set using the projective algorithm. The comparison in Table TABREF24 shows that in terms of convergence time, our model is basically the same speed as BIAF, while STACKPTR is much slower. For decoding, our model is the fastest, followed by BIAF. STACKPTR is unexpectedly the slowest. This is because the time cost of attention scoring in decoding is not negligible when compared with the processing speed and actually even accounts for a significant portion of the runtime.
This paper presents a new global greedy parser in which we enable greedy parsing inference compatible with the global arc scoring of graph-based parsing models instead of the local feature scoring of transitional parsing models. The proposed parser can perform projective parsing when only using two arc-building actions, and it also supports non-projective parsing when introducing two extra non-projective arc-building actions. Compared to graph-based and transition-based parsers, our parser achieves a better tradeoff between parsing accuracy and efficiency by taking advantages of both graph-based models' training methods and transition-based models' linear time decoding strategies. Experimental results on 28 treebanks show the effectiveness of our parser by achieving good performance on 27 treebanks, including the PTB and CTB benchmarks.

Figure and table captions:
Figure 1: A fully built dependency tree for “The test may come today.” including part-of-speech (POS) tags and root token.
Figure 2: Overview for our global greedy parser.
Figure 3: Illustration of the reason of errors generated when only using biaffine arc score for easy-first parsing.
Table 1: Comparison of results on the test sets. “T”, “G” and “E” indicate transition-based, graph-based and easy-first models, respectively. The “G + E” represents the graph-based training while the easy-first algorithm is used for inference. Acronyms used: (g) – greedy, (b) – beam search, (re) – re-ranking, (3rd) – 3rd-order, (1st) – 1st-order. The “*” in the upper right corner of the results is because the original ELMo (Peters et al. 2018) has no Chinese version. We instead used the multilingual version “HIT-ELMo” pre-trained by (Che et al. 2018).
Table 2: UAS and LAS on 14 treebanks from CoNLL shared tasks, together with several state-of-the-art parsers. Bi-Att is the bi-directional attention based parser (Cheng et al. 2016), and NeuroMST is the neural MST parser (Ma and Hovy 2017). “Best Published” includes the best results in recent years among (Koo et al. 2010), (Martins et al. 2011), (Martins, Almeida, and Smith 2013), (Lei et al. 2014), (Zhang et al. 2014), (Zhang and McDonald 2014), (Pitler and McDonald 2015), and (Cheng et al. 2016) in addition to the ones we listed above.
Table 4: Training time and decoding speed. The experimental environment is on the same machine with Intel i9 9900k CPU and NVIDIA 1080Ti GPU.
Table 3: UAS and LAS on test datasets of 12 treebanks from UD Treebanks, together with BIAF and STACKPTR for comparison.

Questions about this paper:
How faster is training and decoding compared to former models?

Answers:
Proposed vs best baseline:
Decoding: 8541 vs 8532 tokens/sec
Training: 8h vs 8h