Incremental Decoding for Phrase-Based Statistical Machine Translation

Proceedings of the Joint 5th Workshop on Statistical Machine Translation and MetricsMATR, pages 216–223, Uppsala, Sweden, 15-16 July 2010. c⃝2010 Association for Computational Linguistics Incremental Decoding for Phrase-based Statistical Machine Translation Baskaran Sankaran, Ajeet Grewal and Anoop Sarkar School of Computing Science Simon Fraser University 8888 University Drive Burnaby BC. V5A 2Y1. Canada {baskaran, asg10, anoop}@cs.sfu.ca Abstract In this paper we focus on the incremental decoding for a statistical phrase-based ma- chine translation system. In incremental decoding, translations are generated incre- mentally for every word typed by a user, instead of waiting for the entire sentence as input. We introduce a novel modifi- cation to the beam-search decoding algo- rithm for phrase-based MT to address this issue, aimed at efficient computation of fu- ture costs and avoiding search errors. Our objective is to do a faster translation dur- ing incremental decoding without signifi- cant reduction in the translation quality. 1 Introduction Statistical Machine Translation has matured sig- nificantly in the past decade and half, resulting in the proliferation of several web-based and com- mercial translation services. Most of these ser- vices work on sentence or document level, where a user enters a sentence or chooses a document for translation, which are then translated by the servers. Translation in such typical scenarios is still offline in the sense that the user input and translation happen sequentially without any inter- action between the two phases. In this paper we study decoding for SMT with the constraint that translations are to be gener- ated incrementally for every word typed in by the user. Such a translation service can be used for language learning, where the user is fluent in the target language and experiments with many differ- ent source language sentences interactively, or in real-time translation environments such as speech- speech translation or translation during interactive chats. We use a phrase-based decoder similar to Moses (Koehn et al., 2007) and propose novel modifications in the decoding algorithm to tackle incremental decoding. Our system maintains a partial decoder state at every stage and uses it while decoding for each newly added word. As the decoder has access only to the partial sentence at every stage, the future costs change with ev- ery additional word and this has to be taken into account while continuing from an existing partial decoder state. Another major issue is that as incre- mental decoding is provided new input one word at at time, some of the entries that were pruned out at an earlier decoder state might later turn out to better candidates resulting in search errors com- pared to decoding the entire sentence at once. It is to be noted that, the search error problem is re- lated to the inability to compute full future cost in incremental decoding. Our proposed modifica- tions address these twin challenges and allow for efficient incremental decoding. 2 Incremental Decoding 2.1 Beam Search for Phrase-based SMT In this section we review the usual beam search de- coder for phrase-based MT because we …

Content truncated to 500 words