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

• I1. Keep the reader's alternatives: the translator reads each verse from one parse, and the parser errors show up as attachment noise (open problem 1). Store the top alternative heads of each meta token in a packed structure, one node per token with its candidate heads, and let the encoder choose among them.
• I2. Measure the k-best cost first: count how many distinct meta-world trees the reader gives per verse for k = 1, 5, 30, with the same tables. If the count grows fast, a packed form is needed; if not, a list is enough.
• I3. Pack by concept, not by word: the forest nodes can be meta tokens with the same concept and span, so that the candidates for one concept are shared across verses. Keep the nodes in BTreeMap order so the run is deterministic.
• I4. Control: the paper's gain is compared with a 30-best list of the same model. The translator should compare its packed reader with a 1-best and a k-best reader on the same dev verses, and report exact match for each.

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.

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

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/mi-2008-forest-based-translation/