Abstract: Markus Saers, Joakim Nivre, and Dekai Wu present a comparative study of Inversion Transduction Grammars (ITG) and Linear Transduction Grammars (LTG) for word alignment in machine translation. While ITGs are the gold standard for structural alignment, their high computational complexity ($O(n^6)$) poses scaling challenges. This paper formalizes LTGs as a faster alternative ($O(n^4)$) and introduces a novel "seeding" technique. By initializing an ITG with parameters learned from a faster LTG, the authors achieve high translation quality with a dramatic reduction in training time.
Introduction
In Statistical Machine Translation (SMT), word alignment is the foundational task of mapping source words to their target counterparts. Traditional models like GIZA++ are fast but lack a shared structural representation. Transduction grammars solve this by parsing both languages simultaneously (biparsing), ensuring structural consistency. However, the computational cost of Inversion Transduction Grammar (ITG) often makes it impractical for large-scale induction. This paper investigates Linear Transduction Grammars (LTGs) to find a better efficiency-accuracy trade-off.
Methodology
The authors contribute three main technical advancements:
- Formalization of LTGs: LTGs are defined as bilingual equivalents of linear grammars. The authors prove their equivalence to Linear Inversion Transduction Grammars (LITGs).
- Pruning Strategies: To make induction feasible, a coverage-based pruning scheme is used, effectively reducing practical complexity to $O(n^3)$ for ITG and $O(n)$ for LTG.
- Seeding Heuristic: Since LTGs are a subclass of ITGs, the authors propose inducing an LTG first and using its rules and probabilities to "seed" an ITG. This allows the more complex model to converge much faster.
Experimental Setup
The models were evaluated on the Europarl corpus for Spanish–English, French–English, and German–English. To allow for exhaustive baselines, the dataset was filtered to sentence pairs with 10 tokens or fewer. The study compared Stochastic Bracketing ITG (SBITG), Stochastic Bracketing LTG (SBLTG), and the seeded "Both" approach against a GIZA++ baseline.
Results and Discussion
The experiments revealed that both transduction grammars outperform GIZA++ once a sufficient beam size is used, highlighting the value of structural constraints.
Key findings include:
- Translation Quality: SBITG achieved the highest BLEU scores (e.g., 0.2671 for Spanish-English), but SBLTG was highly competitive (0.2633).
- Efficiency: SBLTG is orders of magnitude faster. At a beam size of 1, SBLTG trained in 35 seconds, while SBITG took over 3 hours.
- Seeding Success: The "Both" approach achieved BLEU scores nearly identical to SBITG while requiring only 20% of the training time.
Conclusion
LTGs provide a high-quality, efficient alternative to ITGs for word alignment. The proposed seeding method successfully bridges the gap between the two, offering the accuracy of ITGs at a fraction of the computational cost. This approach opens the door for applying transduction grammars to much larger parallel corpora.
Summary updated