Elamur Research⌕
☰
home / papers / 2010 / On Dual Decomposition and Linear Programming Relaxations for Natural Language Processing

On Dual Decomposition and Linear Programming Relaxations for Natural Language Processing

Paper · 2010 · Alexander M. Rush, David Sontag, Michael Collins et al.

Summary

The paper tackles a recurring NLP problem: combining several structured models (for example, a parser and a tagger) makes exact decoding through one joint dynamic program slow and hard to implement. The authors apply dual decomposition, a Lagrangian relaxation technique. Each component model keeps its own off-the-shelf decoder, and these decoders are run repeatedly. Between runs, adjustable penalty weights push the decoders toward agreeing on shared parts, such as POS tags or dependencies. The authors prove that this procedure solves a linear programming relaxation of the joint problem. When the decoders reach agreement, the result is guaranteed to be the true optimum.

They test the method on two combinations, evaluated on the Penn treebank WSJ:

  • Collins (2003) Model 1 with the Koo et al. (2008) second-order dependency parser.
  • The same parser with the Toutanova and Manning (2000) trigram tagger.

In practice the relaxation almost always produces exact solutions within a few iterations, and accuracy beats pipeline baselines. The work matters because it offers a general, cheap way to integrate models that relies only on decoders practitioners already have.

Key points

  • Parser combination: exact solutions were found on more than 99% of sentences, usually in fewer than 10 decoding iterations.
  • Parsing F1:
    • Collins (2003) Model 1 alone: 88.1.
    • Baseline that forces the parser to match the dependency parser's 1-best output: 89.7.
    • Dual decomposition: 90.7.
    • Dependency accuracy also exceeded that of the Koo et al. (2008) model.
  • Effect of the iteration cap K: results are almost unchanged below K = 50 (90.69 F1 at K = 10, 90.63 at K = 5), although fewer sentences receive an optimality certificate.
  • Parser + tagger combination (WSJ Section 23, 2416 test sentences, K = 50):
    • 98.9% of sentences were solved exactly, and over 94% converged within 10 iterations.
    • F1 rose to 88.3 (vs. 87.9 for the fixed-tags baseline).
    • POS accuracy rose to 97.1 (vs. 96.7).
  • Comparison with intersected dynamic programs: an intersected dynamic program (e.g., the Bar-Hillel et al. construction) also solves the joint problem exactly in polynomial time, but it is much slower and more complex than the proposed approach.

Interesting ideas

  • I1. Decoders as black boxes. Existing decoders serve as interchangeable oracles. Model combination becomes a matter of adding penalty terms to their scores rather than writing a new joint decoder, which suits any project that already has separately trained components.
  • I2. Built-in correctness check. When the sub-models agree, the solution is provably optimal. This gives a free per-sentence diagnostic that tells you which outputs to trust and which ones fell short.
  • I3. Over-complete representations. The parse tree is augmented with explicit word-tag indicator variables so that two very different structures share a common interface for agreement. This trick generalizes to coupling any models that overlap on some sub-decision.
  • I4. Adaptive step size. The step size starts at 0.5 and is halved every time the dual objective goes up. This is a simple, aggressive schedule worth reusing in other subgradient-style optimization loops.
  • I5. Graceful early stopping. If convergence fails within K iterations, the method returns the best-scoring iterate seen so far. This allows a time-budgeted decoding mode with minimal accuracy loss.

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

 Institutions

🔬MIT Computer Science and Artificial Intelligence LaboratoryCambridge · United States54 works · 29,441 citations

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 9,085 worksArtificial Intelligence · 8,888 worksArts and Humanities · 9,296 worksLanguage and Linguistics · 9,206 works

Cite

Cite as Alexander M. Rush, David Sontag, Michael Collins and Tommi Jaakkola. 2010. On Dual Decomposition and Linear Programming Relaxations for Natural Language Processing. 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{rush2010dual,
  title = {{On Dual Decomposition and Linear Programming Relaxations for Natural Language Processing}},
  author = {Alexander M. Rush, David Sontag, Michael Collins and Tommi Jaakkola},
  booktitle = {Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing},
  year = {2010},
  url = {https://aclanthology.org/D10-1001/}
}

References

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

  1. Y. Bar-Hillel, M. Perles, and E. Shamir. 1964. On formal properties of simple phrase structure grammars. In Language and Information: Selected Essays on their Theory and Application, pages 116–150. find
  2. X. Carreras, M. Collins, and T. Koo. 2008. TAG, dynamic programming, and the perceptron for efficient, feature-rich parsing. In Proc CONLL, pages 9–16. find
  3. X. Carreras. 2007. Experiments with a higher-order projective dependency parser. In Proc. CoNLL, pages 957–961.
  4. M. Collins. 2002. Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms. In Proc. EMNLP, page 8.
  5. M. Collins. 2003. Head-driven statistical models for natural language parsing. In Computational linguistics, volume 29, pages 589–637.
  6. G.B. Dantzig and P. Wolfe. 1960. Decomposition principle for linear programs. In Operations research, volume 8, pages 101–111. find
  7. J. Duchi, D. Tarlow, G. Elidan, and D. Koller. 2007. Using combinatorial optimization within max-product belief propagation. In NIPS, volume 19. find
  8. J. Eisner. 2000. Bilexical grammars and their cubic-time parsing algorithms. In Advances in Probabilistic and Other Parsing Technologies, pages 29–62. find
  9. A. Globerson and T. Jaakkola. 2007. Fixing max-product: Convergent message passing algorithms for MAP LP-relaxations. In NIPS, volume 21. find
  10. N. Komodakis, N. Paragios, and G. Tziritas. 2007. MRF optimization via dual decomposition: Message-passing revisited. In International Conference on Computer Vision. find
  11. T. Koo, X. Carreras, and M. Collins. 2008. Simple semi-supervised dependency parsing. In Proc. ACL/HLT.
  12. T. Koo, A.M. Rush, M. Collins, T. Jaakkola, and D. Sontag. 2010. Dual Decomposition for Parsing with Non-Projective Head Automata. In Proc. EMNLP, pages 63–70.
  13. B.H. Korte and J. Vygen. 2008. Combinatorial optimization: theory and algorithms. Springer Verlag. find
  14. M.P. Marcus, B. Santorini, and M.A. Marcinkiewicz. 1994. Building a large annotated corpus of English: The Penn Treebank. In Computational linguistics, volume 19, pages 313–330.
  15. R.K. Martin, R.L. Rardin, and B.A. Campbell. 1990. Polyhedral characterization of discrete dynamic programming. Operations research, 38(1):127–138. find
  16. A.F.T. Martins, N.A. Smith, and E.P. Xing. 2009. Concise integer linear programming formulations for dependency parsing. In Proc. ACL. find
  17. R. McDonald, F. Pereira, K. Ribarov, and J. Hajic. 2005. Non-projective dependency parsing using spanning tree algorithms. In Proc. HLT/EMNLP, pages 523– 530.
  18. Angelia Nedić and Asuman Ozdaglar. 2009. Approximate primal solutions and rate analysis for dual subgradient methods. SIAM Journal on Optimization, 19(4):1757–1780. find
  19. B. Pang and L. Lee. 2004. A sentimental education: Sentiment analysis using subjectivity summarization based on minimum cuts. In Proc. ACL.
  20. S. Riedel and J. Clarke. 2006. Incremental integer linear programming for non-projective dependency parsing. In Proc. EMNLP, pages 129–137. find
  21. D. Roth and W. Yih. 2005. Integer linear programming inference for conditional random fields. In Proc. ICML, pages 737–744. find
  22. Hanif D. Sherali and Warren P. Adams. 1994. A hierarchy of relaxations and convex hull characterizations for mixed-integer zero–one programming problems. Discrete Applied Mathematics, 52(1):83 – 106. find
  23. D.A. Smith and J. Eisner. 2008. Dependency parsing by belief propagation. In Proc. EMNLP, pages 145–156.
  24. D. Sontag, T. Meltzer, A. Globerson, T. Jaakkola, and Y. Weiss. 2008. Tightening LP relaxations for MAP using message passing. In Proc. UAI. find
  25. B. Taskar, D. Klein, M. Collins, D. Koller, and C. Manning. 2004. Max-margin parsing. In Proc. EMNLP, pages 1–8. find
  26. K. Toutanova and C.D. Manning. 2000. Enriching the knowledge sources used in a maximum entropy part-of-speech tagger. In Proc. EMNLP, pages 63–70.
  27. M. Wainwright and M. I. Jordan. 2008. Graphical Models, Exponential Families, and Variational Inference. Now Publishers Inc., Hanover, MA, USA. find
  28. M. Wainwright, T. Jaakkola, and A. Willsky. 2005a. MAP estimation via agreement on trees: message-passing and linear programming. In IEEE Transactions on Information Theory, volume 51, pages 3697– 3717. find
  29. M. Wainwright, T. Jaakkola, and A. Willsky. 2005b. A new class of upper bounds on the log partition function. In IEEE Transactions on Information Theory, volume 51, pages 2313–2335. find
  30. C. Yanover, T. Meltzer, and Y. Weiss. 2006. Linear Programming Relaxations and Belief Propagation–An Empirical Study. In The Journal of Machine Learning Research, volume 7, page 1907. MIT Press. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/rush-2010-dual-decomposition-linear-programming-relaxations/