Inversion Transduction Grammar for Joint Phrasal Translation Modeling

Colin Cherry, Dekang LinNAACL 2007 · OpenReview

Colin Cherry and Dekang Lin
Proceedings of SSST, NAACL-HLT 2007 / AMTA Workshop on Syntax and Structure in Statistical Translation

Introduction

In the mid-2000s, Statistical Machine Translation (SMT) was dominated by phrase-based systems that relied on heuristic extraction methods. While effective, these methods lacked a principled statistical foundation. This paper presents a significant advancement by introducing a Phrasal Inversion Transduction Grammar (ITG). This model bridges the gap between computationally expensive joint translation models and efficient heuristic methods, achieving both statistical rigor and practical performance.

The Challenge of Joint Phrasal Modeling

Standard phrase-based systems typically follow a two-step process: align words using models like GIZA++, then extract all phrase pairs consistent with those alignments. A more theoretically sound alternative is the Joint Phrasal Translation Model (JPTM), which learns phrase alignments directly. However, the search space for all possible phrasal alignments is astronomical. Previous JPTM implementations relied on slow, stochastic search methods like hill-climbing or random sampling, which were prone to local optima and difficult to scale.

Methodology: Phrasal ITG

The authors propose a Phrasal ITG to formalize the alignment process as a synchronous parsing problem. By treating translation as a grammar, they can leverage efficient parsing algorithms.

  1. Grammar Extension: Standard ITG operates on single words. The authors extended this by allowing the "leaves" of the synchronous tree to be entire multi-word phrases, represented by the production rule $A \to \bar{e}/\bar{f}$.
Phrasal leaf production allows the model to treat multi-word sequences as single units.
  1. ITG Constraints: ITG naturally restricts the alignment space by only allowing monotone or inverted compositions. This excludes complex "crossed" structures that are statistically rare in human translation, simplifying the search space without sacrificing significant accuracy.
Inverted composition rule enables the model to handle systematic word order differences between languages.
  1. Polynomial-Time Algorithms: Because the model is a formal grammar, the authors could replace unreliable sampling with exact algorithms like Viterbi for finding the best alignment and Inside-Outside for Expectation-Maximization (EM) training.

Despite the $O(n^6)$ complexity of ITG, parsing long sentences remains computationally demanding. To address this, the authors introduced Fixed-Link Pruning. They used high-confidence word alignments (the intersection of bidirectional GIZA++ alignments) as anchors. By pruning any phrasal span that violated these anchors, they reduced the search space by 95%, resulting in an 80x speedup in training.

Additionally, they introduced a Non-Compositional Constraint (NCC). This prevents the model from creating compositional phrases (those that can be decomposed into smaller, already-aligned parts), forcing the learner to focus on idiomatic, non-compositional translations.

Experimental Results

The researchers evaluated their system on the French-English Europarl corpus, focusing on sentences up to 25 words in length.

  • Translation Quality: The Phrasal ITG achieved a 28.85 BLEU score, representing a substantial 2.5 point improvement over the previous state-of-the-art joint model (C-JPTM).
  • Alignment Accuracy: When used as a word aligner with the NCC constraint, the model achieved an F-measure of 76.7, outperforming the standard GIZA++ "Grow-Diag-Final" heuristic (75.2).
  • Computational Efficiency: Fixed-link pruning reduced the processing time for the Inside-Outside algorithm from 415 seconds to just 5 seconds per 100 sentences.

Conclusion

Cherry and Lin demonstrated that joint phrasal translation modeling can be both principled and efficient. By combining the structural constraints of ITG with a clever pruning strategy based on word-level anchors, they created a system that outperforms both previous joint models and standard heuristic-based aligners. While scaling to massive datasets remains a challenge, this work provided a vital framework for incorporating syntax and formal grammars into phrase-based translation.

Summary updated

BibTeX
@inproceedings{cherry2007inversion,
  author = {Colin Cherry and Dekang Lin},
  title = {{Inversion Transduction Grammar for Joint Phrasal Translation Modeling}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2007},
  url = {https://openreview.net/forum?id=H6vbK8dmBe5},
}
Figure