Vine Pruning for Efficient Multi-Pass Dependency Parsing

2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 498–507, Montr´eal, Canada, June 3-8, 2012. c⃝2012 Association for Computational Linguistics Vine Pruning for Efficient Multi-Pass Dependency Parsing Alexander M. Rush∗ MIT CSAIL Cambridge, MA 02139, USA srush@csail.mit.edu Slav Petrov Google New York, NY 10027, USA slav@google.com Abstract Coarse-to-fine inference has been shown to be a robust approximate method for improving the efficiency of structured prediction models while preserving their accuracy. We propose a multi-pass coarse-to-fine architecture for de- pendency parsing using linear-time vine prun- ing and structured prediction cascades. Our first-, second-, and third-order models achieve accuracies comparable to those of their un- pruned counterparts, while exploring only a fraction of the search space. We observe speed-ups of up to two orders of magnitude compared to exhaustive search. Our pruned third-order model is twice as fast as an un- pruned first-order model and also compares favorably to a state-of-the-art transition-based parser for multiple languages. 1 Introduction Coarse-to-fine inference has been extensively used to speed up structured prediction models. The gen- eral idea is simple: use a coarse model where in- ference is cheap to prune the search space for more complex models. In this work, we present a multi- pass coarse-to-fine architecture for graph-based de- pendency parsing. We start with a linear-time vine pruning pass and build up to higher-order models, achieving speed-ups of two orders of magnitude while maintaining state-of-the-art accuracies. In constituency parsing, exhaustive inference for all but the simplest grammars tends to be pro- hibitively slow. Consequently, most high-accuracy constituency parsers routinely employ a coarse grammar to prune dynamic programming chart cells ∗ Research conducted at Google. of the final grammar of interest (Charniak et al., 2006; Carreras et al., 2008; Petrov, 2009). While there are no strong theoretical guarantees for these approaches,1 in practice one can obtain significant speed improvements with minimal loss in accuracy. This benefit comes primarily from reducing the large grammar constant |G| that can dominate the runtime of the cubic-time CKY inference algorithm. De- pendency parsers on the other hand do not have a multiplicative grammar factor |G|, and until recently were considered efficient enough for exhaustive in- ference. However, the increased model complex- ity of a third-order parser forced Koo and Collins (2010) to prune with a first-order model in order to make inference practical. While fairly effective, all these approaches are limited by the fact that infer- ence in the coarse model remains cubic in the sen- tence length. The desire to parse vast amounts of text necessitates more efficient dependency parsing algorithms. We thus propose a multi-pass coarse-to-fine ap- proach where the initial pass is a linear-time sweep, which tries to resolve local ambiguities, but leaves arcs beyond a fixed length b unspecified (Section 3). The dynamic program is a form of vine parsing (Eisner and Smith, 2005), which we use to compute parse max-marginals, rather than for finding the 1- best parse tree. To reduce pruning errors, the param- eters …

Content truncated to 500 words