Dual Decomposition for Parsing with Non-Projective Head Automata

Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 1288–1298, MIT, Massachusetts, USA, 9-11 October 2010. c⃝2010 Association for Computational Linguistics Dual Decomposition for Parsing with Non-Projective Head Automata Terry Koo Alexander M. Rush Michael Collins Tommi Jaakkola David Sontag MIT CSAIL, Cambridge, MA 02139, USA {maestro,srush,mcollins,tommi,dsontag}@csail.mit.edu Abstract This paper introduces algorithms for non- projective parsing based on dual decomposi- tion. We focus on parsing algorithms for non- projective head automata, a generalization of head-automata models to non-projective struc- tures. The dual decomposition algorithms are simple and efficient, relying on standard dy- namic programming and minimum spanning tree algorithms. They provably solve an LP relaxation of the non-projective parsing prob- lem. Empirically the LP relaxation is very of- ten tight: for many languages, exact solutions are achieved on over 98% of test sentences. The accuracy of our models is higher than pre- vious work on a broad range of datasets. 1 Introduction Non-projective dependency parsing is useful for many languages that exhibit non-projective syntactic structures. Unfortunately, the non-projective parsing problem is known to be NP-hard for all but the sim- plest models (McDonald and Satta, 2007). There has been a long history in combinatorial optimization of methods that exploit structure in complex problems, using methods such as dual decomposition or La- grangian relaxation (Lemar´echal, 2001). Thus far, however, these methods are not widely used in NLP. This paper introduces algorithms for non- projective parsing based on dual decomposition. We focus on parsing algorithms for non-projective head automata, a generalization of the head-automata models of Eisner (2000) and Alshawi (1996) to non- projective structures. These models include non- projective dependency parsing models with higher- order (e.g., sibling and/or grandparent) dependency relations as a special case. Although decoding of full parse structures with non-projective head automata is intractable, we leverage the observation that key components of the decoding can be efficiently com- puted using combinatorial algorithms. In particular, 1. Decoding for individual head-words can be ac- complished using dynamic programming. 2. Decoding for arc-factored models can be ac- complished using directed minimum-weight spanning tree (MST) algorithms. The resulting parsing algorithms have the following properties: • They are efficient and easy to implement, relying on standard dynamic programming and MST al- gorithms. • They provably solve a linear programming (LP) relaxation of the original decoding problem. • Empirically the algorithms very often give an ex- act solution to the decoding problem, in which case they also provide a certificate of optimality. In this paper we first give the definition for non- projective head automata, and describe the parsing algorithm. The algorithm can be viewed as an in- stance of Lagrangian relaxation; we describe this connection, and give convergence guarantees for the method. We describe a generalization to models that include grandparent dependencies. We then in- troduce a perceptron-driven training algorithm that makes use of point 1 above. We describe experiments on non-projective pars- ing for a number of languages, and in particu- lar compare the dual decomposition algorithm to …

Content truncated to 500 words