Headed-Span-Based Projective Dependency Parsing

Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics Volume 1: Long Papers, pages 2188 - 2200 May 22-27, 2022 c⃝2022 Association for Computational Linguistics 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 We propose a new method for projective de- pendency parsing based on headed spans. In a projective dependency tree, the largest sub- tree 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 rep- resented 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(n3) dynamic programming algorithm to enable global training and exact inference. Our model achieves state-of-the-art or compet- itive results on PTB, CTB, and UD 1. 1 Introduction Dependency parsing is an important task in natu- ral language processing, which has numerous ap- plications 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 meth- ods. 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 Man- ning, 2014, inter alia) read the sentence sequen- tially and conduct a series of local decisions to build the final parse. Recently, transition-based ∗Corresponding Author 1Our 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; Fernández-González and Gómez-Rodríguez, 2019; Fernández-González and Gómez-Rodríguez, 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 sub- trees 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 con- sidering multiple arcs, have been found to outper- form 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 dif- ferent …

Content truncated to 500 words