Elamur Research⌕
☰
home / papers / 2008 / Lattice Minimum Bayes-Risk Decoding for Statistical Machine Translation

Lattice Minimum Bayes-Risk Decoding for Statistical Machine Translation

Paper · 2008 · Roy Tromble, Shankar Kumar, Franz Och et al.

Summary

The paper extends Minimum Bayes-Risk (MBR) decoding for statistical machine translation beyond N-best lists of a few thousand candidates. It applies MBR to translation lattices, compact acyclic weighted automata that can encode an astronomically large set of translations. The authors identify a property that makes this tractable: the gain function must decompose into a sum of local, n-gram-based terms plus a length term. With such a gain, the expected gain of a candidate no longer requires summing over all lattice paths. It reduces to n-gram counts weighted by each n-gram's posterior probability in the lattice. Because BLEU does not decompose this way, they derive a linear approximation of corpus BLEU that does. The decoder is built from Weighted Finite State Automata operations. On Arabic-to-English, Chinese-to-English and English-to-Chinese tasks, lattice MBR gives moderate but consistent gains over N-best MBR. The analysis shows the gain comes mainly from a richer evidence space for estimating risk, not from having more candidates to choose from. This makes the work relevant to any system that relies on posteriors over hypotheses.

Key points

  • Lattices are far larger than N-best lists. At lattice density 30, the aren lattices hold on average about 10^81 hypotheses, while N-best MBR usually uses 100–10,000 entries and becomes costly above roughly 20,000.
  • Decoding has four steps: collect the n-grams in the evidence lattice, compute each n-gram's posterior, intersect weighted n-gram automata with an unweighted copy of the hypothesis lattice, and take the best path.
  • The scale factor α, which flattens or sharpens the posterior, strongly affects results. It was tuned by grid search on dev2 and evaluated on eval08, and the same optimum held for all three language pairs.
  • Results by maximum n-gram order (BLEU %):
    • aren goes from 38.7 at order 1 to 44.9 at order 3 and 4, so trigrams are enough.
    • zhen rises from 26.8 to 28.5 at order 4.
    • enzh rises from 40.0 to 42.6 at order 4.
  • Tuning with Minimum Error Rate Training concentrates probability on the MAP output. The distribution therefore has to be flattened before MBR can choose anything other than the MAP hypothesis.

Interesting ideas

  • I1. Separate hypothesis space from evidence space. The set of candidates you choose from can differ from the set used to estimate expected loss. This lets you rerank a small shortlist while drawing risk estimates from a much larger distribution, which is useful in any reranking setup.
  • I2. Rewrite a global metric as local n-gram terms. Once a gain function is a weighted sum of n-gram matches, the expectation over exponentially many structures collapses to a sum over n-gram posteriors. The same trick could make other metrics, or tasks like ASR and summarization, tractable over lattices.
  • I3. Treat posterior temperature as a key hyperparameter. A discriminatively trained model can be overconfident, so tuning a flattening factor on a dev set can matter as much as the decoding rule itself.
  • I4. Tune the maximum n-gram order per language pair. Checking the order separately for each pair can save computation without hurting quality, as with trigrams for Arabic-English.
  • I5. Use the lattice as a better posterior estimator. The finding that richer evidence improves risk estimates suggests lattice-based posteriors could also help discriminative training and confidence estimation.

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

🏢GoogleMountain View · United States353 works · 364,806 citations🎓Johns Hopkins UniversityBaltimore · United States187 works · 92,194 citations

📚 Shelves 4 Computer Science · 9,086 works Artificial Intelligence · 8,889 works Arts and Humanities · 9,296 works Language and Linguistics · 9,206 works

🧭 Topics 1 Machine translation · 958 works

Cite

Cite as Roy Tromble, Shankar Kumar, Franz Och and Wolfgang Macherey. 2008. Lattice Minimum Bayes-Risk Decoding for Statistical Machine Translation. Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing.

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

@inproceedings{tromble2008lattice,
  title = {{Lattice Minimum Bayes-Risk Decoding for Statistical Machine Translation}},
  author = {Roy Tromble, Shankar Kumar, Franz Och and Wolfgang Macherey},
  booktitle = {Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing},
  year = {2008},
  doi = {10.3115/1613715.1613792},
  url = {https://doi.org/10.3115/1613715.1613792}
}

References

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

  1. P. J. Bickel and K. A. Doksum. 1977. Mathematical Statistics: Basic Ideas and Selected topics. Holden-Day Inc., Oakland, CA, USA. find
  2. P. F. Brown, J. Cocke, S. A. Della Pietra, V. J . Della Pietra, F. Jelinek, J. D. Lafferty, R. L. Mercer, and P. S. find
  3. Roossin. 1990. A Statistical Approach to Machine Translation. Computational Linguistics, 16(2):79–85. find
  4. M. Dreyer, K. Hall, and S. Khudanpur. 2007. Comparing Reordering Constraints for SMT Using Efficient BLEU Oracle Computation. In SSST, NAACL-HLT 2007, pages 103–110, Rochester, NY, USA, April. find
  5. N. Ehling, R. Zens, and H. Ney. 2007. Minimum Bayes Risk Decoding for BLEU. In ACL 2007, pages 101– 104, Prague, Czech Republic, June. find
  6. V. Goel and W. Byrne. 2000. Minimum Bayes-Risk Automatic Speech Recognition. Computer Speech and Language, 14(2):115–135. find
  7. V. Goel. 2001. Minimum Bayes-Risk Automatic Speech Recognition. Ph.D. thesis, Johns Hopkins University, Baltimore, MD, USA. find
  8. J. Goodman. 1996. Parsing Algorithms and Metrics. In ACL, pages 177–183, Santa Cruz, CA, USA. find
  9. L. Karttunen, J-p. Chanod, G. Grefenstette, and A. Schiller. 1996. Regular Expressions for Language Engineering. Natural Language Engineering, 2:305– 328. find
  10. P. Koehn. 2004. Statistical Significance Tests for Machine Translation Evaluation. In EMNLP, Barcelona, Spain.
  11. S. Kumar and W. Byrne. 2002. Minimum Bayes-Risk word alignments of bilingual texts. In EMNLP, pages 140–147, Philadelphia, PA, USA. find
  12. S. Kumar and W. Byrne. 2004. Minimum Bayes-Risk Decoding for Statistical Machine Translation. In HLT-NAACL, pages 169–176, Boston, MA, USA.
  13. A. Lavie and A. Agarwal. 2007. METEOR: An Automatic Metric for MT Evaluation with High Levels of Correlation with Human Judgments. In SMT Workshop, ACL, pages 228–231, Prague, Czech Republic.
  14. W. Macherey, F. Och, I. Thayer, and J. Uszkoreit. 2008. Lattice-based Minimum Error Rate Training for Statistical Machine Translation. In EMNLP, Honolulu, Hawaii, USA.
  15. E. Matusov, R. Zens, and H. Ney. 2004. Symmetric Word Alignments for Statistical Machine Translation. In COLING, Geneva, Switzerland. find
  16. H. Mi, L. Huang, and Q. Liu. 2008. Forest-Based Translation. In ACL, Columbus, OH, USA.
  17. M. Mohri. 1997. Finite-state transducers in language and speech processing. Computational Linguistics, 23(3).
  18. M. Mohri. 2002. Semiring frameworks and algorithms for shortest-distance problems. Journal of Automata, Languages and Combinatorics, 7(3):321–350. find
  19. NIST. 2002-2008. The NIST Machine Translation Evaluations. http://www.nist.gov/speech/tests/mt/. ↗
  20. F. Och and H. Ney. 2003. A systematic comparison of various statistical alignment models. Computational Linguistics, 29(1):19 – 51. find
  21. F. Och and H. Ney. 2004. The Alignment Template Approach to Statistical Machine Translation. Computational Linguistics, 30(4):417 – 449. find
  22. F. Och. 2003. Minimum Error Rate Training in Statistical Machine Translation. In ACL, Sapporo, Japan. find
  23. K. Papineni, S. Roukos, T. Ward, and W. Zhu. 2001. Bleu: a Method for Automatic Evaluation of Machine Translation. Technical Report RC22176 (W0109-022), IBM Research Division.
  24. A. Sixtus and S. Ortmanns. 1999. High Quality Word Graphs Using Forward-Backward Pruning. In ICASSP, Phoenix, AZ, USA. find
  25. D. Smith and J. Eisner. 2006. Minimum Risk Annealing for Training Log-Linear Models. In ACL, Sydney, Australia.
  26. D. Smith and N. Smith. 2007. Probabilistic models of nonprojective dependency trees. In EMNLP-CoNLL, Prague, Czech Republic. find
  27. M. Snover, B. Dorr, R. Schwartz, L. Micciulla, and J. Makhoul. 2006. A Study of Translation Edit Rate with Targeted Human Annotation. In AMTA, Boston, MA, USA.
  28. I. Titov and J. Henderson. 2006. Loss Minimization in Parse Reranking. In EMNLP, Sydney, Australia. find
  29. N. Ueffing, F. Och, and H. Ney. 2002. Generation of Word Graphs in Statistical Machine Translation. In EMNLP, Philadelphia, PA, USA. find
  30. H. Zhang and D. Gildea. 2008. Efficient Multi-pass Decoding for Synchronous Context Free Grammars. In ACL, Columbus, OH, USA. find
  31. A. Zollmann and A. Venugopal. 2006. Syntax Augmented Machine Translation via Chart Parsing. In HLT-NAACL, New York, NY, USA.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/tromble-2008-lattice-minimum-bayes-risk-decoding/