Elamur Research
☰
home / papers / 2006 / Tree-to-String Alignment Template for Statistical Machine Translation

Tree-to-String Alignment Template for Statistical Machine Translation

What it is about

A tree-to-string alignment template (TAT) pairs a source parse subtree, with variables at some of its leaves, with a target string that uses the same variables. The templates are extracted automatically from word-aligned, source-parsed bitext: for a given tree and string alignment, the paper takes subtrees whose spans are consistent with the alignment and limits their height and number of leaves. A translation is produced by parsing the input, applying matching templates top-down, and scoring with a log-linear model over seven features: the template probabilities in both directions, a trigram language model, lexical weights and a word penalty. The system Lynx is compared with the phrase-based Pharaoh on Chinese-English. The full-feature Lynx scores about 0.006 BLEU absolute above Pharaoh (3.1 percent relative, significant at p < 0.01), and it uses 88,066 templates on the test set against 221,453 bilingual phrases for Pharaoh. Adding bilingual phrases as templates without a tree gives a further small gain, to BLEU 0.2240.

Ideas

For Mova

The code is tools/translate (hebrew.rs for the Hebrew subtrees, profile.rs for the encoder). The template model is a count-based table with a log-linear score, which Mova can keep in ordered maps. The first measure is the ablation in I4, since it decides whether the tree side of the encoder is worth building.

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/P06-1077.pdf

Summary

Phrase-based SMT handles local reordering well. However, it treats phrases as plain word strings and models long-distance reordering only through word-offset distortion, so syntax is largely ignored. Liu, Liu and Lin propose a model built on the tree-to-string alignment template (TAT). A TAT pairs a fragment of a source parse tree with a target string, and both sides may contain words and placeholders, together with the alignment between them. TATs are learned automatically from parallel text that has been word-aligned with GIZA++ and parsed on the source side. To translate, the Chinese input is parsed, the tree is split into subtrees, each subtree is rewritten by a chosen template, and the outputs are joined into English. The decoder, Lynx, combines seven features in a log-linear model tuned by minimum error rate training. On Chinese-to-English translation it beats the phrase-based Pharaoh baseline under every feature setting, with a statistically significant margin, while using far fewer rules. The work shows that source-side syntax alone can drive reordering at word, phrase and clause levels, and that this approach is cheaper to train than tree-to-tree models.

Key points

  • The model splits into four sub-models: parse, detachment, TAT selection and TAT application. In the experiments, only the single best parse is used and all detachments are treated as equally likely.
  • Extraction is limited in three ways to keep it tractable:
    • the first and last target symbols must be aligned;
    • tree height is capped at h;
    • the number of children per node is capped at c.
  • With full features, Lynx gains 0.006 BLEU absolute over Pharaoh (3.1% relative, p < 0.01). It uses 88,066 TATs on the test corpus, compared with 221,453 bilingual phrases for Pharaoh (1,231,959 phrases extracted in total).
  • Adding Pharaoh's bilingual phrases as tree-less TATs raises BLEU4 from 0.2178 to 0.2240.
  • In a large-data setting, Lynx scores 0.2830 BLEU on the 2005 NIST Chinese-to-English test set. This setup used 2.6M sentence pairs for phrases, 800K pairs for TATs, two trigram LMs (one built on part of the Gigaword Xinhua portion), and rule-based handling of named entities, dates and numbers.

Interesting ideas

  • Syntax on one side only. Parsing just the source language and producing a flat target string avoids requiring a parser for both languages. This is attractive whenever only one side of a language pair has a good treebank-trained parser.
  • Building larger rules from smaller ones. Templates for a big subtree are composed recursively from those of its child sub-alignments. Simple caps on tree height and branching then control the explosion in rule count. The same pattern could apply to any grammar-induction task where the candidate rule space grows combinatorially.
  • Backing off to phrases. When a source span consists only of words, plain phrase pairs are wrapped as templates over that subtree. This recovers non-constituent translations that strict syntax would lose, which is a cheap way to mix linguistic and purely statistical units.
  • Reading tuned weights as a diagnostic. The weights learned by minimum error rate training showed that φ(f|e) was nearly useless for Lynx. The authors traced this to the single placeholder symbol and to templates containing no words at all. Inspecting tuned weights can reveal design flaws in a feature set.
  • Aligning the significance test with the metric. The authors adjusted Zhang's significance tester so its BLEU brevity penalty matched NIST's current definition. This keeps confidence intervals consistent with the official metric and is worth doing whenever an evaluation tool and the benchmark definition may drift apart.

Topics: Machine translation

Cite

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

@inproceedings{liu2006tree,
  title = {{Tree-to-String Alignment Template for Statistical Machine Translation}},
  author = {Liu, Yang and Liu, Qun and Lin, Shouxun},
  booktitle = {Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics},
  year = {2006},
  doi = {10.3115/1220175.1220252},
  url = {https://doi.org/10.3115/1220175.1220252}
}

References

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

  1. Hiyan Alshawi, Srinivas Bangalore, and Shona Douglas. 2000. Learning dependency translation models as collections of finite-state head transducers. Computational Linguistics, 26(1):45-60. find
  2. 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(2):263-311. find
  3. Stanley F. Chen and Joshua Goodman. 1998. Am empirical study of smoothing techniques for language modeling. Technical Report TR-10-98, Harvard University Center for Research in Computing Technology. find
  4. David Chiang. 2005. A hierarchical phrase-based model for statistical machine translation. In Proceedings of 43rd Annual Meeting of the ACL, pages 263-270. find our card
  5. Yuan Ding and Martha Palmer. 2005. Machine translation using probabilistic synchronous dependency insert grammars. In Proceedings of 43rd Annual Meeting of the ACL, pages 541-548. find
  6. Michel Galley, Mark Hopkins, Kevin Knight, and Daniel Marcu. 2004. What’s in a translation rule? In Proceedings of NAACL-HLT 2004, pages 273-280. find our card
  7. Jonathan Graehl and Kevin Knight. 2004. Training tree transducers. In Proceedings of NAACL-HLT 2004, pages 105-112. find our card
  8. Philipp Koehn, Franz J. Och, and Daniel Marcu. 2003. Statistical phrase-based translation. In Proceedings of HLT-NAACL 2003, pages 127-133. find
  9. Philipp Koehn. 2004. Pharaoh: a beam search decoder for phrase-based statistical machine trnasla-tion models. In Proceedings of the Sixth Conference of the Association for Machine Translation in the Americas, pages 115-124. find
  10. Yang Liu, Qun Liu, and Shouxun Lin. 2005. Log-linear models for word alignment. In Proceedings of 43rd Annual Meeting of the ACL, pages 459-466. find
  11. Daniel Marcu and William Wong. 2002. A phrase-based, joint probability model for statistical machine translation. In Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 133-139. find
  12. Dan Melamed. 2004. Statistical machine translation by parsing. In Proceedings of 42nd Annual Meeting of the ACL, pages 653-660. find
  13. Franz J. Och and Hermann Ney. 2000. Improved statistical alignment models. In Proceedings of 38th Annual Meeting of the ACL, pages 440-447. find
  14. Franz J. Och and Hermann Ney. 2002. Discriminative training and maximum entropy models for statistical machine translation. In Proceedings of 40th Annual Meeting of the ACL, pages 295-302. find
  15. Franz J. Och and Hermann Ney. 2004. The alignment template approach to statistical machine translation. Computational Linguistics, 30(4):417-449. find
  16. Franz J. Och. 2003. Minimum error rate training in statistical machine translation. In Proceedings of 41st Annual Meeting of the ACL, pages 160-167. find
  17. Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002. BLEU: a method for automatic evaluation of machine translation. In Proceedings of 40th Annual Meeting of the ACL, pages 311-318. find our card
  18. Chris Quirk, Arul Menezes, and Colin Cherry. 2005. Dependency treelet translation: Syntactically informed phrasal SMT. In Proceedings of 43rd Annual Meeting of the ACL, pages 271-279. find our card
  19. Andreas Stolcke. 2002. SRILM - an extensible language modeling toolkit. In Proceedings of International Conference on Spoken Language Processing, volume 2, pages 901-904. find
  20. Ashish Venugopal and Stephan Vogel. 2005. Considerations in maximum mutual information and minimum classification error training for statistical machine translation. In Proceedings of the Tenth Conference of the European Association for Machine Translation (EAMT-05). find
  21. Dekai Wu. 1997. Stochastic inversion transduction grammars and bilingual parsing of parallel corpora. Computational Linguistics, 23(3):377-403. find our card
  22. Deyi Xiong, Shuanglong Li, Qun Liu, Shouxun Lin, and Yueliang Qian. 2005. Parsing the Penn Chinese treebank with semantic knowledge. In Proceedings of IJCNLP 2005, pages 70-81. find
  23. Kenji Yamada and Kevin Knight. 2001. A syntax-based statistical translation model. In Proceedings of 39th Annual Meeting of the ACL, pages 523-530. find our card
  24. Ying Zhang, Stephan Vogel, and Alex Waibel. 2004. Interpreting BLEU/NIST scores: How much improvement do we need to have a better system? In Proceedings of the Fourth International Conference on Language Resources and Evaluation (LREC), pages 2051-2054. find