Abstract
Most statistical machine translation (SMT) systems generate target sentences from left to right. However, for language pairs with significant structural differences, such as English and Japanese, this unidirectional approach can be suboptimal. This paper investigates the impact of decoding direction on translation quality. We propose a bidirectional decoding method that merges partial translations generated from both ends of a sentence. Our experiments on a travel conversation corpus demonstrate that right-to-left decoding significantly improves English-to-Japanese translation, while the bidirectional approach achieves the best performance for Japanese-to-English translation.
Introduction
In the early 2000s, the standard for Statistical Machine Translation (SMT) was "stack decoding" or beam search, which typically proceeded from left to right (LtoR). This design assumes that the most critical structural information appears early in the sentence—a characteristic of "prefix" languages like English.
However, for "postfix" languages such as Japanese, which follows a Subject-Object-Verb (SOV) structure, the verb and essential grammatical markers often appear at the end. Translating into such languages LtoR forces the decoder to make early decisions without the structural "anchor" of the verb. Figure 1 illustrates the complex word alignments between English and Japanese, highlighting how structural elements are often reordered and why the generation order matters.
Methods
The researchers implemented and compared three decoding strategies based on the IBM Model 4 translation framework:
- Left-to-Right (LtoR): The standard approach that appends new words to the end of a partial hypothesis.
- Right-to-Left (RtoL): The inverse approach that starts at the end of the sentence and "prepends" words, moving toward the beginning. This is designed to capture the "postfix" nature of Japanese.
- Bidirectional (Bi): This novel approach runs both LtoR and RtoL searches simultaneously until they have each processed half of the input string. It then attempts to merge these partial hypotheses into a complete sentence.
To facilitate bidirectional decoding, the researchers adapted the beam search to handle "open" and "closed" hypotheses, tracking whether a partial translation is ready to be extended. Merging requires stitching together compatible partial translations, as shown in Figure 6.
The authors utilized a large-scale travel conversation corpus consisting of 172,481 bilingual sentence pairs (English and Japanese) for training and evaluation.
Key Results and Discussion
The performance was evaluated using Word Error Rate (WER) and human subjective evaluation (SE).
Japanese-to-English (J-E)
The Bidirectional method performed best, achieving a WER of 69.9 (compared to 70.0 for LtoR and 74.6 for RtoL). Human evaluators also gave it the highest "Perfect" (A-rank) scores at 27.3%. While RtoL was expected to help, it suffered from a high rate of search errors (59.3%) due to a mismatch with the standard left-to-right Language Model (LM).
English-to-Japanese (E-J)
For translation into Japanese, the Right-to-Left method was the clear winner with a WER of 64.0, significantly beating the standard LtoR approach (66.2). This confirms that the "postfix" nature of Japanese is better served by a decoding direction that prioritizes the end of the sentence.
The Language Model Bottleneck
A major hurdle for RtoL decoding is the Language Model (LM). Standard trigram LMs are trained to predict the next word based on left history. When decoding RtoL, the "history" is actually the future of the sentence, leading to poor local probability estimates. Despite these search errors, the RtoL direction was still linguistically superior for Japanese output.
Conclusion
This research proves that the "best" decoding direction depends entirely on the target language's structure. English (prefix-heavy) favors LtoR, while Japanese (postfix-heavy) favors RtoL. Bidirectional decoding acts as a "best of both worlds" strategy by anchoring the sentence at both ends. Future work suggests that using a language model that matches the generation direction—or a truly bidirectional LM—would likely yield even better results.
Summary updated