Abstract
This paper introduces a novel phrase-based machine translation (MT) system that breaks the traditional "continuity" constraint, allowing for translation units with gaps—discontinuous phrases—in both source and target languages. By moving away from the rigid tree-based structures of hierarchical models while retaining the flexibility of gaps, the authors' system outperforms state-of-the-art hierarchical systems like Hiero and Joshua by over 1.0 BLEU point. Crucially, this performance gain is achieved while maintaining the linear decoding complexity of standard phrase-based systems.
Introduction: The Problem of Discontinuity
Standard phrase-based MT systems, such as the widely used Moses toolkit, rely on the extraction and translation of "continuous" phrases—sequences of words that appear contiguously in the text. However, natural language is inherently messy and frequently employs discontinuous dependencies. Common examples include the French negation "ne ... pas," German separable verbs, or English phrasal verbs like "set ... up."
When a translation system is restricted to continuous blocks, it is often forced to break these logical dependencies apart. This leads to "data sparsity," where the system fails to recognize the relationship between separated words, resulting in poor translation quality. To address this, researchers previously turned to hierarchical systems (like Hiero), which use Synchronous Context-Free Grammars (SCFG) to handle gaps using non-terminal symbols (e.g., $X$). However, these systems impose "hard" hierarchical constraints that can be overly restrictive and computationally expensive, typically requiring cubic time complexity ($O(n^3)$) for decoding.
Methodology: Decoding Beyond the Tree
The authors propose extending the standard multi-beam string-based decoder to handle discontinuous phrases in a non-hierarchical manner. This approach aims to capture the benefits of gaps without the overhead of a hierarchical tree structure.
1. Efficient Extraction
The system utilizes suffix arrays to efficiently identify all discontinuous phrases in the training data that match the input sentence. This allows the model to consider a much wider array of potential translation units than standard phrase-based models.
2. The Discontinuous Decoder
Unlike Moses, which tracks a simple translation prefix, this decoder's state includes a set of isolated subphrases. If a translation rule contains a gap (e.g., "A ... B"), the decoder can place "A," store "B" in a buffer, and then "fill in" the gap with other phrases before finally appending "B" later in the sequence. This allows for a flexible, non-linear construction of the target sentence.
3. Linear Distortion and New Features
The authors redefined the calculation of "jump" costs (distortion). Instead of treating a discontinuous phrase as a single block, they treat it as a sequence of subphrases and calculate the distance between each successive element. Additionally, they introduced features to penalize target-side gaps and count specific complex alignment configurations, such as "cross-serial" alignments, which hierarchical systems are mathematically incapable of representing.
Challenging the Hierarchical Paradigm
A central insight of this work is that the tree-based nature of systems like Hiero is not necessarily what drives their performance; rather, it is the ability to handle discontinuities. By removing tree constraints, the authors' system can handle complex reorderings—such as "inside-out" alignments—that hierarchical models cannot physically produce.
As shown in the comparison above, the proposed system extracts more granular and flexible rules. While Hiero requires a non-terminal placeholder ($X$) to bridge gaps, this work allows for direct mapping of discontinuous segments (e.g., ne ... plus to not ... anymore), providing better context for the decoder.
Evaluation and Key Results
The system was evaluated on Chinese-to-English translation tasks using approximately 28 million words of training data and a massive 5-gram language model. The proposed system, integrated into the Phrasal toolkit, showed significant gains across the NIST MT03–MT08 evaluation sets:
- Vs. Moses (Phrase-based): Improved by 0.77 BLEU and 1.53 TER points on average.
- Vs. Joshua (Hierarchical): Outperformed the state-of-the-art hierarchical system by 1.03 BLEU points on average across five test sets.
- Efficiency: By using a distortion limit, the system maintains the linear time complexity of phrase-based decoding, avoiding the cubic scaling issues of SCFG-based models.
Insights and Future Directions
The authors found that supporting gaps in the source language provides a more significant boost than gaps in the target language. This is likely because identifying a gap in the input is a matching problem, whereas generating a gap in the output is a more complex search problem. Furthermore, the use of discontinuous phrases increased the average words per phrase from 1.73 to 2.16, reducing the system's reliance on weak, single-word translations by 43%.
Future work will focus on adding syntactic features to encourage gaps that align with grammatical structures and updating lexicalized reordering models to be fully "gap-aware."
Summary updated