[Mova](https://md.mova.elamur.ai/free/en/) · [this page in HTML](https://mova.elamur.ai/free/en/docs/papers/huang-2006-statistical-syntax-directed-translation-extended/)

[home](https://md.mova.elamur.ai/free/en/) / [docs](https://md.mova.elamur.ai/free/en/docs/) / [papers](https://md.mova.elamur.ai/free/en/docs/papers/) / [Machine translation](https://md.mova.elamur.ai/free/en/docs/papers/mtrans/) / Statistical Syntax-Directed Translation with Extended Domain of Locality

# Statistical Syntax-Directed Translation with Extended Domain of Locality

**Authors:** [Liang Huang](https://md.mova.elamur.ai/free/en/docs/papers/authors/liang-huang/), [Kevin Knight](https://md.mova.elamur.ai/free/en/docs/papers/authors/kevin-knight/), [Aravind Joshi](https://md.mova.elamur.ai/free/en/docs/papers/authors/aravind-joshi/) · **Year:** 2006 · **Venue:** Proceedings of the 7th Conference of the Association for Machine Translation in the Americas (AMTA) **Link:** [aclanthology.org/2006.amta-papers.8](https://aclanthology.org/2006.amta-papers.8/) · **Licence:** [CC BY-NC-SA 3.0](https://creativecommons.org/licenses/by-nc-sa/3.0/) — summary only

[**102** citations in our library](https://md.mova.elamur.ai/free/en/docs/papers/cited-by/huang-2006-statistical-syntax-directed-translation-extended/) of the 140673 papers whose bibliographies we read[Proceedings of the 7th Conference of the Association for Machine Translation in the Americas: Technical Papers](https://aclanthology.org/volumes/2006.amta-papers/)[licence](https://creativecommons.org/licenses/by-nc-sa/3.0/)

- [Publisher's page](https://aclanthology.org/2006.amta-papers.8/)
- [PDF](https://aclanthology.org/2006.amta-papers.8.pdf)

**Authors (3)**

1. Liang Huang
2. Kevin Knight
3. Aravind Joshi

Citations and author metrics from OpenAlex (); authors with the same name are not always told apart.

## 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](https://md.mova.elamur.ai/free/en/docs/papers/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/}
}
```

- [← previous PANGLOSS: Knowledge-Based Machine Translation](https://md.mova.elamur.ai/free/en/docs/papers/hovy-1994-pangloss-knowledge-based-machine-translation/)
- [next → Unsupervised Syntactically Controlled Paraphrase Generation with Abstract Meaning Representations](https://md.mova.elamur.ai/free/en/docs/papers/huang-2022-unsupervised-syntactically-controlled-paraphrase-generation/)
- [↑ back to Machine translation](https://md.mova.elamur.ai/free/en/docs/papers/mtrans/)

## 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](https://scholar.google.com/scholar?q=A%2E+V%2E+Aho+and+S%2E+C%2E+Johnson%2E+1976%2E+Optimal+code+generation+for+expression+trees%2E+J%2E+ACM%2C+23%283%29%3A488%E2%80%93+501%2E)
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](https://scholar.google.com/scholar?q=Alfred+V%2E+Aho+and+Jeffrey+D%2E+Ullman%2E+1972%2E+The+Theory+of+Parsing%2C+Translation%2C+and+Compiling%2C+volume+I%3A+Parsing%2E+Prentice+Hall%2C+Englewood+Cliffs%2C+New+Jersey%2E)
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](https://scholar.google.com/scholar?q=Peter+F%2E+Brown%2C+Stephen+A%2E+Della+Pietra%2C+Vincent+J%2E+Della+Pietra%2C+and+Robert+L%2E+Mercer%2E+1993%2E+The+mathematics+of+statistical+machine+translation%3A+Parameter+estimation%2E+Computational+Linguistics%2C+19%3A26)
4. Eugene Charniak. 2000. A maximum-entropy-inspired parser. In Proc. of NAACL, pages 132–139. [find](https://scholar.google.com/scholar?q=Eugene+Charniak%2E+2000%2E+A+maximum%2Dentropy%2Dinspired+parser%2E+In+Proc%2E+of+NAACL%2C+pages+132%E2%80%93139%2E)
5. David Chiang. 2005. A hierarchical phrase-based model for statistical machine translation. In Proc. of the 43rd ACL. [find](https://scholar.google.com/scholar?q=David+Chiang%2E+2005%2E+A+hierarchical+phrase%2Dbased+model+for+statistical+machine+translation%2E+In+Proc%2E+of+the+43rd+ACL%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/chiang-2005-hierarchical-phrase-based-model-statistical/)
6. Michael Collins, Philipp Koehn, and Ivona Kucerova. 2005. Clause restructuring for statistical machine translation. In Proc. of ACL. [find](https://scholar.google.com/scholar?q=Michael+Collins%2C+Philipp+Koehn%2C+and+Ivona+Kucerova%2E+2005%2E+Clause+restructuring+for+statistical+machine+translation%2E+In+Proc%2E+of+ACL%2E)
7. Michael Collins. 1999. Head-Driven Statistical Models for Natural Language Parsing. Ph.D. thesis, University of Pennsylvania. [find](https://scholar.google.com/scholar?q=Michael+Collins%2E+1999%2E+Head%2DDriven+Statistical+Models+for+Natural+Language+Parsing%2E+Ph%2ED%2E+thesis%2C+University+of+Pennsylvania%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/cl-2003-collins-head-driven-statistical-models-natural/)
8. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2001. Introduction to Algorithms. MIT Press, second edition. [find](https://scholar.google.com/scholar?q=Thomas+H%2E+Cormen%2C+Charles+E%2E+Leiserson%2C+Ronald+L%2E+Rivest%2C+and+Clifford+Stein%2E+2001%2E+Introduction+to+Algorithms%2E+MIT+Press%2C+second+edition%2E)
9. Yuan Ding and Martha Palmer. 2005. Machine translation using probablisitic synchronous dependency insertion grammars. In Proceedings of the 43rd ACL. [find](https://scholar.google.com/scholar?q=Yuan+Ding+and+Martha+Palmer%2E+2005%2E+Machine+translation+using+probablisitic+synchronous+dependency+insertion+grammars%2E+In+Proceedings+of+the+43rd+ACL%2E)
10. Jason Eisner. 2003. Learning non-isomorphic tree mappings for machine translation. In Proceedings of ACL (companion volume), pages 205–208. [find](https://scholar.google.com/scholar?q=Jason+Eisner%2E+2003%2E+Learning+non%2Disomorphic+tree+mappings+for+machine+translation%2E+In+Proceedings+of+ACL+%28companion+volume%29%2C+pages+205%E2%80%93208%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/eisner-2003-learning-non-isomorphic-tree-mappings/)
11. Heidi J. Fox. 2002. Phrasal cohesion and statistical machine translation. In In Proc. of EMNLP. [find](https://scholar.google.com/scholar?q=Heidi+J%2E+Fox%2E+2002%2E+Phrasal+cohesion+and+statistical+machine+translation%2E+In+In+Proc%2E+of+EMNLP%2E)
12. Michel Galley, Mark Hopkins, Kevin Knight, and Daniel Marcu. 2004. What’s in a translation rule? In HLT-NAACL. [find](https://scholar.google.com/scholar?q=Michel+Galley%2C+Mark+Hopkins%2C+Kevin+Knight%2C+and+Daniel+Marcu%2E+2004%2E+What%E2%80%99s+in+a+translation+rule%3F+In+HLT%2DNAACL%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/galley-2004-what-s-translation-rule/)
13. F. Gécseg and M. Steinby. 1984. Akadémiai Kiadó, Budapest. Tree Automata. [find](https://scholar.google.com/scholar?q=F%2E+Ge%CC%81cseg+and+M%2E+Steinby%2E+1984%2E+Akade%CC%81miai+Kiado%CC%81%2C+Budapest%2E+Tree+Automata%2E)
14. Jonathan Graehl and Kevin Knight. 2004. Training tree transducers. In HLT-NAACL, pages 105–112. [find](https://scholar.google.com/scholar?q=Jonathan+Graehl+and+Kevin+Knight%2E+2004%2E+Training+tree+transducers%2E+In+HLT%2DNAACL%2C+pages+105%E2%80%93112%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/graehl-2004-training-tree-transducers/)
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](https://scholar.google.com/scholar?q=Liang+Huang+and+David+Chiang%2E+2005%2E+Better+k%2Dbest+Parsing%2E+In+Proceedings+of+the+Nineth+International+Workshop+on+Parsing+Technologies+%28IWPT%2D2005%29%2C+9%2D10+October+2005%2C+Vancouver%2C+Canada%2E)
16. E. T. Irons. 1961. A syntax-directed compiler for AL-GOL 60. Comm. ACM, 4(1):51–55. [find](https://scholar.google.com/scholar?q=E%2E+T%2E+Irons%2E+1961%2E+A+syntax%2Ddirected+compiler+for+AL%2DGOL+60%2E+Comm%2E+ACM%2C+4%281%29%3A51%E2%80%9355%2E)
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](https://scholar.google.com/scholar?q=Aravind+Joshi+and+Yves+Schabes%2E+1997%2E+Tree%2Dadjoining+grammars%2E+In+G%2E+Rozenberg+and+A%2E+Salomaa%2C+editors%2C+Handbook+of+Formal+Languages%2C+volume+3%2C+pages+69+%E2%80%93+124%2E+Springer%2C+Berlin%2E)
18. Philipp Koehn, Franz Joseph Och, and Daniel Marcu. 2003. Statistical phrase-based translation. In Proc. of HLT-NAACL, pages 127–133. [find](https://scholar.google.com/scholar?q=Philipp+Koehn%2C+Franz+Joseph+Och%2C+and+Daniel+Marcu%2E+2003%2E+Statistical+phrase%2Dbased+translation%2E+In+Proc%2E+of+HLT%2DNAACL%2C+pages+127%E2%80%93133%2E)
19. Philipp Koehn. 2004. Pharaoh: a beam search decoder for phrase-based statistical machine translation models. In Proc. of AMTA, pages 115–124. [find](https://scholar.google.com/scholar?q=Philipp+Koehn%2E+2004%2E+Pharaoh%3A+a+beam+search+decoder+for+phrase%2Dbased+statistical+machine+translation+models%2E+In+Proc%2E+of+AMTA%2C+pages+115%E2%80%93124%2E)
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](https://scholar.google.com/scholar?q=Shankar+Kumar+and+William+Byrne%2E+2003%2E+A+weighted+finite+state+transducer+implementation+of+the+alignment+template+model+for+statistical+machine+translation%2E+In+Proc%2E+of+HLT%2DNAACL%2C+pages+142%E2%80%93149%2E)
21. P. M. Lewis and R. E. Stearns. 1968. Syntax-directed transduction. Journal of the ACM, 15(3):465–488. [find](https://scholar.google.com/scholar?q=P%2E+M%2E+Lewis+and+R%2E+E%2E+Stearns%2E+1968%2E+Syntax%2Ddirected+transduction%2E+Journal+of+the+ACM%2C+15%283%29%3A465%E2%80%93488%2E)
22. Dekang Lin. 2004. A path-based transfer model for machine translation. In Proceedings of the 20th COLING. [find](https://scholar.google.com/scholar?q=Dekang+Lin%2E+2004%2E+A+path%2Dbased+transfer+model+for+machine+translation%2E+In+Proceedings+of+the+20th+COLING%2E)
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](https://scholar.google.com/scholar?q=Jonathan+May+and+Kevin+Knight%2E+2006%2E+A+better+nbest+list%3A+Practical+determinization+of+weighted+finite+tree+automata%2E+In+Proc%2E+of+HLT%2DNAACL+2006%2E)
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](https://scholar.google.com/scholar?q=Mehryar+Mohri+and+Michael+Riley%2E+2002%2E+An+efficient+algorithm+for+the+n%2Dbest%2Dstrings+problem%2E+In+Proceedings+of+the+International+Conference+on+Spoken+Language+Processing+2002+%28ICSLP+%E2%80%9902%29%2C+Denver%2C+Col)
25. Franz Josef Och and Hermann Ney. 2002. Discriminative training and maximum entropy models for statistical machine translation. In Proc. of ACL. [find](https://scholar.google.com/scholar?q=Franz+Josef+Och+and+Hermann+Ney%2E+2002%2E+Discriminative+training+and+maximum+entropy+models+for+statistical+machine+translation%2E+In+Proc%2E+of+ACL%2E)
26. F. J. Och and H. Ney. 2004. The alignment template approach to statistical machine translation. Computational Linguistics, 30:417–449. [find](https://scholar.google.com/scholar?q=F%2E+J%2E+Och+and+H%2E+Ney%2E+2004%2E+The+alignment+template+approach+to+statistical+machine+translation%2E+Computational+Linguistics%2C+30%3A417%E2%80%93449%2E)
27. Franz Och. 2003. Minimum error rate training for statistical machine translation. In Proc. of ACL. [find](https://scholar.google.com/scholar?q=Franz+Och%2E+2003%2E+Minimum+error+rate+training+for+statistical+machine+translation%2E+In+Proc%2E+of+ACL%2E)
28. Chris Quirk and Simon Corston-Oliver. 2006. The impact of parse quality on syntactically-informed statistical machine translation. In Proc. of EMNLP. [find](https://scholar.google.com/scholar?q=Chris+Quirk+and+Simon+Corston%2DOliver%2E+2006%2E+The+impact+of+parse+quality+on+syntactically%2Dinformed+statistical+machine+translation%2E+In+Proc%2E+of+EMNLP%2E)
29. Chris Quirk, Arul Menezes, and Colin Cherry. 2005. Dependency treelet translation: Syntactically informed phrasal smt. In Proceedings of the 43rd ACL. [find](https://scholar.google.com/scholar?q=Chris+Quirk%2C+Arul+Menezes%2C+and+Colin+Cherry%2E+2005%2E+Dependency+treelet+translation%3A+Syntactically+informed+phrasal+smt%2E+In+Proceedings+of+the+43rd+ACL%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/quirk-2005-dependency-treelet-translation-syntactically-informed/)
30. Stuart Shieber and Yves Schabes. 1990. Synchronous tree-adjoining grammars. In Proc. of COLING, pages 253–258. [find](https://scholar.google.com/scholar?q=Stuart+Shieber+and+Yves+Schabes%2E+1990%2E+Synchronous+tree%2Dadjoining+grammars%2E+In+Proc%2E+of+COLING%2C+pages+253%E2%80%93258%2E)
31. Andrea Stolcke. 2002. Srilm: an extensible language modeling toolkit. In Proc. of ICSLP. [find](https://scholar.google.com/scholar?q=Andrea+Stolcke%2E+2002%2E+Srilm%3A+an+extensible+language+modeling+toolkit%2E+In+Proc%2E+of+ICSLP%2E)
32. Dekai Wu. 1997. Stochastic inversion transduction grammars and bilingual parsing of parallel corpora. Computational Linguistics, 23(3):377–404. [find](https://scholar.google.com/scholar?q=Dekai+Wu%2E+1997%2E+Stochastic+inversion+transduction+grammars+and+bilingual+parsing+of+parallel+corpora%2E+Computational+Linguistics%2C+23%283%29%3A377%E2%80%93404%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/wu-1997-stochastic-inversion-transduction-grammars-bilingual/)
33. Kenji Yamada and Kevin Knight. 2001. A syntax-based statistical translation model. In Proc. of ACL. [find](https://scholar.google.com/scholar?q=Kenji+Yamada+and+Kevin+Knight%2E+2001%2E+A+syntax%2Dbased+statistical+translation+model%2E+In+Proc%2E+of+ACL%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/yamada-2001-syntax-based-statistical-translation-model/)