The mathematics of statistical machine translation: parameter estimation

Abstract

We describe a series of five statistical models of the translation process and give algorithms for estimating the parameters of these models given a set of pairs of sentences that are translations of one another. We define a concept of word-by-word alignment between such pairs of sentences. For any given pair of such sentences each of our models assigns a probability to each of the possible word-by-word alignments. We give an algorithm for seeking the most probable of these alignments. Although the algorithm is suboptimal, the alignment thus obtained accounts well for the word-by-word relationships in the pair of sentences. We have a great deal of data in French and English from the proceedings of the Canadian Parliament. Accordingly, we have restricted our work to these two languages; but we feel that because our algorithms have minimal linguistic content they would work well on other pairs of languages. We also feel, again because of the minimal linguistic content of our algorithms, that it is reasonable to argue that word-by-word alignments are inherent in any sufficiently large bilingual corpus.

References

1. Baum, L. E. (1972). "An inequality and associated maximization technique in statistical estimation of probabilistic functions of a Markov process." Inequalities, 3, 1--8.
2. Brown, Peter F.; Cocke, John; Della Pietra, Stephen A.; Della Pietra, Vincent J.; Jelinek, Frederick; Lafferty, John D.; Mercer, Robert L.; and Roossin, Paul S. (1990). "A statistical approach to machine translation." Computational Linguistics, 16(2), 79--85.
3. Brown, Peter F.; Cocke, John; Della Pietra, Stephen A.; Della Pietra, Vincent J.; Jelinek, Frederick; Mercer, Robert L.; and Roossin, Paul S. (1988). "A statistical approach to language translation." In Proceedings, 12th International Conference on Computational Linguistics (COLING-88). Budapest, Hungary, August 1988, 71--76.
4. Brown, Peter F.; Della Pietra, Stephen A.; Della Pietra, Vincent J.; and Mercer, Robert L. (1991a). "A statistical approach to sense disambiguation in machine translation." In Fourth DARPA Workshop on Speech and Natural Language. Morgan Kaufmann Publishers, Inc., 146--151.
5. Brown, Peter F.; Della Pietra, Stephen A.; Della Pietra, Vincent J.; and Mercer, Robert L. (1991b). "Word sense disambiguation using statistical methods." In Proceedings, 29th Annual Meeting of the Association for Computational Linguistics. Berkeley CA, June 1991, 265--270.
6. Brown, Peter F.; Della Pietra, Vincent J.; deSouza, Peter V.; and Mercer, Robert L. (1990). "Class-based n-gram models of natural language." In Proceedings of the IBM Natural Language ITI. Paris, France, March 1990, 283--298. Also in Computational Linguistics 18(4), 1992, 467--479.
7. Brown, Peter F.; Lai, Jennifer C.; and Mercer, Robert L. (1991). "Aligning sentences in parallel corpora." In Proceedings, 29th Annual Meeting of the Association for Computational Linguistics. Berkeley CA, June 1991, 169--176.
8. Dempster, A. P.; Laird, N. M.; and Rubin, D. B. (1977). "Maximum likelihood from incomplete data via the EM algorithm." Journal of the Royal Statistical Society, 39(B), 1--38.
9. Gale, William A.; and Church, Kenneth W. (1991a). "Identifying word correspondences in parallel texts." In Fourth DARPA Workshop on Speech and Natural Language. Morgan Kaufmann Publishers, Inc., 152--157.
10. Gale, William A.; and Church, Kenneth W. (1991b). "A program for aligning sentences in bilingual corpora." In Proceedings, 29th Annual Meeting of the Association for Computational Linguistics. Berkeley CA, June 1991, 177--184.
11. Itô, Kiyoshi, editor. (1987). Encyclopedic Dictionary of Mathematics, Second Edition. MIT Press.
12. Kay, Martin (1991). "Text-translation alignment." In ACH/ALLC '91: "Making Connections" Conference Handbook. Tempe AZ, March 1991.
13. Maltese, G., and Mancini, F. (1992). "An automatic technique to include grammatical and morphological information in a trigram-based statistical language model." In Proceedings, IEEE International Conference on Acoustics, Speech and Signal Processing. San Francisco CA, March 1992, I-157-I-160.
14. Warwick, Susan, and Russell, Graham (1990). "Bilingual concordancing and bilingual lexicography." In EURALEX 4th International Congress. Málaga, Spain.
15. Weaver, W. (1955). Translation (1949). In Machine Translation of Languages. MIT Press.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Natural language processing

  • Machine learning

• Hardware

  • Power and energy

    • Power estimation and optimization

      • Platform power issues