Elamur Research⌕
☰
home / papers / 2008 / A Simple and Effective Hierarchical Phrase Reordering Model

A Simple and Effective Hierarchical Phrase Reordering Model

Summary

Phrase-based statistical MT systems handle word-order changes poorly. Lexicalized reordering models, such as the one in Moses, only classify a phrase as monotone (M), swap (S) or discontinuous (D) relative to its immediate neighbour. Long-distance movements therefore end up in the vague D class. Galley and Manning propose a hierarchical orientation model to address this. During training, orientation is decided by checking whether phrase-extract could build a block of any length next to the current phrase, rather than looking only at a single word or an adjacent phrase. During decoding, adjacent phrases are merged into larger blocks using shift-reduce parsing, which runs alongside left-to-right beam search. This keeps the decoder's asymptotic running time unchanged and avoids cubic-time CKY or Earley parsing. Experiments on NIST Chinese-English and Arabic-English test sets show statistically significant BLEU gains over the word-based (Moses) and phrase-based (Tillman) orientation models. The work matters because it captures reorderings that usually motivate syntax-based MT, such as moving a prepositional phrase around a noun phrase, while keeping the speed of phrase-based decoding.

Key points

  • Three orientation estimators are compared on word-aligned data:
    • word-based, as in Moses;
    • phrase-based, after Tillman 2004;
    • hierarchical, using phrase-extract with no maximum length.
  • Phrase pairs are extracted with a maximum length of 7.
  • Class distributions were estimated on 12M words of Chinese-English data with grow-diag symmetrization:
    • the word-based model puts about 81% of its mass on D;
    • the hierarchical model gives M 0.488, S 0.100 and D 0.412.
  • Chinese-English results use four classes {M, S, Dl, Dr}. The best hierarchical systems reach 34.36, 32.85 and 27.03 BLEU on MT06, MT05 and MT08. The best non-hierarchical systems reach 33.79, 32.32 and 26.32.
  • Arabic-English results show the same pattern. Hierarchical systems reach 45.64 (MT06) and 56.07 (MT05), against 45.01 and 55.52 for the best non-hierarchical systems. All reported differences are significant at the .05 level.
  • A distortion limit of 6 (the Moses default) was used for all test experiments. MERT was rerun separately for each distortion limit when that setting was explored.

Interesting ideas

  • I1. Label by what could be merged. Training labels come from the question of whether any consistent block exists next to the phrase, not from the immediate neighbour alone. This yields far fewer uninformative "discontinuous" labels, and the same trick could clean up other sequence-labelling targets derived from alignments.
  • I2. Use cheap parsing when ambiguity doesn't matter. The trees serve only to group blocks, not to resolve linguistic ambiguity, so a greedy linear-time shift-reduce procedure inside the decoder is enough. Many tasks that seem to need chart parsing may only need such incremental structure.
  • I3. Split the catch-all class. Dividing D into left and right discontinuity helped most where D held much probability mass (Chinese-English) and helped less for Arabic-English. It is a useful diagnostic: refine a default category only when it is large.
  • I4. Give each class its own feature weight. Each orientation class gets a separately tuned log-linear weight instead of a single log-probability feature. Combining local and hierarchical models also adds gains, since each captures different kinds of swaps.
  • I5. Keep training and test labels consistent. The authors suggest part of the gain comes from the hierarchical model's labels meaning the same thing at training and decoding time. Aligning how labels are defined in both phases is worth checking in any pipeline.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Natural language processing

Cited by

181 papers of our library cite it (of the 140884 whose bibliographies we read); 6 of them have a page here, 175 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work.

@inproceedings{galley2008simple,
  title = {{A Simple and Effective Hierarchical Phrase Reordering Model}},
  author = {Galley, Michel and Manning, Christopher D.},
  booktitle = {Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing},
  year = {2008},
  doi = {10.3115/1613715.1613824},
  url = {https://doi.org/10.3115/1613715.1613824}
}

References

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

  1. Yaser Al-Onaizan and Kishore Papineni. 2006. Distortion models for statistical machine translation. In Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the ACL (COLING/ACL), pages 529–536, Morristown, NJ, USA. find
  2. David Chiang. 2005. A hierarchical phrase-based model for statistical machine translation. In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL), pages 263–270, June. find our card
  3. Ronald L. Graham. 1972. An efficient algorithm for determining the convex hull of a finite planar set. Information Processing Letters, 1(4):132–133. find
  4. Liang Huang, Hao Zhang, Daniel Gildea, and Kevin Knight. 2008. Binarization of synchronous context-free grammars. Technical report, University of Pennsylvania. find our card
  5. Philipp Koehn, Franz Josef Och, and Daniel Marcu. 2003. Statistical phrase-based translation. In NAACL ’03: Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology. find
  6. Philipp Koehn, Hieu Hoang, Alexandra Birch Mayne, Christopher Callison-Burch, Marcello Federico, Nicola Bertoldi, Brooke Cowan, Wade Shen, Christine Moran, Richard Zens, Chris Dyer, Ondrej Bojar, Alexandra Constantin, and Evan Herbst. 2007. Moses: Open source toolkit for statistical machine translat… find
  7. Philipp Koehn. 2004a. Pharaoh: a beam search decoder for phrase-based statistical machine translation models. In Proceedings of the Sixth Conference of the Association for Machine Translation in the Americas, pages 115–124. find
  8. Philipp Koehn. 2004b. Statistical significance tests for machine translation evaluation. In Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 388–395. find
  9. M. Maamouri, A. Bies, T. Buckwalter, and W. Mekki. 2004. The Penn Arabic treebank: Building a large-scale annotated Arabic corpus. find
  10. I. Dan Melamed. 2003. Multitext grammars and synchronous parsers. In NAACL ’03: Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology, pages 79–86. find
  11. Eric W. Noreen. 1989. Computer Intensive Methods for Testing Hypotheses. An Introduction. Wiley, New York. find
  12. Franz Josef Och and Hermann Ney. 2004. The alignment template approach to statistical machine translation. Computational Linguistics, 30(4):417–449. find
  13. F. Och, D. Gildea, S. Khudanpur, A. Sarkar, K. Yamada, A. Fraser, S. Kumar, L. Shen, D. Smith, K. Eng, V. Jain, Z. Jin, and D. Radev. 2004. A smorgasbord of features for statistical machine translation. In Proceedings of HLT-NAACL. find our card
  14. Franz Josef Och. 2003. Minimum error rate training for statistical machine translation. In Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics (ACL). find
  15. Stefan Riezler and John T. Maxwell. 2005. On some pitfalls in automatic evaluation and significance testing for MT. In Proceedings of the ACL Workshop on Intrinsic and Extrinsic Evaluation Measures for Machine Translation and/or Summarization, pages 57– 64, June. find
  16. Christoph Tillman. 2004. A unigram orientation model for statistical machine translation. In Proceedings of HLT-NAACL 2004: Short Papers, pages 101–104. find our card
  17. Taro Watanabe, Hajime Tsukada, and Hideki Isozaki. 2006. Left-to-right target generation for hierarchical phrase-based translation. In ACL ’06: Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the ACL, pages 777–784. find
  18. Dekai Wu. 1997. Stochastic inversion transduction grammars and bilingual parsing of parallel corpora. Computational Linguistics, 23(3):377–404. find our card
  19. Deyi Xiong, Qun Liu, and Shouxun Lin. 2006. Maximum entropy based phrase reordering model for statistical machine translation. In ACL-44: Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics, pages… find our card
  20. Richard Zens and Herman Ney. 2006. Discriminative reordering models for statistical machine translation. In Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics (HLT-NAACL): Proceedings of the Workshop on Statistical Machine Translation,… find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/galley-2008-simple-effective-hierarchical-phrase-reordering/