Abstract: Peng Li, Yang Liu, Maosong Sun. Proceedings of COLING 2012: Posters.
2012.
Introduction
In Statistical Machine Translation (SMT), word alignment is a fundamental task that identifies correspondences between source and target language words. Among various modeling approaches, Inversion Transduction Grammar (ITG) is highly regarded for its ability to structurally model word order shifts (distortion) between languages. However, the computational cost of finding the optimal Viterbi ITG alignment is traditionally $O(n^6)$, making it prohibitively slow for large-scale datasets and long sentences. Researchers from Tsinghua University have proposed a beam search algorithm that reduces this complexity to $O(bn^3)$, achieving significant speedups without compromising translation quality.
The Beam Search Approach
To overcome the inefficiency of exhaustive bilingual parsing, the authors shift the problem from a parsing task to a search task. The algorithm iteratively constructs an alignment by adding "promising links"—word pairs with high alignment probability—one by one.
Enforcing ITG Constraints
A critical challenge in this iterative approach is ensuring that the resulting alignment remains a valid ITG structure. The authors introduce a shift-reduce "ITG-checker" to solve this. As each link is added to a hypothesis, the checker validates whether the new set of links can still be derived using ITG rules. By maintaining a "beam" of the top $b$ most probable hypotheses, the algorithm avoids the exponential search space while preventing the search from settling on suboptimal local maxima.
Experimental Evaluation
The algorithm was evaluated on Chinese-English translation tasks, which feature significant structural divergence. The researchers used 461 hand-aligned sentence pairs for alignment evaluation and the FBIS corpus (138K pairs) for translation evaluation, testing across both phrase-based (Moses) and hierarchical phrase-based (Joshua) SMT systems.
Key Results
- Efficiency: With a beam size of $b=10$, the algorithm was 20 times faster than state-of-the-art biparsing with tic-tac-toe pruning.
- Alignment Quality: The Alignment Error Rate (AER) remained competitive at 30.52, compared to 29.13 for exhaustive biparsing, outperforming faster but less accurate pruning configurations.
- Translation Performance: BLEU scores were comparable across all methods, with the beam search even slightly outperforming slower methods in the Moses system (23.95 vs 23.86).
Conclusion
The proposed beam search algorithm demonstrates that ITG word alignment can be made practical for real-world SMT applications. By "growing" alignments and using a shift-reduce filter, the system avoids the $O(n^6)$ bottleneck. Future work aims to extend this framework to block-based ITG to support many-to-many word mappings and integrate discriminative training to further refine link selection.
Summary updated