A Direct Syntax-Driven Reordering Model for Phrase-Based Machine Translation

Niyu GeNAACL 2010

TL;DR

This paper introduces a novel direct syntax-driven reordering model for phrase-based machine translation that leverages syntactic parse trees to predict source word order. By directly modeling the source traversal order with rich syntactic features, this approach significantly improves translation quality, particularly for languages with substantial word order differences like Chinese and English.

What Problem Does This Paper Address?

Statistical Machine Translation (SMT) systems often struggle with reordering words from the source language to match the target language's natural word order. While earlier SMT models (like IBM Models 3-5) used limited surface word information, and phrase-based SMT (PB-SMT) implicitly handles local reorderings, neither effectively addresses long-distance reordering phenomena or captures the underlying structural reasons for these differences. Languages like Spanish and Arabic often place adjectives after nouns, while English places them before, necessitating complex reordering for fluent translation. Existing approaches often rely on limited context, lack structural information, or suffer from data sparsity due to their reliance on lexical features. This paper aims to bridge this gap by proposing a model that directly predicts the source traversal order using syntax, enabling arbitrary long-distance word movement.

Methods

The core of this paper is a Maximum Entropy (MaxEnt) reordering model. This model directly predicts the source sentence's "visit order" (the order in which source words are translated) for the target language. Instead of modeling the distance of word movement, it models the traversal order itself.

The key innovation lies in the syntax-driven features used to train the MaxEnt model. These features leverage the structure of a Chinese parse tree to understand how constituents should be reordered. The paper details several types of features:

  • Parse-based Syntax Features: These are the most prominent. They examine how parse nodes are reordered during translation. Examples include:
  • First Child Features: Determine which child of a parse node is visited first (e.g., translating the main verb before other elements under a VP).
  • Node Jump Features: Model how to jump from one sibling node to another.
  • Jump Over Sibling Features: Consider siblings that are jumped over to make more informed reordering decisions.
  • Back Jump Sibling Features: Handle backward jumps to cover skipped words.
  • Broken Features: Address cases where translation doesn't strictly follow constituent boundaries, allowing for "broken" nodes.
  • Non-Parse Features: These use less fine-grained information from the parse tree or surface words:
  • Barrier Features: Treat punctuation as "barrier words" that shouldn't move freely.
  • Number of Zero Islands Features: Discourage scattered jumps that leave large gaps of unvisited words.

The model is trained using word alignments and source-side parses. During decoding, the reordering model generates a reorder lattice which encodes various reordering possibilities and their costs (negative log probabilities). This lattice is then used by a phrase-based decoder.

Datasets

  • Training Data: The paper uses Chinese-English parallel corpora from LDC (Levy and Manning 2003 parser was used on Chinese). Specific datasets mentioned are LDC2006E93 and LDC2008E57.
  • Evaluation Data: The NIST MT03, MT04, and MT05 Chinese-English test sets were used for machine translation experiments. For reordering evaluation, the first 100 sentences from NIST MT03 were used, manually word-aligned using LDC annotation guidelines.

Key Insights and Ideas

  • Syntax is Crucial for Long-Distance Reordering: The paper strongly suggests that syntactic structure is key to understanding and modeling complex, long-distance reordering phenomena, which simpler phrase-based or surface-level models struggle with.
  • Directly Modeling Traversal Order: Instead of trying to predict the distance of a reordering, directly predicting the order in which source words should be visited offers a more powerful approach.
  • Reorder Lattices for Flexible Decoding: Generating a reorder lattice allows the reordering model to be decoupled from the translation decoder, providing a flexible way to integrate reordering information into various decoding frameworks.
  • Feature Engineering is Key: The success of the model hinges on the carefully designed syntactic features that capture specific reordering patterns observed in language pairs like Chinese-English.
  • Trade-off Between Lexical and Structural Features: While syntactic features are powerful, the paper acknowledges that a lack of rich lexical features can still lead to errors, suggesting a need for joint models in the future.

Key Results

  • Reordering Accuracy: The model achieved a top-1 reordering prediction accuracy of 80.56% on a test set, significantly outperforming a monotone (no reordering) baseline of 65.39%. Top-3 accuracy reached 93.05%.
  • Machine Translation Improvement: Decoding with MaxEnt reorder lattices showed significant improvements in BLEU scores across multiple test sets (MT03, MT04, MT05) compared to a baseline using distance-based reordering or no reordering. For example, on MT03, BLEU increased from 0.3005 to 0.3315 (+3.1 points).
  • Feature Utility: Ablation studies showed that different features contribute to the overall accuracy. "First Child" features alone achieved 75.97% accuracy, while adding "Node Jump" features improved it to 78.40%, and the full feature set reached 80.56%.
  • Error Analysis: About 34% of reordering errors were attributed to lexical choices, highlighting the need for better lexical integration. Parsing errors accounted for another 30%.

Limitations and Future Work

  • Data Sparsity: The model, despite using syntactic features, can still suffer from data sparsity, particularly for complex structures like "PP ADVP VP."
  • Lexical Idiosyncrasies: The current model lacks sufficient lexical features to handle word-choice-driven reordering phenomena.
  • Regularization: The paper notes that the current feature selection is primitive and suggests that regularization would prevent overfitting and improve the model's robustness, especially with limited training data.
  • Joint Modeling: The authors propose building joint models that integrate reordering and translation decisions, rather than treating them separately. This approach is expected to better address the interplay between reordering and lexical choice.

Summary updated

BibTeX
@inproceedings{ge2010direct,
  author = {Niyu Ge},
  title = {{A Direct Syntax-Driven Reordering Model for Phrase-Based Machine Translation}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2010},
}
Figure