Improving reordering performance using higher order and structural features

Mitesh M. Khapra, Ananthakrishnan Ramanathan, Karthik VisweswariahNAACL 2013

TL;DR

This paper tackles the challenge of word reordering in machine translation, particularly for languages with significantly different sentence structures like Urdu and English. They propose a novel approach that goes beyond simple pairwise word relationships by incorporating higher-order and structural features to better capture long-range dependencies, leading to improved translation quality.

What Problem Does This Paper Address?

Machine translation systems often struggle with languages that have different word orders. For instance, Urdu typically follows a Subject-Object-Verb (SOV) structure, while English uses Subject-Verb-Object (SVO). This discrepancy requires a "reordering" step to rearrange source language words into a more natural target language order. Previous methods, like those based on the Traveling Salesman Problem (TSP), were efficient but limited to considering only pairs of words and their immediate neighbors. This pairwise approach is insufficient for capturing complex, long-range dependencies that are crucial for accurate reordering, especially when dealing with languages with very different syntactic structures. The paper aims to overcome this limitation by introducing richer features that can model these longer dependencies.

Methods

The core of the paper's contribution lies in its re-ranking approach. Instead of trying to solve the NP-hard problem of finding the absolute best reordering from scratch, they first use a base TSP model (similar to previous work) to generate an "n-best list" of plausible reorderings for a given source sentence. Then, they employ a separate re-ranking model to score and select the best reordering from this list.

The novelty lies in the features used by this re-ranking model:

  • Higher-Order Features: These go beyond pairwise interactions to consider trigrams of words and their associated "jumps" (the difference in their original positions). This allows the model to capture more complex relationships between words.
  • Structural Features: These features are derived from an induced segmentation of the sentence. The segmentation is based on identifying points where adjacent words in the original sentence are no longer adjacent in the reordered sentence. These features help the model understand the hierarchical structure of the sentence, which is crucial for correct reordering.
  • Interpolated MT Score: To indirectly capture target-side information (which the reordering model doesn't directly see), they interpolate their model's score with the score assigned by a standard Machine Translation (MT) system to the translation produced by a given reordering.

The re-ranking model's parameters are learned using the averaged perceptron algorithm. A modification to the standard Lin-Kernighan heuristic is also introduced to generate the n-best lists for the TSP model.

Datasets

The experiments were conducted on the Urdu-English language pair.

  • Training Data: The authors used a combination of manually aligned data (part of the NIST MT-08 training data) and automatically generated machine alignments (from NIST MT-08 and web sources).
  • Evaluation Data: A development set of 8017 Urdu tokens reordered manually was used for intrinsic evaluation. For extrinsic evaluation (impact on MT performance), the NIST MT-08 evaluation set (News and Web conditions) was used.

Key Insights and Ideas

  • Beyond Pairwise: The paper strongly demonstrates that relying solely on pairwise word relationships is a significant bottleneck for accurate reordering, especially for languages with divergent word orders.
  • Segmentation as Structure: The idea that reordering induces a sentence segmentation, and that this segmentation can be leveraged through structural features, is a key insight. This allows the model to implicitly understand hierarchical sentence structure.
  • N-best List Re-ranking: Tackling the NP-hard reordering problem by first generating a manageable set of candidates (n-best list) and then re-ranking them is an effective strategy to incorporate complex features without prohibitive computational cost.
  • Indirect Target-Side Features: Interpolating with the MT system's score is a clever way to inject target-language information into the reordering process, which is otherwise source-language-centric.

Key Results

  • Intrinsic Evaluation (mBLEU): The proposed approach achieved a gain of 1.8 mBLEU points over an improved TSP model.
  • Extrinsic Evaluation (BLEU):
    • Outperformed a baseline system with no pre-ordering by 6.2 BLEU points.
  • Outperformed a PBSMT system using the TSP model by 1.3 BLEU points.
  • Outperformed a state-of-the-art hierarchical phrase-based translation system (HIERO) by 3 BLEU points.
  • Performance by Sentence Length: The model showed greater improvements on medium-to-long sentences, with a slight drop in performance on very short sentences.
  • Feature Importance: An ablation study indicated that pos_triplet_jumps features were the most informative, supporting the claim that higher-order features are crucial.

Limitations and Future Work

  • Short Sentences: The model's performance dropped on short sentences, possibly due to the heuristic nature of structural feature extraction being more detrimental than helpful in simpler cases. The authors suggest combining the base TSP model for short sentences with their new model for longer ones.
  • Computational Cost: Interpolating with the MT score requires decoding n reorderings for each source sentence, which is computationally expensive.
  • Future Work:
    • Evaluate the algorithm on other language pairs.
  • Integrate the re-ranking score directly into the MT decoder to avoid multiple decodings.
  • Explicitly model sentence segmentation, potentially using a two-level hierarchical reordering model (segments first, then words within segments).

Summary updated

BibTeX
@inproceedings{khapra2013improving,
  author = {Mitesh M. Khapra and Ananthakrishnan Ramanathan and Karthik Visweswariah},
  title = {{Improving reordering performance using higher order and structural features}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2013},
}
Figure