Combining (Second-Order) Graph-Based and Headed-Span-Based Projective Dependency Parsing (2022)

Abstract: Graph-based methods, which decompose the score of a dependency tree into scores of dependency arcs, are popular in dependency parsing for decades. Recently, (CITATION) propose a headed-span-based method that decomposes the score of a dependency tree into scores of headed spans. They show improvement over first-order graph-based methods. However, their method does not score dependency arcs at all, and dependency arcs are implicitly induced by their cubic-time algorithm, which is possibly sub-optimal since modeling dependency arcs is intuitively useful. In this work, we aim to combine graph-based and headed-span-based methods, incorporating both arc scores and headed span scores into our model. First, we show a direct way to combine with O(n^4) parsing complexity. To decrease complexity, inspired by the classical head-splitting trick, we show two O(n^3) dynamic programming algorithms to combine first- and second-order graph-based and headed-span-based methods. Our experiments on PTB, CTB, and UD show that combining first-order graph-based and headed-span-based methods is effective. We also confirm the effectiveness of second-order graph-based parsing in the deep learning age, however, we observe marginal or no improvement when combining second-order graph-based and headed-span-based methods .

## introduction dependency parsing is an important task in natural language processing. there are many methods to tackle projective dependency parsing. in this paper, we focus on two kinds of global methods: graphbased and headed-span-based methods. they both score all parse trees and globally find the highest reads child the the child reads book a a book the a child book reads figure 1 : an example projective dependency parse tree with all its headed spans. to decrease the parsing complexity, inspired by the classical head-splitting trick @xcite , we propose to decompose the score of a headed span into two terms, assuming that the score of the left span boundary is independent of that of the right span boundary for each headword. this allows us to adapt the eisner algorithm to parse in cubic time considering both arc and headed span scores ( §3.2) at the cost of imposing a stronger independence assumption. more interestingly, we can also combine second-order graph-based and headed-span-based methods and need only cubic time to parse ( §3.3), which would be much slower (to the best of our knowledge, o(n 7 )) if we do not apply the headsplitting trick. we conduct extensive experiments on ptb, ctb, and ud. we find that combining first-order graphbased and headed-span-based methods is effective, and applying the head-splitting trick or not result in a similar performance, thus it is more advantageous to apply this trick to enjoy a lower parsing complexity. we also confirm the effectiveness of secondorder parsing in the deep learning age, however, we observe only marginal improvement or even no improvement when combining second-order graphbased and headed-span-based methods. ## parsing we use the parsing-as-deduction framework @xcite to describe the parsing algorithms of our proposed models. r-comb: figure 2: deduction rules for our modified eisner-satta algorithm @xcite . our modifications are highlighted in red. all deduction items are annotated with their scores. note that "finished" spans are marked by double underlines, whereas "unfinished' spans take the original triangle notations. figure 3: deduction rules for our modified eisner algorithm @xcite (first two rows) and its second-order extension @xcite ) (all rows). our modifications are highlighted in red. all deduction items are annotated with their scores. note that "finished" (in)complete spans are marked by double underlines. ## conclusion in this paper, we have studied different ways to combine graph-based and headed-span-based methods. we found that applying the head-splitting trick can retain the cubic parsing complexity and meanwhile improve parsing performance when combining first-order graph-based and headed-span-based methods. we also confirmed the effectiveness of second-order parsing, however, we observed marginal or no improvement when combining it with the headed-span-based method. benjamin taskar, vassil chatalbashev, daphne koller, and carlos guestrin. 2005. learning structured prediction models: a large margin approach. in machine learning, proceedings of the twenty-second international conference (icml 2005), bonn, germany, august 7-11, 2005, volume 119 of acm international conference proceeding series, pages 896-903. acm. xinyu wang and kewei tu. 2020. second-order neural dependency parsing with message passing and endto-end training. in proceedings of the 1st conference of the asia-pacific chapter of the association for computational linguistics and the 10th international joint conference on natural language processing, pages 93-99, suzhou, china. association for computational linguistics. naiwen xue, fei xia, fu-dong chiou, and martha palmer. 2005. the penn chinese treebank: phrase structure annotation of a large corpus. nat. lang. eng., 11(2):207-238. songlin yang and kewei tu. 2022. headed-span-based projective dependency parsing. in acl. yu zhang, zhenghua li, and min zhang. 2020. efficient second-order treecrf for neural dependency parsing. in proceedings of the 58th annual meeting of the association for computational linguistics, pages 3295-3305, online. association for computational linguistics. junru zhou and hai zhao. 2019. head-driven phrase structure grammar parsing on penn treebank. in proceedings of the 57th annual meeting of the association for computational linguistics, pages 2396-2408, florence, italy. association for computational linguistics.