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:
- 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.
- 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.
- 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.
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.
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