A Root of a Problem: Optimizing Single-Root Dependency Parsing

Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 10540–10557 November 7–11, 2021. c⃝2021 Association for Computational Linguistics 10540 A Root of a Problem: Optimizing Single-Root Dependency Parsing Miloš Stanojević School of Informatics University of Edinburgh m.stanojevic@ed.ac.uk Shay B. Cohen School of Informatics University of Edinburgh scohen@inf.ed.ac.uk Abstract We describe two approaches to single-root dependency parsing that yield significant speed ups in such parsing. One approach has been previously used in dependency parsers in practice, but remains undocu- mented in the parsing literature, and is considered a heuristic. We show that this approach actually finds the optimal depen- dency tree. The second approach relies on simple reweighting of the inference graph being input to the dependency parser and has an optimal running time. Here, we again show that this approach is fully correct and identifies the highest-scoring parse tree. Our experiments demonstrate a manyfold speed up compared to a pre- vious graph-based state-of-the-art parser without any loss in accuracy or optimal- ity.1 1 Introduction Dependency parsing is one of the core steps in many Natural Language Processing pipelines. Given its wide and large-scale use, both in aca- demic and commercial settings, even moderate improvements in the speed and accuracy of a dependency parser may significantly impact its utility. In this paper, we show how to improve the speed of graph-based dependency parsers (McDonald et al., 2005; Qi et al., 2020) without compromising at all on accuracy. Graph-based dependency parsers work in two steps. The first step forms a complete weighted directed graph of words and a special ROOT token by computing the weights using a trained statistical model.2 The second step then exe- cutes the main inference procedure: it identifies a directed spanning tree (often referred to as 1Our code is available at https://github.com/ stanojevic/Fast-MST-Algorithm. 2The weights of edges entering ROOT are −∞. 40 60 80 100 sentence length 0 2 4 6 8 time in ms weights computation time MST finding time Figure 1: Time proportion used by the neural and MST component when parsing with Stanza on GPU. arborescence) in this graph, aiming to maxi- mize its weight, and retaining ROOT as the root node of the arborescence. While some of the previous work to optimize the speed of graph-based parsers focused on the first step (Anderson and Gómez-Rodríguez, 2020), we demonstrate in Figure 1 that most of the parsing time is actually spent on the span- ning tree inference routine. As sentence length increases, the gap between the spanning tree inference time and time spent on constructing the weighted graph increases significantly.3 MST search is often done using the Chu-Liu- Edmonds (CLE) algorithm (Chu and Liu, 1965; Edmonds, 1967) that runs in O(n3) where n is the sentence length. Tarjan (1977) presents a relatively complicated way of implementing the CLE algorithm in O(n2). Tarjan’s algorithm is often cited in NLP literature, but to the best of our knowledge has never been implemented for dependency parsing. This is due to the common 3For this …

Content truncated to 500 words