Elamur Research
☰
home / papers / 2006 / Statistical Syntax-Directed Translation with Extended Domain of Locality

Statistical Syntax-Directed Translation with Extended Domain of Locality

What it is about

The paper models syntax-directed translation as a tree-to-string transducer whose source side has multi-level trees, so each rule can cover a larger piece of the parse than a one-level rule. Such rules can express reorderings that no synchronous context-free rule can, for example English subject-verb-object order turned into Arabic verb-subject-object order. The authors give a direct probability model and a linear-time dynamic programme for the best derivation. They then extend it to a log-linear model with an n-gram language model. Because several derivations give the same string, the k-best list for rescoring is filtered with a hash table of unique strings. On English-to-Chinese, the rescored output improves over the direct model's 1-best and over a phrase-based system, and the paper reports character-based BLEU on a 140-sentence test set, with confidence intervals of about two points.

Ideas

For Mova

The code is en/src/lin.rs (order rules) and tools/hbo with tools/translate/src/hebrew.rs (the Hebrew order). The paper's rules are counted and rule-based, which fits Mova. Its decoder with n-gram rescoring is not for Mova, since the translator has no search at test time.

Library summary

The Research library's own summary of the paper, in our words — not the paper's text.

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" does not allow redistributing the text itself. Original — aclanthology.org/2006.amta-papers.8.pdf

Summary

The paper tackles a weakness in statistical MT. Phrase-based systems and one-level synchronous grammars handle reordering poorly between languages with very different word order, and they miss constructions that span several tree levels. The authors revive the compiler idea of syntax-directed translation. A Treebank parser first parses the English input. A tree-to-string transducer whose rules carry multi-level source-side trees (1-xRLNs, a restricted xRs transducer) then recursively rewrites the tree into a Chinese string. A direct model Pr(c|e) is decoded with linear-time dynamic programming over the tree. A log-linear extension adds a trigram language model and a length penalty via k-best rescoring, using a new method that extracts only distinct output strings. Rules come from 1.95M English–Chinese sentence pairs. On a small English-to-Chinese test built by reversing NIST 2003 data, the rescored system significantly beats Pharaoh. This shows that separating parsing from transfer enables richer rules and fast decoding.

Key points

  • Training data was 1.95M aligned sentence pairs, with 28.3M English words. Alignment used GIZA++ and English parsing used a Collins (1999)-style parser. Galley et al. (2004) extraction produced 24.7M xRs rules.
  • The Chinese trigram LM was trained with the SRI Language Modeling Toolkit using Kneser-Ney smoothing.
  • Evaluation used 140 short sentences (fewer than 25 Chinese words) from the Xinhua part of the NIST 2003 Chinese-to-English set.
    • These were split into 70/70 Chinese sentences for dev and test.
    • Two English references per sentence served as input, giving 140 English inputs per set.
    • The original Chinese served as the single reference.
  • Scores are character-based BLEU, so results do not depend on Chinese tokenization. Test BLEU-4 was:
    • Pharaoh: 23.54
    • direct model (1-best): 24.53
    • 5000-best rescoring: 25.74
    • 50000-best rescoring: 26.69
  • The gain over Pharaoh is significant by sign test (p < 0.05 for BLEU-4, p < 0.01 for BLEU-8). Larger k consistently helped.

Interesting ideas

  • Separate analysis from transfer. Committing to one parse tree lets transfer rules cover multi-level fragments, and each stage searches a smaller space. This is a useful pattern whenever a joint search would force overly local rules.
  • Typed, deep rules block false matches. The passive rule fires only when its slots are a past participle (VBN) and a noun phrase (NP-C). Requiring that syntactic context guards against surface look-alikes such as "was asleep by sunset", which a single-nonterminal grammar would wrongly treat as passive.
  • Deduplicate during k-best extraction instead of determinizing. Each hypergraph node keeps a hash table of strings it has already produced and keeps requesting the next-best derivation until a new string appears. This removes spurious ambiguity without the possible blow-up of determinization, and it works for any equivalence relation on derivations.
  • Cheap tuning for few features. The system has only two free weights. A grid search over the LM weight is combined with a binary search for the length bonus that makes output length closest to the reference, avoiding full MERT.
  • Build a blind test set by reversing the direction. The multiple English references of an existing Chinese-to-English set become source inputs, and the original Chinese becomes the reference. This is handy when no evaluation data exists for the opposite direction.

Topics: Machine translation

Cite

The paper itself, not this card. BibTeX from the library's record of the work.

@inproceedings{huang2006statistical,
  title = {{Statistical Syntax-Directed Translation with Extended Domain of Locality}},
  author = {Huang, Liang and Knight, Kevin and Joshi, Aravind},
  booktitle = {Proceedings of the 7th Conference of the Association for Machine Translation in the Americas: Technical Papers},
  year = {2006},
  url = {https://aclanthology.org/2006.amta-papers.8/}
}

References

33 references, 8 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. A. V. Aho and S. C. Johnson. 1976. Optimal code generation for expression trees. J. ACM, 23(3):488– 501. find
  2. Alfred V. Aho and Jeffrey D. Ullman. 1972. The Theory of Parsing, Translation, and Compiling, volume I: Parsing. Prentice Hall, Englewood Cliffs, New Jersey. find
  3. Peter F. Brown, Stephen A. Della Pietra, Vincent J. Della Pietra, and Robert L. Mercer. 1993. The mathematics of statistical machine translation: Parameter estimation. Computational Linguistics, 19:263–311. find
  4. Eugene Charniak. 2000. A maximum-entropy-inspired parser. In Proc. of NAACL, pages 132–139. find
  5. David Chiang. 2005. A hierarchical phrase-based model for statistical machine translation. In Proc. of the 43rd ACL. find our card
  6. Michael Collins, Philipp Koehn, and Ivona Kucerova. 2005. Clause restructuring for statistical machine translation. In Proc. of ACL. find
  7. Michael Collins. 1999. Head-Driven Statistical Models for Natural Language Parsing. Ph.D. thesis, University of Pennsylvania. find our card
  8. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2001. Introduction to Algorithms. MIT Press, second edition. find
  9. Yuan Ding and Martha Palmer. 2005. Machine translation using probablisitic synchronous dependency insertion grammars. In Proceedings of the 43rd ACL. find
  10. Jason Eisner. 2003. Learning non-isomorphic tree mappings for machine translation. In Proceedings of ACL (companion volume), pages 205–208. find our card
  11. Heidi J. Fox. 2002. Phrasal cohesion and statistical machine translation. In In Proc. of EMNLP. find
  12. Michel Galley, Mark Hopkins, Kevin Knight, and Daniel Marcu. 2004. What’s in a translation rule? In HLT-NAACL. find our card
  13. F. Gécseg and M. Steinby. 1984. Akadémiai Kiadó, Budapest. Tree Automata. find
  14. Jonathan Graehl and Kevin Knight. 2004. Training tree transducers. In HLT-NAACL, pages 105–112. find our card
  15. Liang Huang and David Chiang. 2005. Better k-best Parsing. In Proceedings of the Nineth International Workshop on Parsing Technologies (IWPT-2005), 9-10 October 2005, Vancouver, Canada. find
  16. E. T. Irons. 1961. A syntax-directed compiler for AL-GOL 60. Comm. ACM, 4(1):51–55. find
  17. Aravind Joshi and Yves Schabes. 1997. Tree-adjoining grammars. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume 3, pages 69 – 124. Springer, Berlin. find
  18. Philipp Koehn, Franz Joseph Och, and Daniel Marcu. 2003. Statistical phrase-based translation. In Proc. of HLT-NAACL, pages 127–133. find
  19. Philipp Koehn. 2004. Pharaoh: a beam search decoder for phrase-based statistical machine translation models. In Proc. of AMTA, pages 115–124. find
  20. Shankar Kumar and William Byrne. 2003. A weighted finite state transducer implementation of the alignment template model for statistical machine translation. In Proc. of HLT-NAACL, pages 142–149. find
  21. P. M. Lewis and R. E. Stearns. 1968. Syntax-directed transduction. Journal of the ACM, 15(3):465–488. find
  22. Dekang Lin. 2004. A path-based transfer model for machine translation. In Proceedings of the 20th COLING. find
  23. Jonathan May and Kevin Knight. 2006. A better nbest list: Practical determinization of weighted finite tree automata. In Proc. of HLT-NAACL 2006. find
  24. Mehryar Mohri and Michael Riley. 2002. An efficient algorithm for the n-best-strings problem. In Proceedings of the International Conference on Spoken Language Processing 2002 (ICSLP ’02), Denver, Colorado, September. find
  25. Franz Josef Och and Hermann Ney. 2002. Discriminative training and maximum entropy models for statistical machine translation. In Proc. of ACL. find
  26. F. J. Och and H. Ney. 2004. The alignment template approach to statistical machine translation. Computational Linguistics, 30:417–449. find
  27. Franz Och. 2003. Minimum error rate training for statistical machine translation. In Proc. of ACL. find
  28. Chris Quirk and Simon Corston-Oliver. 2006. The impact of parse quality on syntactically-informed statistical machine translation. In Proc. of EMNLP. find
  29. Chris Quirk, Arul Menezes, and Colin Cherry. 2005. Dependency treelet translation: Syntactically informed phrasal smt. In Proceedings of the 43rd ACL. find our card
  30. Stuart Shieber and Yves Schabes. 1990. Synchronous tree-adjoining grammars. In Proc. of COLING, pages 253–258. find
  31. Andrea Stolcke. 2002. Srilm: an extensible language modeling toolkit. In Proc. of ICSLP. find
  32. Dekai Wu. 1997. Stochastic inversion transduction grammars and bilingual parsing of parallel corpora. Computational Linguistics, 23(3):377–404. find our card
  33. Kenji Yamada and Kevin Knight. 2001. A syntax-based statistical translation model. In Proc. of ACL. find our card