Effective Greedy Inference for Graph-based Non-Projective Dependency Parsing

Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 711–720, Austin, Texas, November 1-5, 2016. c⃝2016 Association for Computational Linguistics Effective Greedy Inference for Graph-based Non-Projective Dependency Parsing Ilan Tchernowitz Liron Yedidsion Faculty of Industrial Engineering and Management, Technion, IIT {ilantc@campus|lirony@ie|roiri@ie}.technion.ac.il Roi Reichart Abstract Exact inference in high-order graph-based non-projective dependency parsing is in- tractable. Hence, sophisticated approximation techniques based on algorithms such as be- lief propagation and dual decomposition have been employed. In contrast, we propose a sim- ple greedy search approximation for this prob- lem which is very intuitive and easy to im- plement. We implement the algorithm within the second-order TurboParser and experiment with the datasets of the CoNLL 2006 and 2007 shared task on multilingual dependency pars- ing. Our algorithm improves the run time of the parser by a factor of 1.43 while losing 1% in UAS on average across languages. More- over, an ensemble method exploiting the joint power of the parsers, achieves an average UAS 0.27% higher than the TurboParser. 1 Introduction Dependency parsing is instrumental in NLP appli- cations, with recent examples in information extrac- tion (Wu and Weld, 2010), word embeddings (Levy and Goldberg, 2014), and opinion mining (Almeida et al., 2015). The two main approaches for this task are graph based (McDonald et al., 2005) and transi- tion based (Nivre et al., 2007). The graph based approach aims to optimize a global objective function. While exact polyno- mial inference algorithms exist for projective pars- ing (Eisner, 1996; McDonald et al., 2005; Carreras, 2007; Koo and Collins, 2010, inter alia), high order non-projective parsing is NP-hard (McDonald and Pereira, 2006). The current remedy for this comes in the form of advanced optimization techniques such as dual decomposition (Martins et al., 2013), LP re- laxations (Riedel et al., 2012), belief propagation (Smith and Eisner, 2008; Gormley et al., 2015) and sampling (Zhang et al., 2014b; Zhang et al., 2014a). The transition based approach (Zhang and Nivre, 2011; Bohnet and Nivre, 2012; Honnibal et al., 2013; Choi and McCallum, 2013a, inter alia), and the easy first approach (Goldberg and Elhadad, 2010) which extends it by training non-directional parsers that consider structural information from both sides of their decision points, lack a global ob- jective function. Yet, their sequential greedy solvers are fast and accurate in practice. We propose a greedy search algorithm for high- order, non-projective graph-based dependency pars- ing. Our algorithm is a simple iterative graph-based method that does not rely on advanced optimization techniques. Moreover, we factorize the graph-based objective into a sum of terms and show that our basic greedy algorithm relaxes the global objective by se- quentially optimizing these terms instead of globally optimizing their sum. Unlike previous greedy approaches to depen- dency parsing, transition based and non-directional, our algorithm does not require a specialized feature set or a training method that specializes in local deci- sions. In contrast, it supports global parameter train- ing based on the comparison between an induced tree and the gold …

Content truncated to 500 words