emnlp emnlp2010 emnlp2010-38 emnlp2010-38-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Terry Koo ; Alexander M. Rush ; Michael Collins ; Tommi Jaakkola ; David Sontag
Abstract: This paper introduces algorithms for nonprojective parsing based on dual decomposition. We focus on parsing algorithms for nonprojective head automata, a generalization of head-automata models to non-projective structures. The dual decomposition algorithms are simple and efficient, relying on standard dynamic programming and minimum spanning tree algorithms. They provably solve an LP relaxation of the non-projective parsing problem. Empirically the LP relaxation is very often tight: for many languages, exact solutions are achieved on over 98% of test sentences. The accuracy of our models is higher than previous work on a broad range of datasets.
H. Alshawi. 1996. Head Automata and Bilingual Tiling: Translation with Minimal Representations. In Proc. ACL, pages 167–176. S. Buchholz and E. Marsi. 2006. CoNLL-X Shared Task on Multilingual Dependency Parsing. In Proc. CoNLL, pages 149–164. X. Carreras. 2007. Experiments with a Higher-Order Projective Dependency Parser. In Proc. EMNLPCoNLL, pages 957–961. M. Collins. 2002. Discriminative Training Methods for Hidden Markov Models: Theory and Experiments with Perceptron Algorithms. In Proc. EMNLP, pages 1–8. J. Duchi, D. Tarlow, G. Elidan, and D. Koller. 2007. Using Combinatorial Optimization within Max-Product Belief Propagation. In NIPS, pages 369–376. J. Eisner. 2000. Bilexical grammars and their cubictime parsing algorithms. Advances in Probabilistic and Other Parsing Technologies, pages 29–62. T. Finley and T. Joachims. 2008. Training structural svms when exact inference is intractable. In ICML, pages 304–3 11. A.K. Joshi and Y. Schabes. 1997. Tree-Adjoining Grammars. Handbook of Formal Languages: Beyond Words, 3:69–123. N. Komodakis, N. Paragios, and G. Tziritas. 2007. MRF Optimization via Dual Decomposition: MessagePassing Revisited. In Proc. ICCV. T. Koo, A. Globerson, X. Carreras, and M. Collins. 2007. Structured Prediction Models via the Matrix-Tree Theorem. In Proc. EMNLP-CoNLL, pages 141–150. B.H. Korte and J. Vygen. 2008. Combinatorial Optimization: Theory and Algorithms. Springer Verlag. A. Kulesza and F. Pereira. 2008. Structured learning with approximate inference. In NIPS. C. Lemar ´echal. 2001 . Lagrangian Relaxation. In Computational Combinatorial Optimization, Optimal or Provably Near-Optimal Solutions [based on a Spring School], pages 112–156, London, UK. SpringerVerlag. A.F.T. Martins, D. Das, N.A. Smith, and E.P. Xing. 2008. Stacking Dependency Parsers. In Proc. EMNLP, pages 157–166. A.F.T. Martins, N.A. Smith., and E.P. Xing. 2009. Concise Integer Linear Programming Formulations for Dependency Parsing. In Proc. ACL, pages 342–350. R. McDonald and F. Pereira. 2006. Online Learning of Approximate Dependency Parsing Algorithms. In Proc. EACL, pages 81–88. R. McDonald and G. Satta. 2007. On the Complexity of Non-Projective Data-Driven Dependency Parsing. In Proc. IWPT. 1298 R. McDonald, F. Pereira, K. Ribarov, and J. Haji cˇ. 2005. Non-Projective Dependency Parsing using Spanning Tree Algorithms. In Proc. HLT-EMNLP, pages 523– 530. O. Meshi, D. Sontag, T. Jaakkola, and A. Globerson. 2010. Learning Efficiently with Approximate Inference via Dual Losses. In Proc. ICML. A. Nedi c´ and A. Ozdaglar. 2009. Approximate Primal Solutions and Rate Analysis for Dual Subgradient Methods. SIAM Journal on Optimization, 19(4): 1757–1780. J. Nivre and R. McDonald. 2008. Integrating GraphBased and Transition-Based Dependency Parsers. In Proc. ACL, pages 950–958. V. Punyakanok, D. Roth, W. Yih, and D. Zimak. 2005. Learning and Inference over Constrained Output. In Proc. IJCAI, pages 1124–1 129. S. Riedel and J. Clarke. 2006. Incremental Integer Linear Programming for Non-projective Dependency Parsing. In Proc. EMNLP, pages 129–137. A.M. Rush, D. Sontag, M. Collins, and T. Jaakkola. 2010. On Dual Decomposition and Linear Programming Relaxations for Natural Language Processing. In Proc. EMNLP. D.A. Smith and J. Eisner. 2008. Dependency Parsing by Belief Propagation. In Proc. EMNLP, pages 145–156. D.A. Smith and N.A. Smith. 2007. Probabilistic Models of Nonprojective Dependency Trees. In Proc. EMNLP-CoNLL, pages 132–140. D. Sontag, T. Meltzer, A. Globerson, T. Jaakkola, and Y. Weiss. 2008. Tightening LP Relaxations for MAP using Message Passing. In Proc. UAI. M. Steedman. 2000. The Syntactic Process. MIT Press. M. Surdeanu, R. Johansson, A. Meyers, L. M `arquez, and J. Nivre. 2008. The CoNLL-2008 Shared Task on Joint Parsing of Syntactic and Semantic Dependencies. In Proc. CoNLL. B. Taskar, C. Guestrin, and D. Koller. 2003. Max-margin Markov networks. In NIPS. M. Wainwright, T. Jaakkola, and A. Willsky. 2005. MAP estimation via agreement on trees: message-passing and linear programming. In IEEE Transactions on Information Theory, volume 5 1, pages 3697–3717.