[Mova](https://md.mova.elamur.ai/free/en/) · [this page in HTML](https://mova.elamur.ai/free/en/docs/papers/setiawan-2009-topological-ordering-function-words-hierarchical/)

[home](https://md.mova.elamur.ai/free/en/) / [docs](https://md.mova.elamur.ai/free/en/docs/) / [papers](https://md.mova.elamur.ai/free/en/docs/papers/) / [Machine translation](https://md.mova.elamur.ai/free/en/docs/papers/mtrans/) / Topological Ordering of Function Words in Hierarchical Phrase-based Translation

# Topological Ordering of Function Words in Hierarchical Phrase-based Translation

**Authors:** Hendra Setiawan, Min-Yen Kan, Haizhou Li, Philip Resnik · **Year:** 2009 · **Venue:** ACL-IJCNLP 2009 **Link:** [aclanthology.org/P09-1037](https://aclanthology.org/P09-1037/) · **Licence:** [CC BY-NC-SA 3.0](https://creativecommons.org/licenses/by-nc-sa/3.0/) — summary only

[**13** citations in our library](https://md.mova.elamur.ai/free/en/docs/papers/cited-by/setiawan-2009-topological-ordering-function-words-hierarchical/) of the 140673 papers whose bibliographies we read[Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP](https://aclanthology.org/volumes/P09-1/)[licence](https://creativecommons.org/licenses/by-nc-sa/3.0/)

- [Publisher's page](https://aclanthology.org/P09-1037/)
- [PDF](https://aclanthology.org/P09-1037.pdf)

**Authors (4)**

1. Hendra Setiawan
2. Min-Yen Kan
3. Haizhou Li
4. Philip Resnik

Citations and author metrics from OpenAlex (); authors with the same name are not always told apart.

## What it is about

Hierarchical phrase-based translation builds one kind of nonterminal, so it overgenerates reorderings. The authors propose a pairwise dominance model: for two neighbouring function words in a rule, it says which one sits higher in the derivation (leftFirst, rightFirst, dontCare or neither). The values are counted from maximal consistent alignments and used as a rule feature. Function words are not a linguistic list here but the N most frequent source words, N from 32 to 2048. On Chinese-English the model with N = 128 raised BLEU from 30.58 to 31.59 on MT06 and from 24.08 to 24.91 on MT08 (significant on MT06); on Arabic-English N = 128 gave 41.56 to 42.66 on MT06. Larger N adds content words and gains less, and N = 32 hurts.

## Ideas

- I1. Dominance values for target function words. In `lin.rs`, for each pair of neighbouring function words, count from verse pairs which one sits higher in the target tree, keep the four values in a BTreeMap, and use them when the linearizer chooses between two orders of neighbouring particles. Measure the order-class residual on dev.
- I2. Frequency as the function-word set. Take the N most frequent tokens of each language's corpus as the function-word set, as the paper does, and compare it with the hand-written list. Report the residual for N = 32, 64, 128, 256, run twice.
- I3. A count threshold. Keep a dominance value only when its count passes a cut; a value seen rarely should fall back to dontCare, the paper's safe default.
- I4. An author diagnostic. Compare the dominance values across author pairs. Where two translators disagree on a pair, that pair is a candidate for an override in the author delta.

## For Mova

The model is count-based and fits the translator's BTreeMap tables. It attacks the same order errors as problem 4 (function words as features) and problem 6 (archaic word order). The Chinese and Arabic results do not transfer to English-only work, so measure on Bible verses first.

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

## Cite

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

```
@inproceedings{setiawan2009topological,
  title = {{Topological Ordering of Function Words in Hierarchical Phrase-based Translation}},
  author = {Setiawan, Hendra and Kan, Min-Yen and Li, Haizhou and Resnik, Philip},
  booktitle = {Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP},
  year = {2009},
  url = {https://aclanthology.org/P09-1037/}
}
```

- [← previous UNL-French deconversion as transfer & generation from an interlingua with possible quality enhancement through offline human interaction](https://md.mova.elamur.ai/free/en/docs/papers/serasset-1999-unl-french-deconversion-as-transfer/)
- [next → Machine Translation, Linguistics, and Interlingua](https://md.mova.elamur.ai/free/en/docs/papers/sgall-1987-machine-translation-linguistics-interlingua/)
- [↑ back to Machine translation](https://md.mova.elamur.ai/free/en/docs/papers/mtrans/)

## References

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

1. David Chiang, Yuval Marton, and Philip Resnik. 2008. [find](https://scholar.google.com/scholar?q=David+Chiang%2C+Yuval+Marton%2C+and+Philip+Resnik%2E+2008%2E)
2. Online large-margin training of syntactic and structural translation features. In Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 224–233, Honolulu, Hawaii, October. [find](https://scholar.google.com/scholar?q=Online+large%2Dmargin+training+of+syntactic+and+structural+translation+features%2E+In+Proceedings+of+the+2008+Conference+on+Empirical+Methods+in+Natural+Language+Processing%2C+pages+224%C2%96233%2C+Honolulu%2C+Hawai)
3. David Chiang. 2005. A hierarchical phrase-based model for statistical machine translation. [find](https://scholar.google.com/scholar?q=David+Chiang%2E+2005%2E+A+hierarchical+phrase%2Dbased+model+for+statistical+machine+translation%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/chiang-2005-hierarchical-phrase-based-model-statistical/)
4. David Chiang. 2007. Hierarchical phrase-based translation. Computational Linguistics, 33(2):201–228. [find](https://scholar.google.com/scholar?q=David+Chiang%2E+2007%2E+Hierarchical+phrase%2Dbased+translation%2E+Computational+Linguistics%2C+33%282%29%3A201%C2%96228%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/chiang-2007-hierarchical-phrase-based-translation/)
5. Jiaying Howard. 2002. A Student Handbook for Chinese Function Words. The Chinese University Press. [find](https://scholar.google.com/scholar?q=Jiaying+Howard%2E+2002%2E+A+Student+Handbook+for+Chinese+Function+Words%2E+The+Chinese+University+Press%2E)
6. Gonzalo Iglesias, Adria de Gispert, Eduardo R. Banga, and William Byrne. 2009. Rule ltering by pattern for efcient hierarchical translation. In Proceedings of the 12th Conference of the European Chapter of the Association of Computational Linguistics (to appear). [find](https://scholar.google.com/scholar?q=Gonzalo+Iglesias%2C+Adria+de+Gispert%2C+Eduardo+R%2E+Banga%2C+and+William+Byrne%2E+2009%2E+Rule+%02ltering+by+pattern+for+ef%02cient+hierarchical+translation%2E+In+Proceedings+of+the+12th+Conference+of+the+European+Cha)
7. R. Kneser and H. Ney. 1995. Improved backing-off for m-gram language modeling. [find](https://scholar.google.com/scholar?q=R%2E+Kneser+and+H%2E+Ney%2E+1995%2E+Improved+backing%2Doff+for+m%2Dgram+language+modeling%2E)
8. Philipp Koehn, Franz J. Och, and Daniel Marcu. 2003. [find](https://scholar.google.com/scholar?q=Philipp+Koehn%2C+Franz+J%2E+Och%2C+and+Daniel+Marcu%2E+2003%2E)
9. Statistical phrase-based translation. In Proceedings of the 2003 Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics, pages 127–133, Edmonton, Alberta, Canada, May. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Statistical+phrase%2Dbased+translation%2E+In+Proceedings+of+the+2003+Human+Language+Technology+Conference+of+the+North+American+Chapter+of+the+Association+for+Computational+Linguistics%2C+pages+127%C2%96133%2C+Edm)
10. Philipp Koehn. 2004. Statistical signicance tests for In Proceedings of machine translation evaluation. [find](https://scholar.google.com/scholar?q=Philipp+Koehn%2E+2004%2E+Statistical+signi%02cance+tests+for+In+Proceedings+of+machine+translation+evaluation%2E)
11. EMNLP 2004, pages 388–395, Barcelona, Spain, July. [find](https://scholar.google.com/scholar?q=EMNLP+2004%2C+pages+388%C2%96395%2C+Barcelona%2C+Spain%2C+July%2E)
12. Yuval Marton and Philip Resnik. 2008. Soft syntactic constraints for hierarchical phrased-based translation. [find](https://scholar.google.com/scholar?q=Yuval+Marton+and+Philip+Resnik%2E+2008%2E+Soft+syntactic+constraints+for+hierarchical+phrased%2Dbased+translation%2E)
13. In Proceedings of The 46th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pages 1003– 1011, Columbus, Ohio, June. Franz Josef Och and Hermann Ney. 2002. Discriminative training and maximum entropy models for statistical machine translation. [find](https://scholar.google.com/scholar?q=In+Proceedings+of+The+46th+Annual+Meeting+of+the+Association+for+Computational+Linguistics%3A+Human+Language+Technologies%2C+pages+1003%C2%96+1011%2C+Columbus%2C+Ohio%2C+June%2E+Franz+Josef+Och+and+Hermann+Ney%2E+2002%2E+)
14. Franz Josef Och and Hermann Ney. 2004. The alignment template approach to statistical machine translation. Computational Linguistics, 30(4):417–449. [find](https://scholar.google.com/scholar?q=Franz+Josef+Och+and+Hermann+Ney%2E+2004%2E+The+alignment+template+approach+to+statistical+machine+translation%2E+Computational+Linguistics%2C+30%284%29%3A417%C2%96449%2E)
15. Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. a method for automatic 2002. Bleu: In Proceedings evaluation of machine translation. of 40th Annual Meeting of the Association for Computational Linguistics, pages 311–318, Philadelphia, Pennsylvania, USA, July. [find](https://scholar.google.com/scholar?q=Kishore+Papineni%2C+Salim+Roukos%2C+Todd+Ward%2C+and+Wei%2DJing+Zhu%2E+a+method+for+automatic+2002%2E+Bleu%3A+In+Proceedings+evaluation+of+machine+translation%2E+of+40th+Annual+Meeting+of+the+Association+for+Computat)
16. Hendra Setiawan, Min-Yen Kan, and Haizhou Li. 2007. Ordering phrases with function words. [find](https://scholar.google.com/scholar?q=Hendra+Setiawan%2C+Min%2DYen+Kan%2C+and+Haizhou+Li%2E+2007%2E+Ordering+phrases+with+function+words%2E)
17. In Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 712– 719, Prague, Czech Republic, June. Libin Shen, Jinxi Xu, and Ralph Weischedel. 2008. [find](https://scholar.google.com/scholar?q=In+Proceedings+of+the+45th+Annual+Meeting+of+the+Association+of+Computational+Linguistics%2C+pages+712%C2%96+719%2C+Prague%2C+Czech+Republic%2C+June%2E+Libin+Shen%2C+Jinxi+Xu%2C+and+Ralph+Weischedel%2E+2008%2E)
18. A new string-to-dependency machine translation algorithm with a target dependency language model. In Proceedings of The 46th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pages 577–585, Columbus, Ohio, June. David Vilar, Daniel Stein, and Hermann Ney. 2008. [find](https://scholar.google.com/scholar?q=A+new+string%2Dto%2Ddependency+machine+translation+algorithm+with+a+target+dependency+language+model%2E+In+Proceedings+of+The+46th+Annual+Meeting+of+the+Association+for+Computational+Linguistics%3A+Human+Lang) [our card](https://md.mova.elamur.ai/free/en/docs/papers/shen-2008-new-string-dependency-machine-translation/)
19. Analysing soft syntax features and heuristics for hierarchical phrase based machine translation. International Workshop on Spoken Language Translation 2008, pages 190–197, October. [find](https://scholar.google.com/scholar?q=Analysing+soft+syntax+features+and+heuristics+for+hierarchical+phrase+based+machine+translation%2E+International+Workshop+on+Spoken+Language+Translation+2008%2C+pages+190%C2%96197%2C+October%2E)
20. Dekai Wu. 1997. Stochastic inversion transduction grammars and bilingual parsing of parallel corpora. [find](https://scholar.google.com/scholar?q=Dekai+Wu%2E+1997%2E+Stochastic+inversion+transduction+grammars+and+bilingual+parsing+of+parallel+corpora%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/wu-1997-stochastic-inversion-transduction-grammars-bilingual/)
21. Computational Linguistics, 23(3):377–404, Sep. Tiejun Zhao, Yajuan Lv, Jianmin Yao, Hao Yu, Muyun Yang, and Fang Liu. 2001. Increasing accuracy of chinese segmentation with strategy of multi-step processing. [find](https://scholar.google.com/scholar?q=Computational+Linguistics%2C+23%283%29%3A377%C2%96404%2C+Sep%2E+Tiejun+Zhao%2C+Yajuan+Lv%2C+Jianmin+Yao%2C+Hao+Yu%2C+Muyun+Yang%2C+and+Fang+Liu%2E+2001%2E+Increasing+accuracy+of+chinese+segmentation+with+strategy+of+multi%2Dstep+proc)
22. Journal of Chinese Information Processing (Chinese Version), 1:13–18. Bowen Zhou, Bing Xiang, Xiaodan Zhu, and Yuqing Gao. 2008. Prior derivation models for formally syntax-based translation using linguistically syntactic parsing and tree kernels. [find](https://scholar.google.com/scholar?q=Journal+of+Chinese+Information+Processing+%28Chinese+Version%29%2C+1%3A13%C2%9618%2E+Bowen+Zhou%2C+Bing+Xiang%2C+Xiaodan+Zhu%2C+and+Yuqing+Gao%2E+2008%2E+Prior+derivation+models+for+formally+syntax%2Dbased+translation+using+lin)
23. Andreas Zollmann and Ashish Venugopal. 2006. Syntax augmented machine translation via chart parsing. [find](https://scholar.google.com/scholar?q=Andreas+Zollmann+and+Ashish+Venugopal%2E+2006%2E+Syntax+augmented+machine+translation+via+chart+parsing%2E)