Word-reordering for Statistical Machine Translation Using Trigram Language Model

Proceedings of the 5th International Joint Conference on Natural Language Processing, pages 1288–1293, Chiang Mai, Thailand, November 8 – 13, 2011. c⃝2011 AFNLP Word-reordering for Statistical Machine Translation Using Trigram Language Model Jing He IIIS, Tsinghua University Beijing, China hejing2929@gmail.com Hongyu Liang IIIS, Tsinghua University Beijing, China sjqxzlhy@gmail.com Abstract In this paper we study the word-reordering problem in the decoding part of statisti- cal machine translation, but independently from the target language generating pro- cess. In this model, a permuted sentence is given and the goal is to recover the correct order. We introduce a greedy algorithm called Local-(k, l)-Step, and show that it performs better than the DP-based algo- rithm. Our word-reordering algorithm can be used in the statistical machine transla- tion process for improving the quality of the translation. Furthermore, motivated by the rank evaluation method, we introduce a novel way for evaluating the results of word-reordering by calculating the inver- sion pair cardinality. 1 Introduction Statistical machine translation is a machine trans- lation method based on statistical models, which is in contrast with rule-based machine translation as well as with example-based machine transla- tion. The most commonly used model in statistical machine translation is the source-channel model built by Brown et. al. (1993). In their pro- posal of translation between English and French, English strings are generated according to some stochastic process and then transformed stochas- tically into French strings. Therefore, to trans- late French to English, it is needed to search for an English source string that is most likely ac- cording to the English language model (Ponte and Croft, 1998) and the channel model. This process of translation is called decoding. Usually, a de- coding process in statistical machine translation is combined with two sub-processes (Chang and Toutanova, 2007; Koehn, Och and Marcu, 2003): generating the words or phrases of the target lan- guage, and deciding the correct order of the words or phrases to get a desired target language sen- tence. For some language pairs, such as English and Chinese, the word-reordering problem is re- ally hard to solve, as the target word order differs a lot from the source word order and little informa- tion about the target word order is obtainable from the source sentence. This is because the grammars of English and Chinese differ from one another significantly. Language model has been successfully applied in the word-reordering process of statistical ma- chine translation. Generally speaking, a language model assigns a probability to a sequence of words according to some probability distribution. sentence then gets a score under the languageA model by means of standard conditional proba- bility. Knight (1999) studied this abstract prob- lem and proved that the word-reordering (also called word-replacement) problem under bigram language model is NP-hard. In this article, we study the word-reordering problem under trigram language model in the de- coding part of statistical machine translation, but independently from the target language generat- ing process. More precisely, suppose we want to translate a sentence from one language …

Content truncated to 500 words