Headed-Span-Based Projective Dependency Parsing (2022)

Abstract: 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

## introduction dependency parsing is an important task in natural language processing, which has numerous applications in downstream tasks, such as opinion mining @xcite , relation extraction @xcite , named entity recognition @xcite , machine translation @xcite ), 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 @xcite , inter alia), the parts are single dependency arcs. in higher-order graph-based methods @xcite @xcite , the parts are combinations of multiple arcs. transition-based methods @xcite , inter alia) read the sentence sequentially and conduct a series of local decisions to build the final parse. recently, transition-based methods with pointer networks @xcite have obtained competitive performance to graph-based methods @xcite @xcite . 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 @xcite in powerful neural encoders such as lstms @xcite and transformers @xcite , 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 @xcite @xcite . 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 foot_0 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 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, spanbased constituency parsers @xcite @xcite decompose the score of a constituency tree into the scores of its constituent spans and use the cyk algorithm @xcite @xcite 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 @xcite 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 transitionbased 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: figure 2: deduction rules for our proposed parsing algorithm. all deduction items are annotated with their scores. ## parsing 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 ≤ @xmath0. 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: our parsing algorithm is based on the following key observations: 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-asdeduction framework @xcite 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: we set α i,@xmath1,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., 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 c-l-conc: 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). the last line is the resulting deduction rules after applying headsplitting on es-l-conc and es-r-conc. all deduction items are annotated with their scores. we only consider the pure dependency versions of these algorithms. we omit axiom items for simplicity. @xcite . we provide the pseudocode of our parsing algorithm in appd. a. 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 foot_1 ). 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. ## conclusion in this work, we have presented a headed-spanbased method for projective dependency parsing. our proposed method can utilize more subtree information and meanwhile enjoy global training and 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.