Learning Stochastic Bracketing Inversion Transduction Grammars with a Cubic Time Biparsing Algorithm

Markus Saers, Joakim Nivre, Dekai WuIWPT 2009 · OpenReview

Abstract: Markus Saers, Joakim Nivre, Dekai Wu. Proceedings of the 11th International Conference on Parsing Technologies (IWPT’09).

2009.

Introduction

Inversion Transduction Grammars (ITGs) provide a robust framework for modeling structural reorderings in Statistical Machine Translation (SMT). By capturing transformations like noun-adjective swaps through synchronous parsing, ITGs offer a more linguistically grounded approach to word alignment than traditional heuristic models. However, the adoption of ITGs has been hindered by the extreme computational cost of biparsing, which typically scales at $O(n^6)$ relative to sentence length $n$.

The Complexity Wall

Word alignment is the process of identifying correspondences between source and target sentences. While ITGs excel at this, the "complexity wall" of $O(n^6)$ makes them impractical for standard-length sentences. For instance, doubling sentence length from 20 to 40 words increases the computational load by a factor of 64. Consequently, the industry has largely relied on faster, albeit less structurally aware, tools like GIZA++.

Methodology: Pruning by Length

The authors propose a novel agenda-based bottom-up chart parser for Stochastic Bracketing ITGs (SBITGs) that reduces complexity to $O(bn^3)$, where $b$ is a pruning parameter.

Agenda-Based Pruning

Instead of an exhaustive search, the algorithm organizes potential alignments into "agendas" based on their total span length (the sum of source and target lengths).

  1. Pruning Strategy: For each agenda, only the top $b$ scoring items are retained.
  2. Complexity Reduction: By limiting each of the $O(n)$ agendas to $b$ items, and with each item requiring $O(n^2)$ processing time, the total complexity is slashed to $O(bn^3)$.

This approach leverages the observation that "skewed" links (e.g., one word aligned to many) are statistically unlikely. Grouping by total length forces skewed hypotheses to compete with more balanced, likely alignments, allowing the parser to discard improbable paths early.

Experimental Setup

The algorithm was evaluated on the Europarl corpus across three language pairs: German–English, French–English, and Spanish–English. To establish a baseline against the exhaustive $O(n^6)$ version, training was restricted to sentence pairs with a maximum length of 10 words, totaling approximately 100,000 pairs per language.

Results and Discussion

The experimental results demonstrate that the $O(bn^3)$ algorithm makes structural word alignment both feasible and effective.

Comparison of translation quality (BLEU/NIST) and training time across different pruning levels (b) and language pairs.

As shown in the table above, the SBITG system consistently matches or outperforms the GIZA++ baseline. For Spanish-English, the SBITG model with $b=100$ achieved a BLEU score of 0.2671, compared to the baseline's 0.2597.

A critical finding is the "sweet spot" for the pruning parameter $b$. Translation quality (BLEU and NIST) rises sharply as $b$ increases from 1 to 10 and plateaus around $b=25$. This suggests that exhaustive search is unnecessary for high-quality alignment. Furthermore, the efficiency gains are substantial: at $b=10$, training takes roughly 17 minutes per iteration, whereas the unpruned version ($\infty$) requires over 3 hours.

Conclusion

By introducing a cubic-time biparsing algorithm, this work overcomes the primary barrier to using ITGs in machine translation. The $O(bn^3)$ approach allows for structural word alignment that is significantly faster than exhaustive methods while maintaining superior translation quality over standard baselines. Future work will focus on scaling this algorithm to full-length sentences and optimizing initialization strategies to further accelerate convergence.

Summary updated

BibTeX
@inproceedings{saers2009learning,
  author = {Markus Saers and Joakim Nivre and Dekai Wu},
  title = {{Learning Stochastic Bracketing Inversion Transduction Grammars with a Cubic Time Biparsing Algorithm}},
  booktitle = {IWPT},
  year = {2009},
  url = {https://openreview.net/forum?id=-EmEL9pFqO2},
}
Figure