---
title: "First- and Second-Order Expectation Semirings with Applications"
description: "Many training objectives for structured models need statistics summed over every… 1.0 BLEU. 35 references, cited by 66 papers here."
authors: ["Zhifei Li", "Jason Eisner"]
year: 2009
venue: "Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing"
source: "https://aclanthology.org/D09-1005/"
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/en/papers/li-2009-first-second-order-expectation-semirings/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/li-2009-first-second-order-expectation-semirings/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2009](https://md.research.elamur.ai/free/en/papers/2009/) / First- and Second-Order Expectation Semirings with Applications to Minimum-Risk Training on Translation Forests

# First- and Second-Order Expectation Semirings with Applications to Minimum-Risk Training on Translation Forests

**Authors:** [Zhifei Li](https://md.research.elamur.ai/free/en/authors/zhifei-li/) and [Jason Eisner](https://md.research.elamur.ai/free/en/authors/jason-eisner/) · **Year:** 2009 · **Venue:** [Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing](https://md.research.elamur.ai/free/en/venues/emnlp/) ([EMNLP 2009](https://md.research.elamur.ai/free/en/venues/emnlp/2009/)) · **Publisher:** [Association for Computational Linguistics](https://md.research.elamur.ai/free/en/publishers/association-for-computational-linguistics/) · **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/D09-1005/) · [PDF](https://aclanthology.org/D09-1005.pdf) · [OpenAlex](https://openalex.org/W2103149536)

**Citations:** 128 citations (OpenAlex, 2026-10-14) · [66](https://md.research.elamur.ai/free/en/papers/li-2009-first-second-order-expectation-semirings/cited-by/) in our library, of the 141,840 papers whose bibliographies we read

## Summary
Many training objectives for structured models need statistics summed over every derivation in a packed forest. Minimum-risk training and deterministic annealing are examples. They require gradients of expected loss and entropy, and those gradients involve second-order quantities. Li and Eisner extend Eisner's (2002) expectation semiring from lattices to hypergraphs. They also introduce a new second-order expectation semiring, informally called the "variance semiring." Combined with standard inside and inside-outside dynamic programming, it computes expectations of products of additive functions, covariances, Hessians, and the gradients of entropy and Bayes risk. All of this runs in time linear in the hypergraph size.

They implement the semirings in the open-source Joshua toolkit and use them for minimum-risk training of a Hiero system on IWSLT 2005 Chinese-to-English data. Optimizing risk over full hypergraphs instead of n-best lists beats MERT on the test set. Adding about 21k sparse features gives a gain of up to 1.0 BLEU. The result matters because it gives one generic, efficient recipe for gradient-based training over exponentially large hypothesis spaces.

## Key points
- **Two semirings:**
  - The first-order expectation semiring uses edge weights ⟨p_e, p_e·r_e⟩ and returns the total weight Z together with the unnormalized expectation of r.
  - The second-order semiring uses 4-tuples ⟨p_e, p_e r_e, p_e s_e, p_e r_e s_e⟩ and also returns the expectation of the product r·s.
- **Quantities covered:** expected hypothesis length and its variance, feature expectations, entropy, cross-entropy, KL divergence, Bayes risk, gradients of entropy and risk, covariance, and the Hessian.
- **Experimental setup:**
  - Data: IWSLT 2005 Chinese-English, about 40k sentence pairs.
  - Language model: 5-gram with modified Kneser-Ney smoothing, built with SRILM.
  - Training objective: minimum risk used an approximated BLEU (Tromble et al., 2008).
- **Five-feature model (test BLEU):**
  - MERT: 47.7.
  - Minimum risk on n-best lists: 47.7–47.8.
  - Minimum risk on hypergraphs: 48.3–48.4, a statistically significant gain over MERT.
- **Large model:** a forest-reranking stage adds 21k target-side unigram/bigram features, which MERT cannot tune. It reaches 48.7 test BLEU.
- **Effect of annealing:** deterministic annealing improved the dev-set objective and dev BLEU, but this did not carry over to the test set.

## Interesting ideas
- **Package the statistic into the weight.** Each edge weight carries a tuple holding a probability and probability-weighted feature values. A single unmodified inside pass then yields expectations. This trick transfers to any chart- or lattice-based model, such as parsers, taggers, or ASR lattices.
- **Go up one order for gradients.** Gradients of expectations, such as risk or entropy, are themselves expectations of products. A second-order semiring therefore gives exact gradients for annealing, semi-supervised entropy regularization, or active learning over whole forests.
- **Train on the full forest, not n-best lists.** Moving minimum-risk optimization from n-best lists to hypergraphs gave a consistent test gain. Using the full hypothesis space is a cheap improvement wherever forests already exist.
- **Use a differentiable risk objective so many features can be tuned.** Unlike MERT, gradient-based risk minimization scales to tens of thousands of sparse features. A two-stage setup (baseline system, then forest reranking) keeps this practical.
- **Optimize a smoothed metric, judge on the real one.** Training against an approximate, decomposable BLEU still won on the test set even though it lost on dev. This is a useful reminder that a surrogate training metric can generalize better than the exact one.

*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

- [Johns Hopkins University](https://md.research.elamur.ai/free/en/universities/johns-hopkins-university/) — University, Baltimore, United States · 187 works · 92,194 citations

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 9,085 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 8,888 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 9,296 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 9,206 works

## Cite

Cite as: Zhifei Li and Jason Eisner. 2009. First- and Second-Order Expectation Semirings with Applications to Minimum-Risk Training on Translation Forests. Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing.

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

```bibtex
@inproceedings{li2009first,
  title = {{First- and Second-Order Expectation Semirings with Applications to Minimum-Risk Training on Translation Forests}},
  author = {Zhifei Li and Jason Eisner},
  booktitle = {Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing},
  year = {2009},
  doi = {10.3115/1699510.1699517},
  url = {https://doi.org/10.3115/1699510.1699517}
}
```

- [← previous Conundrums in Noun Phrase Coreference Resolution: Making Sense of the State-of-the-Art](https://md.research.elamur.ai/free/en/papers/stoyanov-2009-conundrums-noun-phrase-coreference-resolution/)
- [next → CATiB: The Columbia Arabic Treebank](https://md.research.elamur.ai/free/en/papers/habash-2009-catib-columbia-arabic-treebank/)
- [↑ back to papers of 2009](https://md.research.elamur.ai/free/en/papers/2009/)

## References

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

1. J. K. Baker. 1979. Trainable grammars for speech recognition. In Jared J. Wolf and Dennis H. Klatt, editors, Speech Communication Papers Presented at the 97th Meeting of the Acoustical Society of America, MIT, Cambridge, MA, June. [find](https://scholar.google.com/scholar?q=J%2E+K%2E+Baker%2E+1979%2E+Trainable+grammars+for+speech+recognition%2E+In+Jared+J%2E+Wolf+and+Dennis+H%2E+Klatt%2C+editors%2C+Speech+Communication+Papers+Presented+at+the+97th+Meeting+of+the+Acoustical+Society+of+Amer)
2. David Chiang, Kevin Knight, and Wei Wang. 2009. 11,001 new features for statistical machine translation. In NAACL, pages 218–226. [find](https://scholar.google.com/scholar?q=David+Chiang%2C+Kevin+Knight%2C+and+Wei+Wang%2E+2009%2E+11%2C001+new+features+for+statistical+machine+translation%2E+In+NAACL%2C+pages+218%E2%80%93226%2E)
3. David Chiang. 2007. [Hierarchical phrase-based translation](https://md.research.elamur.ai/free/en/papers/chiang-2007-hierarchical-phrase-based-translation/). Computational Linguistics, 33(2):201–228.
4. W. K. Clifford. 1873. Preliminary sketch of biquaternions. Proceedings of the London Mathematical Society, 4:381–395. [find](https://scholar.google.com/scholar?q=W%2E+K%2E+Clifford%2E+1873%2E+Preliminary+sketch+of+biquaternions%2E+Proceedings+of+the+London+Mathematical+Society%2C+4%3A381%E2%80%93395%2E)
5. Matthias Eck and Chiori Hori. 2005. Overview of the iwslt 2005 evaluation campaign. In In Proc. of the International Workshop on Spoken Language Translation. [find](https://scholar.google.com/scholar?q=Matthias+Eck+and+Chiori+Hori%2E+2005%2E+Overview+of+the+iwslt+2005+evaluation+campaign%2E+In+In+Proc%2E+of+the+International+Workshop+on+Spoken+Language+Translation%2E)
6. Jason Eisner, Eric Goldlust, and Noah A. Smith. 2005. Compiling comp ling: practical weighted dynamic programming and the dyna language. In HLT/EMNLP, pages 281–290. [find](https://scholar.google.com/scholar?q=Jason+Eisner%2C+Eric+Goldlust%2C+and+Noah+A%2E+Smith%2E+2005%2E+Compiling+comp+ling%3A+practical+weighted+dynamic+programming+and+the+dyna+language%2E+In+HLT%2FEMNLP%2C+pages+281%E2%80%93290%2E)
7. Jason Eisner. 2002. [Parameter estimation for probabilistic finite-state transducers](https://md.research.elamur.ai/free/en/papers/eisner-2002-parameter-estimation-probabilistic-finite-state/). In ACL, pages 1–8.
8. Jason Eisner. 2003. [Learning non-isomorphic tree mappings for machine translation](https://md.research.elamur.ai/free/en/papers/eisner-2003-learning-non-isomorphic-tree-mappings/). In ACL, pages 205–208.
9. Michel Galley, Jonathan Graehl, Kevin Knight, Daniel Marcu, Steve DeNeefe, Wei Wang, and Ignacio Thayer. 2006. [Scalable inference and training of context-rich syntactic translation models](https://md.research.elamur.ai/free/en/papers/galley-2006-scalable-inference-training-context-rich/). In ACL, pages 961–968.
10. Giorgio Gallo, Giustino Longo, Stefano Pallottino, and Sang Nguyen. 1993. Directed hypergraphs and applications. Discrete Appl. Math., 42(2-3):177–201. [find](https://scholar.google.com/scholar?q=Giorgio+Gallo%2C+Giustino+Longo%2C+Stefano+Pallottino%2C+and+Sang+Nguyen%2E+1993%2E+Directed+hypergraphs+and+applications%2E+Discrete+Appl%2E+Math%2E%2C+42%282%2D3%29%3A177%E2%80%93201%2E)
11. Kevin Gimpel and Noah A. Smith. 2009. Cube summing, approximate inference with non-local features, and dynamic programming without semirings. In EACL, pages 318–326. [find](https://scholar.google.com/scholar?q=Kevin+Gimpel+and+Noah+A%2E+Smith%2E+2009%2E+Cube+summing%2C+approximate+inference+with+non%2Dlocal+features%2C+and+dynamic+programming+without+semirings%2E+In+EACL%2C+pages+318%E2%80%93326%2E)
12. Joshua Goodman. 1999. Semiring parsing. Computational Linguistics, 25(4):573–605. [find](https://scholar.google.com/scholar?q=Joshua+Goodman%2E+1999%2E+Semiring+parsing%2E+Computational+Linguistics%2C+25%284%29%3A573%E2%80%93605%2E)
13. Y Grandvalet and Y Bengio. 2004. Semi-supervised learning by entropy minimization. In NIPS, pages 529–536. [find](https://scholar.google.com/scholar?q=Y+Grandvalet+and+Y+Bengio%2E+2004%2E+Semi%2Dsupervised+learning+by+entropy+minimization%2E+In+NIPS%2C+pages+529%E2%80%93536%2E)
14. Liang Huang and David Chiang. 2005. Better k-best parsing. In IWPT, pages 53–64. [find](https://scholar.google.com/scholar?q=Liang+Huang+and+David+Chiang%2E+2005%2E+Better+k%2Dbest+parsing%2E+In+IWPT%2C+pages+53%E2%80%9364%2E)
15. Liang Huang. 2008. Forest reranking: Discriminative parsing with non-local features. In ACL, pages 586– 594. [find](https://scholar.google.com/scholar?q=Liang+Huang%2E+2008%2E+Forest+reranking%3A+Discriminative+parsing+with+non%2Dlocal+features%2E+In+ACL%2C+pages+586%E2%80%93+594%2E)
16. Feng Jiao, Shaojun Wang, Chi-Hoon Lee, Russell Greiner, and Dale Schuurmans. 2006. Semi-supervised conditional random fields for improved sequence segmentation and labeling. In ACL, pages 209–216. [find](https://scholar.google.com/scholar?q=Feng+Jiao%2C+Shaojun+Wang%2C+Chi%2DHoon+Lee%2C+Russell+Greiner%2C+and+Dale+Schuurmans%2E+2006%2E+Semi%2Dsupervised+conditional+random+fields+for+improved+sequence+segmentation+and+labeling%2E+In+ACL%2C+pages+209%E2%80%93216%2E)
17. Dan Klein and Christopher D. Manning. 2004. Parsing and hypergraphs. New developments in parsing technology, pages 351–372. [find](https://scholar.google.com/scholar?q=Dan+Klein+and+Christopher+D%2E+Manning%2E+2004%2E+Parsing+and+hypergraphs%2E+New+developments+in+parsing+technology%2C+pages+351%E2%80%93372%2E)
18. Raymond Lau, Ronald Rosenfeld, and Salim Roukos. 1993. Adaptive language modelling using the maximum entropy principle. In Proc. ARPA Human Language Technologies Workshop, pages 81–86. [find](https://scholar.google.com/scholar?q=Raymond+Lau%2C+Ronald+Rosenfeld%2C+and+Salim+Roukos%2E+1993%2E+Adaptive+language+modelling+using+the+maximum+entropy+principle%2E+In+Proc%2E+ARPA+Human+Language+Technologies+Workshop%2C+pages+81%E2%80%9386%2E)
19. Zhifei Li and Sanjeev Khudanpur. 2008. Large-scale discriminative n-gram language models for statistical machine translation. In AMTA, pages 133–142. [find](https://scholar.google.com/scholar?q=Zhifei+Li+and+Sanjeev+Khudanpur%2E+2008%2E+Large%2Dscale+discriminative+n%2Dgram+language+models+for+statistical+machine+translation%2E+In+AMTA%2C+pages+133%E2%80%93142%2E)
20. Zhifei Li and Sanjeev Khudanpur. 2009. Forest reranking for machine translation with the perceptron algorithm. In GALE book chapter on ”MT From Text”. [find](https://scholar.google.com/scholar?q=Zhifei+Li+and+Sanjeev+Khudanpur%2E+2009%2E+Forest+reranking+for+machine+translation+with+the+perceptron+algorithm%2E+In+GALE+book+chapter+on+%E2%80%9DMT+From+Text%E2%80%9D%2E)
21. Zhifei Li, Chris Callison-Burch, Chris Dyer, Juri Ganitkevitch, Sanjeev Khudanpur, Lane Schwartz, Wren Thornton, Jonathan Weese, and Omar. Zaidan. 2009a. [Joshua: An open source toolkit for parsing-based machine translation](https://md.research.elamur.ai/free/en/papers/li-2009-joshua-open-source-toolkit-parsing/). In WMT09, pages 26–30.
22. Zhifei Li, Jason Eisner, and Sanjeev Khudanpur. 2009b. Variational decoding for statistical machine translation. In ACL. [find](https://scholar.google.com/scholar?q=Zhifei+Li%2C+Jason+Eisner%2C+and+Sanjeev+Khudanpur%2E+2009b%2E+Variational+decoding+for+statistical+machine+translation%2E+In+ACL%2E)
23. Yang Liu, Qun Liu, and Shouxun Lin. 2006. [Tree-to-string alignment template for statistical machine translation](https://md.research.elamur.ai/free/en/papers/liu-2006-tree-string-alignment-template-statistical/). In ACL, pages 609–616.
24. Adam Lopez. 2009. Translation as weighted deduction. In EACL, pages 532–540. [find](https://scholar.google.com/scholar?q=Adam+Lopez%2E+2009%2E+Translation+as+weighted+deduction%2E+In+EACL%2C+pages+532%E2%80%93540%2E)
25. Franz Josef Och. 2003. Minimum error rate training in statistical machine translation. In ACL, pages 160– 167. [find](https://scholar.google.com/scholar?q=Franz+Josef+Och%2E+2003%2E+Minimum+error+rate+training+in+statistical+machine+translation%2E+In+ACL%2C+pages+160%E2%80%93+167%2E)
26. Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2001. [BLEU: A method for automatic evaluation of machine translation](https://md.research.elamur.ai/free/en/papers/papineni-2002-bleu-method-automatic-evaluation-machine/). In ACL, pages 311–318.
27. Adam Pauls, John DeNero, and Dan Klein. 2009. Consensus training for consensus decoding in machine translation. In EMNLP. [find](https://scholar.google.com/scholar?q=Adam+Pauls%2C+John+DeNero%2C+and+Dan+Klein%2E+2009%2E+Consensus+training+for+consensus+decoding+in+machine+translation%2E+In+EMNLP%2E)
28. B. A. Pearlmutter and J. M. Siskind. 2007. Lazy multivariate higher-order forward-mode ad. In Proceedings of the 34th Annual Symposium on Principles of Programming Languages (POPL), pages 155–160. [find](https://scholar.google.com/scholar?q=B%2E+A%2E+Pearlmutter+and+J%2E+M%2E+Siskind%2E+2007%2E+Lazy+multivariate+higher%2Dorder+forward%2Dmode+ad%2E+In+Proceedings+of+the+34th+Annual+Symposium+on+Principles+of+Programming+Languages+%28POPL%29%2C+pages+155%E2%80%93160%2E)
29. Fernando C. N. Pereira and David H. D. Warren. 1983. Parsing as deduction. In ACL, pages 137–144. [find](https://scholar.google.com/scholar?q=Fernando+C%2E+N%2E+Pereira+and+David+H%2E+D%2E+Warren%2E+1983%2E+Parsing+as+deduction%2E+In+ACL%2C+pages+137%E2%80%93144%2E)
30. Chris Quirk, Arul Menezes, and Colin Cherry. 2005. [Dependency treelet translation: syntactically informed phrasal smt](https://md.research.elamur.ai/free/en/papers/quirk-2005-dependency-treelet-translation-syntactically-informed/). In ACL, pages 271–279.
31. Kenneth Rose. 1998. Deterministic annealing for clustering, compression, classification, regression, and related optimization problems. In Proceedings of the IEEE, pages 2210–2239. [find](https://scholar.google.com/scholar?q=Kenneth+Rose%2E+1998%2E+Deterministic+annealing+for+clustering%2C+compression%2C+classification%2C+regression%2C+and+related+optimization+problems%2E+In+Proceedings+of+the+IEEE%2C+pages+2210%E2%80%932239%2E)
32. Stuart M. Shieber, Yves Schabes, and Fernando C. N. Pereira. 1994. Principles and implementation of deductive parsing. Journal of Logic Programming, 24:3–36. [find](https://scholar.google.com/scholar?q=Stuart+M%2E+Shieber%2C+Yves+Schabes%2C+and+Fernando+C%2E+N%2E+Pereira%2E+1994%2E+Principles+and+implementation+of+deductive+parsing%2E+Journal+of+Logic+Programming%2C+24%3A3%E2%80%9336%2E)
33. David A. Smith and Jason Eisner. 2006. [Minimum risk annealing for training log-linear models](https://md.research.elamur.ai/free/en/papers/smith-2006-minimum-risk-annealing-training-log/). In ACL, pages 787–794.
34. Andreas Stolcke. 2002. SRILM—an extensible language modeling toolkit. In Proceedings of the International Conference on Spoken Language Processing, pages 901–904. [find](https://scholar.google.com/scholar?q=Andreas+Stolcke%2E+2002%2E+SRILM%E2%80%94an+extensible+language+modeling+toolkit%2E+In+Proceedings+of+the+International+Conference+on+Spoken+Language+Processing%2C+pages+901%E2%80%93904%2E)
35. Roy Tromble, Shankar Kumar, Franz Och, and Wolfgang Macherey. 2008. [Lattice minimum-Bayes-risk decoding for statistical machine translation](https://md.research.elamur.ai/free/en/papers/tromble-2008-lattice-minimum-bayes-risk-decoding/). In EMNLP, pages 620–629.

*Updated 24 October 2026*