Source-Side Left-to-Right or Target-Side Left-to-Right? An Empirical Comparison of Two Phrase-Based Decoding Algorithms

Yin-Wen Chang, Michael CollinsEMNLP 2017 · OpenReview

Abstract

Traditionally, phrase-based machine translation (PBMT) decoders process the target sentence from left to right, necessitating complex "future cost" estimations for non-contiguous source phrases. This paper evaluates an alternative approach: decoding the source sentence strictly from left to right. We demonstrate that this source-side approach achieves translation quality and speed comparable to state-of-the-art target-side decoders like Moses, while significantly simplifying the decoding process and offering linear complexity.

Introduction

In Statistical Machine Translation (SMT), the "decoder" is the engine that determines how to transform a source sentence into a target sentence. For decades, the standard approach—exemplified by the Moses system—has been target-side left-to-right decoding. Because word orders differ between languages, this method requires the decoder to "jump around" the source sentence to find the appropriate phrases. This jumping makes it difficult to estimate the "future cost"—the predicted difficulty of translating the remaining parts of the sentence.

This paper provides the first empirical evaluation of the algorithm proposed by Chang and Collins (2017), which flips the script by processing the source sentence strictly from left to right.

Methodology

The authors implemented the Chang and Collins algorithm with several key features:

  1. Strict Source Order: The algorithm translates the input sentence linearly (word 1, then word 2, etc.), never skipping ahead.
  2. Maintaining Segments: To handle reordering, the decoder maintains multiple "segments" or sub-strings of the target language. These are merged as the decoder progresses through the source text.
  3. Beam Search & Pruning: To maintain efficiency, the system uses beam search. A specific pruning method, Segment2, limits the decoder to maintaining a maximum of two active target-language segments at any given time.

Experimental Results

The researchers evaluated the algorithm across a wide variety of language pairs, including Europarl (English to/from various European languages), Newstest (Czech-to-English), and IWSLT’15 (Vietnamese-to-English).

Comparison of BLEU scores and decoding time across various language pairs for SegmentD, Segment2, and Moses.

As shown in the results, the source-side decoder achieved BLEU scores virtually identical to the Moses decoder. For instance, on German-to-English, both systems achieved a score of 26.69. However, the Segment2 approach was notably faster, completing the task in 5m 25s compared to Moses' 7m 37s.

Complexity and Efficiency

A major advantage of the source-side approach is that calculating the future score becomes trivial: it is simply the cost of translating the remaining suffix of the source sentence. Furthermore, the algorithm’s complexity is linear relative to the sentence length.

Scatter plot demonstrating that the number of operations scales linearly with sentence length.

Empirical data confirms that the number of operations scales beautifully in practice, avoiding the combinatorial explosion common in other translation algorithms. Analysis of optimal translations revealed that over 97% of sentences can be translated using three or fewer segments, justifying the efficiency of the Segment2 pruning strategy.

Conclusion and Future Work

While the industry has largely moved toward Neural Machine Translation (NMT), this study proves that source-side phrase-based decoding is a viable, efficient alternative to traditional methods. This approach is particularly well-suited for simultaneous translation, as it does not need to wait for the end of a source sentence to begin building target segments. Future research may explore integrating these monotonic processing ideas into modern attention-based neural models.

Summary updated

BibTeX
@inproceedings{chang2017source,
  author = {Yin-Wen Chang and Michael Collins},
  title = {{Source-Side Left-to-Right or Target-Side Left-to-Right? An Empirical Comparison of Two Phrase-Based Decoding Algorithms}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2017},
  url = {https://openreview.net/forum?id=rk-X8zzuZr},
}
Figure