A weighted finite state transducer implementation of the alignment template model for statistical machine translation

ABSTRACT

We present a derivation of the alignment template model for statistical machine translation and an implementation of the model using weighted finite state transducers. The approach we describe allows us to implement each constituent distribution of the model as a weighted finite state transducer or acceptor. We show that bitext word alignment and translation under the model can be performed with standard FSM operations involving these transducers. One of the benefits of using this framework is that it obviates the need to develop specialized search procedures, even for the generation of lattices or N-Best lists of bitext word alignments and translation hypotheses. We evaluate the implementation of the model on the French-to-English Hansards task and report alignment and translation performance.

REFERENCES

• 1: Srinivas Bangalore , Giuseppe Riccardi, A finite-state approach to machine translation, Second meeting of the North American Chapter of the Association for Computational Linguistics on Language technologies 2001, p.1-8, June 01-07, 2001, Pittsburgh, Pennsylvania [doi>10.3115/1073336.1073354]
• 2: Peter F. Brown , Vincent J. Della Pietra , Stephen A. Della Pietra , Robert L. Mercer, The mathematics of statistical machine translation: parameter estimation, Computational Linguistics, v.19 n.2, June 1993
• 3: G. Doddington. 2002. Automatic evaluation of machine translation quality using n-gram co-occurrence statistics. In Proc. of HLT 2002, San Diego, CA. USA.
• 4: Kevin Knight , Yaser Al-Onaizan, Translation with Finite-State Devices, Proceedings of the Third Conference of the Association for Machine Translation in the Americas on Machine Translation and the Information Soup, p.421-437, October 28-31, 1998
• 5: D. Marcu and U. Germann, 2002. The ISI ReWrite Decoder Release 0.7.0b. http://www.isi.edu/licensedsw/rewrite-decoder/.
• 6: M. Mohri, F. Pereira, and M. Riley, 1997. ATT General-purpose finite-state machine software tools. http://www.research.att.com/sw/tools/fsm/.
• 7: M. Mohri, F. Pereira, and M. Riley. 2002. Weighted finite-state transducers in speech recognition. Computer Speech and Language, 16(1):69--88.
• 8: Franz Josef Och , Hermann Ney, Improved statistical alignment models, Proceedings of the 38th Annual Meeting on Association for Computational Linguistics, p.440-447, October 03-06, 2000, Hong Kong [doi>10.3115/1075218.1075274]
• 9: F. Och, C. Tillmann, and H. Ney. 1999. Improved alignment models for statistical machine translation. In Proc. of the Joint Conf. of Empirical Methods in Natural Language Processing and Very Large Corpora, pages 20--28, College Park, MD, USA.
• 10: F. Och. 2002. Statistical Machine Translation: From Single Word Models to Alignment Templates. Ph.D. thesis, RWTH Aachen, Germany.
• 11: 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.
• 12: A. Stolcke. 2002. SRILM -- an extensible language modeling toolkit. In Proc. of the International Conference on Spoken Language Processing, pages 901--904, Denver, CO, USA. http://www.speech.sri.com/projects/srilm/.
• 13: Nicola Ueffing , Franz Josef Och , Hermann Ney, Generation of word graphs in statistical machine translation, Proceedings of the ACL-02 conference on Empirical methods in natural language processing, p.156-163, July 06, 2002 [doi>10.3115/1118693.1118714]
• 14: F. Wessel, K. Macherey, and R. Schlueter. 1998. Using word probabilities as confidence measures. In Proc. of ICASSP-98, pages 225--228, Seattle, WA, USA.