Empirical Lower Bounds on Aligment Error Rates in Syntax-Based Machine Translation

Anders Søgaard, Jonas KuhnNAACL 2009 · OpenReview

Abstract

Anders Søgaard, Jonas Kuhn. Proceedings of the Third Workshop on Syntax and Structure in Statistical Translation (SSST-3) at NAACL HLT 2009.

2009.

Introduction

Popular syntax-based machine translation (MT) models, such as Inversion Transduction Grammars (ITGs), are mathematically incapable of representing certain complex word alignments found in human translations. This paper quantifies this "expressivity gap" by analyzing 12 hand-aligned corpora, proving that even a theoretically perfect version of these models would still suffer from significant inherent error rates.

The Expressivity Problem in Syntax-Based MT

In syntax-based machine translation, researchers use synchronous grammars to model the structural transformation between languages. To maintain computational efficiency, most systems utilize grammars of "rank two" (e.g., 2-SCFGs or ITGs), meaning each rule tracks at most two non-terminals simultaneously.

However, human translation often involves complex word movements and discontinuous units. The authors investigate whether these efficient rank-two grammars are expressive enough to capture the reality of human translation. If a grammar cannot represent a specific alignment, the MT system is fundamentally limited, regardless of the amount of training data.

Methodology: Identifying Illegal Configurations

The authors identify specific alignment patterns that rank-two grammars cannot induce, establishing a formal basis for their empirical study:

  1. Inside-Out Alignments: Specific permutations that exceed the reordering capabilities of ITGs.
  2. Cross-Serial Discontinuous Translation Units (CDTUs): Patterns where word groups "leapfrog" each other in a way that cannot be nested.
Inside-out alignment configuration
Cross-serial discontinuous translation unit (CDTU) pattern

To quantify these limitations, the authors introduce the Translation Unit Error Rate (TUER). Unlike the standard Alignment Error Rate (AER), which rewards partial matches, TUER treats translation units (groups of words translating together) as atomic. If a model cannot capture the entire unit correctly, it receives no credit.

Empirical Analysis and Datasets

The study examines 12 hand-aligned parallel corpora to establish empirical lower bounds:

  • Copenhagen Dependency Treebank: Danish paired with English, German, Italian, Russian, and Spanish.
  • Padó and Lapata (2006): German-English parallel corpus.
  • Europarl (Graca et al., 2008): English paired with French, Portuguese, Spanish, and others.

By searching these "gold standard" human alignments for "illegal" configurations, the authors calculate the minimum possible error rate (lower bound) for specific grammar types.

Key Insights

  • The Rank Constraint Bottleneck: Restricting grammars to rank two for $O(n^6)$ efficiency creates a hard ceiling on accuracy.
  • Prevalence of Discontinuity: CDTUs are surprisingly common, appearing in approximately every second sentence pair across the studied corpora.
  • AER vs. TUER: Standard AER metrics often mask failures. By rewarding partial links within a complex unit, AER hides the fact that the model is fundamentally incapable of producing the correct full translation unit.
  • Formalism Hierarchy: While 2-STAGs (Synchronous Tree-Adjoining Grammars) are more expressive than ITGs, even they fail to handle "multigap" units (units with more than two gaps).

Results: Quantifying the Lower Bounds

The inherent error rates for popular MT formalisms are significant:

  • ITG Lower Bounds: For the Danish-Spanish corpus, ITGs have an empirical lower bound for TUER of at least 14.7%.
  • 2-STSG Lower Bounds: For English-Portuguese, Synchronous Tree Substitution Grammars have a lower bound of 16.0%.
  • Inside-Out Frequency: In pairs like English-German and Danish-Spanish, "inside-out" alignments are frequent, directly contributing to the failure of simpler synchronous grammars.

Conclusion and Future Work

The authors acknowledge that these lower bounds are likely conservative, as their search algorithms might miss even more complex configurations. While more expressive grammars (like 2-STAGs) could lower these bounds, they introduce massive computational costs ($O(n^{12})$). Future research must focus on either excluding less frequent alignment classes or designing new formalisms that increase expressivity without prohibitive complexity.

Summary updated

BibTeX
@inproceedings{sgaard2009empirical,
  author = {Anders Søgaard and Jonas Kuhn},
  title = {{Empirical Lower Bounds on Aligment Error Rates in Syntax-Based Machine Translation}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2009},
  url = {https://openreview.net/forum?id=O1wD96fVDGc},
}
Figure