---
title: "Forest-based Translation Rule Extraction — Mi 2008"
description: "Syntax-based machine translation systems usually learn their translation rules from a single best parse of each training sentence."
authors: ["Haitao Mi", "Liang Huang"]
year: 2008
venue: "Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing"
source: "https://aclanthology.org/D08-1022/"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/mi-2008-forest-based-translation-rule-extraction/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/mi-2008-forest-based-translation-rule-extraction/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2008](https://md.research.elamur.ai/free/en/papers/2008/) / Forest-based Translation Rule Extraction

# Forest-based Translation Rule Extraction

**Authors:** [Haitao Mi](https://md.research.elamur.ai/free/en/authors/haitao-mi/), [Liang Huang](https://md.research.elamur.ai/free/en/authors/liang-huang/) · **Year:** 2008 · **Venue:** Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/D08-1022/) · [PDF](https://aclanthology.org/D08-1022.pdf) · [OpenAlex](https://openalex.org/W1979495315)

**Citations:** 116 citations (openalex-snapshot · 2026-10-14) · [62](#cited-by) in our library, of the 140673 papers whose bibliographies we read

## Summary
Syntax-based machine translation systems usually learn their translation rules from a single best parse of each training sentence. Parser mistakes therefore become wrong or missing rules. Mi and Huang propose extracting tree-to-string rules from a packed parse forest instead. A forest is a hypergraph that shares common subtrees and so represents a very large number of alternative analyses compactly. They generalize the alignment-based extraction procedure of Galley et al. (admissible nodes, minimal and composed rules) from a single tree to such hypergraphs. Rules are weighted with fractional counts derived from the forest. Experiments use Chinese-to-English translation with the Xiong et al. (2005) parser, modified to output pruned forests, in a tree-to-string system. On small data, forest extraction beats 1-best extraction by about 1 BLEU point and beats 30-best extraction by 0.5 points while running about twice as fast. On the larger FBIS data, combining forest-based extraction with the authors' earlier forest-based decoding improves on the baseline by roughly 2.5 BLEU and surpasses Hiero. The work shows that keeping parser ambiguity during training makes linguistically informed MT more robust.

## Key points
- **Small-data BLEU (case-insensitive):**
  - 1-best extraction: 0.2430
  - 30-best extraction: 0.2488
  - forest extraction (pruning p_e = 8): 0.2533
  - Pharaoh: 0.2297
  - The gain over 1-best is significant under the sign test (p \< 0.01).
- **Extraction time** per 1000 sentences was 0.24 s for 1-best, 5.56 s for 30-best and 2.36 s for forest. Decoding with forest-extracted rules took under double the time needed when using 1-best rules.
- **Rule counts:** 1-best gave 440k rules, 30-best 1.2M and forest 3.3M. After filtering on the dev set, 90k, 130k and 188k remained. Of the rules used in 1-best derivations, 16.3% came only from non-1-best parses.
- **Large-data setup:** FBIS (239K sentence pairs, about 6.9M Chinese and 8.9M English words) with a trigram LM trained on part of the Xinhua portion of Gigaword. Pruning was p_e = 5 for extraction and p_d = 10 for decoding.
- **Large-data BLEU:** the 1-best extraction with tree decoding baseline scored 0.2560. Forest extraction with forest decoding scored 0.2816, compared with 0.2738 for Hiero.

## Interesting ideas
- **Use the whole forest, not a k-best list.** K-best lists are highly redundant and cover only a small part of the parse space. Working on the shared hypergraph gives more diversity at lower cost, which applies to any pipeline that consumes uncertain parser output.
- **Weight rules by fractional counts.** Each rule's count comes from the posterior probability of the forest parts it covers, not a hard 0/1 count. Noisy upstream analyses then contribute in proportion to the confidence the model has in them.
- **Prune by marginal probability.** Inside-outside marginals cut the forest down before extraction. A single threshold then controls the trade-off between coverage, speed and rule-table size.
- **Test whether the extra material is actually used.** The authors count how many rules in final derivations exist only because of non-1-best parses. This is a cleaner diagnostic than a BLEU change alone and suits any method that enlarges a resource.
- **Treat uncertainty-aware training and decoding as separate, combinable steps.** Forest-based extraction and forest-based decoding each help, and the gains add up. Handling parser uncertainty at both stages is a reusable design pattern.

*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: [Machine translation](https://md.research.elamur.ai/free/en/shelves/machine-translation/) · [Natural language processing](https://md.research.elamur.ai/free/en/shelves/nlp/)

Topics: [Machine translation](https://md.research.elamur.ai/free/en/topics/machine-translation/)

## Cited by

Cited by

62 papers of our library cite it (of the 140673 whose bibliographies we read); 2 of them have a page here, 60 not yet.

- [Translation Divergences in Chinese–English Machine Translation: An Empirical Investigation](https://md.research.elamur.ai/free/en/papers/deng-2017-translation-divergences-chinese-english-machine/)
- [Effective Use of Function Words for Rule Generalization in Forest-Based Translation](https://md.research.elamur.ai/free/en/papers/wu-2011-effective-use-function-words-rule/)

## Cite

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

```bibtex
@inproceedings{mi2008forest,
  title = {{Forest-based Translation Rule Extraction}},
  author = {Mi, Haitao and Huang, Liang},
  booktitle = {Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing},
  year = {2008},
  doi = {10.3115/1613715.1613745},
  url = {https://doi.org/10.3115/1613715.1613745}
}
```

- [← previous Forest-Based Translation](https://md.research.elamur.ai/free/en/papers/mi-2008-forest-based-translation/)
- [next → GDEX: Automatically Finding Good Dictionary Examples in a Corpus](https://md.research.elamur.ai/free/en/papers/lex-2008-kilgarriff-gdex-examples/)
- [↑ back to papers of 2008](https://md.research.elamur.ai/free/en/papers/2008/)

## References

19 references, 7 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](https://scholar.google.com/scholar?q=Sylvie+Billot+and+Bernard+Lang%2E+1989%2E+The+structure+of+shared+forests+in+ambiguous+parsing%2E+In+Proceedings+of+ACL+%E2%80%9989%2C+pages+143%E2%80%93151%2E)
2. Eugene Charniak and Mark Johnson. 2005. Coarse-to-fine-grained n-best parsing and discriminative reranking. In Proceedings of the 43rd ACL, Ann Arbor, MI. [find](https://scholar.google.com/scholar?q=Eugene+Charniak+and+Mark+Johnson%2E+2005%2E+Coarse%2Dto%2Dfine%2Dgrained+n%2Dbest+parsing+and+discriminative+reranking%2E+In+Proceedings+of+the+43rd+ACL%2C+Ann+Arbor%2C+MI%2E)
3. David Chiang. 2005. A hierarchical phrase-based model for statistical machine translation. In Proceedings of the 43rd ACL, Ann Arbor, MI. [find](https://scholar.google.com/scholar?q=David+Chiang%2E+2005%2E+A+hierarchical+phrase%2Dbased+model+for+statistical+machine+translation%2E+In+Proceedings+of+the+43rd+ACL%2C+Ann+Arbor%2C+MI%2E) [our card](https://md.research.elamur.ai/free/en/papers/chiang-2005-hierarchical-phrase-based-model-statistical/)
4. 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](https://scholar.google.com/scholar?q=Michael+Collins%2C+Philipp+Koehn%2C+and+Ivona+Kucerova%2E+2005%2E+Clause+restructuring+for+statistical+machine+translation%2E+In+Proceedings+of+ACL%2C+pages+531%E2%80%93540%2C+Ann+Arbor%2C+Michigan%2C+June%2E) [our card](https://md.research.elamur.ai/free/en/papers/collins-2005-clause-restructuring-statistical-machine-translation/)
5. Yuan Ding and Martha Palmer. 2005. Machine translation using probablisitic synchronous dependency insertion grammars. In Proceedings of the 43rd ACL, Ann Arbor, MI. [find](https://scholar.google.com/scholar?q=Yuan+Ding+and+Martha+Palmer%2E+2005%2E+Machine+translation+using+probablisitic+synchronous+dependency+insertion+grammars%2E+In+Proceedings+of+the+43rd+ACL%2C+Ann+Arbor%2C+MI%2E)
6. Jay Earley. 1970. An efficient context-free parsing algorithm. Communications of the ACM, 13(2):94–102. [↗](https://doi.org/10.1145/357980.358005)
7. Michel Galley, Mark Hopkins, Kevin Knight, and Daniel Marcu. 2004. What’s in a translation rule? In Proceedings of HLT-NAACL, pages 273–280. [↗](https://doi.org/10.21236/ada460212) [our card](https://md.research.elamur.ai/free/en/papers/galley-2004-what-s-translation-rule/)
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. [find](https://scholar.google.com/scholar?q=Michel+Galley%2C+Jonathan+Graehl%2C+Kevin+Knight%2C+Daniel+Marcu%2C+Steve+DeNeefe%2C+Wei+Wang%2C+and+Ignacio+Thayer%2E+2006%2E+Scalable+inference+and+training+of+context%2Drich+syntactic+translation+models%2E+In+Proceedi) [our card](https://md.research.elamur.ai/free/en/papers/galley-2006-scalable-inference-training-context-rich/)
9. Liang Huang and David Chiang. 2005. Better k-best Parsing. In Proceedings of the Ninth International Workshop on Parsing Technologies (IWPT-2005). [find](https://scholar.google.com/scholar?q=Liang+Huang+and+David+Chiang%2E+2005%2E+Better+k%2Dbest+Parsing%2E+In+Proceedings+of+the+Ninth+International+Workshop+on+Parsing+Technologies+%28IWPT%2D2005%29%2E)
10. Liang Huang and David Chiang. 2007. Forest rescoring: Fast decoding with integrated language models. In Proceedings of ACL, Prague, Czech Rep., June. [find](https://scholar.google.com/scholar?q=Liang+Huang+and+David+Chiang%2E+2007%2E+Forest+rescoring%3A+Fast+decoding+with+integrated+language+models%2E+In+Proceedings+of+ACL%2C+Prague%2C+Czech+Rep%2E%2C+June%2E)
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](https://scholar.google.com/scholar?q=Liang+Huang%2C+Kevin+Knight%2C+and+Aravind+Joshi%2E+2006%2E+Statistical+syntax%2Ddirected+translation+with+extended+domain+of+locality%2E+In+Proceedings+of+AMTA%2C+Boston%2C+MA%2C+August%2E) [our card](https://md.research.elamur.ai/free/en/papers/huang-2006-statistical-syntax-directed-translation-extended/)
12. Liang Huang. 2008. Forest reranking: Discriminative parsing with non-local features. In Proceedings of the ACL: HLT, Columbus, OH, June. [find](https://scholar.google.com/scholar?q=Liang+Huang%2E+2008%2E+Forest+reranking%3A+Discriminative+parsing+with+non%2Dlocal+features%2E+In+Proceedings+of+the+ACL%3A+HLT%2C+Columbus%2C+OH%2C+June%2E)
13. Yang Liu, Qun Liu, and Shouxun Lin. 2006. Tree-tostring alignment template for statistical machine translation. In Proceedings of COLING-ACL, pages 609– 616. [find](https://scholar.google.com/scholar?q=Yang+Liu%2C+Qun+Liu%2C+and+Shouxun+Lin%2E+2006%2E+Tree%2Dtostring+alignment+template+for+statistical+machine+translation%2E+In+Proceedings+of+COLING%2DACL%2C+pages+609%E2%80%93+616%2E)
14. Haitao Mi, Liang Huang, and Qun Liu. 2008. Forest-based translation. In Proceedings of ACL: HLT, Columbus, OH. [find](https://scholar.google.com/scholar?q=Haitao+Mi%2C+Liang+Huang%2C+and+Qun+Liu%2E+2008%2E+Forest%2Dbased+translation%2E+In+Proceedings+of+ACL%3A+HLT%2C+Columbus%2C+OH%2E) [our card](https://md.research.elamur.ai/free/en/papers/mi-2008-forest-based-translation/)
15. Franz Joseph Och. 2003. Minimum error rate training in statistical machine translation. In Proceedings of ACL, pages 160–167. [find](https://scholar.google.com/scholar?q=Franz+Joseph+Och%2E+2003%2E+Minimum+error+rate+training+in+statistical+machine+translation%2E+In+Proceedings+of+ACL%2C+pages+160%E2%80%93167%2E)
16. Chris Quirk, Arul Menezes, and Colin Cherry. 2005. Dependency treelet translation: Syntactically informed phrasal smt. In Proceedings of the 43rd ACL, Ann Arbor, MI. [find](https://scholar.google.com/scholar?q=Chris+Quirk%2C+Arul+Menezes%2C+and+Colin+Cherry%2E+2005%2E+Dependency+treelet+translation%3A+Syntactically+informed+phrasal+smt%2E+In+Proceedings+of+the+43rd+ACL%2C+Ann+Arbor%2C+MI%2E) [our card](https://md.research.elamur.ai/free/en/papers/quirk-2005-dependency-treelet-translation-syntactically-informed/)
17. Ashish Venugopal, Andreas Zollmann, Noah A. Smith, and Stephan Vogel. 2008. Wider pipelines: N-best alignments and parses in mt training. In Proceedings of AMTA, Honolulu, Hawaii. [↗](https://doi.org/10.5445/ir/1000166368)
18. Wei Wang, Kevin Knight, and Daniel Marcu. 2007. Binarizing syntax trees to improve syntax-based machine translation accuracy. In Proceedings of EMNLP, Prague, Czech Rep., July. [find](https://scholar.google.com/scholar?q=Wei+Wang%2C+Kevin+Knight%2C+and+Daniel+Marcu%2E+2007%2E+Binarizing+syntax+trees+to+improve+syntax%2Dbased+machine+translation+accuracy%2E+In+Proceedings+of+EMNLP%2C+Prague%2C+Czech+Rep%2E%2C+July%2E)
19. 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. [find](https://scholar.google.com/scholar?q=Deyi+Xiong%2C+Shuanglong+Li%2C+Qun+Liu%2C+and+Shouxun+Lin%2E+2005%2E+Parsing+the+penn+chinese+treebank+with+semantic+knowledge%2E+In+Proceedings+of+IJCNLP+2005%2C+pages+70%E2%80%9381%2E)