Context-free reordering, finite-state translation

Chris Dyer, Philip ResnikNAACL 2010

TL;DR

This paper introduces a novel machine translation model that separates word order reordering from phrase translation. By representing source-side reordering alternatives as a context-free forest and using a finite-state transducer for translation, they achieve state-of-the-art performance while enabling more effective learning of long-range reordering patterns.

What Problem Does This Paper Address?

Traditional machine translation models, especially those based on finite-state transducers (FSTs), struggle with long-range word reordering. While synchronous context-free grammars (SCFGs) can handle reordering better, they can be computationally expensive. This paper aims to bridge this gap by proposing a two-step translation pipeline: first, reordering the source sentence into a target-like order using a context-free forest, and second, translating this reordered source into the target language using an FST. This approach leverages the strengths of both formalisms: SCFGs for flexible reordering and FSTs for efficient phrase translation. A key challenge addressed is learning effective reordering models without requiring manually created "reference reorderings," which are difficult to obtain.

Methods

The core of the proposed method is a two-stage translation process:

  1. Context-Free Reordering Forest: The source sentence is first transformed into a context-free grammar that generates strings representing alternative word orders. These alternatives are designed to approximate the target language's word order. This is achieved by "expanding" nodes in a source language parse tree, creating a forest that encodes various permutations of the sentence's constituents.
  2. Finite-State Phrase Transduction: The reordering forest is then translated into the target language using a finite-state transducer (FST) that represents phrasal correspondences. The novelty here lies in treating the FST as the "parser" and the reordering forest as the "grammar" to be parsed, enabling efficient composition.

Crucially, the reordering model is trained as a latent variable within a discriminative translation model. This allows learning from parallel corpora without explicit reordering annotations. The model uses a log-linear parameterization with potentially overlapping features to capture complex reordering patterns.

Datasets

The paper evaluates its model on three conditions:

  • BTEC Chinese-English corpus: A small data scenario.
  • Large data Chinese-English corpus: Designed to be comparable to NIST MT evaluations.
  • Large data Arabic-English task: A language pair requiring significant reordering.

The parallel training data was aligned using Giza++ (IBM Model 4). Chinese text was segmented using a CRF-based segmenter, and Arabic text used a technique described by Lee et al. (2003). Stanford parser was used for source parsing.

Key Insights and Ideas

  • Decoupling Reordering and Translation: Separating the problem into a reordering forest generation step and a phrase transduction step allows each component to specialize in what it does best: SCFGs for flexible reordering and FSTs for efficient translation.
  • Latent Variable Reordering: Training the reordering model as a latent variable is a significant contribution, enabling learning from standard parallel corpora without the need for costly manual reordering annotations.
  • Context-Free Forests as Input to FSTs: This paper demonstrates the feasibility and effectiveness of using context-free structures (reordering forests) as input to finite-state transducers, a departure from traditional approaches.
  • Learning Long-Range Reordering: The model shows evidence of learning large-scale reordering successfully, particularly for language pairs with different word orders (e.g., English SVO vs. Japanese SOV).

Key Results

The proposed model achieves state-of-the-art translation performance across the tested conditions. Specifically:

  • The "Forest" model (their proposed approach) outperforms "Mono" (no reordering), "PB" (phrase-based with distance distortion), and "Hiero" (hierarchical phrase-based) models on all three datasets.
  • For the BTEC dataset, the Forest model achieved a BLEU score of 54.1, compared to 52.4 for Hiero.
  • For Chinese-English, the Forest model achieved 32.4 BLEU, outperforming Hiero at 32.1.
  • For Arabic-English, the Forest model achieved 44.9 BLEU, slightly lower than Hiero (46.6), but the authors note this language pair presents unique challenges.

Qualitative analysis shows that the learned reordering features are intuitive and reflect expected word order differences between languages.

Limitations and Future Work

  • Reachability: A substantial portion of sentence pairs could not be regenerated by the model due to alignment errors, parse errors, or inadequate reordering capabilities in the generated forests. The authors suggest targeting reachable oracles or using minimum risk training as potential solutions.
  • Feature Engineering: While the model uses linguistically motivated features, the authors suggest that exploring a wider range of features for reordering prediction could further improve performance.
  • Reordering Forest Complexity: The current approach to generating reordering forests could be expanded to explore more complex structures.
  • Training Suboptimality: The discriminative training approach, while effective, is noted as suboptimal for state-of-the-art MT systems because it optimizes likelihood rather than an MT metric and doesn't initially include a language model. The paper describes how they addressed this for experiments by incorporating cube pruning for LM integration and using minimum error training techniques.
  • Arabic-English Performance: The model's performance on Arabic-English was slightly lower than the hierarchical phrase-based model, possibly due to the complexity of Arabic syntax and the specific reordering rules used.

Summary updated

BibTeX
@inproceedings{dyer2010context,
  author = {Chris Dyer and Philip Resnik},
  title = {{Context-free reordering, finite-state translation}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2010},
}
Figure