Elamur Research⌕
☰
home / papers / 2006 / Maximum Entropy Based Phrase Reordering Model for Statistical Machine Translation

Maximum Entropy Based Phrase Reordering Model for Statistical Machine Translation

Paper · 2006 · Deyi Xiong, Qun Liu and Shouxun Lin

Summary

Phrase-based SMT systems need to decide how translated phrases should be ordered. Common solutions have clear weaknesses. Distortion penalties and flat models ignore the content of the phrases. Lexicalized models tie reordering decisions to specific phrase pairs, so they suffer from sparse data and cannot handle phrases unseen in training. The authors adopt the ITG/BTG framework, where any two adjacent blocks are combined either straight or inverted. This turns reordering into a binary classification task, which they solve with a maximum entropy classifier. The classifier uses features drawn from block boundary words rather than whole blocks. They also give an algorithm that harvests all neighbor-block reordering events from a word-aligned bitext. The classifier's output is one feature inside a log-linear translation model, decoded with a CKY-style beam search decoder that builds translations hierarchically. On Chinese-to-English translation (NIST MT-05 and IWSLT-04), the MaxEnt model significantly improves BLEU over the other reordering variants and over a distortion-based Pharaoh baseline. Because the features generalize beyond concrete phrases, the model can reorder blocks never observed in training.

Key points

  • The paper compares four reordering models in the same BTG system:
    • NONE, where reordering is left entirely to the language model.
    • A distortion-style penalty.
    • A flat model with straight probability p_m = 0.95, chosen because Chinese and English word orders are usually similar.
    • The proposed MaxEnt model.
  • Reordering examples are extracted from the bitext without a phrase-length cap. Word alignments come from GIZA-style training in both directions, refined with "grow-diag-final".
  • Decoder settings:
    • Recombination, threshold pruning (α = 0.5) and histogram pruning (n = 40).
    • A lazy k-best list generator (k = 200) for minimum error rate training.
    • Speed is roughly 6 seconds per sentence of 28.3 words on average.
  • Collocation features added little gain but greatly increased the feature count. For scaling, only last-word lexical features were kept.
  • The large-scale setup used 2.4M sentence pairs, two trigram LMs (one trained on Gigaword Xinhua, 181.1M words) and rule-based handling of numbers, times and names. It reached BLEU 0.291 on NIST MT-05.

Interesting ideas

  • I1. Reframe a structured decision as binary classification. Restricting combinations to straight vs. inverted makes reordering a simple, learnable classification problem. The same trick could suit other structure decisions, such as clause ordering or attachment choices.
  • I2. Use features of an item instead of its identity. Describing blocks by boundary words lets the model generalize to unseen phrases. This is valuable for low-resource or morphologically rich languages like Ukrainian, where many phrase pairs are rare.
  • I3. Keep the classifier as a modular sub-model. The MaxEnt score enters the log-linear model as a single real-valued feature. This keeps computation cheap and lets one component be retrained or replaced without touching the others.
  • I4. Prune features for scale based on ablations. The authors dropped collocation features after seeing that they added many parameters for little gain. Checking cost against benefit before scaling up is a good general practice.
  • I5. Compare variants inside one framework. Swapping only the reordering function (none, distortion, flat, MaxEnt) in the same decoder gives a clean comparison. This evaluation design isolates the component under study.

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

 Institutions

🏛️Chinese Academy of SciencesBeijing · China68 works · 22,753 citations🔬Institute of Computing TechnologyBeijing · China18 works · 3,078 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 9,085 worksArtificial Intelligence · 8,888 worksArts and Humanities · 9,296 worksLanguage and Linguistics · 9,206 works

🧭 Topics 1Research subjects and languages the work is about.Machine translation · 958 works

Cite

Cite as Deyi Xiong, Qun Liu and Shouxun Lin. 2006. Maximum Entropy Based Phrase Reordering Model for Statistical Machine Translation. Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics.

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

@inproceedings{xiong2006maximum,
  title = {{Maximum Entropy Based Phrase Reordering Model for Statistical Machine Translation}},
  author = {Deyi Xiong, Qun Liu and Shouxun Lin},
  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.1220241},
  url = {https://doi.org/10.3115/1220175.1220241}
}

References

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

  1. Ashish Venugopal, Stephan Vogel. 2005. Considerations in Maximum Mutual Information and Minimum Classification Error training for Statistical Machine Translation. In the Proceedings of EAMT-05, Budapest, Hungary May 30-31. find
  2. Christoph Tillmann. 2004. A block orientation model for statistical machine translation. In HLT-NAACL, Boston, MA, USA. find
  3. Christoph Tillmann and Tong Zhang. 2005. A Localized Prediction Model for statistical machine translation. In Proceedings of ACL 2005, pages 557–564. find
  4. David Chiang. 2005. A hierarchical phrase-based model for statistical machine translation. In Proceedings of ACL 2005, pages 263–270.
  5. Dekai Wu. 1996. A Polynomial-Time Algorithm for Statistical Machine Translation. In Proceedings of ACL 1996.
  6. Dekai Wu. 1997. Stochastic inversion transduction grammars and bilingual parsing of parallel corpora. Computational Linguistics, 23:377–404.
  7. Franz Josef Och and Hermann Ney. 2000. Improved statistical alignment models. In Proceedings of ACL 2000, pages 440–447.
  8. Franz Josef Och. 2003a. Minimum error rate training in statistical machine translation. In Proceedings of ACL 2003, pages 160–167. find
  9. Franz Josef Och. 2003b. Statistical Machine Translation: From Single-Word Models to Alignment Templates Thesis. find
  10. Franz Josef Och and Hermann Ney. 2004. The alignment template approach to statistical machine translation. Computational Linguistics, 30:417–449. find
  11. Franz Josef Och, 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. find
  12. Heidi J. Fox. 2002. Phrasal cohesion and statistical machine translation. In Proceedings of EMNLP 2002.
  13. J. R. Quinlan. 1993. C4.5: progarms for machine learning. Morgan Kaufmann Publishers. find
  14. Kevin Knight. 1999. Decoding complexity in wordreplace-ment translation models. Computational Linguistics, Squibs & Discussion, 25(4). find
  15. Liang Huang and David Chiang. 2005. Better k-best parsing. In Proceedings of the Ninth International Workshop on Parsing Technology, Vancouver, October, pages 53–64. find
  16. Philipp Koehn, Franz Joseph Och, and Daniel Marcu. 2003. Statistical Phrase-Based Translation. In Proceedings of HLT/NAACL. find
  17. Philipp Koehn. 2004. 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
  18. Philipp Koehn, Amittai Axelrod, Alexandra Birch Mayne, Chris Callison-Burch, Miles Osborne and David Talbot. 2005. Edinburgh System Description for the 2005 IWSLT Speech Translation Evaluation. In International Workshop on Spoken Language Translation.
  19. R. Zens, H. Ney, T. Watanabe, and E. Sumita. 2004. Reordering Constraints for Phrase-Based Statistical Machine Translation. In Proceedings of CoLing 2004, Geneva, Switzerland, pp. 205-211. find
  20. Robert Malouf. 2002. A comparison of algorithms for maximum entropy parameter estimation. In Proceedings of the Sixth Conference on Natural Language Learning (CoNLL-2002).
  21. Shankar Kumar and William Byrne. 2005. Local phrase reordering models for statistical machine translation. In Proceedings of HLT-EMNLP. find
  22. 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 LREC 2004, pages 2051– 2054. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/xiong-2006-maximum-entropy-based-phrase-reordering/