Elamur Research
☰
home / papers / 2008 / Forest-Based Translation

Forest-Based Translation

What it is about

Tree-based translation takes the 1-best parse of the source sentence as input. A parser error then becomes a translation error. The paper proposes decoding over a packed forest, a compact graph that holds exponentially many parses, instead of the single tree. A k-best list is shown to be a poor substitute: a 50-best list usually encodes only five or six binary choices and repeats many subtrees. The decoder works on the forest with the target language model integrated, and rules are matched to forest nodes. On Chinese-English, with training on a large corpus and the NIST test set of 1,082 sentences, the 1-best baseline reaches BLEU-4 of 0.2325. Forest decoding with pruning reaches 0.2485, an absolute gain of 1.6 points, which is 0.8 points better than decoding over 30-best parses and takes less time.

Ideas

For Mova

The code is tools/roundtrip (the parser output and frames) and tools/translate/src/meta.rs (the meta tokens). The forest is a packed set of alternatives, which fits Mova's tables as counted structures. The decoder is not for Mova, but the idea of reading from alternatives instead of one tree answers open problem 1 directly, if the alternatives are counted from the data.

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/P08-1023.pdf

Summary

Tree-to-string translation systems are fast and simple, but they usually rely on a single 1-best parse of the source sentence, so parser mistakes carry over into the translation. Passing k-best lists to the decoder helps only partly: the lists hold few real alternatives, repeat the same subtrees many times, and are slow to decode one by one. Mi, Huang and Liu propose decoding directly over a pruned packed parse forest, a hypergraph that compactly stores exponentially many parses. The decoder pattern-matches tree-to-string rules against local sub-forests to build a translation forest, then searches it with an integrated language model. On Chinese-to-English (NIST test data, BLEU-4), forest decoding beats the 1-best baseline by 1.6 points on the smaller setup and by 1.7 points with 2.2M training pairs. It also outperforms 30-best decoding while running faster. The approach sits between string-based and tree-based MT: it avoids committing to one parse without paying cubic-time parsing costs inside the decoder.

Key points

  • On the smaller setup, the 1-best tree-to-string baseline reaches BLEU 0.2325 (Pharaoh: 0.2182). Forest decoding with pruning threshold p = 12 reaches 0.2485, a significant gain (sign test, p < 0.01).
  • On the large setup (2.2M sentence pairs, plus a second trigram LM trained on part of the Xinhua portion of Gigaword), translation rules alone give these scores:
    • 1-best: 0.2666
    • 30-best: 0.2755
    • forest: 0.2839
  • Adding bilingual phrases (TR+BP) gives these scores:
    • 1-best: 0.2939
    • 30-best: 0.3084
    • forest: 0.3149, i.e. 2.1 points above its 1-best counterpart
  • Forest decoding is both more accurate and faster than k-best decoding, because subtrees shared across parses are processed only once.
  • In an analysis of which parse rank the decoder actually uses:
    • The forest decoder picks the 1-best parse only 23% of the time.
    • About 40% of its chosen trees lie beyond the top-30, 32% beyond the top-100, and 20% beyond the top-1000.

Interesting ideas

  • Pass the parser's whole forest downstream. Instead of passing one tree or an n-best list, give the next component a pruned packed forest. This lets any pipeline that consumes parses, such as semantic parsing or information extraction, delay committing to one analysis at a modest cost.
  • Build the task structure by local pattern matching. Rules are matched top-down against local sub-forests, turning the parse hypergraph into a task-specific hypergraph. The same trick could build other derivation spaces, such as rewriting or generation, directly on ambiguous input.
  • Treat the forest as a virtual ∞-best list. Measuring the rank of the parse the decoder ends up choosing is a simple diagnostic. It shows how far beyond a k-best cutoff the useful analyses lie, which can justify or rule out k-best pipelines in other tasks.
  • Add default fallback hyperedges. For every parse hyperedge, the authors add a fallback that simply translates its children in order. This guarantees the system always produces complete output despite rule-coverage gaps, which is useful for any grammar-driven system.
  • Create phrase rules on the fly for each span. Flat rules are built at decode time from phrase-table entries matching a node's span. The authors suggest the forest's alternative constituents unlock phrases that a single parse would block, so richer input structures can raise the usefulness of existing resources.

Topics: Machine translation

Cite

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

@inproceedings{mi2008forest,
  title = {{Forest-Based Translation}},
  author = {Mi, Haitao and Huang, Liang and Liu, Qun},
  booktitle = {Proceedings of ACL-08: HLT},
  year = {2008},
  url = {https://aclanthology.org/P08-1023/}
}

References

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

  1. Sylvie Billot and Bernard Lang. 1989. The structure of shared forests in ambiguous parsing. In Proceedings of ACL ’89, pages 143–151. find
  2. Eugene Charniak and Mark Johnson. 2005. Coarse-to-fine-grained n-best parsing and discriminative reranking. In Proceedings of the 43rd ACL. find
  3. David Chiang. 2005. A hierarchical phrase-based model for statistical machine translation. In Proceedings of ACL, pages 263–270, Ann Arbor, Michigan, June. find our card
  4. David Chiang. 2007. Hierarchical phrase-based translation. Comput. Linguist., 33(2):201–228. find our card
  5. Michael Collins, Philipp Koehn, and Ivona Kucerova. 2005. Clause restructuring for statistical machine translation. In Proceedings of ACL, pages 531–540, Ann Arbor, Michigan, June. find
  6. Yuan Ding and Martha Palmer. 2005. Machine translation using probabilistic synchronous dependency insertion grammars. In Proceedings of ACL, pages 541– 548, Ann Arbor, Michigan, June. find our card
  7. Michel Galley, Mark Hopkins, Kevin Knight, and Daniel Marcu. 2004. What’s in a translation rule? In HLT-NAACL, pages 273–280, Boston, MA. find our card
  8. Michel Galley, Jonathan Graehl, Kevin Knight, Daniel Marcu, Steve DeNeefe, Wei Wang, and Ignacio Thayer. 2006. Scalable inference and training of context-rich syntactic translation models. In Proceedings of COLING-ACL, pages 961–968, Sydney, Australia, July. find our card
  9. Liang Huang and David Chiang. 2005. Better k-best parsing. In Proceedings of Ninth International Workshop on Parsing Technologies (IWPT-2005), Vancouver, Canada. find
  10. Liang Huang and David Chiang. 2007. Forest rescoring: Faster decoding with integrated language models. In Proceedings of ACL, pages 144–151, Prague, Czech Republic, June. find
  11. Liang Huang, Kevin Knight, and Aravind Joshi. 2006. Statistical syntax-directed translation with extended domain of locality. In Proceedings of AMTA, Boston, MA, August. find our card
  12. Liang Huang. 2008. Forest reranking: Discriminative parsing with non-local features. In Proceedings of ACL, Columbus, OH. find
  13. Dan Klein and Christopher D. Manning. 2001. Parsing and Hypergraphs. In Proceedings of the Seventh International Workshop on Parsing Technologies (IWPT-2001), 17-19 October 2001, Beijing, China. find
  14. Philipp Koehn, Franz Joseph Och, and Daniel Marcu. 2003. Statistical phrase-based translation. In Proceedings of HLT-NAACL, Edmonton, AB, Canada. find
  15. Philipp Koehn. 2004. Pharaoh: a beam search decoder for phrase-based statistical machine translation models. In Proceedings of AMTA, pages 115–124. find
  16. Dekang Lin. 2004. A path-based transfer model for machine translation. In Proceedings of the 20th COLING, Barcelona, Spain. find
  17. Yang Liu, Qun Liu, and Shouxun Lin. 2006. Tree-tostring alignment template for statistical machine translation. In Proceedings of COLING-ACL, pages 609– 616, Sydney, Australia, July. find
  18. Yang Liu, Yun Huang, Qun Liu, and Shouxun Lin. 2007. Forest-to-string statistical translation rules. In Proceedings of ACL, pages 704–711, Prague, Czech Republic, June. find
  19. Franz J. Och. 2003. Minimum error rate training in statistical machine translation. In Proceedings of ACL, pages 160–167. find
  20. Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002. Bleu: a method for automatic evaluation of machine translation. In Proceedings of ACL, pages 311–318, Philadephia, USA, July. find our card
  21. Chris Quirk and Simon Corston-Oliver. 2006. The impact of parse quality on syntactically-informed statistical machine translation. In Proceedings of EMNLP. find
  22. Chris Quirk, Arul Menezes, and Colin Cherry. 2005. Dependency treelet translation: Syntactically informed phrasal SMT. In Proceedings of ACL, pages 271–279, Ann Arbor, Michigan, June. find our card
  23. Andreas Stolcke. 2002. SRILM - an extensible language modeling toolkit. In Proceedings of ICSLP, volume 30, pages 901–904. find
  24. Dekai Wu. 1997. Stochastic inversion transduction grammars and bilingual parsing of parallel corpora. Computational Linguistics, 23(3):377–404. find our card
  25. Deyi Xiong, Shuanglong Li, Qun Liu, and Shouxun Lin. 2005. Parsing the Penn Chinese Treebank with semantic knowledge. In Proceedings of IJCNLP 2005, pages 70–81, Jeju Island, South Korea. find
  26. Hao Zhang, Liang Huang, Daniel Gildea, and Kevin Knight. 2006. Synchronous binarization for machine translation. In Proceedings of HLT-NAACL, New York, NY. find