We propose a new method for projective dependency parsing based on headed spans. In a projective dependency tree, the largest subtree rooted at each word covers a contiguous sequence (i.e., a span) in the surface order. We call such a span marked by a root word headed span . A projective dependency tree can be represented as a collection of headed spans. We decompose the score of a dependency tree into the scores of the headed spans and design a novel O ( n 3 ) dynamic programming algorithm to enable global training and exact inference. Our model achieves state-of-the-art or competitive results on PTB, CTB, and UD 1 . Dependency parsing is an important task in natural language processing, which has numerous applications in downstream tasks, such as opinion mining (Zhang et al., 2020a), relation extraction (Jin et al., 2020), named entity recognition (Jie and Lu, 2019), machine translation (Bugliarello and Okazaki, 2020), among others. There are two main paradigms in dependency parsing: graph-based and transition-based methods. Graph-based methods decompose the score of a tree into the scores of parts. In the simplest first-order graph-based methods (McDonald et al., 2005, inter alia) , the parts are single dependency arcs. In higher-order graph-based methods (Mc-Donald and Pereira, 2006; Carreras, 2007; Koo and Collins, 2010; Ma and Zhao, 2012), the parts are combinations of multiple arcs. Transition-based methods (Nivre and Scholz, 2004; Chen and Manning, 2014, inter alia) read the sentence sequentially and conduct a series of local decisions to build the final parse. Recently, transition-based  Corresponding Author 1 Our code is publicly available at https://github.com/sustcsonglin/span-based-dependency-parsing methods with Pointer Networks (Vinyals et al., 2015) have obtained competitive performance to graph-based methods (Ma et al., 2018; Liu et al., 2019; Fernndez-Gonzlez and Gmez-Rodrguez, 2019; Fernndez-Gonzlez and Gmez-Rodrguez, 2021). A main limitation of first-order graph-based methods is that they independently score each arc based solely on the two words connected by the arc. Ideally, the appropriateness of an arc should depend on the whole parse tree, particularly the subtrees rooted at the two words connected by the arc. Although subtree information could be implicitly encoded (Falenska and Kuhn, 2019) in powerful neural encoders such as LSTMs (Hochreiter and Schmidhuber, 1997) and Transformers (Vaswani et al., 2017), there is evidence that their encoding of such information is inadequate. For example, higher-order graph-based methods, which capture more subtree information by simultaneously considering multiple arcs, have been found to outperform first-order methods despite using powerful encoders (Fonseca and Martins, 2020; Zhang et al., 2020b; Wang and Tu, 2020). In contrast to the line of work on higher-order parsing, we propose a different way to incorporate more subtree information as discussed later. Transition-based methods, on the other hand, can easily utilize information from partially built subtrees, but they have their own shortcomings. For instance, most of them cannot perform global optimization during decoding 2 and rely on greedy or beam search to find a locally optimal parse, and their sequential decoding may cause error propagation as past decision mistakes will negatively affect the decisions in the future. To overcome the aforementioned limitations of 2 We are aware of few transition-based parsers performing global optimization via dynamic programming algorithms, cf. first-order graph-based and transition-based methods, we propose a new method for projective dependency parsing based on so-called headed spans. A projective dependency tree has a nice structural property that the largest subtree rooted at each word covers a contiguous sequence (i.e., a span) in the surface order. We call such a span marked with its root word a headed span . A projective dependency tree can be treated as a collection of headed spans such that each word corresponds to exactly one headed span, as illustrated in Figure 1. For example, (0 , 5 , inventory ) is a headed span, in which span (0 , 5) has a head word inventory . In this view, projective dependency parsing is similar to constituency parsing as a constituency tree can be treated as a collection of constituent spans. The main difference is that in a binary constituency tree, a constituent span ( i, k ) is made up by two adjacent spans ( i, j ) and ( j, k ) , while in a projective dependency tree, a headed span ( i, k, x h ) is made up by one or more smaller headed spans and a single word span ( h  1 , h ) . For instance, (0 , 5 , inventory ) is made up by (0 , 1 , An ) , (1 , 2) and (2 , 5 , of ) . There are a few constraints between headed spans to force projectivity (section 3). These structural constraints are the key to designing an efficient dynamic programming algorithm for exact inference. Because of the similarity between constituency parsing and our head-span-based view of projective dependency parsing, we can draw inspirations from the constituency parsing literature to design our dependency parsing method. Specifically, span-based constituency parsers (Stern et al., 2017; Kitaev and Klein, 2018; Zhang et al., 2020c; Xin et al., 2021) decompose the score of a constituency tree into the scores of its constituent spans and use the CYK algorithm (Cocke, 1969; Younger, 1967; Kasami, 1965) for global training and inference. Built upon powerful neural encoders, they have obtained state-of-the-art performance in constituency parsing. Inspired by them, we propose to decompose the score of a projective dependency tree into the scores of headed spans and design a novel O ( n 3 ) dynamic programming algorithm for global training and exact inference, which is on par with the Eisner algorithm (Eisner, 1996) in time complexity for projective dependency parsing. We make a departure from existing graph-based methods since we do not model dependency arcs directly. Instead, the dependency arcs are induced from the collection of headed spans (section 3). Compared with first-order graph-based methods, our method can utilize more subtree information since a headed span contains all children (if any) of the corresponding headword (and all words within the subtree). Compared with most of transition-based methods, our method allows global training and exact inference and does not suffer from error propagation or exposure bias. Our contributions can be summarized as follows:  We treat a projective dependency tree as a collection of headed spans, providing a new perspective of projective dependency parsing. We design a novel O ( n 3 ) dynamic programming algorithm to enable global training and exact inference for our proposed model. We have obtained the state-of-the-art or competitive results on PTB, CTB, and UD v2.2, showing the effectiveness of our proposed method. We adopt the two-stage parsing strategy, i.e., we first predict an unlabeled tree and then predict the dependency labels. Given a sentence x 1 , ..., x n , its unlabeled projective dependency parse tree y can be regarded as a collection of headed spans ( l i , r i , x i ) where 1  i  n . For each word x i , we can find exactly one headed span ( l i , r i , i ) (where l i and r i are the left and right span boundaries) given parse tree y , so there are totally n headed spans in y as we can see in Figure 1. We can use a simple post-order traversal algorithm to obtain all headed spans in O ( n ) time. We then define the score of y as: s ( y ) = (cid:88) i =1 ,...,n s span l i ,r i ,i and we show how to compute them using neural networks in the next section. Our parsing algorithm is based on the following key observations:  For a given parent word x k , if it has any children to the left (right), then all headed spans of its children in this direction should be consecutive and form a larger span, which we refer to as the left (right) child span. The left (right) boundary of the headed span of x k is the left (right) boundary of the leftmost (rightmost) child span, or k  1 ( k ) if x k has no child to the left (right). If a parent word x k has children in both directions, then its left span and right span are separated by the single word span ( k  1 , k ) . Based on these observations, we design the following parsing items: (1)  i,j : the accumulated score of span ( i, j ) serving as a left or right child span. (2)  i,j,k : the accumulated score of the headed span ( i, j, k ) . We use the parsing-as-deduction framework (Pereira and Warren, 1983) to describe our algorithm in Fig. 2. We draw  i,j as rectangles and  i,j,k as triangles. The rule S-CONC is used to concatenate two consecutive child spans into a single child span; C-CONC is used to concatenate left and right child span ( i, k  1) and ( k, j ) along with the root word-span ( k  1 , k ) to form a headed span ( i, j, k ) ; HEADLESS is used to obtain a headless child span from a headed span. Fig. 2 corresponds to the following recursive formulas:  i,i +1 ,i +1 = s span i,i +1 ,i +1 (1)  i,i = 0 (2)  i,j,k =  i,k  1 +  k,j + s span i,j,k (3)  i,j = max( max i<k<j (  i,k +  k,j ) , max i<h  j (  i,j,h )) (4) We set  i,i = 0 for the convenience of calculating  i,j,k when x k does not have children on either side. In Eq. 4, we can see that the child span comes from either multiple smaller consecutive child spans (i.e., max i<k<j (  ( i, k ) +  ( k, j )) ) or a single headed span (i.e., max i<h  j (  ( i, j, h ))) ). We also maintain backpointers based on these equations (i.e., maintain all arg max ) for parsing. A key point of our parsing algorithm is that, during backtracking, we add arcs emanated from the headword of a large headed span to every headword of (zero or more) smaller headed spans within the left/right child span, so that we can induce a dependency tree. Finding all smaller headed spans within left and right child spans requires finding the best segmentation, which is similar to the inference procedure of the semi-Markov CRF model 2190 C-L-CONC : i c k s 1 k h j s 2 i h j s 1 + s 2 + s arc h,c C-R-CONC : i h k s 1 k c j s 2 i h j s 1 + s 2 + s arc h,c ES-R-CONC : i h k s 1 k +1 j h s 2 i h j s 1 + s 2 ES-R-LINK : i c j s 1 i j h s 1 + s arc h,c ES-L-CONC : i k  1 h s 1 k h j s 2 i h j s 1 + s 2 ES-L-LINK : i c j s 1 i j h s 1 + s arc h,c E-L-CONC : j k s 1 k i s 2 j i s 1 + s 2 E-L-LINK : j k  1 s 1 k i s 2 j i s 1 + s 2 + s arc i,j E-R-CONC : i k s 1 k j s 2 i j s 1 + s 2 E-R-LINK : i k s 1 k +1 j s 2 i j s 1 + s 2 + s arc i,j R-CONC : i k h s 1 k j h s 2 i j h s 1 + s 2 L-CONC : i k h s 1 k j h s 2 i j h s 1 + s 2 CONC : i h h s 1 h + 1 j h s 2 i h j s 1 + s 2 Figure 3: Deductive rules of the parsing algorithms of Collins (1996) (the first line), Eisner and Satta (1999) (the second line), Eisner (1997) (the third line). Parsing complexity. From Eq. 1 to 4, we can see that at most three variables (i.e., i, j, k ) are required to iterate over and therefore the total parsing time complexity is O ( n 3 ) . Spurious ambiguity. Note that different order of concatenation of child spans can result in the same parse, although this does not affect finding the optimal parse. Comparison with previous parsing algorithms. We compare our algorithm with three classical parsing algorithms (Collins, 1996; Eisner and Satta, 1999; Eisner, 1997) in order to help readers better understand our algorithm. We only consider their pure dependency versions 3 for the convenience of discussion. Fig. 2 shows the deductive rules of the three algorithms. Collins (1996) adapt the CYK algorithm by maintaining head positions for both sides, thereby 3 The parsing algorithms of Collins (1996) and Eisner and Satta (1999) are defined with (lexicalized) context-free gramars. Gmez-Rodrguez et al. (2008, 2011) provide their pure dependency versions, which amounts to considering arc scores only. increasing the parsing complexity from O ( n 3 ) to O ( n 5 ) . Their parsing items are identified by two endpoints and a head position, which is similar to our concept of headed spans superficially. However, in their algorithm, there could be multiple spans sharing the same head position within a single parse. For instance, ( i, j ) and ( k, j ) share the same head position h in C-L-CONC . In contrast, spans cannot share a head position in a single parse under our definition, because there is exactly one headed span for each word. Besides, the concatenation order of subtrees differs. Eisner and Satta (1999) note that the linking of heads and the concatenation of subtrees can be separated (e.g., C-R-CONC can be decomposed into two rules, ES-R-CONC and ES-R-LINK ) so that the parsing complexity can be reduced to O ( n 4 ) . This strategy is also known as the hook trick, which reduces subtrees to headless spans (e.g., ( i, c, j ) to ( i, j ) in ES-L-LINK and ES-R-LINK ). Eisner (1997) uses the head-splitting trick to decrease parsing complexity to O ( n 3 ) . The key idea is to split each subtree into a left and a right fragment, so that the head is always placed at one of the two boundaries of a fragment instead of an 2191 internal position, thereby eliminating the need of maintaining the head positions. Our algorithm adopts a combination of the hook trick and the head-splitting trick. Starting from the rules of Eisner and Satta (1999) that apply the hook trick, we can rewrite ES-L-CONC , ES-R-CONC as L-CONC , R-CONC and CONC . It is easy to verify the equivalence of the rules before and after the rewrite 4 . The key difference is in the concatenation order of subtrees. We concatenate all subtrees to the left/right of the new head first, which can be viewed as adopting the head-splitting trick. Then, note that the position of the head is uniquely determined by the two concatenations of subtrees, and that our model does not consider s arc . Consequently, we have no need to maintain head position h in L-CONC and R-CONC and can merge these two rules to S-CONC of fig. 2. Accordingly, CONC can be modified to C-CONC of fig. 2. Eliminating bookkeeping of h is how we can obtain better parsing complexity than Eisner and Satta (1999). Finally, we can incorporate span score s span i,j,h into C-CONC . We add <bos> (beginning of sentence) at x 0 and <eos> (end of sentence) at x n +1 . In the embedding layer, we apply mean-pooling to the last layer of BERT (Devlin et al., 2019) (i.e., taking the mean value of all subword embeddings) to generate dense word-level representation e i for each token x i 5 . Then we feed e 0 , ..., e n +1 into a 3-layer bidirectional LSTM (BiLSTM) to get c 0 , ..., c n +1 , where c i = [ f i ; b i ] and f i and b i are the forward and backward hidden states of the last BiLSTM layer at position i respectively. We then use the fencepost representation, which is commonly used in constituency parsing (Cross and Huang, 2016; Stern et al., 2017), to encode span ( i, j ) as e i,j : h k = [ f k , b k +1 ] e i,j = h j  h i After obtaining the word and span representations, we use deep biaffine function (Dozat and 4 Note that this only holds for the pure dependency version, since otherwise we cannot track some intermediate constituent spans after changing the concatenation order of subtrees. Manning, 2017) to score headed spans: c (cid:48) k = MLP word ( c k ) e (cid:48) i,j = MLP span ( e i,j ) s span i,j,k = (cid:2) c (cid:48) k ; 1 (cid:3) (cid:62) W span (cid:2) e (cid:48) i,j ; 1 (cid:3) where MLP word and MLP span are multi-layer per-ceptrons (MLPs) that project word and span representations into d -dimensional spaces respectively; W span  R ( d +1)  ( d +1) . Similarly, we use deep biaffine functions to score the labels of dependency arcs for a given gold or predicted tree 6 : c (cid:48) i = MLP parent ( c i ) c (cid:48) j = MLP child ( c j ) s label i,j,r = (cid:2) c (cid:48) i ; 1 (cid:3) (cid:62) W label r (cid:2) c (cid:48) j ; 1 (cid:3) where MLP parent and MLP child are MLPs that map word representations into d (cid:48) -dimensional spaces; W label r  R ( d (cid:48) +1)  ( d (cid:48) +1) for each relation type r  R in which R is the set of all relation types. Following previous work, we decompose the training loss into the unlabeled parse loss and arc label loss: L = L + L which is akin to the head-selection loss (Dozat and Manning, 2017), or use global structural loss. Experimentally, we find that the max-margin loss (Taskar et al., 2004) (also known as structured SVM) performs best. The max-margin loss aims to maximize the margin between the score of the gold tree y and the incorrect tree y (cid:48) of the highest score: L parse = max(0 , max y (cid:48) (cid:54) = y ( s ( y (cid:48) ) + ( y (cid:48) , y )  s ( y )) (5) 6 In our preliminary experiments, we find that directly calculating the scores based on parent-child word representations leads to a slightly better result (< 0.1 LAS) than those based on span representations. A possible reason is that, since LAS is arc-factorized, even if we predict a correct parent-child pair, we can predict the wrong headed spans for the parent or child or both, thereby negatively affecting the labeling scores and resulting in worse LAS. Therefore, in our work we use arc-based label scores to suit the LAS metric. where  measures the difference between the incorrect tree and gold tree. Here we let  to be the Hamming distance (i.e., the total number of mismatches of headed spans). We can perform cost-augmented inference (Taskar et al., 2005) to compute Eq. 5. Finally, we use cross entropy for L label : L label = (cid:88) ( x i  x j ,r )  y  log exp( s label i,j,r ) (cid:80) r (cid:48)  R exp( s label i,j,r (cid:48) ) where ( x i  x j , r )  y denotes every dependency arc from x i to x j with label r in y . Following Wang and Tu (2020), we evaluate our proposed method on Penn Treebank (PTB) 3.0 (Marcus et al., 1993), Chinese Treebank (CTB) 5.1 (Xue et al., 2005) and 12 languages on Universal Dependencies (UD) 2.2: BG-btb, CA-ancora, CS-pdt, DE-gsd, EN-ewt, ES-ancora, FR-gsd, IT-isdt, NL-alpino, NO-rrt, RO-rrt, RU-syntagrus 7 . For PTB, we use the Stanford Dependencies conversion software of version 3.3 to obtain dependency trees. For CTB, we use head-rules from Zhang and Clark (2008) and Penn2Malt 8 to obtain dependency trees. Following Wang and Tu (2020), we use gold POS tags for CTB and UD. We do not use POS tags in PTB. For PTB/CTB, we drop all nonprojective trees during training. For UD, we use MaltParser v1.9.2 9 to adopt the pseudo-projective transformation (Nivre and Nilsson, 2005) to convert nonprojective trees into projective trees when training, and convert back when evaluating, for both our model and reimplemented baseline model. See Appd. B for implementation details. We report the unlabeled attachment score (UAS) and labeled attachment score (LAS) averaged from three runs with different random seeds. In each run, we select the model based on the performance on the development set. Following Wang and Tu (2020), we ignore all punctuation marks during evaluation. 7 We do not concatenate all datasets during training. We train on each dataset separately. 8 https://cl.lingfil.uu.se/~nivre/ research/Penn2Malt.html 9 http://www.maltparser.org/download. Table 1 shows the results on PTB and CTB. Note that Biaffine+MM is our reimplementation of the Biaffine Parser that uses the same setting as in our method, including the use of the max-margin loss instead of the local head-selection loss. Interestingly, we find that Biaffine+MM has already 2193 bg ca cs de en es fr it nl no ro ru Avg TreeCRF2O 90.77 91.29 91.54 80.46 87.32 90.86 87.96 91.91 88.62 91.02 86.90 93.33 89.33 MFVI2O 90.53 92.83 92.12 81.73 89.72 92.07 88.53 92.78 90.19 91.88 85.88 92.67 90.07 +BERT multilingual MFVI2O 91.30 93.60 92.09 82.00 90.75 92.62 89.32 93.66 91.21 91.74 86.40 92.61 90.61 Biaffine+MM  90.30 94.49 92.65 85.98 91.13 93.78 91.77 94.72 91.04 94.21 87.24 94.53 91.82 Ours 91.10 94.46 92.57 85.87 91.32 93.84 91.69 94.78 91.65 94.28 87.48 94.45 91.96 Table 2: Labeled Attachment Score (LAS) on twelve languages in UD 2.2. surpassed many strong baselines, and this may be due to the proper choices of hyperparameters and the use of the max-margin loss (we observe that using the max-margin loss leads to a better performance compared with the original head-selection loss), so Biaffine+MM is a very strong baseline. It also has the same number of parameters as our methods. Our method surpasses Bi-affine+MM on both datasets, showing the competitiveness of our headed-span-based method in a fair comparison with first-order graph-based parsing. Our method also obtains the state-of-the-art result among methods that only use dependency training data (HPSG+LAL uses additional constituency trees as training data, so it is not directly comparable with the other systems.). Table 2 shows the results on UD. We can see that our reimplemented Biaffine+MM has already surpassed MFVI2O, which utilizes higher-order information. Our method outperforms Biaffine+MM by 0.14 LAS on average, validating the effectiveness of our proposed method in the multilingual scenarios. Table 3 shows the influence of the training loss function. We find that the max-margin loss performs better on both datasets: 0.17 UAS improvement on PTB and 0.05 UAS improvement on CTB comparing to the local span-selection loss, which shows the effectiveness of using global loss. As previously argued, first-order graph-based methods are insufficient to model complex subtrees, so they may have difficulties in parsing long sentences and handling long-range dependencies. To verify this, we follow (McDonald and Nivre, 2011) to plot UAS as a function of the sentence length and plot F1 scores as functions of the distance to root and dependency length on the CTB test set. We additionally plot the F1 score of the predicted headed spans against the gold headed spans with different span lengths. From Figure 4a, we can see that Biaffine+MM has a better UAS score on short sentences (of length <=20), while for long sentences (of length >=30), our headed span-based method has a higher performance, which validates our conjecture. Figure 4b shows the F1 score for arcs of varying distances to root. Our model is better at predicting arcs of almost all distances to root in the dependency tree, which reveals our model's superior ability to predict complex subtrees. Figure 4c shows the F1 score for arcs of varying lengths. Both Biaffine+MM and our model have a very similar performance in predicting arcs of distance < 7, while our model is better at predicting arcs of distance >= 7, which validates the ability of our model at capturing long-range dependencies. Figure 4d shows the F1 score for headed spans of varying lengths. We can see that when the span length is small (<=10), Biaffine+MM and our model have a very similar performance. However, our model is much better in predicting longer spans (especially for spans of length >30). Inspired by Zhang et al. (2020b) and Rush (2020) who independently propose to batchify the Eisner algorithm using Pytorch , we batchify our proposed method so that O ( n 2 ) out of O ( n 3 ) can be computed in parallel, which greatly accelerates parsing. We achieve a similar parsing speed of our method to the fast implementation of the Eisner algorithm by Zhang et al. (2020b): it parses 273 sentences per second, using BERT as the encoder under a single TITAN RTX GPU. Dependency parsing with more complex subtree information. There has always been an interest to incorporate more complex subtree information into graph-based and transition-based methods since their invention. Before the deep learning era, it was difficult to incorporate sufficient contextual information in first-order graph-based parsers. To mitigate this, researchers develop higher-order dependency parsers to capture more contextual information (McDonald and Pereira, 2006; Car-reras, 2007; Koo and Collins, 2010; Ma and Zhao, 2012). However, incorporating more complex factors worsens inference time complexity. For example, exact inference for third-order projective dependency parsing has a O ( n 4 ) time complexity and exact inference for higher-order non-projective dependency parsing is NP-hard (McDonald and Pereira, 2006). To decrease inference complexity, researchers use approximate parsing methods. Smith and Eisner (2008) use belief propagation (BP) framework for approximate inference to trade accuracy for efficiency. They show that third-order parsing can be done in O ( n 3 ) time using BP. Gorm-ley et al. (2015) unroll the BP process and use gradient descent to train their parser in an end-to-end manner. Wang and Tu (2020) extend their work by using neural scoring functions to score factors. For higher-order non-projective parsing, researchers resort to dual decomposition algorithm (e.g., AD 3 ) for decoding (Martins et al., 2011, 2013). They observe that the approximate decoding algorithm often obtains exact solutions. Fonseca and Martins (2020) combine neural scoring functions and their decoding algorithms for non-projective higher-order parsing. Zheng (2017) proposes a incremental graph-based method to utilize higher-order information without hurting the advantage of global inference. Ji et al. (2019) use a graph attention network to incorporate higher-order information into the Biaffine Parser. Zhang et al. (2020b) enhance the Biaffine Parser by using a deep triaffine function to score sibling factors. Mohammadshahi and Henderson (2021) propose an iterative refinement network that injects the predicted soft trees from the previous iteration to the self-attention layers to predict the soft trees of the next iteration, so that information of the whole tree is considered in parsing. As for transition-based methods, Ma et al. (2018); Liu et al. (2019); Fernndez-Gonzlez and Gmez-Rodrguez (2021) incorporate sibling and grandparent information into transition-based parsing with Pointer Networks. The hook trick and the head-splitting trick. These two tricks have been used in the parsing literature to accelerate parsing. Eisner and Satta (1999, 2000) use the hook trick to decrease the parsing complexity of lexicalized PCFGs and Tree Adjoining Grammars. Huang et al. (2005, 2009) adapt the hook trick to accelerate machine translation decoding. The parsing algorithms of Corro (2020) and Xin et al. (2021) can be viewed as adapting the hook trick to accelerate discontinuous and continuous constituency parsing, respectively. Eisner (1997); Satta and Kuhlmann (2013) use the head-splitting trick to accelerate projective and nonprojective dependency parsing. Span-based constituency parsing. Span-based parsing is originally proposed in continuous constituency parsing (Stern et al., 2017; Kitaev and Klein, 2018; Zhang et al., 2020c; Xin et al., 2021). Span-based constituency parsers decompose the score of a constituency tree into the scores of its constituents. Recovering the highest-scoring tree can be done via the exact CYK algorithm or greedy top-down approximate inference algorithm (Stern et al., 2017). Kitaev and Klein (2018) propose a self-attentive network to improve the parsing accuracy. They separate content and positional attentions and show the improvement. Zhang et al. (2020c) use a two-stage bracketing-then-labeling framework and replace the max-margin loss with the TreeCRF loss (Finkel et al., 2008). Xin et al. (2021) recently propose a recursive semi-Markov model, incorporating sibling factor scores into the score of a tree to explicitly model n-ary branching structures. Corro (2020) adapts span-based parsing to discontinuous constituency parsing and obtains the state-of-the-art result. In this work, we have presented a headed-span-based method for projective dependency parsing. Our proposed method can utilize more subtree information and meanwhile enjoy global training and 2195 exact inference. Experiments show the competitive performance of our method in multiple datasets. In addition to its empirical competitiveness, we believe our work provides a novel perspective of projective dependency parsing and could lay the foundation for further algorithmic advancements in the future. We thank the anonymous reviewers for their constructive comments. This work was supported by the National Natural Science Foundation of China (61976139).
objective abstain abstain abstain objective result abstain abstain abstain abstain abstain abstain other abstain abstain abstain abstain objective abstain abstain method objective abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain objective abstain abstain objective method objective objective objective abstain abstain abstain abstain abstain method abstain abstain method abstain method abstain other method abstain abstain abstain method other abstain abstain abstain abstain abstain abstain method method abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain method method abstain abstain abstain method abstain abstain abstain abstain method method abstain other other method method abstain abstain other abstain method abstain abstain abstain abstain method other result result abstain abstain abstain abstain abstain abstain method method method method method other abstain abstain result result abstain abstain result abstain result abstain abstain abstain abstain abstain method abstain abstain abstain abstain method abstain abstain method abstain abstain abstain other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other method objective result objective other other