[Mova](https://md.mova.elamur.ai/free/en/) · [this page in HTML](https://mova.elamur.ai/free/en/docs/papers/zabokrtsky-2009-hidden-markov-tree-model-dependency/)

[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/) / Hidden Markov Tree Model in Dependency-based Machine Translation

# Hidden Markov Tree Model in Dependency-based Machine Translation

**Authors:** [Zdeněk Žabokrtský](https://md.mova.elamur.ai/free/en/docs/papers/authors/zdenek-zabokrtsku/), [Martin Popel](https://md.mova.elamur.ai/free/en/docs/papers/authors/martin-popel/) · **Year:** 2009 · **Venue:** Proceedings of the ACL-IJCNLP 2009 Conference Short Papers **Link:** [aclanthology.org/P09-2037](https://aclanthology.org/P09-2037/) · **Licence:** [CC BY-NC-SA 3.0](https://creativecommons.org/licenses/by-nc-sa/3.0/) — summary only

[**12** citations in our library](https://md.mova.elamur.ai/free/en/docs/papers/cited-by/zabokrtsky-2009-hidden-markov-tree-model-dependency/) of the 140673 papers whose bibliographies we read[Proceedings of the ACL-IJCNLP 2009 Conference Short Papers](https://aclanthology.org/volumes/P09-2/)[licence](https://creativecommons.org/licenses/by-nc-sa/3.0/)

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

**Authors (2)**

1. Zdeněk Žabokrtský
2. Martin Popel

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

## What it is about

The paper applies Hidden Markov Tree Models (HMTM), a tree version of the hidden Markov chain, to the transfer step of a tree-based MT system. The source tree is the observed labelling, and the target tree is the hidden labelling. Each node carries a pair (lemma, formeme) on both sides. The emission probability is a backward translation model, and the transition probability is a model of the target tree given the parent, so the two parts can be estimated separately from a parallel and a monolingual corpus. A modified Viterbi algorithm finds the best target labelling over the whole tree in one pass. The model needs the source and target trees to have the same shape, which the paper argues is roughly true for deep-syntactic trees. Trained on 800 million words of Czech and a 60 million word parallel corpus, the model is tested on 2,700 WMT 2009 English-Czech sentences. It raises BLEU from 0.0898 to 0.1043 and NIST from 4.567 to 4.845 over the transfer step it replaces.

## Ideas

- I1. A tree Viterbi over meta tokens: give the reader's meta-world tree a count-based emission (source concept and tag given target concept and tag) and a transition (child target given parent target, by relation). Find the best target labelling in one pass and compare with the greedy per-token choice in `tools/translate/src/profile.rs`, run twice for identical output.
- I2. Factor the encoder into channels, as the paper does: the lexical choice (concept), the surface form (function words and case, the formeme idea) and the grammatical categories (number, person from UD FEATS, open problems 4 and 5). Measure the residual bits per channel, so each factor is judged on its own.
- I3. Check the isomorphism assumption before using it: count the share of verse pairs (KJV against WEB, say) whose meta trees have the same shape after the reader. If the share is low, the transition model is not usable on those pairs.
- I4. Controls: run emission-only against emission plus transition on the same dev split. The paper's gain is small, so the transition term must show a gain on dev, not only in the sum of scores.

## For Mova

The code is `tools/translate/src/profile.rs` (the encoder) and `tools/translate/src/meta.rs` (the meta tokens). The paper is statistical with simple count tables, which is the form Mova needs. Its HMTM is not a neural model, so the whole idea carries over. The main risk is the same-shape assumption, which is open problem 1 in another form.

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{zabokrtsku2009hidden,
  title = {{Hidden Markov Tree Model in Dependency-based Machine Translation}},
  author = {Žabokrtský, Zdeněk and Popel, Martin},
  booktitle = {Proceedings of the ACL-IJCNLP 2009 Conference Short Papers},
  year = {2009},
  url = {https://aclanthology.org/P09-2037/}
}
```

- [← previous Fast and Accurate Non-Projective Dependency Tree Linearization](https://md.mova.elamur.ai/free/en/docs/papers/yu-2020-fast-accurate-non-projective-dependency/)
- [next → Russian-English system, Georgetown University](https://md.mova.elamur.ai/free/en/docs/papers/zarechnak-1976-russian-english-system-georgetown-university/)
- [↑ back to Machine translation](https://md.mova.elamur.ai/free/en/docs/papers/mtrans/)

## References

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

1. Igor Boguslavsky, Leonid Iomdin, and Victor Sizov. 2004. Multilinguality in ETAP-3: Reuse of Lexical Resources. In Proceedings of Workshop Multilingual Linguistic Resources, COLING, pages 7–14. [find](https://scholar.google.com/scholar?q=Igor+Boguslavsky%2C+Leonid+Iomdin%2C+and+Victor+Sizov%2E+2004%2E+Multilinguality+in+ETAP%2D3%3A+Reuse+of+Lexical+Resources%2E+In+Proceedings+of+Workshop+Multilingual+Linguistic+Resources%2C+COLING%2C+pages+7%E2%80%9314%2E)
2. Ondřej Bojar. 2008. Exploiting Linguistic Data in Machine Translation. Ph.D. thesis, ÚFAL, MFF UK, Prague, Czech Republic. [find](https://scholar.google.com/scholar?q=Ondr%CC%8Cej+Bojar%2E+2008%2E+Exploiting+Linguistic+Data+in+Machine+Translation%2E+Ph%2ED%2E+thesis%2C+U%CC%81FAL%2C+MFF+UK%2C+Prague%2C+Czech+Republic%2E)
3. Peter E. Brown, Vincent J. Della Pietra, Stephen A. Della Pietra, and Robert L. Mercer. 1993. The mathematics of statistical machine translation: Parameter estimation. Computational Linguistics. [find](https://scholar.google.com/scholar?q=Peter+E%2E+Brown%2C+Vincent+J%2E+Della+Pietra%2C+Stephen+A%2E+Della+Pietra%2C+and+Robert+L%2E+Mercer%2E+1993%2E+The+mathematics+of+statistical+machine+translation%3A+Parameter+estimation%2E+Computational+Linguistics%2E)
4. Matthew Crouse, Robert Nowak, and Richard Baraniuk. 1998. Wavelet-based statistical signal processing using hidden markov models. IEEE Transactions on Signal Processing, 46(4):886–902. [find](https://scholar.google.com/scholar?q=Matthew+Crouse%2C+Robert+Nowak%2C+and+Richard+Baraniuk%2E+1998%2E+Wavelet%2Dbased+statistical+signal+processing+using+hidden+markov+models%2E+IEEE+Transactions+on+Signal+Processing%2C+46%284%29%3A886%E2%80%93902%2E)
5. Michelangelo Diligenti, Paolo Frasconi, and Marco Gori. 2003. Hidden tree Markov models for document image classification. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25:2003. [find](https://scholar.google.com/scholar?q=Michelangelo+Diligenti%2C+Paolo+Frasconi%2C+and+Marco+Gori%2E+2003%2E+Hidden+tree+Markov+models+for+document+image+classification%2E+IEEE+Transactions+on+Pattern+Analysis+and+Machine+Intelligence%2C+25%3A2003%2E)
6. Jean-Baptiste Durand, Paulo Goncalvès, and Yann Guédon. 2004. Computational methods for hidden Markov tree models - An application to wavelet trees. IEEE Transactions on Signal Processing, 52(9):2551–2560. [find](https://scholar.google.com/scholar?q=Jean%2DBaptiste+Durand%2C+Paulo+Goncalve%CC%80s%2C+and+Yann+Gue%CC%81don%2E+2004%2E+Computational+methods+for+hidden+Markov+tree+models+%2D+An+application+to+wavelet+trees%2E+IEEE+Transactions+on+Signal+Processing%2C+52%289%29%3A255)
7. Jan Hajič et al. 2006. Prague Dependency Treebank 2.0. Linguistic Data Consortium, LDC Catalog No.: LDC2006T01, Philadelphia. [find](https://scholar.google.com/scholar?q=Jan+Hajic%CC%8C+et+al%2E+2006%2E+Prague+Dependency+Treebank+2%2E0%2E+Linguistic+Data+Consortium%2C+LDC+Catalog+No%2E%3A+LDC2006T01%2C+Philadelphia%2E)
8. Philipp Koehn, Franz Josef Och, and Daniel Marcu. 2003. Statistical phrase based translation. In Proceedings of the HLT/NAACL. [find](https://scholar.google.com/scholar?q=Philipp+Koehn%2C+Franz+Josef+Och%2C+and+Daniel+Marcu%2E+2003%2E+Statistical+phrase+based+translation%2E+In+Proceedings+of+the+HLT%2FNAACL%2E)
9. Arul Menezes and Stephen D. Richardson. 2001. A best-first alignment algorithm for automatic extraction of transfer mappings from bilingual corpora. In Proceedings of the workshop on Data-driven methods in machine translation, volume 14, pages 1–8. [find](https://scholar.google.com/scholar?q=Arul+Menezes+and+Stephen+D%2E+Richardson%2E+2001%2E+A+best%2Dfirst+alignment+algorithm+for+automatic+extraction+of+transfer+mappings+from+bilingual+corpora%2E+In+Proceedings+of+the+workshop+on+Data%2Ddriven+metho)
10. Petr Sgall. 1967. Generativnı́ popis jazyka a česká deklinace. Academia, Prague, Czech Republic. [find](https://scholar.google.com/scholar?q=Petr+Sgall%2E+1967%2E+Generativn%C4%B1%CC%81+popis+jazyka+a+c%CC%8Ceska%CC%81+deklinace%2E+Academia%2C+Prague%2C+Czech+Republic%2E)
11. Zdeněk Žabokrtský, Jan Ptáček, and Petr Pajas. 2008. TectoMT: Highly Modular MT System with Tectogrammatics Used as Transfer Layer. In Proceedings of the 3rd Workshop on SMT, ACL. [find](https://scholar.google.com/scholar?q=Zdene%CC%8Ck+Z%CC%8Cabokrtsky%CC%81%2C+Jan+Pta%CC%81c%CC%8Cek%2C+and+Petr+Pajas%2E+2008%2E+TectoMT%3A+Highly+Modular+MT+System+with+Tectogrammatics+Used+as+Transfer+Layer%2E+In+Proceedings+of+the+3rd+Workshop+on+SMT%2C+ACL%2E)