Vine Pruning for Efficient Multi-Pass Dependency Parsing
Venue
The 2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL '12), Best Paper Award
Publication Year
2012
Authors
Alexander Rush, Slav Petrov
BibTeX
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 dependency
parsing using linear-time vine pruning and structured prediction cascades. Our
first-, second-, and third-order models achieve accuracies comparable to those of
their unpruned 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 unpruned first-order
model and also compares favorably to a state-of-the-art transition-based parser for
multiple languages.
