Elamur Research⌕
☰
home / papers / 2010 / Turbo Parsers: Dependency Parsing by Approximate Variational Inference

Turbo Parsers: Dependency Parsing by Approximate Variational Inference

Summary

Rich non-projective dependency parsers that score sibling and grandparent arcs make exact inference intractable, so they need approximate decoding. Martins and colleagues show that two such parsers fit one framework, which they call "turbo parsers" after turbo codes. These are the parser by Smith and Eisner (2008), which relies on loopy belief propagation, and the LP-relaxation parser of Martins et al. (2009). The authors model both as inference in a factor graph with hard constraint factors such as TREE, and both optimize over a local approximation of the marginal polytope. Building on this view, they:

  • add new combinatorial factors (OR, OR-WITH-OUTPUT) with closed-form messages, entropies and local agreement constraints;
  • propose an aggressive online learner that generalizes MIRA, needs no learning rate, and covers a loss family that includes CRFs and structured SVMs;
  • show how to use features never seen in training.

Experiments on 14 languages reach state-of-the-art accuracy. The work matters because it links message passing and LP relaxation for parsing and gives a reusable toolkit for structured models with hard constraints.

Key points

  • The factor graph has one binary variable per candidate arc (O(n²) of them) and a global TREE hard factor. It adds O(n³) pairwise sibling and grandparent factors, which create loops.
  • Turbo Parser #1 uses loopy BP and handles finite β. Turbo Parser #2 solves the LP relaxation with CPLEX and covers the SVM-like case. Both reuse the pruning from Martins et al. (2009).
  • In second-order models, the SVM loss gave a consistent gain over the CRF loss. Arc-factored models performed similarly under both losses.
  • Table 3 reports UAS on the English Non-Projective dataset. Second-order models score about 92.0 with losses between the two extremes, versus about 91.8 for SVM and about 91.1 for CRF.
  • Unsupported features instantiated about 2.5× more features on average and helped most languages. The parser was not beaten by the exact third-order projective parser of Koo and Collins (2010) on projective English. Code is released as TurboParser.

Interesting ideas

  • I1. Hard logic as factors. Encoding hard logical constraints (one-hot, OR, implication, NAND) as factors with cheap closed-form messages lets global structure enter approximate inference. This could transfer to tagging, coreference or other constrained structured tasks.
  • I2. Recognizing a shared method. Writing down the explicit optimization problem behind a heuristic algorithm, such as loopy BP, can reveal that two differently motivated methods solve related relaxations. That clarifies which one approximates less.
  • I3. One tunable loss family. A single loss family whose parameters slide between CRF and structured SVM lets one learner cover both. The best results sat between the two extremes, which suggests tuning the loss rather than picking one by convention.
  • I4. Learning-rate-free online training. A MIRA-style aggressive update that works for arbitrary convex losses avoids tuning a learning rate, which is handy when training many per-language models.
  • I5. Unsupported features. Instantiating feature conjunctions that never fire in gold training structures adds useful signal at modest cost. This is a cheap way to enrich discriminative models in low-resource treebanks.

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

Fields: Linguistics & languages · Natural language processing

Topics: Dependency parsing

Cited by

69 papers of our library cite it (of the 140673 whose bibliographies we read); 10 of them have a page here, 59 not yet.

Cite

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

@inproceedings{martins2010turbo,
  title = {{Turbo Parsers: Dependency Parsing by Approximate Variational Inference}},
  author = {Martins, André and Smith, Noah and Xing, Eric and Aguiar, Pedro and Figueiredo, Mário},
  booktitle = {Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing},
  year = {2010},
  url = {https://aclanthology.org/D10-1004/}
}

References

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

  1. C. Berrou, A. Glavieux, and P. Thitimajshima. 1993. Near Shannon limit error-correcting coding and decoding. In Proc. of ICC, volume 93, pages 1064–1070. find
  2. S. Buchholz and E. Marsi. 2006. CoNLL-X shared task on multilingual dependency parsing. In CoNLL. find our card
  3. K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz, and Y. Singer. 2006. Online passive-aggressive algorithms. JMLR, 7:551–585. find
  4. J. Duchi, D. Tarlow, G. Elidan, and D. Koller. 2007. Using combinatorial optimization within max-product belief propagation. NIPS, 19. find
  5. J. R. Finkel, A. Kleeman, and C. D. Manning. 2008. Efficient, feature-based, conditional random field parsing. Proc. of ACL. find
  6. K. Gimpel and N. A. Smith. 2010. Softmax-margin crfs: Training log-linear models with loss functions. In Proc. of NAACL. find
  7. A. Globerson and T. Jaakkola. 2008. Fixing max-product: Convergent message passing algorithms for MAP LP-relaxations. NIPS, 20. find
  8. L. Huang. 2008. Forest reranking: Discriminative parsing with non-local features. In Proc. of ACL. find
  9. S. Kahane, A. Nasr, and O. Rambow. 1998. Pseudo-projectivity: a polynomially parsable non-projective dependency grammar. In Proc. of COLING. find
  10. T. Koo and M. Collins. 2010. Efficient third-order dependency parsers. In Proc. of ACL. find
  11. T. Koo, A. Globerson, X. Carreras, and M. Collins. 2007. Structured prediction models via the matrix-tree theorem. In Proc. of EMNLP. find
  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. of EMNLP. find
  13. F. R. Kschischang, B. J. Frey, and H. A. Loeliger. 2001. Factor graphs and the sum-product algorithm. IEEE Trans. Inf. Theory, 47(2):498–519. find
  14. J. Lafferty, A. McCallum, and F. Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proc. of ICML. find
  15. A. F. T. Martins, D. Das, N. A. Smith, and E. P. Xing. 2008. Stacking dependency parsers. In EMNLP. find
  16. A. F. T. Martins, N. A. Smith, and E. P. Xing. 2009. Concise integer linear programming formulations for dependency parsing. In Proc. of ACL-IJCNLP. find
  17. A. F. T. Martins, K. Gimpel, N. A. Smith, E. P. Xing, P. M. Q. Aguiar, and M. A. T. Figueiredo. 2010a. Learning structured classifiers with dual coordinate descent. Technical Report CMU-ML-10-109. find
  18. A. F. T. Martins, N. A. Smith, E. P. Xing, P. M. Q. Aguiar, and M. A. T. Figueiredo. 2010b. Turbo parsers: Dependency parsing by approximate variational inference (extended version). find
  19. A. McCallum, K. Schultz, and S. Singh. 2009. Factorie: Probabilistic programming via imperatively defined factor graphs. In NIPS. find
  20. R. T. McDonald, F. Pereira, K. Ribarov, and J. Hajic. 2005. Non-projective dependency parsing using spanning tree algorithms. In Proc. of HLT-EMNLP. find our card
  21. R. McDonald, K. Lerman, and F. Pereira. 2006. Multilingual dependency analysis with a two-stage discriminative parser. In Proc. of CoNLL. find our card
  22. R. J. McEliece, D. J. C. MacKay, and J. F. Cheng. 1998. Turbo decoding as an instance of Pearl’s “belief propagation” algorithm. IEEE Journal on Selected Areas in Communications, 16(2). find
  23. J. Pearl. 1988. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann. find
  24. F. Sha and F. Pereira. 2003. Shallow parsing with conditional random fields. In Proc. of HLT-NAACL. find
  25. D. A. Smith and J. Eisner. 2008. Dependency parsing by belief propagation. In Proc. of EMNLP. find
  26. D. A. Smith and N. A. Smith. 2007. Probabilistic models of nonprojective dependency trees. In EMNLP. find
  27. 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. CoNLL. find our card
  28. C. Sutton, A. McCallum, and K. Rohanimanesh. 2007. Dynamic conditional random fields: Factorized probabilistic models for labeling and segmenting sequence data. JMLR, 8:693–723. find
  29. R. E. Tarjan. 1977. Finding optimum branchings. Networks, 7(1):25–36. find
  30. D. Tarlow, I. E. Givoni, and R. S. Zemel. 2010. HOP-MAP: Efficient message passing with high order potentials. In Proc. of AISTATS. find
  31. B. Taskar, C. Guestrin, and D. Koller. 2003. Max-margin Markov networks. In NIPS. find
  32. B. Taskar, S. Lacoste-Julien, and M. I. Jordan. 2006. Structured prediction, dual extragradient and Bregman projections. JMLR, 7:1627–1653. find
  33. I. Tsochantaridis, T. Hofmann, T. Joachims, and Y. Altun. 2004. Support vector machine learning for interdependent and structured output spaces. In Proc. of ICML. find
  34. M. J. Wainwright and M. I. Jordan. 2008. Graphical Models, Exponential Families, and Variational Inference. Now Publishers. find
  35. M. J. Wainwright, T.S. Jaakkola, and A.S. Willsky. 2005. A new class of upper bounds on the log partition function. IEEE Trans. Inf. Theory, 51(7):2313–2335. find
  36. H. Yamada and Y. Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proc. of IWPT. find our card
  37. J. S. Yedidia, W. T. Freeman, and Y. Weiss. 2001. Generalized belief propagation. In NIPS. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/papers/martins-2010-turbo-parsers-dependency-parsing-approximate/