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

Findings of the Association for Computational Linguistics: ACL 2022, pages 1428 - 1434 May 22-27, 2022 c⃝2022 Association for Computational Linguistics Combining (Second-Order) Graph-Based and Headed-Span-Based Projective Dependency Parsing Songlin Yang, Kewei Tu∗ School of Information Science and Technology, ShanghaiTech University Shanghai Engineering Research Center of Intelligent Vision and Imaging {yangsl,tukw}@shanghaitech.edu.cn Abstract Graph-based methods, which decompose the score of a dependency tree into scores of de- pendency arcs, are popular in dependency pars- ing for decades. Recently, Yang and Tu (2022) propose a headed-span-based method that de- composes the score of a dependency tree into scores of headed spans. They show im- provement over first-order graph-based meth- ods. However, their method does not score dependency arcs at all, and dependency arcs are implicitly induced by their cubic-time al- gorithm, which is possibly sub-optimal since modeling dependency arcs is intuitively use- ful. In this work, we aim to combine graph- based and headed-span-based methods, incor- porating both arc scores and headed span scores into our model. First, we show a di- rect way to combine with O(n4) parsing com- plexity. To decrease complexity, inspired by the classical head-splitting trick, we show two O(n3) dynamic programming algorithms to combine first- and second-order graph-based and headed-span-based methods. Our exper- iments on PTB, CTB, and UD show that combining first-order graph-based and headed- span-based methods is effective. We also con- firm the effectiveness of second-order graph- based parsing in the deep learning age, how- ever, we observe marginal or no improve- ment when combining second-order graph- based and headed-span-based methods 1. 1 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: graph- based and headed-span-based methods. They both score all parse trees and globally find the highest ∗Corresponding Author 1Our code is publicly available at https://github.com/sustcsonglin/ span-based-dependency-parsing 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. scoring tree. The difference between the two is how they score dependency trees. The simplest first- order graph-based methods (McDonald et al., 2005) decompose the score of a dependency tree into the scores of dependency arcs. Second-order graph- based methods (McDonald and Pereira, 2006) ad- ditionally score adjacent siblings, i.e., pairs of adja- cent arcs with a shared head. There are many other higher-order graph-based methods (Carreras, 2007; Koo and Collins, 2010; Ma and Zhao, 2012). In contrast, the headed-span-based method (Yang and Tu, 2022) decomposes the score of a dependency tree into the scores of headed spans: in a projective tree, a headed span is a word-span pair such that the subtree rooted at the word covers the span in the surface order. Fig. 1 shows an example projective parse tree and all its headed spans. First-order graph-based parsers have difficulties in incorporating sufficient subtree information be- fore the deep learning era. Dozat and Manning (2017) …

Content truncated to 500 words