---
title: "Turbo Parsers — Martins 2010"
description: "Rich non-projective dependency parsers that score sibling and grandparent arcs make exact inference intractable, so they need approximate decoding."
authors: ["André Martins", "Noah Smith", "Eric Xing", "Pedro Aguiar", "Mário Figueiredo"]
year: 2010
venue: "Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing"
source: "https://aclanthology.org/D10-1004/"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/papers/martins-2010-turbo-parsers-dependency-parsing-approximate/"
---
[Elamur Research](https://md.research.elamur.ai/) · [this page in HTML](https://research.elamur.ai/free/papers/martins-2010-turbo-parsers-dependency-parsing-approximate/)

[home](https://md.research.elamur.ai/) / [papers](https://md.research.elamur.ai/free/papers/) / [2010](https://md.research.elamur.ai/free/papers/2010/) / Turbo Parsers: Dependency Parsing by Approximate Variational Inference

# Turbo Parsers: Dependency Parsing by Approximate Variational Inference

**Authors:** [André Martins](https://md.research.elamur.ai/free/authors/andre-martins/), [Noah Smith](https://md.research.elamur.ai/free/authors/noah-smith/), [Eric Xing](https://md.research.elamur.ai/free/authors/eric-xing/), Pedro Aguiar, Mário Figueiredo · **Year:** 2010 · **Venue:** Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/D10-1004/) · [PDF](https://aclanthology.org/D10-1004.pdf)

**Citations:** [69](#cited-by) in our library, of the 140673 papers whose bibliographies we read

## 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
- **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.
- **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.
- **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.
- **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.
- **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](https://md.research.elamur.ai/free/shelves/linguistics/) · [Natural language processing](https://md.research.elamur.ai/free/shelves/nlp/)

Topics: [Dependency parsing](https://md.research.elamur.ai/free/topics/dependency-parsing/)

## Cited by

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.

- [Turning on the Turbo: Fast Third-Order Non-Projective Turbo Parsers](https://md.research.elamur.ai/free/papers/aclbulk-2013-martins-turning-turbo-fast-third-order/)
- [A Dependency Parser for Tweets](https://md.research.elamur.ai/free/papers/aclbulk-2014-kong-dependency-parser-tweets/)
- [Survey: Multiword Expression Processing: A Survey](https://md.research.elamur.ai/free/papers/constant-2017-survey-multiword-expression-processing-survey/)
- [Frame-Semantic Parsing](https://md.research.elamur.ai/free/papers/das-2014-frame-semantic-parsing/)
- [An Empirical Comparison of Parsing Methods for Stanford Dependencies](https://md.research.elamur.ai/free/papers/enud-2014-kong-empirical-comparison-parsing-methods-stanford/)
- [Transferring Coreference Resolvers with Posterior Regularization](https://md.research.elamur.ai/free/papers/martins-2015-transferring-coreference-resolvers-posterior-regularization/)
- [Integer Linear Programming for Discourse Parsing](https://md.research.elamur.ai/free/papers/perret-2016-integer-linear-programming-discourse-parsing/)
- [Large-Scale Cross-Document Coreference Using Distributed Inference and Hierarchical Models](https://md.research.elamur.ai/free/papers/singh-2011-large-scale-cross-document-coreference/)
- [Exploring Compositional Architectures and Word Vector Representations for Prepositional Phrase Attachment](https://md.research.elamur.ai/free/papers/tacl-2014-belinkov-exploring-compositional-architectures-word-vector/)
- [A Graph-based Lattice Dependency Parser for Joint Morphological Segmentation and Syntactic Analysis](https://md.research.elamur.ai/free/papers/tacl-2015-seeker-graph-based-lattice-dependency-parser/)

## Cite

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

```bibtex
@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/}
}
```

- [← previous Treebank of Chinese Bible Translations](https://md.research.elamur.ai/free/papers/wu-2010-treebank-chinese-bible-translations/)
- [next → Twitter as a Corpus for Sentiment Analysis and Opinion Mining](https://md.research.elamur.ai/free/papers/pak-2010-twitter-as-corpus-sentiment-analysis/)
- [↑ back to papers of 2010](https://md.research.elamur.ai/free/papers/2010/)

## 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](https://scholar.google.com/scholar?q=C%2E+Berrou%2C+A%2E+Glavieux%2C+and+P%2E+Thitimajshima%2E+1993%2E+Near+Shannon+limit+error%2Dcorrecting+coding+and+decoding%2E+In+Proc%2E+of+ICC%2C+volume+93%2C+pages+1064%E2%80%931070%2E)
2. S. Buchholz and E. Marsi. 2006. CoNLL-X shared task on multilingual dependency parsing. In CoNLL. [find](https://scholar.google.com/scholar?q=S%2E+Buchholz+and+E%2E+Marsi%2E+2006%2E+CoNLL%2DX+shared+task+on+multilingual+dependency+parsing%2E+In+CoNLL%2E) [our card](https://md.research.elamur.ai/free/papers/parsers-2006-buchholz-conll-x-shared-task-multilingual/)
3. K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz, and Y. Singer. 2006. Online passive-aggressive algorithms. JMLR, 7:551–585. [find](https://scholar.google.com/scholar?q=K%2E+Crammer%2C+O%2E+Dekel%2C+J%2E+Keshet%2C+S%2E+Shalev%2DShwartz%2C+and+Y%2E+Singer%2E+2006%2E+Online+passive%2Daggressive+algorithms%2E+JMLR%2C+7%3A551%E2%80%93585%2E)
4. J. Duchi, D. Tarlow, G. Elidan, and D. Koller. 2007. Using combinatorial optimization within max-product belief propagation. NIPS, 19. [find](https://scholar.google.com/scholar?q=J%2E+Duchi%2C+D%2E+Tarlow%2C+G%2E+Elidan%2C+and+D%2E+Koller%2E+2007%2E+Using+combinatorial+optimization+within+max%2Dproduct+belief+propagation%2E+NIPS%2C+19%2E)
5. J. R. Finkel, A. Kleeman, and C. D. Manning. 2008. Efficient, feature-based, conditional random field parsing. Proc. of ACL. [find](https://scholar.google.com/scholar?q=J%2E+R%2E+Finkel%2C+A%2E+Kleeman%2C+and+C%2E+D%2E+Manning%2E+2008%2E+Efficient%2C+feature%2Dbased%2C+conditional+random+field+parsing%2E+Proc%2E+of+ACL%2E)
6. K. Gimpel and N. A. Smith. 2010. Softmax-margin crfs: Training log-linear models with loss functions. In Proc. of NAACL. [find](https://scholar.google.com/scholar?q=K%2E+Gimpel+and+N%2E+A%2E+Smith%2E+2010%2E+Softmax%2Dmargin+crfs%3A+Training+log%2Dlinear+models+with+loss+functions%2E+In+Proc%2E+of+NAACL%2E)
7. A. Globerson and T. Jaakkola. 2008. Fixing max-product: Convergent message passing algorithms for MAP LP-relaxations. NIPS, 20. [find](https://scholar.google.com/scholar?q=A%2E+Globerson+and+T%2E+Jaakkola%2E+2008%2E+Fixing+max%2Dproduct%3A+Convergent+message+passing+algorithms+for+MAP+LP%2Drelaxations%2E+NIPS%2C+20%2E)
8. L. Huang. 2008. Forest reranking: Discriminative parsing with non-local features. In Proc. of ACL. [find](https://scholar.google.com/scholar?q=L%2E+Huang%2E+2008%2E+Forest+reranking%3A+Discriminative+parsing+with+non%2Dlocal+features%2E+In+Proc%2E+of+ACL%2E)
9. S. Kahane, A. Nasr, and O. Rambow. 1998. Pseudo-projectivity: a polynomially parsable non-projective dependency grammar. In Proc. of COLING. [find](https://scholar.google.com/scholar?q=S%2E+Kahane%2C+A%2E+Nasr%2C+and+O%2E+Rambow%2E+1998%2E+Pseudo%2Dprojectivity%3A+a+polynomially+parsable+non%2Dprojective+dependency+grammar%2E+In+Proc%2E+of+COLING%2E)
10. T. Koo and M. Collins. 2010. Efficient third-order dependency parsers. In Proc. of ACL. [find](https://scholar.google.com/scholar?q=T%2E+Koo+and+M%2E+Collins%2E+2010%2E+Efficient+third%2Dorder+dependency+parsers%2E+In+Proc%2E+of+ACL%2E)
11. T. Koo, A. Globerson, X. Carreras, and M. Collins. 2007. Structured prediction models via the matrix-tree theorem. In Proc. of EMNLP. [find](https://scholar.google.com/scholar?q=T%2E+Koo%2C+A%2E+Globerson%2C+X%2E+Carreras%2C+and+M%2E+Collins%2E+2007%2E+Structured+prediction+models+via+the+matrix%2Dtree+theorem%2E+In+Proc%2E+of+EMNLP%2E)
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](https://scholar.google.com/scholar?q=T%2E+Koo%2C+A%2E+M%2E+Rush%2C+M%2E+Collins%2C+T%2E+Jaakkola%2C+and+D%2E+Sontag%2E+2010%2E+Dual+decomposition+for+parsing+with+non%2Dprojective+head+automata%2E+In+Proc%2E+of+EMNLP%2E)
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](https://scholar.google.com/scholar?q=F%2E+R%2E+Kschischang%2C+B%2E+J%2E+Frey%2C+and+H%2E+A%2E+Loeliger%2E+2001%2E+Factor+graphs+and+the+sum%2Dproduct+algorithm%2E+IEEE+Trans%2E+Inf%2E+Theory%2C+47%282%29%3A498%E2%80%93519%2E)
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](https://scholar.google.com/scholar?q=J%2E+Lafferty%2C+A%2E+McCallum%2C+and+F%2E+Pereira%2E+2001%2E+Conditional+random+fields%3A+Probabilistic+models+for+segmenting+and+labeling+sequence+data%2E+In+Proc%2E+of+ICML%2E)
15. A. F. T. Martins, D. Das, N. A. Smith, and E. P. Xing. 2008. Stacking dependency parsers. In EMNLP. [find](https://scholar.google.com/scholar?q=A%2E+F%2E+T%2E+Martins%2C+D%2E+Das%2C+N%2E+A%2E+Smith%2C+and+E%2E+P%2E+Xing%2E+2008%2E+Stacking+dependency+parsers%2E+In+EMNLP%2E)
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](https://scholar.google.com/scholar?q=A%2E+F%2E+T%2E+Martins%2C+N%2E+A%2E+Smith%2C+and+E%2E+P%2E+Xing%2E+2009%2E+Concise+integer+linear+programming+formulations+for+dependency+parsing%2E+In+Proc%2E+of+ACL%2DIJCNLP%2E)
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](https://scholar.google.com/scholar?q=A%2E+F%2E+T%2E+Martins%2C+K%2E+Gimpel%2C+N%2E+A%2E+Smith%2C+E%2E+P%2E+Xing%2C+P%2E+M%2E+Q%2E+Aguiar%2C+and+M%2E+A%2E+T%2E+Figueiredo%2E+2010a%2E+Learning+structured+classifiers+with+dual+coordinate+descent%2E+Technical+Report+CMU%2DML%2D10%2D109%2E)
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](https://scholar.google.com/scholar?q=A%2E+F%2E+T%2E+Martins%2C+N%2E+A%2E+Smith%2C+E%2E+P%2E+Xing%2C+P%2E+M%2E+Q%2E+Aguiar%2C+and+M%2E+A%2E+T%2E+Figueiredo%2E+2010b%2E+Turbo+parsers%3A+Dependency+parsing+by+approximate+variational+inference+%28extended+version%29%2E)
19. A. McCallum, K. Schultz, and S. Singh. 2009. Factorie: Probabilistic programming via imperatively defined factor graphs. In NIPS. [find](https://scholar.google.com/scholar?q=A%2E+McCallum%2C+K%2E+Schultz%2C+and+S%2E+Singh%2E+2009%2E+Factorie%3A+Probabilistic+programming+via+imperatively+defined+factor+graphs%2E+In+NIPS%2E)
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](https://scholar.google.com/scholar?q=R%2E+T%2E+McDonald%2C+F%2E+Pereira%2C+K%2E+Ribarov%2C+and+J%2E+Hajic%2E+2005%2E+Non%2Dprojective+dependency+parsing+using+spanning+tree+algorithms%2E+In+Proc%2E+of+HLT%2DEMNLP%2E) [our card](https://md.research.elamur.ai/free/papers/narrative-2005-mcdonald-non-projective-dependency-parsing-spanning/)
21. R. McDonald, K. Lerman, and F. Pereira. 2006. Multilingual dependency analysis with a two-stage discriminative parser. In Proc. of CoNLL. [find](https://scholar.google.com/scholar?q=R%2E+McDonald%2C+K%2E+Lerman%2C+and+F%2E+Pereira%2E+2006%2E+Multilingual+dependency+analysis+with+a+two%2Dstage+discriminative+parser%2E+In+Proc%2E+of+CoNLL%2E) [our card](https://md.research.elamur.ai/free/papers/mcdonald-2006-multilingual-dependency-analysis-two-stage/)
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](https://scholar.google.com/scholar?q=R%2E+J%2E+McEliece%2C+D%2E+J%2E+C%2E+MacKay%2C+and+J%2E+F%2E+Cheng%2E+1998%2E+Turbo+decoding+as+an+instance+of+Pearl%E2%80%99s+%E2%80%9Cbelief+propagation%E2%80%9D+algorithm%2E+IEEE+Journal+on+Selected+Areas+in+Communications%2C+16%282%29%2E)
23. J. Pearl. 1988. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann. [find](https://scholar.google.com/scholar?q=J%2E+Pearl%2E+1988%2E+Probabilistic+Reasoning+in+Intelligent+Systems%3A+Networks+of+Plausible+Inference%2E+Morgan+Kaufmann%2E)
24. F. Sha and F. Pereira. 2003. Shallow parsing with conditional random fields. In Proc. of HLT-NAACL. [find](https://scholar.google.com/scholar?q=F%2E+Sha+and+F%2E+Pereira%2E+2003%2E+Shallow+parsing+with+conditional+random+fields%2E+In+Proc%2E+of+HLT%2DNAACL%2E)
25. D. A. Smith and J. Eisner. 2008. Dependency parsing by belief propagation. In Proc. of EMNLP. [find](https://scholar.google.com/scholar?q=D%2E+A%2E+Smith+and+J%2E+Eisner%2E+2008%2E+Dependency+parsing+by+belief+propagation%2E+In+Proc%2E+of+EMNLP%2E)
26. D. A. Smith and N. A. Smith. 2007. Probabilistic models of nonprojective dependency trees. In EMNLP. [find](https://scholar.google.com/scholar?q=D%2E+A%2E+Smith+and+N%2E+A%2E+Smith%2E+2007%2E+Probabilistic+models+of+nonprojective+dependency+trees%2E+In+EMNLP%2E)
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](https://scholar.google.com/scholar?q=M%2E+Surdeanu%2C+R%2E+Johansson%2C+A%2E+Meyers%2C+L%2E+Ma%CC%80rquez%2C+and+J%2E+Nivre%2E+2008%2E+The+CoNLL%2D2008+shared+task+on+joint+parsing+of+syntactic+and+semantic+dependencies%2E+CoNLL%2E) [our card](https://md.research.elamur.ai/free/papers/surdeanu-2008-conll-2008-shared-task-joint/)
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](https://scholar.google.com/scholar?q=C%2E+Sutton%2C+A%2E+McCallum%2C+and+K%2E+Rohanimanesh%2E+2007%2E+Dynamic+conditional+random+fields%3A+Factorized+probabilistic+models+for+labeling+and+segmenting+sequence+data%2E+JMLR%2C+8%3A693%E2%80%93723%2E)
29. R. E. Tarjan. 1977. Finding optimum branchings. Networks, 7(1):25–36. [find](https://scholar.google.com/scholar?q=R%2E+E%2E+Tarjan%2E+1977%2E+Finding+optimum+branchings%2E+Networks%2C+7%281%29%3A25%E2%80%9336%2E)
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](https://scholar.google.com/scholar?q=D%2E+Tarlow%2C+I%2E+E%2E+Givoni%2C+and+R%2E+S%2E+Zemel%2E+2010%2E+HOP%2DMAP%3A+Efficient+message+passing+with+high+order+potentials%2E+In+Proc%2E+of+AISTATS%2E)
31. B. Taskar, C. Guestrin, and D. Koller. 2003. Max-margin Markov networks. In NIPS. [find](https://scholar.google.com/scholar?q=B%2E+Taskar%2C+C%2E+Guestrin%2C+and+D%2E+Koller%2E+2003%2E+Max%2Dmargin+Markov+networks%2E+In+NIPS%2E)
32. B. Taskar, S. Lacoste-Julien, and M. I. Jordan. 2006. Structured prediction, dual extragradient and Bregman projections. JMLR, 7:1627–1653. [find](https://scholar.google.com/scholar?q=B%2E+Taskar%2C+S%2E+Lacoste%2DJulien%2C+and+M%2E+I%2E+Jordan%2E+2006%2E+Structured+prediction%2C+dual+extragradient+and+Bregman+projections%2E+JMLR%2C+7%3A1627%E2%80%931653%2E)
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](https://scholar.google.com/scholar?q=I%2E+Tsochantaridis%2C+T%2E+Hofmann%2C+T%2E+Joachims%2C+and+Y%2E+Altun%2E+2004%2E+Support+vector+machine+learning+for+interdependent+and+structured+output+spaces%2E+In+Proc%2E+of+ICML%2E)
34. M. J. Wainwright and M. I. Jordan. 2008. Graphical Models, Exponential Families, and Variational Inference. Now Publishers. [find](https://scholar.google.com/scholar?q=M%2E+J%2E+Wainwright+and+M%2E+I%2E+Jordan%2E+2008%2E+Graphical+Models%2C+Exponential+Families%2C+and+Variational+Inference%2E+Now+Publishers%2E)
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](https://scholar.google.com/scholar?q=M%2E+J%2E+Wainwright%2C+T%2ES%2E+Jaakkola%2C+and+A%2ES%2E+Willsky%2E+2005%2E+A+new+class+of+upper+bounds+on+the+log+partition+function%2E+IEEE+Trans%2E+Inf%2E+Theory%2C+51%287%29%3A2313%E2%80%932335%2E)
36. H. Yamada and Y. Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proc. of IWPT. [find](https://scholar.google.com/scholar?q=H%2E+Yamada+and+Y%2E+Matsumoto%2E+2003%2E+Statistical+dependency+analysis+with+support+vector+machines%2E+In+Proc%2E+of+IWPT%2E) [our card](https://md.research.elamur.ai/free/papers/parsers-2003-yamada-statistical-dependency-analysis-support-vector/)
37. J. S. Yedidia, W. T. Freeman, and Y. Weiss. 2001. Generalized belief propagation. In NIPS. [find](https://scholar.google.com/scholar?q=J%2E+S%2E+Yedidia%2C+W%2E+T%2E+Freeman%2C+and+Y%2E+Weiss%2E+2001%2E+Generalized+belief+propagation%2E+In+NIPS%2E)