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

• I1. Multi-level rules as counted patterns: the encoder can learn rules over a meta-tree, such as "subject, verb, object" to "verb, subject, object", from the verse pairs. Count each pattern and its target order, keep the patterns above a threshold, and use them in en/src/lin.rs as order rules for the encoder, not as a search.
• I2. Unique output as a rule: the paper removes duplicate strings from the k-best list. The translator's standard can produce the same string from different trees. Count the duplicate trees per verse and report them, so the exact-match measure is not inflated.
• I3. Confidence intervals as a gate: the paper's test set is small, and its intervals are wide. In Mova, a change is claimed only when its gain is larger than the interval of the dev run, measured across runs twice.
• I4. Reordering rules by class: for Hebrew verb-initial order (open problem 7), write the verb-subject to subject-verb normaliser as one multi-level rule, and count how many verses it changes against the MACULA order.

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.

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

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/huang-2006-statistical-syntax-directed-translation-extended/