What's in a translation rule?

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

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 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}
}

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
2. M. Collins. 1999. Head-driven Statistical Models for Natural Language Parsing. Ph.D. thesis, University of Pennsylvania, Philadelphia. find our card
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 our card
4. H. Fox. 2002. Phrasal cohesion and statistical machine translation. In Proc. of Conference on Empirical Methods in Natural Language Processing (EMNLP). find
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
6. P. Koehn, F. Och, and D. Marcu. 2003. Statistical phrase-based translation. In Proceedings of HLT/NAACL. find
7. F. Och and H. Ney. 2000. Improved statistical alignment models. Proc. of the 38th Annual Meeting of the Association for Computational Linguistics. find
8. F. Och and H Ney. 2003. A systematic comparison of various statistical alignment models. Computational Linguistics, 29(1):19–51. find
9. D. Wu. 1997. Stochastic inversion transduction grammars and bilingual parsing of parallel corpora. Computational Linguistics, 23(3):377–404. find our card
10. K. Yamada and K. Knight. 2001. A syntax-based statistical translation model. In ACL, pages 523–530. find our card

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/galley-2004-what-s-translation-rule/