Elamur Research
☰
home / papers / 2007 / Hierarchical Phrase-Based Translation

Hierarchical Phrase-Based Translation

What it is about

This is the full version of the hierarchical model. Rules are extracted from a parallel text with no syntactic annotation, under length and nonterminal limits on the phrases they contain. The model is a synchronous context-free grammar with a log-linear score over features (phrase and lexical weights in both directions, a language model, rule counts and a word penalty). Decoding is a chart parser with cube pruning and k-best lists, and the language model is added in one of three ways, which are compared for time per sentence and BLEU on 400 development sentences. The system, Hiero, is written in Python with a just-in-time compiler. On the Chinese-English test sets, it beats the alignment template system in BLEU, and it beats a monotone version of itself, which is the nearest phrase-based equivalent.

Ideas

For Mova

The code is tools/translate (profile.rs for the search over chunks, measure.rs for the table). The paper's search is a chart with pruning, which is deterministic if the beam ordering uses ordered maps. The monotone control is the cheapest check to add, and it is the first measure to take before any change to the search.

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/J07-2003.pdf

Summary

Phrase-based statistical MT systems handle local reordering well, but they struggle to move whole groups of phrases, such as Chinese prepositional phrases or relative clauses that must appear on the opposite side in English. Chiang proposes Hiero, a model built on hierarchical phrases: translation pairs with gaps that can be filled by other phrases. Formally, Hiero is a synchronous CFG with essentially a single generic nonterminal. Its rules are extracted from word-aligned parallel text (GIZA++ run in both directions, with the alignments merged) without any treebank or parser. The system combines this grammar with log-linear features, minimum-error-rate training and an m-gram language model. Decoding uses a modified CKY parser with a new technique called cube pruning, which keeps language-model integration fast. On Chinese–English NIST test sets, Hiero clearly outperforms the phrase-based Alignment Template System (ATS) and a monotone phrase-only version of itself. The paper matters because it was, by the author's account, the first grammar-based system to beat strong phrase-based systems at large scale.

Key points

  • BLEU results: Hiero scored 33.72 on MT03, 34.57 on MT04 and 31.79 on MT05. ATS scored 30.84, 31.74 and 30.50, and Hiero Monotone scored 28.27, 28.83 and 26.35. All of Hiero's gains are significant (sign test, p < 0.01).
  • Rule extraction: Rules come from initial phrase pairs consistent with the word alignment. Gapped rules are then formed by replacing sub-phrases with linked nonterminals. Glue rules join the resulting pieces sequentially.
  • Decoding speed: On 400 development sentences, cube pruning took about 23–111 s per sentence and reached a BLEU of 36.1–36.9. Full intersection with the language model took about 1455 s for 37.09, and simple k-best rescoring reached only about 33.3.
  • Grammar size: Filtered for the development set, Hiero's grammar holds about 3.7M rules, compared with roughly 448K phrases for the monotone baseline.
  • Evaluation history: An earlier version of the system was the University of Maryland's primary entry in the 2005 NIST MT Evaluation.

Topics: Machine translation

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.1162/coli.2007.33.2.201

@article{chiang2007hierarchical,
  title = {{Hierarchical Phrase-Based Translation}},
  author = {Chiang, David},
  journal = {Computational Linguistics},
  year = {2007},
  doi = {10.1162/coli.2007.33.2.201},
  url = {https://doi.org/10.1162/coli.2007.33.2.201}
}

References

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

  1. Alshawi, Hiyan, Srinivas Bangalore, and Shona Douglas. 2000. Learning dependency translation models as collections of finite-state head transducers. Computational Linguistics, 26:45–60. find
  2. Bar-Hillel, Yehoshua, M. Perles, and E. Shamir. 1964. On formal properties of simple phrase structure grammars. In Yehoshua Bar-Hillel, editor, Language and Information: Selected Essays on their Theory and Application. Addison-Wesley, Reading, MA, pages 116–150. find
  3. Block, Hans Ulrich. 2000. Example-based incremental synchronous interpretation. In Wolfgang Wahlster, editor, Verbmobil: Foundations of Speech-to-Speech Translation. Springer-Verlag, Berlin, pages 411–417. find
  4. Bod, Rens. 1992. A computational model of language performance: Data Oriented Parsing. In Proceedings of the Fourteenth International Conference on Computational Linguistics (COLING), pages 855–859, Nantes, France. MT05 26.35 ± 0.92 30.50 ± 0.95 31.79 ± 0.91 find
  5. Brown, Peter F., 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
  6. Chen, Stanley F. and Joshua Goodman. 1998. An empirical study of smoothing techniques for language modeling. Technical Report TR-10-98, Harvard University Center for Research in Computing Technology. find
  7. Chiang, David. 2005. A hierarchical phrase-based model for statistical machine translation. In Proceedings of the 43rd Annual Meeting of the ACL, pages 263–270, Ann Arbor, MI. find our card
  8. Chiang, David, Adam Lopez, Nitin Madnani, Christof Monz, Philip Resnik, and Michael Subotin. 2005. The Hiero machine translation system: Extensions, evaluation, and analysis. In Proceedings of HLT/EMNLP 2005, pages 779–786, Vancouver, Canada. find
  9. Collins, Michael, Philipp Koehn, and Ivona Kučerová. 2005. Clause restructuring for statistical machine translation. In Proceedings of the 43rd Annual Meeting of the ACL, pages 531–540, Ann Arbor, MI. find
  10. Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2001. Introduction to Algorithms. MIT Press, second edition, Cambridge, MA. find
  11. Ding, Yuan and Martha Palmer. 2005. Machine translation using probabilistic synchronous dependency insertion grammars. In Proceedings of the 43rd Annual Meeting of the ACL, pages 541–548, Ann Arbor, MI. find our card
  12. Galley, Michel, Mark Hopkins, Kevin Knight, and Daniel Marcu. 2004. What’s in a translation rule? In Proceedings of HLT-NAACL 2004, pages 273–280, Boston, MA. find our card
  13. Goodman, Joshua. 1999. Semiring parsing. Computational Linguistics, 25:573–605. find
  14. Huang, Liang and David Chiang. 2005. Better k-best parsing. In Proceedings of the Ninth International Workshop on Parsing Technologies (IWPT), pages 53–64, Vancouver, Canada. find
  15. Kneser, Reinhard and Hermann Ney. 1995. Improved backing-off for M-gram language modeling. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing, pages 181–184, Detroit, MI. find
  16. Koehn, Philipp. 2003. Noun Phrase Translation. Ph.D. thesis, University of Southern California, Los Angeles, CA. find
  17. Koehn, Philipp, Franz Josef Och, and Daniel Marcu. 2003. Statistical phrase-based translation. In Proceedings of HLT-NAACL 2003, pages 127–133, Edmonton, Canada. find
  18. Kumar, Shankar, Yonggang Deng, and William Byrne. 2006. A weighted finite state transducer translation template model for statistical machine translation. Natural Language Engineering, 12:35–75. find
  19. Lewis, P. M., II and R. E. Stearns. 1968. Syntax-directed transduction. Journal of the ACM, 15:465–488. find
  20. Magerman, David M. 1995. Statistical decision-tree models for parsing. In Proceedings of the 33rd Annual Meeting of the ACL, pages 276–283, Cambridge, MA. find
  21. Marcu, Daniel and William Wong. 2002. A phrase-based, joint probability model for statistical machine translation. In Proceedings of EMNLP 2002, pages 133–139, Philadelphia, PA. find
  22. Och, Franz Josef. 2003. Minimum error rate training in statistical machine translation. In Proceedings of the 41st Annual Meeting of the ACL, pages 160–167, Sapporo, Japan. find
  23. Och, Franz Josef and Hermann Ney. 2000. Improved statistical alignment models. In Proceedings of the 38th Annual Meeting of the ACL, pages 440–447, Hong Kong. find
  24. Och, Franz Josef and Hermann Ney. 2002. Discriminative training and maximum entropy models for statistical machine translation. In Proceedings of the 40th Annual Meeting of the ACL, pages 295–302, Philadelphia, PA. find
  25. Och, Franz Josef and Hermann Ney. 2004. The alignment template approach to statistical machine translation. Computational Linguistics, 30:417–449. find
  26. Och, Franz Josef, Ignacio Thayer, Daniel Marcu, Kevin Knight, Dragos Stefan Munteanu, Quamrul Tipu, Michel Galley, and Mark Hopkins. 2004. Arabic and Chinese MT at USC/ISI. Presentation given at NIST Machine Translation Evaluation Workshop, Alexandria, VA. find
  27. Papineni, Kishore, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002. B LEU : a method for automatic evaluation of machine translation. In Proceedings of the 40th Annual Meeting of the ACL, pages 311–318, Philadelphia, PA. find
  28. Probst, Katharina, Lori Levin, Erik Peterson, Alon Lavie, and Jaime Carbonell. 2002. MT for minority languages using elicitation-based learning of syntactic transfer rules. Machine Translation, 17:245–270. find
  29. Quirk, Chris, Arul Menezes, and Colin Cherry. 2005. Dependency treelet translation: Syntactically informed phrasal SMT. In Proceedings of the 43rd Annual Meeting of the ACL, pages 271–279, Ann Arbor, MI. find our card
  30. Rigo, Armin. 2004. Representation-based just-in-time specialization and the Psyco prototype for Python. In Nevin Heintze and Peter Sestoft, editors, Proceedings of the 2004 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-based Program Manipulation, pages 15–26, Verona, Italy. find
  31. Shieber, Stuart M., Yves Schabes, and Fernando C. N. Pereira. 1995. Principles and implementation of deductive parsing. Journal of Logic Programming, 24:3–36. find
  32. Simard, Michel, Nicola Cancedda, Bruno Cavestro, Marc Dymetman, Eric Gaussier, Cyril Goutte, Kenji Yamada, Philippe Langlais, and Arne Mauser. 2005. Translating with non-contiguous phrases. In Proceedings of HLT/EMNLP 2005, pages 755–762, Ann Arbor, MI. find
  33. Stolcke, Andreas. 2002. SRILM – an extensible language modeling toolkit. In Proceedings of the International Conference on Spoken Language Processing, volume 2, pages 901–904, Denver, CO. find
  34. Thayer, Ignacio, Emil Ettelaie, Kevin Knight, Daniel Marcu, Dragos Stefan Munteanu, Franz Joseph Och, and Quamrul Tipu. 2004. The ISI/USC MT system. In Proceedings of IWSLT 2004, pages 59–60, Kyoto, Japan. find
  35. Tillmann, Christoph. 2004. A unigram orientation model for statistical machine translation. In Proceedings of HLT-NAACL 2004, pages 101–104. Companion volume, Boston, MA. find
  36. Tillmann, Christoph and Tong Zhang. 2005. A localized preduction model for statistical machine translation. In Proceedings of the 43rd Annual Meeting of the ACL, pages 557–564, Ann Arbor, MI. find
  37. Wu, Dekai. 1996. A polynomial-time algorithm for statistical machine translation. In Proceedings of the 34th Annual Meeting of the ACL, pages 152–158, Santa Cruz, CA. find
  38. Wu, Dekai. 1997. Stochastic inversion transduction grammars and bilingual parsing of parallel corpora. Computational Linguistics, 23:377–404. find our card
  39. Xia, Fei and Michael McCord. 2004. Improving a statistical MT system with automatically learned rewrite patterns. In Proceedings of the Twentienth International Conference on Computational Linguistics (COLING), pages 508–514, Geneva, Switzerland. find
  40. Yamada, Kenji and Kevin Knight. 2001. A syntax-based statistical translation model. In Proceedings of the 39th Annual Meeting of the ACL, pages 523–530, Toulouse, France. find our card
  41. Zens, Richard and Hermann Ney. 2004. Improvements in phrase-based statistical machine translation. In Proceedings of HLT-NAACL 2004, pages 257–264, Boston, MA. find