Accurate Non-Hierarchical Phrase-Based Translation

Michel Galley, Christopher D. Manning

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.

Alignment of a French sentence with discontinuous negation and verb structures.

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.

Comparison of translation rules extracted by Hiero versus the proposed non-hierarchical system.

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

Abstract

A principal weakness of conventional (i.e., non-hierarchical) phrase-based statistical machine translation is that it can only exploit continuous phrases. In this paper, we extend phrase-based decoding to allow both source and target phrasal discontinuities, which provide better generalization on unseen data and yield significant improvements to a standard phrase-based system (Moses). More interestingly, our discontinuous phrase-based system also outperforms a state-of-the-art hierarchical system (Joshua) by a very significant margin (+1.03 BLEU on average on five Chinese-English NIST test sets), even though both Joshua and our system support discontinuous phrases. Since the key difference between these two systems is that ours is not hierarchical---i.e., our system uses a string-based decoder instead of CKY, and it imposes no hard hierarchical reordering constraints during training and decoding---this paper sets out to challenge the commonly held belief that the tree-based parameterization of systems such as Hiero and Joshua is crucial to their good performance against Moses.
BibTeX
@inproceedings{galley2010accurate,
  author = {Michel Galley and Christopher D. Manning},
  title = {{Accurate Non-Hierarchical Phrase-Based Translation}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2010},
}
Figure