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).
- Pruning Strategy: For each agenda, only the top $b$ scoring items are retained.
- 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.
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