A Comparative Study on Reordering Constraints in Statistical Machine Translation

Richard Zens, Hermann NeyACL 2003 · DOI

Abstract

This study investigates the balance between translation quality and computational efficiency in Statistical Machine Translation (SMT) by analyzing word-reordering constraints. We compare Inversion Transduction Grammar (ITG) and IBM constraints, demonstrating that while baseline ITG has limitations on complex datasets, an extended version achieves 96% alignment coverage.

Introduction

The "search problem" in SMT—identifying the most probable target sentence for a given source—is inherently complex. Allowing arbitrary word reordering makes the problem NP-hard. To maintain feasibility, researchers employ reordering constraints. This paper evaluates the theoretical flexibility and empirical performance of these constraints across diverse bilingual corpora.

Methodology: ITG vs. IBM Constraints

The authors contrast two primary frameworks for limiting the search space:

  1. IBM Constraints: These utilize a "sliding window" approach where a target word aligns with one of the first $k$ available source positions.
  2. ITG Constraints: Based on Inversion Transduction Grammars, this method treats sentences as sequences of blocks that can be merged either monotonically or by inversion (swapping).
ITG constraints illustrating monotone (without inversion) and swapped (with inversion) block reordering.

To address the restrictiveness of baseline ITG, the authors propose an Extended ITG that permits non-consecutive source phrases, effectively treating them as bilingual grammar productions. A CYK-style polynomial-time search algorithm is implemented, utilizing histogram and threshold pruning to manage the $O(J^3 \cdot E^4)$ complexity.

Theoretical Analysis: The Schröder Connection

A significant theoretical contribution of this work is the discovery of a mathematical link between ITG constraints and Schröder numbers. The number of permutations allowed by ITG constraints grows at a rate of approximately $5.83^n$.

Growth rate of the number of permutations permitted by ITG constraints, related to Schröder numbers.

This growth rate suggests that ITG constraints offer greater flexibility for long sentences compared to IBM constraints, which scale at $k^n$.

Empirical Evaluation

The study utilizes two datasets: Verbmobil (short German-English speech, ~10 words/sentence) and Canadian Hansards (complex French-English parliamentary proceedings, ~16-18 words/sentence).

Key Results

  • Alignment Coverage: On the Canadian Hansards task, baseline ITG covered only 73-81% of Viterbi alignments. However, the Extended ITG reached 96% coverage, surpassing the 87% achieved by IBM constraints.
  • Translation Quality: In the Verbmobil task, ITG-based search produced a Word Error Rate (WER) of 45.6%, slightly better than the 46.2% for IBM constraints. Subjective evaluations (SSER) were comparable (IBM 40.8% vs. ITG 42.0%).
  • Qualitative Performance: ITG successfully modeled long-range German verb reorderings in subordinate clauses, a task where IBM constraints often failed.

Conclusion

While ITG is theoretically more flexible, its baseline implementation can struggle with complex linguistic structures. The Extended ITG framework bridges this gap, offering high coverage and competitive translation quality. Future work should focus on the automatic extraction of bilingual grammars to enhance scalability and adaptability across different language pairs.

Summary updated

BibTeX
@inproceedings{zens2003comparative,
  author = {Richard Zens and Hermann Ney},
  title = {{A Comparative Study on Reordering Constraints in Statistical Machine Translation}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2003},
  doi = {10.3115/1075096.1075115},
}
Figure