Efficient Path Counting Transducers for Minimum Bayes-Risk Decoding of Statistical Machine Translation Lattices

Graeme W. Blackwood, Adrià de Gispert, William J. ByrneACL 2010 · OpenReview

Graeme Blackwood, Adrià de Gispert, William Byrne
Proceedings of the ACL 2010 Conference Short Papers. 2010.

Abstract

This paper addresses a core efficiency bottleneck in Statistical Machine Translation (SMT): the rapid identification of the optimal translation from a massive graph of possibilities. The authors present a novel, exact method for Minimum Bayes-Risk (MBR) decoding on translation lattices using Weighted Finite State Transducers (WFSTs). By introducing a "last-occurrence" path-counting transducer, they achieve significant speedups—decoding in roughly 0.1 seconds per sentence—without the approximations common in previous high-speed decoders.

The Challenge of Lattice MBR Decoding

In SMT, a decoder typically generates a lattice—a directed acyclic graph representing millions of possible translation hypotheses. While standard decoding picks the single most likely path (Maximum Likelihood), Minimum Bayes-Risk (MBR) decoding is often superior. It selects the translation that is "closest" to all other likely translations, effectively hedging against errors.

The mathematical challenge in Lattice MBR (LMBR) is calculating the path posterior probability for every n-gram (sequences of 1 to 4 words) in the lattice. This requires identifying every path that contains a specific n-gram at least once and summing their probabilities. Doing this sequentially for every n-gram is computationally prohibitive, while using "expected counts" (how many times an n-gram appears in total) is a faster but often inaccurate approximation.

Methods: The "Last-Occurrence" Transducer

The authors leverage Weighted Finite State Transducers (WFSTs) to perform these calculations simultaneously and exactly. Their approach involves three key steps:

  1. N-gram Mapping ($\Phi_n$): A transducer transforms a standard word lattice into an "n-gram lattice," treating sequences like "the cat sat" as single symbols to simplify counting.
  2. The "Last-Occurrence" Transducer ($\Psi_n^R$): This is the paper's primary innovation. To avoid overcounting paths that contain the same n-gram multiple times, they design a transducer that only "counts" the very last time an n-gram appears on any given path.
  3. Modified Forward Algorithm: Unlike previous methods that relied on expensive WFST operations like determinization, the authors use a modified forward algorithm tailored to the $\Psi_n^R$ structure. This algorithm sums probabilities efficiently by tracking the last encountered n-gram, avoiding the creation of redundant states.
The structure of the path-counting transducer used to identify n-gram occurrences within the lattice.

Key Insights and Results

The researchers evaluated their method on the NIST Arabic-to-English machine translation task using the HiFST decoder and OpenFst library. Several key findings emerged:

  • Directionality and Efficiency: The authors discovered that searching for the last occurrence of an n-gram ($\Psi_n^R$) is much more efficient than searching for the first occurrence ($\Psi_n^L$). The latter requires creating many copies of the lattice during composition, leading to memory and speed explosions.
  • Translation Quality: LMBR decoding provided a gain of +0.8 to +1.0 BLEU points over standard Maximum Likelihood decoding on newswire data. Their method provides the accuracy of exact path posteriors with the speed of an approximation.
  • Computational Performance: The proposed $\Psi_n^R$ method was nearly twice as fast as the traditional sequential approach. Total decoding time was reduced to approximately 0.1 seconds per sentence, making exact LMBR feasible for large-scale production systems.
Comparison of total decoding time (seconds) versus lattice n-grams for the sequential and simultaneous $\Psi_n^R$ methods.

Conclusion

By tailoring a forward algorithm to the specific structure of their counting transducer, the authors bypassed the heavy lifting usually required by general-purpose WFST libraries. While some overhead remains in processing $\epsilon$-arcs (empty transitions), the "last-occurrence" approach represents a significant step forward in making sophisticated MBR decoding practical for real-time translation tasks.

Summary updated

BibTeX
@inproceedings{blackwood2010efficient,
  author = {Graeme W. Blackwood and Adrià de Gispert and William J. Byrne},
  title = {{Efficient Path Counting Transducers for Minimum Bayes-Risk Decoding of Statistical Machine Translation Lattices}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2010},
  url = {https://openreview.net/forum?id=BgfhgXWlpee},
}
Figure