[Mova](https://md.mova.elamur.ai/free/en/) · [this page in HTML](https://mova.elamur.ai/free/en/docs/papers/galley-2004-what-s-translation-rule/) [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/) / What's in a translation rule? # What's in a translation rule? **Authors:** [Michel Galley](https://md.mova.elamur.ai/free/en/docs/papers/authors/michel-galley/), [Mark Hopkins](https://md.mova.elamur.ai/free/en/docs/papers/authors/mark-hopkins/), [Kevin Knight](https://md.mova.elamur.ai/free/en/docs/papers/authors/kevin-knight/), [Daniel Marcu](https://md.mova.elamur.ai/free/en/docs/papers/authors/daniel-marcu/) · **Year:** 2004 · **Venue:** HLT-NAACL 2004 **Link:** [aclanthology.org/N04-1035](https://aclanthology.org/N04-1035/) · **Licence:** [CC BY-NC-SA 3.0](https://creativecommons.org/licenses/by-nc-sa/3.0/) — summary only [**460** citations](https://openalex.org/works?filter=cites:W1551202288) openalex · 2026-10-19[**272** citations in our library](https://md.mova.elamur.ai/free/en/docs/papers/cited-by/galley-2004-what-s-translation-rule/) of the 140673 papers whose bibliographies we read[Proceedings of the Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics: HLT-NAACL 2004](https://aclanthology.org/volumes/N04-1/)[licence](https://creativecommons.org/licenses/by-nc-sa/3.0/) - [Publisher's page](https://aclanthology.org/N04-1035/) - [PDF](https://aclanthology.org/N04-1035.pdf) - [DOI 10.21236/ada460212](https://doi.org/10.21236/ada460212) - [OpenAlex](https://openalex.org/W1551202288) **Authors (4)** 1. [Michel Galley](https://openalex.org/A5107838508) [Semantic Scholar](https://www.semanticscholar.org/author/1947267) · h 50 · 14582 citations · 165 works 2. Mark Hopkins [Semantic Scholar](https://www.semanticscholar.org/author/145599343) 3. [Kevin Knight](https://openalex.org/A5106821597) [ORCID](https://orcid.org/0000-0001-9117-1718) · [Semantic Scholar](https://www.semanticscholar.org/author/152971314) · h 83 · 24348 citations · 407 works 4. [Daniel Marcu](https://openalex.org/A5005020376) [Semantic Scholar](https://www.semanticscholar.org/author/1695463) · h 58 · 17433 citations · 209 works Citations and author metrics from openalex (2026-10-19); authors with the same name are not always told apart. ## What it is about The paper gives a formal meaning to word alignments between a parsed English sentence and its translation. It defines a generative process that maps a source string to a target tree, and the transformation rules it allows are made of a tree fragment on the English side and the words it produces on the other side. The key notion is a frontier set: nodes whose spans do not overlap their complement spans, which fixes a reliable order between them. From a word-aligned, parsed corpus the method extracts the minimal set of rules that explain the pairs. A first algorithm has exponential running time and a second one is linear in the corpus size. On 1,000 sentences, the exponential one takes 304 seconds at rule size 7 and the linear one 6.4 seconds. The paper also measures how many parse trees are fully explained by rules of at most k expansions, with coverage rising with k on English-French and English-Chinese data, and it argues that child-reordering models are too weak for real translation pairs. ## Ideas - I1. Use the frontier-set criterion to extract rules from verse pairs, with the English side as the meta-world tree. The linear algorithm is cheap enough to run on all verses, and its output is counts that can go into the encoder tables (`tools/translate`, `profile.rs`). - I2. Coverage as a diagnostic. Report the share of UD trees of each verse that the extracted rules explain at each size limit. Low coverage in one author's verses points at reader attachment noise (open problem 1), and the report costs one run. - I3. Unaligned function words. The paper lets unaligned words attach to a neighbouring rule. Mova can treat an unaligned *the* or *that* as a feature of the neighbouring meta token, not as a separate rule (open problem 4). - I4. Control: shuffle the word alignment inside each verse and check that the rule counts and the coverage fall. If they do not, the extractor is reading the order of the verse and not its alignment. ## For Mova The code is `tools/translate` (the rules come from the meta-world subtrees and the alignment that `hebrew.rs` and `meta.rs` produce). The paper is not neural, and its rule set is a count table that Mova can keep in ordered maps. The scale result is the useful part: measure extraction time at two rule sizes on the Bible pairs before choosing a size limit. 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. [DOI 10.21236/ada460212](https://doi.org/10.21236/ada460212) ``` @inproceedings{galley2004what, title = {{What's in a translation rule?}}, author = {Galley, Michel and Hopkins, Mark and Knight, Kevin and Marcu, Daniel}, booktitle = {Proceedings of the Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics: HLT-NAACL 2004}, year = {2004}, doi = {10.21236/ada460212}, url = {https://doi.org/10.21236/ada460212} } ``` - [← previous Results of WMT22 Metrics Shared Task: Stop Using BLEU – Neural Metrics Are Better and More Robust](https://md.mova.elamur.ai/free/en/docs/papers/freitag-2022-results-wmt22-metrics-shared-task/) - [next → Scalable Inference and Training of Context-Rich Syntactic Translation Models](https://md.mova.elamur.ai/free/en/docs/papers/galley-2006-scalable-inference-training-context-rich/) - [↑ back to Machine translation](https://md.mova.elamur.ai/free/en/docs/papers/mtrans/) ## References 10 references, 4 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet. 1. E. Charniak, K. Knight, and K. Yamada. 2003. Syntax-based language models for machine translation. In Proc. MT Summit IX. [find](https://scholar.google.com/scholar?q=E%2E+Charniak%2C+K%2E+Knight%2C+and+K%2E+Yamada%2E+2003%2E+Syntax%2Dbased+language+models+for+machine+translation%2E+In+Proc%2E+MT+Summit+IX%2E) 2. M. Collins. 1999. Head-driven Statistical Models for Natural Language Parsing. Ph.D. thesis, University of Pennsylvania, Philadelphia. [find](https://scholar.google.com/scholar?q=M%2E+Collins%2E+1999%2E+Head%2Ddriven+Statistical+Models+for+Natural+Language+Parsing%2E+Ph%2ED%2E+thesis%2C+University+of+Pennsylvania%2C+Philadelphia%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/cl-2003-collins-head-driven-statistical-models-natural/) 3. J. Eisner. 2003. Learning non-isomorphic tree mappings for machine translation. In Proc. of the 41st Meeting of the Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=J%2E+Eisner%2E+2003%2E+Learning+non%2Disomorphic+tree+mappings+for+machine+translation%2E+In+Proc%2E+of+the+41st+Meeting+of+the+Association+for+Computational+Linguistics%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/eisner-2003-learning-non-isomorphic-tree-mappings/) 4. H. Fox. 2002. Phrasal cohesion and statistical machine translation. In Proc. of Conference on Empirical Methods in Natural Language Processing (EMNLP). [find](https://scholar.google.com/scholar?q=H%2E+Fox%2E+2002%2E+Phrasal+cohesion+and+statistical+machine+translation%2E+In+Proc%2E+of+Conference+on+Empirical+Methods+in+Natural+Language+Processing+%28EMNLP%29%2E) 5. D. Gildea. 2003. Loosely tree-based alignment for machine translation. In Proc. of the 41th Annual Conference of the Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=D%2E+Gildea%2E+2003%2E+Loosely+tree%2Dbased+alignment+for+machine+translation%2E+In+Proc%2E+of+the+41th+Annual+Conference+of+the+Association+for+Computational+Linguistics%2E) 6. P. Koehn, F. Och, and D. Marcu. 2003. Statistical phrase-based translation. In Proceedings of HLT/NAACL. [find](https://scholar.google.com/scholar?q=P%2E+Koehn%2C+F%2E+Och%2C+and+D%2E+Marcu%2E+2003%2E+Statistical+phrase%2Dbased+translation%2E+In+Proceedings+of+HLT%2FNAACL%2E) 7. F. Och and H. Ney. 2000. Improved statistical alignment models. Proc. of the 38th Annual Meeting of the Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=F%2E+Och+and+H%2E+Ney%2E+2000%2E+Improved+statistical+alignment+models%2E+Proc%2E+of+the+38th+Annual+Meeting+of+the+Association+for+Computational+Linguistics%2E) 8. F. Och and H Ney. 2003. A systematic comparison of various statistical alignment models. Computational Linguistics, 29(1):19–51. [find](https://scholar.google.com/scholar?q=F%2E+Och+and+H+Ney%2E+2003%2E+A+systematic+comparison+of+various+statistical+alignment+models%2E+Computational+Linguistics%2C+29%281%29%3A19%E2%80%9351%2E) 9. D. 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=D%2E+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/) 10. K. Yamada and K. Knight. 2001. A syntax-based statistical translation model. In ACL, pages 523–530. [find](https://scholar.google.com/scholar?q=K%2E+Yamada+and+K%2E+Knight%2E+2001%2E+A+syntax%2Dbased+statistical+translation+model%2E+In+ACL%2C+pages+523%E2%80%93530%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/yamada-2001-syntax-based-statistical-translation-model/)