We recast dependency parsing as a sequence labeling problem, exploring several encodings of dependency trees as labels. While dependency parsing by means of sequence labeling had been attempted in existing work, results suggested that the technique was impractical. We show instead that with a conventional BILSTM -based model it is possible to obtain fast and accurate parsers. These parsers are conceptually simple, not needing traditional parsing algorithms or auxiliary structures. However, experiments on the PTB and a sample of UD treebanks show that they provide a good speed-accuracy tradeoff, with results competitive with more complex approaches. The application of neural architectures to syntactic parsing, and especially the ability of long short-term memories (LSTMs) to obtain context-aware feature representations (Hochreiter and Schmid-huber, 1997), has made it possible to parse natural language with conceptually simpler models than before. For example, in dependency parsing, the rich feature models with dozens of features used in transition-based approaches (Zhang and Nivre, 2011) can be simplified when using feedforward neural networks (Chen and Manning, 2014), and even more with BiLSTM architectures (Kiper-wasser and Goldberg, 2016), where in fact two positional features can suffice (Shi et al., 2017). Similarly, in graph-based approaches, Dozat and Manning (2017) have shown that an arc-factored model can achieve state-of-the-art accuracy, without the need for the higher-order features used in systems like (Koo and Collins, 2010). In the same way, neural feature representations have made it possible to relax the need for structured representations. This is the case of sequence-to-sequence models that translate sentences into linearized trees, which were first applied to constituent (Vinyals et al., 2015) and later to dependency parsing (Wiseman and Rush, 2016; Zhang et al., 2017b; Li et al., 2018). Recently, Gomez-Rodrguez and Vilares (2018) have shown that sequence labeling models, where each word is associated with a label (thus simpler than sequence to sequence, where the mapping from input to output is not one to one) can learn constituent parsing. Contribution We show that sequence labeling is useful for dependency parsing, in contrast to previous work (Spoustova and Spousta, 2010; Li et al., 2018). We explore four different encodings to represent dependency trees for a sentence of length n as a set of n labels associated with its words. We then use these representations to perform dependency parsing with an off-the-shelf sequence labeling model. The results show that we produce models with an excellent speed-accuracy tradeoff, without requiring any explicit parsing algorithm or auxiliary structure (e.g. stack or buffer). The source code is available at https://github. com/mstrise/dep2label 2 Parsing as sequence labeling Sequence labeling is a structured prediction problem where a single output label is generated for every input token. This is the case of tasks such as PoS tagging, chunking or named-entity recognition, for which different approaches obtain accurate results (Brill, 1995; Ramshaw and Marcus, 1999; Reimers and Gurevych, 2017). On the contrary, previous work on dependency parsing as sequence labeling is vague and reports results that are significantly lower than those provided by transition-, graph-based or sequence-to-sequence models (Dyer et al., 2015; Kiperwasser and Goldberg, 2016; Dozat and Manning, 2017; Zhang et al., 2017a). Spoustova and Spousta (2010) encoded dependency trees using a relative PoS-based scheme to represent the head of a node, to then train an averaged perceptron. They did not provide comparable results, but claimed that the accuracy was between 5-10% below the state of the art in the pre-deep learning era. Recently, Li et al. (2018) used a relative positional encoding of head indexes with respect to the target token. This is used to train Bidirectional LSTM-CRF sequence-to-sequence models (Huang et al., 2015), that make use of sub-root decomposition. They compared their performance against an equivalent BiLSTM-CRF labeling model. The reported UAS for the sequence labeling model was 87.6% on the Penn Treebank, more than 8 points below the current best model (Ma et al., 2018), concluding that sequence-to-sequence models are required to obtain competitive results. Given a sentence w 1 . . . w n , we associate the words with nodes { 0 , 1 , . . . , n } , where the extra node 0 is used as a dummy root for the sentence. A dependency parser will find a set of labeled relations encoded as edges of the form ( h, d, l ) , where h  { 0 , 1 , . . . , n } is the head, d  { 1 , . . . , n } the dependent, and l a dependency label. The resulting dependency graph must be acyclic and such that each node in { 1 , . . . , n } has exactly one head, so it will be a directed tree rooted at node 0 . Thus, to encode a dependency tree, it suffices to encode the unique head position and dependency label associated with each word of w 1 . . . w n . To do so, we will give each word w i a discrete label of the form ( x i , l i ) , where l i is the dependency label and x i encodes the position of the head in one of the following four ways (see also Figure 1): 1. Naive positional encoding: x i directly stores the position of the head, i.e., a label ( x i , l i ) encodes an edge ( x i , i, l i ) . This is the encoding used in the CoNLL file format. 2. Relative positional encoding: x i stores the difference between the head index minus that of the dependent, i.e., ( x i , l i ) encodes an edge ( i + x i , i, l i ) . This was the encoding used for the sequence-to-sequence and sequence labeling models in (Li et al., 2018), as well as for the sequence-to-sequence model in (Kiper-wasser and Ballesteros, 2018). 3. Relative PoS-based encoding: x i is a tuple p i , o i . If o i > 0 , the head of w i is the o i th closest among the words to the right of w i that have PoS tag p i . If o i < 0 , the head of w i is the  o i th closest among the words to the left of w i that have PoS tag p i . For example, ( V,  2) means the second verb to the left of w i . This scheme is closer to the notion of valency, and was used by Spoustova and Spousta (2010). 4. Bracketing-based encoding: based on (Yli-Jyra, 2012; Yli-Jyra and Gomez-Rodrguez, 2017). In each label ( x i , l i ) , the component x i is a string following the regular expression (<)?((\)*|(/)*)(>)? where the presence of character < means that w i  1 has an incoming arc from the right, k copies of character \ mean that w i has k outgoing arcs towards the left, k copies of / mean that w i  1 has k outgoing arcs towards the right, and the presence of > means that w i has an incoming arc from the left. Thus, each right dependency from a word i to j is encoded by a ( / , > ) pair in the label components x i +1 and x j , and each left dependency from j to i by a ( < , \ ) pair in the label components x i +1 and x j . Note that the intuition that explains why information related to a word is encoded in a neighboring node is that each x i corresponds to a fencepost position (i.e., x i represents the space between w i  1 and w i ), and the character pair associated to an arc is encoded in the most external fencepost positions covered by that arc. These pairs act as pairs of matching brackets, which can be decoded using a stack to reconstruct the dependencies. The first three encodings can represent any dependency tree, as they encode any valid head position for each node, while the bracketing encoding only supports projective trees, as it assumes that brackets are properly nested. All the encodings are total and injective, but they are not surjective: head indexes can be out of range in the first three encodings, brackets can be unbalanced in encoding 4, and all the encodings can generate graphs with cycles. We will deal with ill-formed trees later. We use a standard encoder-decoder network, to show that dependency parsing as sequence label< Encoder We use bidirectional LSTMs (Hochre-iter and Schmidhuber, 1997; Schuster and Pali-wal, 1997). Let LSTM  ( x ) be an abstraction of a long short-term memory network that processes the sequence of vectors x = [ x 1 , ..., x | x | ] , then output for x i is defined as h i = BiLSTM  ( x , i ) = LSTM l ( x [1: i ] )  LSTM r ( x [ | x | : i ] ) . We consider stacked BiLSTMs, where the output h mi of the m th BiLSTM layer is fed as input to the m +1th layer. Unless otherwise specified, the input token at a given time step is the concatenation of a word, PoS tag, and another word embedding learned through a character LSTM. Decoder We use a feed-forward network, which is fed the output of the last BiLSTM. The output is computed as P ( y i | h i ) = softmax ( W  h i + b ) . Well-formedness (i) Each token must be assigned a head (one must be the dummy root), and (ii) the graph must be acyclic. If no token is the real root (no head is the dummy root), we search for candidates by relying on the three most likely labels for each token. 1 If none is found, we assign it to the first token of the sentence. The single-head constraint is ensured by the nature of the encodings themselves, but some of the predicted head indexes might be out of bounds. If so, we attach those tokens to the real root. If a cycle exists, we do the same for the leftmost token in the cycle. We use the English Penn Treebank (PTB) (Marcus et al., 1993) and its splits for parsing. We transform it into Stanford Dependencies (De Marn-effe et al., 2006) and obtain the predicted PoS tags using Stanford tagger (Toutanova et al., 2003). We also select a sample of UDv2.2 treebanks (Nivre et al., 2018): Ancient-Greek PROIEL , Czech PDT , Chinese GSD , English EWT , Finnish TDT , 1 If single-rooted trees are a prerequisite, the most probable node will be selected among multiple root nodes. Hebrew HTB , Kazakh KTB and Tamil TTB , as a representative sample, following (de Lhoneux et al., 2017). As evaluation metrics, we use Labeled (LAS) and Unlabeled Attachment Score (UAS). We measure speed in sentences/second, both on a single core of a CPU 2 and on a GPU 3 . Setup We use NCRFpp as our sequence labeling framework (Yang and Zhang, 2018). For PTB, we use the embeddings by Ling et al. (2015), for comparison to BIST parser (Kiperwasser and Goldberg, 2016), which uses a similar architecture, but also needs a parsing algorithm and auxiliary structures. For UD, we follow an end-to-end setup and run UDPipe 4 (Straka and Strakova, 2017) for tok-enization and tagging. We use the pretrained word embeddings by Ginter et al. (2017). Appendix A contains additional hyperparameters. We first examine the four encodings on the PTB dev set. Table 1 shows the results and also compares them against Li et al. (2018), who proposed seq2seq and sequence labeling models that use a relative positional encoding. As the relative PoS-based encoding and bracketing-based encoding provide the best results, we will conduct the rest of our experiments with these two encodings. Furthermore, we perform a small hyperparameter search involving encoding, number of hidden layers, their dimension and presence of character embeddings, as these parameters influence speed and accuracy. From now on, we write P zx , y for a PoS-based encoding model and B zx , y for a bracketing-based encoding 2 Intel Core i7-7700 CPU 4.2 GHz. model, where z indicates whether character representation was used in the model, x the number of BiLSTM layers, and y the word hidden vector dimension. We take as starting points (1) the hyperparameters used by the BIST parser (Kiperwasser and Goldberg, 2016), as it uses a BiLSTM architecture analogous to ours, with the difference that it employs a transition-based algorithm that uses a stack data structure instead of plain sequence labeling without explicit representation of structure, and (2) the best hyperparameters used by Gomez-Rodrguez and Vilares (2018) for constituent parsing as sequence labeling, as it is an analogous task for a different parsing formalism. From there, we explore different combinations of parameters and evaluate 20 models on the PTB development set, with respect to accuracy (UAS) and speed (sentences/second on a single CPU core), obtaining the Pareto front in Figure 2. The two starting models based on previous literature ( P 2 , 250 and PC 2 , 800 , respectively) happen to be in the Pareto front, confirming that they are reasonable hyperparameter choices also for this setting. In addition, we select two more models from the Pareto front (models P C2 , 400 and B 2 , 250 ) for our test set experiments on PTB, as they also provide a good balance between speed and accuracy. Table 2 compares the chosen models, on the PTB test set, against state-of-the-art mod-5 based on the test set. 7 Tamil was run on gold segmented and tokenized inputs, as there is no pretrained UDpipe model. We did not use pretrained word embeddings either. els. Contrary to previous dependency-parsing-as-sequence-labeling attempts, we are competitive and provide a good speed-accuracy tradeoff. For instance, the P C2 , 800 model runs faster than the BIST parser (Kiperwasser and Goldberg, 2016) while being almost as accurate (-0.18 LAS). This comes in spite of its simplicity. While our BiLSTM architecture is similar to that of BIST, the sequence labeling approach does not need a stack, a specific transition system or a dynamic oracle. Using the BIST hyperparameters for our model ( P 2 , 250 ) yields further increases in speed, at some cost to accuracy: 3.34x faster and -0.04 LAS score than the graph-based model, and 3.51x faster and Treebank P C2 , 800 KG (transition-based) PoS type (sent/s) UAS LAS (sent/s) UAS LAS CPU CPU Ancient Greek XPOS 123  1 75.31 70.87 116  4 69.43 64.41 Chinese UPOS 105  0 63.20 59.12 73  1 64.69 60.45 Czech UPOS 125  1 89.10 86.68 94  3 89.25 86.11 English UPOS 139  1 81.48 78.64 120  2 82.22 79.00 Finnish UPOS 168  0 80.12 76.22 127  3 80.99 76.63 Hebrew equal PoS 120  0 63.04 58.66 70  1 63.56 58.80 Kazakh XPOS 283  3 32.93 17.07 178  5 23.09 12.73 Tamil 7 UPOS 150  2 71.59 64.00 127  3 75.41 68.58 Table 4: Comparison on UD-CoNLL18 test sets. We now extend our experiments to the sample of UD-CoNLL18 treebanks. To this end, we focus on the PC 2 , 800 model and since our PoS tag-based encoding can be influenced by the specific PoS tags used, we first conduct an experiment on the development sets to determine what tag set (UPoS, the universal PoS tag set, common to all languages, or XPoS, extended language-specific PoS tags) produces the best results for each dataset. Table 3 shows how the number of unique UPoS and XPoS tags found in the training set differs in various languages. The results suggest that the performance of our system can be influenced by the size of the tag set. It appears that a very large tag set (for instance the XPoS tag set for Czech and Tamil) can hurt the performance of the model and significantly slow down the system, as it results into a large number of distinct labels for the sequence labeling model, increasing sparsity and making the classification harder. In case of Ancient Greek and Kazakh, the best performance is achieved with the XPoS-based encoding. In these corpora, the tag set is slightly bigger than the UPoS tag set. One can argue that the XPoS tags in this case were possibly more fine-grained and hence provided additional useful information to the system facilitating a correct label prediction, without being so large as to produce excessive sparsity. Table 4 shows experiments on the UD test sets, with the chosen PoS tag set for each corpus. P C2 , 800 outperforms transition-based BIST in LAS in 3 out of 8 treebanks, 8 and is clearly faster in all analyzed 8 For Ancient Greek, this may be related to the large languages. We believe that the variations between languages in terms of LAS difference with respect to BIST can be largely due to differences in the accuracy and granularity of predicted PoS tags, since our chosen encoding relies on them to encode arcs. The bracketing-based encoding, which does not use PoS tags, may be more robust to this. On the other hand, finding the optimal granularity of PoS tags for the PoS-based encoding can be an interesting avenue for future work. In this work, we have also examined the impact of the training data size on the performance of our system compared to the performance of BIST parser. The results in Figure 3 suggest that our model requires more data during the training than BIST parser in order to achieve similar performance. The performance is slightly worse when little training data is available, but later on our model reduces the gap when increasing the training data size. This paper has explored fast and accurate dependency parsing as sequence labeling. We tested four different encodings, training a standard BiLSTM-based architecture. In contrast to previous work, our results on the PTB and a subset of UD treebanks show that this paradigm can obtain competitive results, despite not using any parsing algorithm nor external structures to parse sentences. This work has received funding from the European Research Council (ERC), under the European Union's Horizon 2020 research and innovation programme (FASTPARSE, grant agreement No 714150), from the TELEPARES-UDC project (FFI2014-51978-C2-2-R) and the ANSWER-ASAP project (TIN2017-85160-C2-1-R) from MINECO, and from Xunta de Galicia (ED431B 2017/01). We gratefully acknowledge NVIDIA Corporation for the donation of a GTX Titan X GPU. amount of non-projectivity (BIST is a projective parser). For extra comparison, a non-projective variant of BIST (Smith et al., 2018) obtains 71.58 LAS with mono-treebank training, but from better segmentation and morphology than used here. UDpipe (Straka and Strakov  a, 2017) obtains 67.57 LAS. Czech and Kazakh have a medium amount of non-projectivity.
objective abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain objective method result other abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain method other method abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain other other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain other abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain objective method objective other other other other other other