Edge-Linear First-Order Dependency Parsing with Undirected Minimum Spanning Tree Inference

Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, pages 2104–2113, Berlin, Germany, August 7-12, 2016. c⃝2016 Association for Computational Linguistics Edge-Linear First-Order Dependency Parsing with Undirected Minimum Spanning Tree Inference Effi Levi1 Roi Reichart2 1Institute of Computer Science, The Hebrew Univeristy 2Faculty of Industrial Engineering and Management, Technion, IIT {efle|arir}@cs.huji.ac.il roiri@ie.technion.ac.il Ari Rappoport1 Abstract The run time complexity of state-of-the- art inference algorithms in graph-based dependency parsing is super-linear in the number of input words (n). Recently, pruning algorithms for these models have shown to cut a large portion of the graph edges, with minimal damage to the re- sulting parse trees. Solving the infer- ence problem in run time complexity de- termined solely by the number of edges (m) is hence of obvious importance. We propose such an inference algorithm for first-order models, which encodes the problem as a minimum spanning tree (MST) problem in an undirected graph. This allows us to utilize state-of-the-art undirected MST algorithms whose run time is O(m) at expectation and with a very high probability. A directed parse tree is then inferred from the undirected MST and is subsequently improved with respect to the directed parsing model through local greedy updates, both steps running in O(n) time. In experiments with 18 languages, a variant of the first-order MSTParser (McDonald et al., 2005b) that employs our algorithm performs very sim- ilarly to the original parser that runs an O(n2) directed MST inference. 1 Introduction Dependency parsers are major components of a large number of NLP applications. As application models are applied to constantly growing amounts of data, efficiency becomes a major consideration. In graph-based dependency parsing models (Eisner, 2000; McDonald et al., 2005a; McDon- ald et al., 2005b; Carreras, 2007; Koo and Collins, 2010b), given an n word sentence and a model or- der k, the run time of exact inference is O(n3) for k = 1 and O(nk+1) for k > 1 in the projective case (Eisner, 1996; McDonald and Pereira, 2006). In the non-projective case it is O(n2) for k = 1 and NP-hard for k ≥ 2 (McDonald and Satta, 2007). 1 Consequently, a number of approximated parsers have been introduced, utilizing a variety of techniques: the Eisner algorithm (McDonald and Pereira, 2006), belief propagation (Smith and Eis- ner, 2008), dual decomposition (Koo and Collins, 2010b; Martins et al., 2013) and multi-commodity flows (Martins et al., 2009; Martins et al., 2011). The run time of all these approximations is super- linear in n. Recent pruning algorithms for graph-based de- pendency parsing (Rush and Petrov, 2012; Riedel et al., 2012; Zhang and McDonald, 2012) have shown to cut a very large portion of the graph edges, with minimal damage to the resulting parse trees. For example, Rush and Petrov (2012) demonstrated that a single O(n) pass of vine- pruning (Eisner and Smith, 2005) can preserve > 98% of the correct edges, while ruling out > 86% of all possible edges. Such results give strong motivation to solving the inference …

Content truncated to 500 words