Elamur Research⌕
☰
home / papers / 2010 / Dual Decomposition for Parsing with Non-Projective Head Automata

Dual Decomposition for Parsing with Non-Projective Head Automata

Paper · 2010 · Terry Koo, Alexander M. Rush, Michael Collins et al.

Summary

Non-projective dependency parsing suits languages with crossing syntactic links, but exact decoding is NP-hard once a model scores more than single arcs, for example sibling or grandparent interactions. Koo et al. extend head-automata models to non-projective trees and decode them with dual decomposition, a form of Lagrangian relaxation. The decoding problem is split into two easy subproblems:

  • each head word picks its modifiers independently via dynamic programming;
  • a directed MST solver guarantees a well-formed spanning tree.

Lagrange multipliers are updated by subgradient steps until the two solutions agree. The procedure provably solves an LP relaxation of the original problem. Whenever the two parts coincide, the answer is exact and comes with a certificate of optimality. Models are trained with a perceptron, and the paper also covers grandparent dependencies. Across many languages the relaxation is usually tight, with exact solutions on over 98% of test sentences for many of them. Accuracy beats earlier work on a wide range of datasets, and the method is faster than general-purpose LP/ILP approaches such as Martins et al. (2009). This shows that cheap, structure-aware combinatorial solvers can replace generic optimizers in NLP decoding.

Key points

  • Subproblems: bigram sibling models decode per head in O(n²), and general head automata in O(n|S|²) using a Viterbi variant. The tree constraint is handled by an MST algorithm.
  • Speed: parsing takes between 0.021 and 0.295 seconds per sentence, depending on language and model complexity.
  • Iteration budget: capping iterations at K = 250 instead of 5000 gave the same output on 99.59% of examples. However, only 89.29% of those outputs were certified optimal.
  • Unconstrained approximation: the per-head solution z*, which ignores tree constraints, still reached 91.11% precision and 88.95% recall on the PTB validation set.
  • Projective vs. non-projective decoding (validation UAS):
DataProjective G+SNon-projective G+S
English (PTB)92.7092.71
Czech (PDT)86.4387.40

Non-projective decoding clearly helps Czech but barely matters for English.

Interesting ideas

  • I1. Split a hard objective into tractable pieces. Give each piece its own efficient solver and force agreement on shared variables through Lagrange multipliers. This applies to any structured prediction task where constraints are what make decoding hard.
  • I2. Free optimality certificate. When the subproblems agree, you know the answer is exact. This gives a cheap way to monitor search quality, or to report how often a fast heuristic is provably correct.
  • I3. Swappable components. Replacing the MST solver with Eisner's projective parser turns the same framework into a projective parser with higher-order features. This avoids designing a specialized dynamic program for each new feature set.
  • I4. Adaptive step sizes. The step size is set from the initial gap between the two subproblem scores. It then shrinks each time the dual objective increases, which is a practical recipe for tuning subgradient methods without heavy search.
  • I5. Leave a small weight for tie-breaking. Keeping a tiny share (β = 0.001) of the arc scores in the MST subproblem stops early iterations from returning near-random trees. That in turn reduces noisy multiplier updates. A similar trick could help in other decomposed or alternating optimization schemes.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 9,086 worksArtificial Intelligence · 8,889 worksArts and Humanities · 9,296 worksLanguage and Linguistics · 9,206 worksComputational Theory and Mathematics · 116 works

Cite

Cite as Terry Koo, Alexander M. Rush, Michael Collins, Tommi Jaakkola and David Sontag. 2010. Dual Decomposition for Parsing with Non-Projective Head Automata. Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing.

The paper itself, not this page. BibTeX from the library's record of the work.

@inproceedings{koo2010dual,
  title = {{Dual Decomposition for Parsing with Non-Projective Head Automata}},
  author = {Terry Koo, Alexander M. Rush, Michael Collins, Tommi Jaakkola and David Sontag},
  booktitle = {Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing},
  year = {2010},
  url = {https://aclanthology.org/D10-1125/}
}

References

31 references, 9 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. H. Alshawi. 1996. Head Automata and Bilingual Tiling: Translation with Minimal Representations. In Proc. ACL, pages 167–176. find
  2. S. Buchholz and E. Marsi. 2006. CoNLL-X Shared Task on Multilingual Dependency Parsing. In Proc. CoNLL, pages 149–164.
  3. X. Carreras. 2007. Experiments with a Higher-Order Projective Dependency Parser. In Proc. EMNLP-CoNLL, pages 957–961.
  4. M. Collins. 2002. Discriminative Training Methods for Hidden Markov Models: Theory and Experiments with Perceptron Algorithms. In Proc. EMNLP, pages 1–8.
  5. J. Duchi, D. Tarlow, G. Elidan, and D. Koller. 2007. Using Combinatorial Optimization within Max-Product Belief Propagation. In NIPS, pages 369–376. find
  6. J. Eisner. 2000. Bilexical grammars and their cubic-time parsing algorithms. Advances in Probabilistic and Other Parsing Technologies, pages 29–62. find
  7. T. Finley and T. Joachims. 2008. Training structural svms when exact inference is intractable. In ICML, pages 304–311. find
  8. A.K. Joshi and Y. Schabes. 1997. Tree-Adjoining Grammars. Handbook of Formal Languages: Beyond Words, 3:69–123. find
  9. N. Komodakis, N. Paragios, and G. Tziritas. 2007. MRF Optimization via Dual Decomposition: Message-Passing Revisited. In Proc. ICCV. find
  10. 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. find
  11. B.H. Korte and J. Vygen. 2008. Combinatorial Optimization: Theory and Algorithms. Springer Verlag. find
  12. A. Kulesza and F. Pereira. 2008. Structured learning with approximate inference. In NIPS. find
  13. C. Lemaréchal. 2001. Lagrangian Relaxation. In Computational Combinatorial Optimization, Optimal or Provably Near-Optimal Solutions [based on a Spring School], pages 112–156, London, UK. Springer-Verlag. find
  14. A.F.T. Martins, D. Das, N.A. Smith, and E.P. Xing. 2008. Stacking Dependency Parsers. In Proc. EMNLP, pages 157–166. find
  15. 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. find
  16. R. McDonald and F. Pereira. 2006. Online Learning of Approximate Dependency Parsing Algorithms. In Proc. EACL, pages 81–88.
  17. R. McDonald and G. Satta. 2007. On the Complexity of Non-Projective Data-Driven Dependency Parsing. In Proc. IWPT. find
  18. R. McDonald, F. Pereira, K. Ribarov, and J. Hajič. 2005. Non-Projective Dependency Parsing using Spanning Tree Algorithms. In Proc. HLT-EMNLP, pages 523– 530.
  19. O. Meshi, D. Sontag, T. Jaakkola, and A. Globerson. 2010. Learning Efficiently with Approximate Inference via Dual Losses. In Proc. ICML. find
  20. A. Nedić and A. Ozdaglar. 2009. Approximate Primal Solutions and Rate Analysis for Dual Subgradient Methods. SIAM Journal on Optimization, 19(4):1757–1780. find
  21. J. Nivre and R. McDonald. 2008. Integrating Graph-Based and Transition-Based Dependency Parsers. In Proc. ACL, pages 950–958.
  22. V. Punyakanok, D. Roth, W. Yih, and D. Zimak. 2005. Learning and Inference over Constrained Output. In Proc. IJCAI, pages 1124–1129. find
  23. S. Riedel and J. Clarke. 2006. Incremental Integer Linear Programming for Non-projective Dependency Parsing. In Proc. EMNLP, pages 129–137. find
  24. 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.
  25. D.A. Smith and J. Eisner. 2008. Dependency Parsing by Belief Propagation. In Proc. EMNLP, pages 145–156.
  26. D.A. Smith and N.A. Smith. 2007. Probabilistic Models of Nonprojective Dependency Trees. In Proc. EMNLP-CoNLL, pages 132–140. find
  27. D. Sontag, T. Meltzer, A. Globerson, T. Jaakkola, and Y. Weiss. 2008. Tightening LP Relaxations for MAP using Message Passing. In Proc. UAI. find
  28. M. Steedman. 2000. The Syntactic Process. MIT Press. find
  29. M. Surdeanu, R. Johansson, A. Meyers, L. Màrquez, and J. Nivre. 2008. The CoNLL-2008 Shared Task on Joint Parsing of Syntactic and Semantic Dependencies. In Proc. CoNLL.
  30. B. Taskar, C. Guestrin, and D. Koller. 2003. Max-margin Markov networks. In NIPS. find
  31. 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 51, pages 3697–3717. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/koo-2010-dual-decomposition-parsing-non-projective/