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

Zhifei Li, Jason EisnerEMNLP 2009 · OpenReview

Abstract

Many statistical translation models can be regarded as weighted logical deduction. Under this paradigm, we use weights from the expectation semiring to compute first-order statistics (e.g., the expected hypothesis length or feature counts) over packed forests of translations. We then introduce a novel second-order expectation semiring, which computes second-order statistics such as the variance of the hypothesis length or the gradient of entropy. This second-order semiring is essential for training paradigms like minimum risk, deterministic annealing, and semi-supervised learning, where gradient descent optimization requires computing the gradient of entropy or risk. We implement these semirings in the Joshua machine translation toolkit, enabling minimum-risk training with gains of up to 1.0 BLEU point.

The Challenge of Packed Forests

In statistical machine translation, the output space is often represented as a "packed forest" or hypergraph. This structure represents an astronomical number of possible sentence structures and word choices in a compact form.

A packed forest (hypergraph) representing multiple translation derivations.

Training models on these forests effectively requires calculating more than just the most likely translation. Advanced objectives like Minimum-Risk Training (MRT) or Deterministic Annealing require calculating gradients of "risk" (expected loss) or "entropy" across the entire forest. While the first-order expectation semiring (Eisner, 2002) allowed for computing expected feature counts, it could not handle the second-order statistics—like variances or gradients of expectations—necessary for these sophisticated objectives.

The Second-Order Expectation Semiring

To address this, we extend the mathematical framework of semiring parsing. A semiring is a set of algebraic rules that can be integrated into dynamic programming algorithms (like the Inside algorithm) to compute various quantities.

Our primary contribution is the second-order expectation semiring. This algebraic structure tracks four values simultaneously: probability ($p$), two first-order expectations ($r$ and $s$), and their product or second-order statistic ($t$).

Algebraic operations for the second-order expectation semiring, tracking the 4-tuple <p, r, s, t>.

Through a "lifting trick," we demonstrate that this second-order semiring can be constructed by nesting one first-order expectation semiring inside another. This ensures mathematical soundness and allows the semiring to inherit existing optimization properties. Furthermore, we show that these semirings are a structured form of "dual numbers" used in automatic differentiation, bridging algebraic parsing and modern optimization.

Key Insights and Scalability

  • Forests vs. N-best Lists: Traditional tuning methods like MERT often rely on small n-best lists. Training on the full hypergraph (the forest) provides a much denser and more accurate gradient of the model's behavior.
  • Unified Framework: This approach provides a unified method to compute entropy, cross-entropy, KL divergence, and Bayes risk within the same dynamic programming framework.
  • Efficiency: By generalizing the Inside-Outside algorithm for these semirings, we significantly accelerate the computation of gradients, particularly for high-dimensional feature vectors.

Experimental Results

We evaluated the approach using the IWSLT 2005 Chinese-to-English task (40,000 sentence pairs). Because BLEU is not additively decomposable, we utilized a linear approximation of BLEU for the training objective.

Minimum-risk (MR) training on hypergraphs consistently outperformed standard MERT. On the test set, hypergraph-based MR training achieved a 48.4 BLEU score compared to MERT's 47.7. By leveraging the efficiency of the semiring approach to tune a model with 21,000 additional bigram features, we reached 48.7 BLEU—a total gain of 1.0 BLEU point over the baseline.

While Deterministic Annealing helped avoid local minima on development data, the gains were less pronounced on the test set, suggesting that the risk surface of translation models may be smoother than previously assumed when trained on full forests.

Summary updated

Abstract

Many statistical translation models can be regarded as weighted logical deduction. Under this paradigm, we use weights from the expectation semiring (Eisner, 2002), to compute first-order statistics (e.g., the expected hypothesis length or feature counts) over packed forests of translations (lattices or hypergraphs). We then introduce a novel second-order expectation semiring, which computes second-order statistics (e.g., the variance of the hypothesis length or the gradient of entropy). This second-order semiring is essential for many interesting training paradigms such as minimum risk, deterministic annealing, active learning, and semi-supervised learning, where gradient descent optimization requires computing the gradient of entropy or risk. We use these semirings in an open-source machine translation toolkit, Joshua, enabling minimum-risk training for a benefit of up to 1.0 bleu point.
BibTeX
@inproceedings{li2009first,
  author = {Zhifei Li and Jason Eisner},
  title = {{First- and Second-Order Expectation Semirings with Applications to Minimum-Risk Training on Translation Forests}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2009},
  url = {https://openreview.net/forum?id=Bk-MAWzdbH},
}
Figure