Elamur Research⌕
☰
home / papers / 2008 / Lattice-based Minimum Error Rate Training for Statistical Machine Translation

Lattice-based Minimum Error Rate Training for Statistical Machine Translation

Summary

Minimum Error Rate Training (MERT) tunes the weights of a log-linear SMT model so that a metric such as BLEU is optimized directly. Classic MERT finds, along a search direction, the exact piecewise-constant error surface over a small set of candidates, usually N-best lists. These lists cover only a tiny part of the search space, so training needs many re-decoding rounds and can overfit badly early on. Macherey et al. extend the line-optimization step to phrase lattices. Their algorithm builds the upper envelope, and therefore the exact error surface, for every translation encoded in a lattice. That means exponentially many candidates, yet the paper proves an upper bound that keeps runtime and memory efficient. On the NIST 2008 tasks with a phrase-based system, lattice MERT converges much faster and avoids the large first-iteration collapse of N-best MERT. It gives moderate but consistent BLEU gains on blind test sets. The approach makes MERT more stable and cheaper in decoding, and it extends naturally to confusion networks and hypergraphs.

Key points

  • The baseline N-best MERT used N = 50, the best-performing setting. Lattice MERT was run with lattices holding 40 arcs for each phrase, a setting that amounts to roughly 2·10^27 candidate translations per sentence.
  • On zhen-dev1, N-best MERT lost more than 27.3 BLEU points after its first iteration and needed until about iteration 5 to recover. Lattice MERT's first-iteration drop was under 0.5% BLEU, and it reached its optimum by the 5th iteration.
  • With the combined dev1+dev2 data for training, lattice MERT beat N-best MERT on all three NIST 2008 blind test sets. On development data, only the aren task improved.
  • Adding random search directions on top of the coordinate axes produced extra blind-test gains of 0.1–0.6 BLEU absolute. Results were reported for both 0-1 and MBR decoding on the aren and zhen tasks.
  • Envelopes are computed with a sweep-line algorithm from computational geometry (Bentley and Ottmann, 1979).

Interesting ideas

  • I1. Candidates as lines: Along a search direction, each hypothesis's model score is a linear function of the step size. The decoder's choice is then the topmost line, so the full set of possible outcomes is captured by an upper envelope. This view can make other argmax-based tuning problems exactly solvable along a line.
  • I2. Separating envelope construction from error projection: Once the envelope's segments are known, mapping them to error counts works the same way regardless of how they were produced. This modularity lets the same tuner run on N-best lists, lattices, confusion networks, or forests.
  • I3. Bigger candidate pools as regularization: Covering a vastly larger hypothesis space produces more breakpoints in the error surface and keeps the weights from overfitting a small repository early. The resulting weights also stay closer to the initial values, which is a useful lesson for any iterative rerank-and-retune loop.
  • I4. Random directions beyond coordinate axes: Searching along random directions as well as the coordinate axes reaches different local optima that can generalize better. It is a cheap trick for any coordinate-wise optimizer of non-smooth objectives.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Machine translation · Natural language processing

Topics: Machine translation

Cited by

63 papers of our library cite it (of the 140673 whose bibliographies we read); 1 of them have a page here, 62 not yet.

Cite

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

@inproceedings{macherey2008lattice,
  title = {{Lattice-based Minimum Error Rate Training for Statistical Machine Translation}},
  author = {Macherey, Wolfgang and Och, Franz and Thayer, Ignacio and Uszkoreit, Jakob},
  booktitle = {Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing},
  year = {2008},
  doi = {10.3115/1613715.1613807},
  url = {https://doi.org/10.3115/1613715.1613807}
}

References

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

  1. J. L. Bentley and T. A. Ottmann. 1979. Algorithms for reporting and counting geometric intersections. IEEE Trans. on Computers, C-28(9):643–647. ↗
  2. D. Cer, D. Jurafsky, and C. D. Manning. 2008. Regularization and Search for Minimum Error Rate Training. In Proceedings of the Third Workshop on Statistical Machine Translation, 46th Annual Meeting of the Association of Computational Linguistics: Human Language Technologies (ACL-2008 HLT), pages 26– 34, Columbus, OH, USA, June. find
  3. D. Chiang. 2005. A Hierarchical Phrase-based Model for Statistical Machine Translation. In ACL-2005, pages 263–270, Ann Arbor, MI, USA, June. find our card
  4. K. Duh and K. Kirchhoff. 2008. Beyond Log-Linear Models: Boosted Minimum Error Rate Training for N-best Re-ranking. In Proceedings of the Third Workshop on Statistical Machine Translation, 46th Annual Meeting of the Association of Computational Linguistics: Human Language Technologies (ACL-2008 HLT), pages 37–40, Columbus, OH, USA, June. find
  5. S. Elizalde and K. Woods. 2006. Bounds on the Number of Inference Functions of a Graphical Model, October. arXiv:math/0610233v1. ↗
  6. S. Kumar and W. Byrne. 2004. Minimum Bayes-Risk Decoding for Statistical Machine Translation. In Proc. HLT-NAACL, pages 196–176, Boston, MA, USA, May. find our card
  7. W. Macherey and F. J. Och. 2007. An Empirical Study on Computing Consensus Translations from Multiple Machine Translation Systems. In Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 986–995, Prague, Czech Republic, June. find
  8. F. J. Och. 2003. Minimum Error Rate Training in Statistical Machine Translation. In 41st Annual Meeting of the Association for Computational Linguistics (ACL), pages 160–167, Sapporo, Japan, July. find
  9. 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, Thomas J. Watson Research Center, Yorktown Heights, NY, USA. find our card
  10. K. A. Papineni. 1999. Discriminative training via linear programming. In IEEE Int. Conf. on Acoustics, Speech, and Signal Processing, volume 2, pages 561– 564, Phoenix, AZ, March. find
  11. W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery. 2007. Numerical Recipes: The Art of Scientific Computing. Cambridge University Press, Cambridge, UK, third edition. find
  12. A. V. Rosti, N. F. Ayan, B. Xiang, S. Matsoukas, R. Schwartz, and B. Dorr. 2007. Combining outputs from multiple machine translation systems. In Human Language Technologies 2007: The Conference of the North American Chapter of the Association for Computational Linguistics; Proceedings of the Main Conference, pages 228–235, Rochester, New York, April. Association for Computational Linguistics. find
  13. D. A. Smith and J. Eisner. 2006. Minimum Risk Annealing for Training Log-linear Models. In 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics (Coling/ACL-2006), pages 787–794, Sydney, Australia, July. find
  14. R. Tromble, S. Kumar, F. J. Och, and W. Macherey. 2008. Lattice minimum bayes-risk decoding for statistical machine translation. In Conference on Empirical Methods in Natural Language Processing (EMNLP), page 10, Waikiki, Honolulu, Hawaii, USA, October. find our card
  15. N. Ueffing, F. J. Och, and H. Ney. 2002. Generation of word graphs in statistical machine translation. In Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing, pages 156– 163, Philadelphia, PE, July. find
  16. T. Watanabe, J. Suzuki, H. Tsukada, and H. Isozaki. 2007. Online large-margin training for statistical machine translation. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL), pages 764–773, Prague, Czech Republic. find
  17. R. Zens, S. Hasan, and H. Ney. 2007. A Systematic Comparison of Training Criteria for Statistical Machine Translation. In Proceedings of the 2007 Conference on Empirical Methods in Natural Language Processing, Prague, Czech Republic, June. Association for Computational Linguistics. find
  18. A. Zollmann and A. Venugopal. 2006. Syntax augmented machine translation via chart parsing. In NAACL ’06: Proceedings of the 2006 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology, pages 138–141, New York, NY, June. Association for Computational Linguistics. ↗ our card

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/macherey-2008-lattice-based-minimum-error-rate/