Better Word Alignments with Supervised ITG Models
Summary
The paper addresses supervised word alignment for machine translation by combining discriminative learning with inversion transduction grammar (ITG) constraints. The authors compare plain one-to-one matchings, one-to-one ITG, and a block ITG (BITG) variant that also allows contiguous many-to-one links. They train these models with margin-based (MIRA) and conditional likelihood objectives. A central difficulty is that many gold alignments, especially Chinese-English ones, cannot be produced by the model family. The authors handle this by training toward the lowest-loss alignments that the model can reach. They also extend the ITG normal form to cover null productions and add pruning that makes summing over ITG alignments about 100 times faster than naive bitext CKY. Rich block features (monolingual N-gram statistics, phrase shapes, length biases) give most of the gains. On NIST 2002 Chinese-English data the system achieves the best reported AER, and in a Hiero-style pipeline it adds 1.1 BLEU over GIZA++. The work shows that structured, tractable alignment models can be both more accurate and more useful downstream.
Key points
- When evaluated on Hansards test data using heuristic Dice-based potentials, the best ITG alignment reaches 28.4 AER, compared with 30.6 for unconstrained one-to-one matching.
- Oracle AER on the NIST 2002 Chinese-English hand-aligned data shows how much each family can express:
- 10.1 for one-to-one matchings,
- 10.2 for ITG,
- 1.2 for BITG, with blocks limited to size 4.
- The full BITG model, which uses HMM posteriors as features, reaches 14.4 AER on Chinese-English. The previous best was 15.9 (Ayan and Dorr, 2006), although the two setups are not strictly comparable.
- On French Hansards, the jointly trained HMM alone scores 5.4 AER, and no supervised model beats it significantly.
- End-to-end MT used the Joshua pipeline, trained on FBIS and evaluated on NIST MT05. BLEU scores were:
- 23.22 for GIZA++,
- 23.05 for the joint HMM,
- 24.28 for Viterbi ITG,
- 24.32 for posterior ITG.
Interesting ideas
- I1. Train toward the best reachable target. When the gold answer lies outside the hypothesis space, the model is updated toward the lowest-loss output it can actually produce. This "best-in-class" target stabilizes MIRA and makes likelihood training well defined. The trick applies to any structured prediction task with a restricted output space.
- I2. Measure the model family before training. Oracle potentials built directly from gold labels reveal how closely each alignment family can fit the gold data. This is a cheap way to decide whether to invest in richer structure, such as blocks, before building features for it.
- I3. Canonicalize derivations for likelihood training. A normal-form grammar ensures each output corresponds to exactly one derivation, so some structures are not counted many times over. Any model that sums over derivations, including spurious-ambiguity parsers, can benefit from this.
- I4. Score multi-word units with monolingual signals. Raw counts and PMI from a large monolingual corpus indicate whether the multi-word side of a block forms a coherent unit. This is useful wherever phrase-level decisions need evidence beyond the labeled data.
- I5. Use phrase shape templates. Every word outside the 25 most frequent ones is replaced with X, giving patterns like "in X of". Such templates generalize over function-word constructions and could transfer to tokenization or multiword-expression detection in other language pairs.
Cite
@inproceedings{haghighi2009better,
title = {{Better Word Alignments with Supervised ITG Models}},
author = {Haghighi, Aria and Blitzer, John and DeNero, John and Klein, Dan},
booktitle = {Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP},
year = {2009},
doi = {10.3115/1690219.1690276},
url = {https://doi.org/10.3115/1690219.1690276}
}References
- Necip Fazil Ayan and Bonnie Dorr. 2006. Going beyond AER: An extensive analysis of word alignments and their impact on MT. In ACL. find
- Colin Cherry and Dekang Lin. 2006. Soft syntactic constraints for word alignment through discriminative training. In ACL. find
- Colin Cherry and Dekang Lin. 2007a. Inversion transduction grammar for joint phrasal translation modeling. In NAACL-HLT 2007. find
- Colin Cherry and Dekang Lin. 2007b. A scalable inversion transduction grammar for joint phrasal translation modeling. In SSST Workshop at ACL. find
- David Chiang, Yuval Marton, and Philip Resnik. 2008. Online large-margin training of syntactic and structural translation features. In EMNLP. find
- David Chiang. 2007. Hierarchical phrase-based translation. Computational Linguistics. ↗ our card
- Michael Collins. 2002. Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms. In EMNLP. find our card
- Koby Crammer, Ofer Dekel, Shai S. Shwartz, and Yoram Singer. 2006. Online passive-aggressive algorithms. Journal of Machine Learning Research. find
- John DeNero and Dan Klein. 2007. Tailoring word alignments to syntactic machine translation. In ACL. find
- John DeNero and Dan Klein. 2008. The complexity of phrase alignment problems. In ACL Short Paper Track. find
- John DeNero, Mohit Bansal, Adam Pauls, and Dan Klein. 2009. Efficient parsing for transducer grammars. In NAACL. find
- Kuzman Ganchev, Joao Graca, and Ben Taskar. 2008. Better alignments = better translations? In ACL. find
- H. W. Kuhn. 1955. The Hungarian method for the assignment problem. Naval Research Logistic Quarterly. ↗
- Simon Lacoste-Julien, Ben Taskar, Dan Klein, and Michael Jordan. 2006. Word alignment via quadratic assignment. In NAACL. find
- Zhifei Li and Sanjeev Khudanpur. 2008. A scalable decoder for parsing-based machine translation with equivalent language model state maintenance. In SSST Workshop at ACL. find
- Percy Liang, Dan Klein, and Dan Klein. 2006. Alignment by agreement. In NAACL-HLT. find our card
- Adam Lopez. 2007. Hierarchical phrase-based translation with suffix arrays. In EMNLP. find our card
- I. Dan Melamed. 2000. Models of translational equivalence among words. Computational Linguistics. ↗
- Rada Mihalcea and Ted Pedersen. 2003. An evaluation exercise for word alignment. In HLT/NAACL Workshop on Building and Using Parallel Texts. find our card
- Robert C. Moore, Wen tau Yih, and Andreas Bode. 2006. Improved discriminative bilingual word alignment. In ACL-COLING. find
- Franz Josef Och. 2003. Minimum error rate training in statistical machine translation. In ACL. find
- Slav Petrov, Aria Haghighi, and Dan Klein. 2008. Coarse-to-fine syntactic machine translation using language projections. In Empirical Methods in Natural Language Processing. find
- Andreas Stolcke. 2002. Srilm: An extensible language modeling toolkit. In ICSLP 2002. find
- Ben Taskar, Simon Lacoste-Julien, and Dan Klein. 2005. A discriminative matching approach to word alignment. In NAACL-HLT. find
- L. G. Valiant. 1979. The complexity of computing the permanent. Theoretical Computer Science, 8:189– 201. ↗
- Dekai Wu. 1997. Stochastic inversion transduction grammars and bilingual parsing of parallel corpora. Computational Linguistics, 23. find our card
- Richard Zens and Hermann Ney. 2003. A comparative study on reordering constraints in statistical machine translation. In ACL. find
- Hao Zhang and Dan Gildea. 2005. Stochastic lexicalized inversion transduction grammar for alignment. In ACL. find
- Hao Zhang, Chris Quirk, Robert C. Moore, and Daniel Gildea. 2008. Bayesian learning of non-compositional phrases with synchronous parsing. In ACL. find
This page in Markdown → https://md.research.elamur.ai/free/papers/haghighi-2009-better-word-alignments-supervised-itg/