Statistical machine translation

Abstract

Statistical machine translation (SMT) treats the translation of natural language as a machine learning problem. By examining many samples of human-produced translation, SMT algorithms automatically learn how to translate. SMT has made tremendous strides in less than two decades, and new ideas are constantly introduced. This survey presents a tutorial overview of the state of the art. We describe the context of the current research and then move to a formal problem description and an overview of the main subproblems: translation modeling, parameter estimation, and decoding. Along the way, we present a taxonomy of some different approaches within these areas. We conclude with an overview of evaluation and a discussion of future directions.

References

1. Aho, A. V. and Ullman, J. D. 1969. Syntax directed translations and the pushdown assembler. J. Comput. Syst. Sci. 3, 37--57.
2. Ahrenberg, L., Merkel, M., Hein, A. S., and Tiedmann, J. 2000. Evaluation of word alignment systems. In Proceedings of the International Conference on Language Resources and Evaluation (LREC). Vol. 3. 1255--1261.
3. Al-Onaizan, Y., Curin, J., Jahr, M., Knight, K., Lafferty, J., Melamed, D., Och, F. J., Purdy, D., Smith, N. A., and Yarowsky, D. 1999. Statistical machine translation: Tech. rep., Center for Speech and Language Processing, Johns Hopkins University.
4. Al-Onaizan, Y. and Papineni, K. 2006. Distortion models for statistical machine translation. In Proceedings of ACL-COLING. 529--536.
5. Albrecht, J. and Hwa, R. 2007. Regression for sentence-level MT evaluation with pseudo references. In Proceedings of the Association for Computational Linguistics (ACL). 296--303.
6. Alshawi, H., Bangalore, S., and Douglas, S. 2000. Learning dependency translation models as collections of finite state head transducers. Computat. Linguist. 26, 1, 45--60.
7. Ayan, N. F. and Dorr, B. 2006a. Going beyond AER: An extensive analysis of word alignments and their impact on MT. In Proceedings of ACL-COLING. 9--16.
8. Ayan, N. F., Dorr, B., and Monz, C. 2005a. Alignment link projection using transformation-based learning. In Proceedings of HLT-EMNLP. 185--192.
9. Ayan, N. F., Dorr, B., and Monz, C. 2005b. Neuralign: Combining word alignments using neural networks. In Proceedings of HLT-EMNLP. 65--72.
10. Ayan, N. F. and Dorr, B. J. 2006b. A maximum entropy approach to combining word alignments. In Proceedings of HLT-NAACL. 96--103.
11. Banchs, R. E., Crego, J. M., de Gispert, A., Lambert, P., and Mariño, J. B. 2005. Statistical machine translation of euparl data by using bilingual n-grams. In Proceedings of ACL Workshop on Building and Using Parallel Texts. 133--136.
12. Bannard, C. and Callison-Burch, C. 2005. Paraphrasing with bilingual parallel corpora. In Proceedings of the Association for Computational Linguistics (ACL). 597--604.
13. Baum, L. E. 1972. An inequality and associated maximization technique in statistical estimation of probabilistic functions of a Markov process. In Proceedings of the 3rd Symposium on Inequalities. Inequalities, vol. 3. Academic Press, 1--8.
14. Berger, A. L., Brown, P. F., Pietra, S. A. D., Pietra, V. J. D., Gillett, J. R., Lafferty, J. D., Mercer, R. L., Printz, H., and Ures, L. 1994. The Candide system for machine translation. In Proceedings of the ARPA Workshop on Human Language Technology. 157--162.
15. Berger, A. L., Brown, P. F., Pietra, S. A. D., Pietra, V. J. D., Kehler, A. S., and Mercer, R. L. 1996. Language translation apparatus and method using context-based translation models. United States Patent 5510981.
16. Berger, A. L., Pietra, S. A. D., and Pietra, V. J. D. 1996. A maximum entropy approach to natural language processing. Comput. Linguist. 22, 1, 39--71.
17. Birch, A., Callison-Burch, C., Osborne, M., and Koehn, P. 2006. Constraining the phrase-based, joint probability statistical translation model. In Proceedings of HLT-NAACL Workshop on Statistical Machine Translation. 154--157.
18. Blunsom, P. and Cohn, T. 2006. Discriminative word alignment with conditional random fields. In Proceedings of ACL-COLING. 65--72.
19. Brants, T., Popat, A. C., Xu, P., Och, F. J., and Dean, J. 2007. Large language models in machine translation. In Proceedings of EMNLP-CoNLL. 858--867.
20. Brown, P. F., Cocke, J., Pietra, S. D., Pietra, V. J. D., Jelinek, F., Lafferty, J. D., Mercer, R. L., and Roossin, P. S. 1990. A statistical approach to machine translation. Comput. Linguist. 16, 2, 79--85.
21. Brown, P. F., deSouza, P. V., Mercer, R. L., Pietra, V. J. D., and Lai, J. C. 1992. Class-based n-gram models of natural language. Comput. Linguist. 18, 4, 467--479.
22. Brown, P. F., Pietra, S. A. D., Pietra, V. J. D., and Mercer, R. L. 1993. The mathematics of statistical machine translation: Parameter estimation. Comput. Linguist. 19, 2, 263--311.
23. Burbank, A., Carpuat, M., Clark, S., Dreyer, M., Fox, P., Groves, D., Hall, K., Hearne, M., Melamed, I. D., Shen, Y., Way, A., Wellington, B., and Wu, D. 2005. Final report of the 2005 language engineering workshop on statistical machine translation by parsing. Tech. rep., Johns Hopkins University Center for Speech and Language Processing.
24. Callison-Burch, C., Bannard, C., and Schroeder, J. 2005. Scaling phrase-based statistical machine translation to larger corpora and longer phrases. In Proceedings of the Association for Computational Linguistics (ACL). 255--262.
25. Callison-Burch, C., Fordyce, C., Koehn, P., Monz, C., and Schroeder, J. 2007. (Meta-) evaluation of machine translation. In Proceedings of the Workshop on Statistical Machine Translation. 136--158.
26. Callison-Burch, C., Koehn, P., and Osborne, M. 2006. Improved statistical machine translation using paraphrases. In Proceedings of HLT-NAACL.
27. Callison-Burch, C., Osborne, M., and Koehn, P. 2006. Re-evaluating the role of BLEU in machine translation research. In Proceedings of European Chapter of the Association for Computational Linguistics (EACL). 249--256.
28. Callison-Burch, C., Talbot, D., and Osborne, M. 2004. Statistical machine translation with word- and sentence-aligned parallel corpora. In Proceedings of the Association for Computational Linguistics (ACL). 176--183.
29. Carpuat, M. and Wu, D. 2005. Word sense disambiguation vs. statistical machine translation. In Proceedings of the Association for Computational Linguistics (ACL). 387--394.
30. Carpuat, M. and Wu, D. 2007. Improving statistical machine translation using word sense disambiguation. In Proceedings of the Association for Computational Linguistics (ACL). 61--72.
31. Chan, Y. S., Ng, H. T., and Chiang, D. 2007. Word sense disambiguation improves statistical machine translation. In Proceedings of the Association for Computational Linguistics (ACL). 33--40.
32. Charniak, E., Knight, K., and Yamada, K. 2003. Syntax-based language models for statistical machine translation. In Proceedings of MT Summit IX.
33. Chelba, C. and Jelinek, F. 1998. Exploiting syntactic structure for language modeling. In Proceedings of ACL-COLING. 225--231.
34. Chen, S. F. and Goodman, J. 1998. An empirical study of smoothing techniques for language modeling. Tech. rep. TR-10-98, Computer Science Group, Harvard University.
35. Cherry, C. and Lin, D. 2003. A probability model to improve word alignment. In Proceedings of the Association for Computational Linguistics (ACL).
36. Chiang, D. 2005. A hierarchical phrase-based model for statistical machine translation. In Proceedings of the Association for Computational Linguistics (ACL). 263--270.
37. Chiang, D. 2006. An introduction to synchronous grammars. Part of a ACL Tutorial.
38. Chiang, D. 2007. Hierarchical phrase-based translation. Comput. Linguist. 33, 2.
39. Chiang, D., Lopez, A., Madnani, N., Monz, C., Resnik, P., and Subotin, M. 2005. The Hiero machine translation system: Extensions, evaluation, and analysis. In Proceedings of HLT-EMNLP. 779--786.
40. Church, K. and Hovy, E. 1993. Good applications for crummy machine translation. Mach. Transl. 8, 239--258.
41. Church, K. and Patil, R. 1982. Coping with syntactic ambiguity or how to put the block in the box on the table. Comput. Linguist. 8, 3--4, 139--149.
42. Collins, M., Hajič, J., Ramshaw, L., and Tillman, C. 1999. A statistical parser for Czech. In Proceedings of the Association for Computational Linguistics (ACL). 505--512.
43. Collins, M., Koehn, P., and Kucerova, I. 2005. Clause restructuring for statistical machine translation. In Proceedings of the Association for Computational Linguistics (ACL). 531--540.
44. Darroch, J. N. and Ratcliff, D. 1972. Generalized iterative scaling for log-linear models. Annals Math. Statist. 43, 5, 1470--1480.
45. Dejean, H., Gaussier, E., Goutte, C., and Yamada, K. 2003. Reducing parameter space for word alignment. In Proceedings of HLT-NAACL Workshop on Building and Using Parallel Texts. 23--26.
46. Dempster, A. P., Laird, N. M., and Rubin, D. B. 1977. Maximum likelihood from incomplete data via the EM algorithm. J. Royal Statist. Soc. 39, 1, 1--38.
47. DeNeefe, S., Knight, K., and Chan, H. H. 2005. Interactively exploring a machine translation model. In Proceedings of the Association for Computational Linguistics (ACL) (Companion Vol.). 97--100.
48. DeNero, J., Gillick, D., Zhang, J., and Klein, D. 2006. Why generative phrase models underperform surface heuristics. In Proceedings of HLT-NAACL Workshop on Statistical Machine Translation. 31--38.
49. DeNero, J. and Klein, D. 2007. Tailoring word alignments to syntactic machine translation. In Proceedings of the Association for Computational Linguistics (ACL). 17--24.
50. Doddington, G. 2002. Automatic evaluation of machine translation quality using n-gram co-occurrence statistics. In Proceedings of the Human Language Technology Conference (HLT).
51. Dorr, B. J., Jordan, P. W., and Benoit, J. W. 1999. A survey of current paradigms in machine translation. In Advances in Computers, M. Zelkowitz, Ed. Vol. 49. Academic Press, 1--68.
52. Eck, M., Vogel, S., and Waibel, A. 2004. Language model adaptation for statistical machine translation based on information retrieval. In Proceedings of the International Conference on Language Resources and Evaluation (LREC).
53. Federico, M. and Bertoldi, N. 2006. How many bits are needed to store probabilities for phrase-based translation? In Proceedings of NAACL Workshop on Statistical Machine Translation. 94--101.
54. Foster, G., Kuhn, R., and Johnson, H. 2006. Phrasetable smoothing for statistical machine translation. In Proceedings of EMNLP. 53--61.
55. Fox, H. J. 2002. Phrasal cohesion and statistical machine translation. In Proceedings of EMNLP. 304--311.
56. Fraser, A. and Marcu, D. 2006. Semi-supervised training for statistical word alignment. In Proceedings of the Association for Computational Linguistics (ACL). 769--776.
57. Fraser, A. and Marcu, D. 2007a. Getting the structure right for word alignment: LEAF. In Proceedings of EMNLP-CoNLL. 51--60.
58. Fraser, A. and Marcu, D. 2007b. Measuring word alignment quality for statistical machine translation. Comput. Linguist. 33, 3.
59. Gale, W. A. and Church, K. W. 1991. Identifying word correspondences in parallel text. In Proceedings of Darpa Workshop on Speech and Natural Language. 152--157.
60. Gale, W. A. and Church, K. W. 1993. A program for aligning sentences in bilingual corpora. Comput. Linguist. 19, 1, 75--102.
61. Galley, M., Graehl, J., Knight, K., Marcu, D., DeNeefe, S., Wang, W., and Thayer, I. 2006. Scalable inference and training of context-rich syntactic translation models. In Proceedings of the Association for Computational Linguistics (ACL). 961--968.
62. Galley, M., Hopkins, M., Knight, K., and Marcu, D. 2004. What's in a translation rule? In Proceedings of HLT-NAACL. 273--280.
63. Germann, U. 2003. Greedy decoding for statistical machine translation in almost linear time. In Proceedings of HLT-NAACL. 72--79.
64. Germann, U., Jahr, M., Knight, K., Marcu, D., and Yamada, K. 2001. Fast decoding and optimal decoding for machine translation. In Proceedings of ACL-EACL.
65. Germann, U., Jahr, M., Knight, K., Marcu, D., and Yamada, K. 2004. Fast and optimal decoding for machine translation. Artif. Intellig. 154, 1--2, 127--143.
66. Gildea, D. 2004. Dependencies vs. constituencies for tree-based alignment. In Proceedings of EMNLP. 214--221.
67. Goldwater, S. and McClosky, D. 2005. Improving statistical MT through morphological analysis. In Proceedings of HLT-EMNLP. 676--683.
68. Graehl, J. and Knight, K. 2004. Training tree transducers. In Proceedings of HLT-NAACL. 105--112.
69. Hopcroft, J. E. and Ullman, J. D. 1979. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley.
70. Hovy, E., King, M., and Popescu-Belis, A. 2002. Principles of context-based machine translation evaluation. Mach. Transl. 17, 1, 43--75.
71. Huang, L. and Chiang, D. 2005. Better k-best parsing. In Proceedings of the International Workshop on Pausing Technologies (IWPT). 53--64.
72. Huang, L. and Chiang, D. 2007. Forest rescoring: Faster decoding with integrated language models. In Proceedings of the Association for Computational Linguistics (ACL). 144--151.
73. Hutchins, J. 2007. Machine translation: A concise history. In Computer Aided Translation: Theory and Practice, C. S. Wai, Ed. Chinese University of Hong Kong.
74. Hwa, R., Resnik, P., Weinberg, A., Cabezas, C., and Kolak, O. 2005. Bootstrapping parsers via syntactic projection across parallel texts. Natural Lang. Engin. 11, 3, 311--325.
75. Ittycheriah, A. and Roukos, S. 2005. A maximum entropy word aligner for Arabic-English machine translation. In Proceedings of HLT-EMNLP. 89--96.
76. Jelinek, F. 1969. A stack algorithm for faster sequential decoding of transmitted information. Tech. rep. RC2441, IBM Research Center, Yorktown Heights, NY.
77. Jelinek, F. 1998. Statistical Methods for Speech Recognition. MIT Press, Cambridge, MA.
78. Johnson, H., Martin, J., Foster, G., and Kuhn, R. 2007. Improving translation quality by discarding most of the phrasetable. In Proceedings of EMNLP-CoNLL. 967--975.
79. Joshi, A. K. and Schabes, Y. 1997. Tree-adjoining grammars. In Handbook of Formal Languages, G. Rozenberg and A. Salomaa, Eds. Vol. 3. Springer, Berlin, Germany, 69--124.
80. Joshi, A. K., Vijay-Shanker, K., and Weir, D. 1991. The convergence of mildly context-sensitive grammar formalisms. In Foundational Issues in Natural Language Processing, P. Sells, S. Shieber, and T. Wasow, Eds. MIT Press, Cambridge, MA, Chapter 2, 31--81.
81. Jurafsky, D. and Martin, J. H. 2008. Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition, 2nd Ed. Prentice-Hall.
82. Kirchhoff, K. and Yang, M. 2005. Improved language modeling for statistical machine translation. In Proceedings of ACL Workshop on Building and Using Parallel Texts. 125--128.
83. Knight, K. 1997. Automating knowledge acquisition for machine translation. AI Mag. 18, 4, 81--96.
84. Knight, K. 1999a. Decoding complexity in word-replacement translation models. Comput. Linguist. 25, 4, 607--615.
85. Knight, K. 1999b. A statistical MT tutorial workbook. Unpublished. http://www.cisp.jhu.edu/ws99/projects/mt/wkbk.rtf.
86. Knight, K. and Al-Onaizan, Y. 1998. Translation with finite-state devices. In Proceedings of the Conference of the Association for Machine Translation in the Americas (AMTA). 421--437.
87. Knight, K. and Graehl, J. 2005. An overview of probabilistic tree transducers for natural language processing. In Proceedings of CICLing.
88. Knight, K. and Marcu, D. 2005. Machine translation in the year 2004. In Proceedings of ICASSP.
89. Koehn, P. 2004a. Pharaoh: A beam search decoder for phrase-based statistical machine translation models. In Proceedings of the Conference of the Association for Machine Translation in the Americas (AMTA).
90. Koehn, P. 2004b. PHARAOH, A Beam Search Decoder for Phrase-Based Statistical Machine Translation Models, User Manual and Description for Version 1.2 USC Information Sciences Institute.
91. Koehn, P. 2004c. Statistical significance tests for machine translation evaluation. In Proceedings of EMNLP. 388--395.
92. Koehn, P. 2005. Europarl: A parallel corpus for statistical machine translation. In Proceedings of MT Summit.
93. Koehn, P. 2008. Statistical Machine Translation. Cambridge University Press. To appear.
94. Koehn, P. and Hoang, H. 2007. Factored translation models. In Proceedings of EMNLP-CoNLL. 868--876.
95. Koehn, P., Hoang, H., Birch, A., Callison-Burch, C., Federico, M., Bertoldi, N., Cowan, B., Shen, W., Moran, C., Zens, R., Dyer, C., Bojar, O., Constantin, A., and Herbst, E. 2007. Moses: Open source toolkit for statistical machine translation. In Proceedings of ACL Demo and Poster Sessions. 177--180.
96. Koehn, P. and Monz, C. 2005. Shared task: Statistical machine translation between european languages. In Proceedings of ACL Workshop on Building and Using Parallel Texts. 119--124.
97. Koehn, P. and Monz, C. 2006. Manual and automatic evaluation of machine translation between european languages. In Proceedings of NAACL Workshop on Statistical Machine Translation. 102--121.
98. Koehn, P., Och, F. J., and Marcu, D. 2003. Statistical phrase-based translation. In Proceedings of HLT-NAACL. 127--133.
99. Kulesza, A. and Shieber, S. M. 2004. A learning approach to improving sentence-level MT evaluation. In Proceedings of the International Conference on Theoretical and Methodological Issues in Machine Translation (TMI).
100. Kumar, S. and Byrne, W. 2004. Minimum bayes-risk decoding for statistical machine translation. In Proceedings of HLT-NAACL. 169--176.
101. Kumar, S., Deng, Y., and Byrne, W. 2006. A weighted finite state transducer translation template model for statistical machine translation. Natural Lang. Engin. 12, 1, 35--75.
102. Lari, K. and Young, S. J. 1990. The estimation of stochastic context-free grammars using the inside-outside algorithm. Comput. Speech Lang. 4, 1.
103. Lewis, P. M. I. and Stearns, R. E. 1968. Syntax-directed transductions. J. ACM 15, 465--488.
104. Liang, P., Bouchard-Côté, A., Taskar, B., and Klein, D. 2006. An end-to-end discriminative approach to machine translation. In Proceedings of ACL-COLING. 761--768.
105. Liang, P., Taskar, B., and Klein, D. 2006. Alignment by agreement. In Proceedings of HLT-NAACL. 104--111.
106. Lin, C.-Y. and Och, F. J. 2004. Automatic evaluation of machine translation quality using longest common subsequence and skip-bigram statistics. In Proceedings of the Association for Computational Linguistics (ACL). 606--613.
107. Lita, L., Rogati, M., and Lavie, A. 2005. BLANC: Learning evaluation metrics for MT. In Proceedings of HLT-EMNLP. 740--747.
108. Liu, D. and Gildea, D. 2007. Source-language features and maximum correlation training for machine translation evaluation. In Proceedings of HLT-NAACL. 41--48.
109. Lopez, A. 2007. Hierarchical phrase-based translation with suffix arrays. In Proceedings of EMNLP-CoNLL. 976--985.
110. Lopez, A. and Resnik, P. 2005. Improved HMM alignment models for languages with scarce resources. In Proceedings of ACL Workshop on Building and Using Parallel Texts. 83--86.
111. Lopez, A. and Resnik, P. 2006. Word-based alignment, phrase-based translation: What's the link? In Proceedings of the Conference of the Association for Machine Translation in the Americas (AMTA). 90--99.
112. Manning, C. D. and Schütze, H. 1999. Foundations of Statistical Natural Language Processing. MIT Press, Cambridge, MA.
113. Marcu, D., Wang, W., Echihabi, A., and Knight, K. 2006. SPMT: Statistical machine translation with syntactified target language phrases. In Proceedings of EMNLP. 44--52.
114. Marcu, D. and Wong, W. 2002. A phrase-based, joint probability model for statistical machine translation. In Proceedings of EMNLP. 133--139.
115. Marcus, M. P., Marcinkiewicz, M. A., and Santorini, B. 1993. Building a large annotated corpus of English: The Penn Treebank. Comput. Linguist. 19, 2, 314--330.
116. Matusov, E., Zens, R., and Ney, H. 2004. Symmetric word alignments for statistical machine translation. In Proceedings of COLING. 219--225.
117. Melamed, I. D. 1996. Automatic construction of clean broad-coverage translation lexicons. In Proceedings of the Conference of the Association for Machine Translation in the Americas (AMTA).
118. Melamed, I. D. 1998. Manual annotation of translational equivalence: The blinker project. Tech. rep. 98-07, University of Pennsylvania Institute for Research in Cognitive Science.
119. Melamed, I. D. 2000. Models of translational equivalence among words. Comput. Linguist. 26, 2, 221--249.
120. Melamed, I. D. 2003. Multitext grammars and synchronous parsers. In Proceedings of HLT-NAACL. 79--86.
121. Melamed, I. D. 2004a. Algorithms for syntax-aware statistical machine translation. In Proceedings of Theoretical and Methodological Issues in Machine Translation (TMI).
122. Melamed, I. D. 2004b. Statistical machine translation by parsing. In Proceedings of the Association for Computational Linguistics (ACL). 654--661.
123. Melamed, I. D., Green, R., and Turian, J. P. 2003. Precision and recall of machine translation. In Proceedings of HLT-NAACL (Companion Vol.). 61--63.
124. Melamed, I. D., Satta, G., and Wellington, B. 2004. Generalized multitext grammars. In Proceedings of the Association for Computational Linguistics (ACL). 662--669.
125. Merialdo, B. 1994. Tagging English text with a probabilistic model. Comput. Linguist. 20, 2, 155--172.
126. Mihalcea, R. and Pedersen, T. 2003. An evaluation exercise for word alignment. In Proceedings of HLT-NAACL Workshop on Building and Using Parallel Texts. 1--10.
127. Minkov, E., Toutanova, K., and Suzuki, H. 2007. Generating complex morphology for machine translation. In Proceedings of the Association for Computational Linguistics (ACL). 128--135.
128. Mitchell, T. M. 1997. Machine Learning. McGraw-Hill.
129. Moore, R. C. 2004. Improving IBM word-alignment model 1. In Proceedings of the Association for Computational Linguistics (ACL). 519--526.
130. Moore, R. C. 2005a. Association-based bilingual word alignment. In Proceedings of ACL Workshop on Building and Using Parallel Texts. 1--8.
131. Moore, R. C. 2005b. A discriminative framework for bilingual word alignment. In Proceedings of HLT-EMNLP. 81--88.
132. Nießen, S. and Ney, H. 2004. Statistical machine translation with scarce resources using morpho-syntactic information. Comput. Linguist. 30, 2, 182--204.
133. Nießen, S., Vogel, S., Ney, H., and Tillman, C. 1998. A DP based search algorithm for statistical machine translation. In Proceedings of ACL-COLING. 960--967.
134. Oard, D. W., Doermann, D., Dorr, B., He, D., Resnik, P., Weinberg, A., Byrne, W., Khudanpur, S., Yarowsky, D., Leuski, A., Koehn, P., and Knight, K. 2003. Desperately seeking Cebuano. In Proceedings of HLT-NAACL (Companion Vol.). 76--78.
135. Oard, D. W. and Och, F. J. 2003. Rapid-response machine translation for unexpected languages. In Proceedings of MT Summit IX.
136. Och, F. J. 1999. An efficient method for determining bilingual word classes. In Proceedings of the European Chapter of the Association for Computational Linguistics (EACL). 71--76.
137. Och, F. J. 2003. Minimum error rate training in statistical machine translation. In Proceedings of the Association for Computational Linguistics (ACL).
138. Och, F. J. 2005. Statistical machine translation: The fabulous present and future. In Proceedings of ACL Workshop on Building and Using Parallel Texts. Invited talk.
139. Och, F. J., Gildea, D., Khudanpur, S., Sarkar, A., Yamada, K., Fraser, A., Kumar, S., Shen, L., Smith, D., Eng, K., Jain, V., Jin, Z., and Radev, D. 2004a. Final report of Johns Hopkins 2003 summer workshop on syntax for statistical machine translation. Tech. rep., Johns Hopkins University.
140. Och, F. J., Gildea, D., Khudanpur, S., Sarkar, A., Yamada, K., Fraser, A., Kumar, S., Shen, L., Smith, D., Eng, K., Jain, V., Jin, Z., and Radev, D. 2004b. A smorgasbord of features for statistical machine translation. In Proceedings of HLT-NAACL. 161--168.
141. Och, F. J. and Ney, H. 2000. A comparison of alignment models for statistical machine translation. In Proceedings of COLING. 1086--1090.
142. Och, F. J. and Ney, H. 2001. Statistical multi-source translation. In Proceedings of MT Summit.
143. Och, F. J. and Ney, H. 2002. Discriminative training and maximum entropy models for machine translation. In Proceedings of the Association for Computational Linguistics (ACL). 156--163.
144. Och, F. J. and Ney, H. 2003. A systematic comparison of various statistical alignment models. Comput. Linguist. 29, 1, 19--51.
145. Och, F. J. and Ney, H. 2004. The alignment template approach to machine translation. Comput. Linguist. 30, 4, 417--449.
146. Och, F. J., Tillman, C., and Ney, H. 1999. Improved alignment models for statistical machine translation. In Proceedings of EMNLP-VLC. 20--28.
147. Och, F. J., Ueffing, N., and Ney, H. 2001. An efficient A* search algorithm for statistical machine translation. In Proceedings of ACL Workshop on Data-Driven Methods in Machine Translation. 55--62.
148. Olteanu, M., Davis, C., Volosen, I., and Moldovan, D. 2006. Phramer—an open source statistical phrase-based translator. In Proceedings of HLT-NAACL Workshop on Statistical Machine Translation. 146--149.
149. Papineni, K., Roukos, S., Ward, T., and Zhu, W.-J. 2002. BLEU: a method for automatic evaluation of machine translation. In Proceedings of the Association for Computational Linguistics (ACL). 311--318.
150. Popovic, M., de Gispert, A., Gupta, D., Lambert, P., Ney, H., Mariño, J. B., Federico, M., and Banchs, R. 2006. Morpho-syntactic information for automatic error analysis of statistical machine translation output. In Proceedings of NAACL Workshop on Statistical Machine Translation. 1--6.
151. Quirk, C., Menezes, A., and Cherry, C. 2005. Dependency treelet translation: Syntactically informed phrasal SMT. In Proceedings of the Association for Computational Linguistics (ACL). 271--279.
152. Ratnaparkhi, A. 1998. Maximum entropy models for natural language ambiguity resolution. Ph.D. thesis, University of Pennsylvania.
153. Resnik, P., Olsen, M. B., and Diab, M. 1997. Creating a parallel corpus from the Book of 2000 Tongues. In Proceedings of the Text Encoding Initiative 10th Anniversary User Conference (TEI-10).
154. Resnik, P. and Smith, N. A. 2003. The Web as parallel corpus. Comput. Linguist. 29, 3, 349--380.
155. Russell, S. and Norvig, P. 2003. Artificial Intelligence: A Modern Approach 2nd Ed. Prentice-Hall.
156. Schafer, C. and Drabek, E. F. 2005. Models for inuktitut-english word alignment. In Proceedings of ACL Workshop on Building and Using Parallel Texts. 79--82.
157. Shen, L., Sarkar, A., and Och, F. J. 2004. Discriminative reranking for machine translation. In Proceedings of HLT-NAACL. 177--184.
158. Shieber, S. M. and Schabes, Y. 1990. Synchronous tree-adjoining grammars. In Proceedings of COLING. 253--258.
159. Simard, M., Cancedda, N., Cavestro, B., Dymetman, M., Gaussier, E., Goutte, C., Yamada, K., Langlais, P., and Mauser, A. 2005. Translating with non-contiguous phrases. In Proceedings of HLT-EMNLP. 755--762.
160. Sipser, M. 2005. Introduction to the Theory of Computation 2nd Ed. PWS Publishing.
161. Smith, D. A. and Smith, N. 2004. Bilingual parsing with factored estimation: Using English to parse Korean. In Proceedings of EMNLP. 49--56.
162. Smith, N. A. 2002. From words to corpora: Recognizing translation. In Proceedings of EMNLP. 95--102.
163. Smith, N. A. 2006. Novel estimation methods for unsupervised discovery of latent structure in natural language text. Ph.D. thesis, Johns Hopkins University.
164. Snover, M., Dorr, B., Schwartz, R., Micciulla, L., and Makhoul, J. 2006. A study of translation edit rate with targeted human annotation. In Proceedings of the Conference of the Association for Machine Translation in the Americas (AMTA). 223--231.
165. Talbot, D. and Osborne, M. 2007a. Randomised language modelling for statistical machine translation. In Proceedings of the Association for Computational Linguistics (ACL). 512--519.
166. Talbot, D. and Osborne, M. 2007b. Smoothed bloom filter language models: Tera-scale LMs on the cheap. In Proceedings of the Association for Computational Linguistics (ACL). 468--476.
167. Taskar, B. 2004. Learning structured prediction models: A large-margin approach. Ph.D. thesis, Stanford University.
168. Taskar, B., Lacoste-Julien, S., and Klein, D. 2005. A discriminative matching approach to word alignment. In Proceedings of HLT-EMNLP. 73--80.
169. Tillman, C. and Ney, H. 2003. Word reordering and a dynamic programming beam search algorithm for statistical machine translation. Comput. Linguist. 29, 1, 98--133.
170. Tillmann, C., Vogel, S., Ney, H., and Zubiaga, A. 1997. A DP-based search using monotone alignments in statistical translation. In Proceedings of ACL-EACL. 289--296.
171. Tillmann, C. and Zhang, T. 2006. A discriminative global training algorithm for statistical MT. In Proceedings of ACL-COLING. 721--728.
172. Toutanova, K., Ilhan, H. T., and Manning, C. D. 2002. Extensions to HMM-based statistical word alignment models. In Proceedings of EMNLP. 87--94.
173. Turian, J. P., Shen, L., and Melamed, I. D. 2003. Evaluation of machine translation and its evaluation. In Proceedings of MT Summit IX.
174. Ueffing, N., Haffari, G., and Sarkar, A. 2007. Transductive learning for statistical machine translation. In Proceedings of the Association for Computational Linguisties (ACL). 25--32.
175. Ueffing, N. and Ney, H. 2005. Word-level confidence estimation for machine translation using phrase-based translation models. In Proceedings of HLT-EMNLP. 763--770.
176. Ueffing, N., Och, F. J., and Ney, H. 2002. Generation of word graphs in statistical machine translation. In Proceedings of EMNLP. 156--163.
177. Venugopal, A., Zollmann, A., and Vogel, S. 2007. An efficient two-pass approach to synchronous-CFG driven statistical MT. In Proceedings of HLT-NAACL.
178. Venugopal, A., Zollmann, A., and Waibel, A. 2005. Training and evaluating error minimization rules for statistical machine translation. In Proceedings of ACL Workshop on Building and Using Parallel Texts. 208--215.
179. Vijay-Shanker, K., Weir, D., and Joshi, A. K. 1987. Characterizing structural descriptions produced by various grammatical formalisms. In Proceedings of the Association for Computational Linguisties (ACL). 104--111.
180. Viterbi, A. J. 1967. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Trans. Inform. Theory 13, 2, 260--269.
181. Vogel, S., Ney, H., and Tillman, C. 1996. HMM-based word alignment in statistical machine translation. In Proceedings of COLING. 836--841.
182. Wang, C., Collins, M., and Koehn, P. 2007. Chinese syntactic reordering for statistical machine translation. In Proceedings of EMNLP-CoNLL. 737--745.
183. Wang, J. 2005. Matching meaning for cross-language information retrieval. Ph.D. thesis, University of Maryland.
184. Wang, Y.-Y. and Waibel, A. 1997. Decoding algorithm in statistical machine translation. In Proceedings of ACL-EACL. 366--372.
185. Watanabe, T. and Sumita, E. 2002. Bidirectional decoding for statistical machine translation. In Proceedings of COLING. 1079--1085.
186. Watanabe, T., Suzuki, J., Tsukada, H., and Isozaki, H. 2007. Online large-margin training for statistical machine translation. In Proceedings of EMNLP-CoNLL. 764--773.
187. Weaver, W. 1955. Translation. In Machine Translation of Languages: Fourteen Essays, W. N. Locke and A. D. Booth, Eds. MIT Press, Chapter 1, 15--23.
188. Wellington, B., Turian, J., Pike, C., and Melamed, I. D. 2006. Scalable purely-discriminative training for word and tree transducers. In Proceedings of the Conference of the Association for Machine Translation in the Americas (AMTA). 251--260.
189. Wellington, B., Waxmonsky, S., and Melamed, I. D. 2006. Empirical lower bounds on the complexity of translational equivalence. In Proceedings of ACL-COLING. 977--984.
190. White, J. S., O'Cornell, T., and O'Nava, F. 1994. The ARPA MT evaluation methodologies: Evolution, lessons and future approaches. In Proceedings of the Association for Machine Translation in the Americas.
191. Wu, D. 1995a. Grammarless extraction of phrasal translation examples from parallel texts. In Proceedings of the Theoretical and Methodological Issues in Machine Translation (TMI). 354--372.
192. Wu, D. 1995b. Stochastic inversion transduction grammars, with application to segmentation, bracketing, and alignment of parallel corpora. In Proceedings of IJCAI. 1328--1335.
193. Wu, D. 1996. A polynomial-time algorithm for statistical machine translation. In Proceedings of the Association for Computational Linguisties (ACL). 152--158.
194. Wu, D. and Wong, H. 1998. Machine translation with a stochastic grammatical channel. In Proceedings of ACL-COLING. 1408--1415.
195. Xiong, D., Liu, Q., and Lin, S. 2006. Maximum entropy based phrase reordering model for statistical machine translation. In Proceedings of ACL-COLING. 521--528.
196. Yamada, K. and Knight, K. 2001. A syntax-based statistical translation model. In Proceedings of ACL-EACL.
197. Yamada, K. and Knight, K. 2002. A decoder for syntax-based statistical MT. In Proceedings of the Association for Computational Linguisties (ACL). 303--310.
198. Yarowsky, D. and Ngai, G. 2001. Inducing multilingual POS taggers and NP bracketers via robust projection across aligned corpora. In Proceedings of NAACL. 200--207.
199. Yarowsky, D., Ngai, G., and Wicentowski, R. 2001. Inducing mulilingual text analysis tools via robust projection across aligned corpora. In Proceedings of the Human Language Technology Conference (HLT). 109--116.
200. Zens, R. and Ney, H. 2003. A comparative study on reordering constraints in statistical machine translation. In Proceedings of the Association for Computational Linguisties (ACL). 144--151.
201. Zens, R. and Ney, H. 2004. Improvements in phrase-based statistical machine translation. In Proceedings of HLT-NAACL. 257--264.
202. Zens, R. and Ney, H. 2007. Efficient phrase-table representation for machine translation with applications to online MT and speech translation. In Proceedings of HLT-NAACL.
203. Zhang, H. and Gildea, D. 2005. Stochastic lexicalized inversion transduction grammar for alignment. In Proceedings of the Association for Computational Linguisties (ACL). 475--482.
204. Zhang, H., Huang, L., Gildea, D., and Knight, K. 2006. Synchronous binarization for machine translation. In Proceedings of HLT-NAACL. 256--263.
205. Zhang, Y., Hildebrand, A. S., and Vogel, S. 2006. Distributed language modeling for N-best list re-ranking. In Proceedings of EMNLP. 216--223.
206. Zhang, Y. and Vogel, S. 2005. An efficient phrase-to-phrase alignment model for arbitrarily long phrase and large corpora. In Proceedings of EAMT.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Natural language processing

      • Machine translation

  • Machine learning

    • Learning paradigms

    • Machine learning approaches

      • Markov decision processes

• Mathematics of computing

  • Probability and statistics

• Theory of computation

  • Theory and algorithms for application domains

    • Machine learning theory

      • Markov decision processes