---
title: "An Efficient Method for Determining Bilingual — Och 1999"
description: "Statistical machine translation suffers from sparse data."
authors: ["Franz Josef Och"]
year: 1999
venue: "Ninth Conference of the European Chapter of the Association for Computational Linguistics"
source: "https://aclanthology.org/E99-1010/"
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/papers/och-1999-efficient-method-determining-bilingual-word/"
---
[Elamur Research](https://md.research.elamur.ai/) · [this page in HTML](https://research.elamur.ai/free/papers/och-1999-efficient-method-determining-bilingual-word/)

[home](https://md.research.elamur.ai/) / [papers](https://md.research.elamur.ai/free/papers/) / [1999](https://md.research.elamur.ai/free/papers/1999/) / An Efficient Method for Determining Bilingual Word Classes

# An Efficient Method for Determining Bilingual Word Classes

**Authors:** [Franz Josef Och](https://md.research.elamur.ai/free/authors/franz-josef-och/) · **Year:** 1999 · **Venue:** Ninth Conference of the European Chapter of the Association for Computational Linguistics · **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/E99-1010/) · [PDF](https://aclanthology.org/E99-1010.pdf) · [OpenAlex](https://openalex.org/W2083460949)

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

## Summary
Statistical machine translation suffers from sparse data. Word classes are a standard remedy in language modelling, but classes built separately for each language need not line up across a language pair. Och proposes bilingual word clustering, which induces corresponding classes for source and target vocabularies from a parallel corpus.

The method maximizes the joint likelihood of the corpus as the product of a class-based bigram model for the target side and a class-based translation model. The translation model uses Viterbi alignments from an HMM alignment model. The resulting criterion has almost the same form as the monolingual Kneser–Ney clustering objective, so the exchange algorithm with threshold accepting can optimize it efficiently.

Three variants (MONO, BIL, BIL-2) were tested on EUTRANS-I (Spanish–English) and EUTRANS-II (German–English) within the alignment template translation system. Bilingual classes made the translation lexicon less spread out and lowered word error rate compared with both monolingual classes and no classes. The best variant, BIL-2, clusters English monolingually first and then fits source classes to it. Clustering takes seconds to a few hours, so the approach is practical.

## Key points
- **Corpora:**
  - EUTRANS-I is an artificial hotel-reception "Traveller Task" corpus with 10,000 training sentence pairs and vocabularies of 686 Spanish and 513 English words.
  - EUTRANS-II is natural tourism text (web pages, brochures, business letters) with 16,226 pairs and vocabularies of about 39.5k German and 25.8k English words.
- **Number of classes:** 60 for EUTRANS-I and 500 for EUTRANS-II, chosen by final translation quality.
- **Clustering time:** on an Alpha workstation, under 20 seconds for EUTRANS-I and under two hours for EUTRANS-II.
- **WER on EUTRANS-I:** 6.31% with no classes (WORD), 5.64% with MONO, 5.38% with BIL and 4.76% with BIL-2.
- **WER on EUTRANS-II:** 64.3% with WORD, 63.5% with MONO, 63.2% with BIL and 62.5% with BIL-2. On EUTRANS-I, average alignment template length grew from 2.85 (WORD) to 5.19 (BIL-2).

## Interesting ideas
- **Single count table:** Monolingual bigram counts and cross-lingual alignment counts can be merged into one count function, because the two never overlap. A bilingual objective then reduces to a familiar monolingual one, and existing clustering code can be reused with minor changes. The same trick could extend other clustering objectives to multiple views of the data.
- **Anchor one side first:** BIL-2 fixes target classes by monolingual quality and then fits source classes to them. This beat joint optimization, which suggests that staged, asymmetric optimization can outperform a "fully joint" one. It may be worth trying when projecting resources, for example onto Ukrainian, from a well-resourced language.
- **Cheap evaluation of class correspondence:** Two intrinsic measures check whether classes in two languages correspond before any downstream system is run. One is the average ε-mirror size, the number of target classes with non-negligible translation probability. The other is the perplexity of the class translation model on held-out data.
- **Classes as rule generalizers:** Classes let phrase-level translation templates generalize, for example from one city name to all cities. The paper links the quality gain to the longer templates that classes make usable. This explains why classes help, beyond simply smoothing the probabilities.
- **Threshold accepting for local search:** Temporarily accepting a worse objective value is a lightweight alternative to simulated annealing. It is useful for any greedy exchange-style partitioning problem that gets stuck in local optima.

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

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

## Cited by

Cited by

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

- [Don't Throw Those Morphological Analyzers Away Just Yet: Neural Morphological Disambiguation for Arabic](https://md.research.elamur.ai/free/papers/aclbulk-2017-zalmout-don-t-throw-those-morphological/)
- [Massively Multilingual Word Embeddings](https://md.research.elamur.ai/free/papers/ammar-2016-massively-multilingual-word-embeddings/)
- [Translation Divergences in Chinese–English Machine Translation: An Empirical Investigation](https://md.research.elamur.ai/free/papers/deng-2017-translation-divergences-chinese-english-machine/)
- [Inferring Shallow-Transfer Machine Translation Rules from Small Parallel Corpora](https://md.research.elamur.ai/free/papers/sanchez-2014-martinez-inferring-shallow-transfer-machine-translation/)
- [Cross-lingual Word Clusters for Direct Transfer of Linguistic Structure](https://md.research.elamur.ai/free/papers/tackstrom-2012-cross-lingual-word-clusters-direct/)

## Cite

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

```bibtex
@inproceedings{och1999efficient,
  title = {{An Efficient Method for Determining Bilingual Word Classes}},
  author = {Och, Franz Josef},
  booktitle = {Ninth Conference of the European Chapter of the Association for Computational Linguistics},
  year = {1999},
  doi = {10.3115/977035.977046},
  url = {https://doi.org/10.3115/977035.977046}
}
```

- [next → Analysis of Syntax-Based Pronoun Resolution Methods](https://md.research.elamur.ai/free/papers/tetreault-1999-analysis-syntax-based-pronoun-resolution/)
- [↑ back to papers of 1999](https://md.research.elamur.ai/free/papers/1999/)

## References

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

1. P. F. Brown, V. J. Della Pietra, P. V. deSouza, J. C. Lai, and R. L. Mercer. 1992. Class-based n-gram models of natural language. Computational Linguistics, 18(4):467-479. [find](https://scholar.google.com/scholar?q=P%2E+F%2E+Brown%2C+V%2E+J%2E+Della+Pietra%2C+P%2E+V%2E+deSouza%2C+J%2E+C%2E+Lai%2C+and+R%2E+L%2E+Mercer%2E+1992%2E+Class%2Dbased+n%2Dgram+models+of+natural+language%2E+Computational+Linguistics%2C+18%284%29%3A467%2D479%2E)
2. Peter F. Brown, Stephen A. Della Pietra, Vincent J. Della Pietra, and Robert L. Mercer. 1993. The mathematics of statistical machine translation: Parameter estimation. Computational Linguistics, 19 (2) :263-311. [find](https://scholar.google.com/scholar?q=Peter+F%2E+Brown%2C+Stephen+A%2E+Della+Pietra%2C+Vincent+J%2E+Della+Pietra%2C+and+Robert+L%2E+Mercer%2E+1993%2E+The+mathematics+of+statistical+machine+translation%3A+Parameter+estimation%2E+Computational+Linguistics%2C+19+%282)
3. G. Dueck and T. Scheuer. 1990. Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing. Journal of Computational Physics, 90(1):161-175. [find](https://scholar.google.com/scholar?q=G%2E+Dueck+and+T%2E+Scheuer%2E+1990%2E+Threshold+accepting%3A+A+general+purpose+optimization+algorithm+appearing+superior+to+simulated+annealing%2E+Journal+of+Computational+Physics%2C+90%281%29%3A161%2D175%2E)
4. Pascale Fung and Dekai Wu. 1995. Coerced markov models for cross-lingual lexical-tag relations. In The Sixth International Conference on Theoretical and Methodological Issues in Machine Translation, pages 240-255, Leuven, Belgium, July. [find](https://scholar.google.com/scholar?q=Pascale+Fung+and+Dekai+Wu%2E+1995%2E+Coerced+markov+models+for+cross%2Dlingual+lexical%2Dtag+relations%2E+In+The+Sixth+International+Conference+on+Theoretical+and+Methodological+Issues+in+Machine+Translation%2C+p)
5. M. Jardino and G. Adda. 1993. Automatic Word Classification Using Simulated Annealing. In Proc. Int. Conf. on Acoustics, Speech, and Signal Processing, volume 2, pages 41-44, Minneapolis. [find](https://scholar.google.com/scholar?q=M%2E+Jardino+and+G%2E+Adda%2E+1993%2E+Automatic+Word+Classification+Using+Simulated+Annealing%2E+In+Proc%2E+Int%2E+Conf%2E+on+Acoustics%2C+Speech%2C+and+Signal+Processing%2C+volume+2%2C+pages+41%2D44%2C+Minneapolis%2E)
6. R. Kneser and H. Ney. 1991. Forming Word Classes by Statistical Clustering for Statistical Language Modelling. In 1. Quantitative Linguistics Conference. [find](https://scholar.google.com/scholar?q=R%2E+Kneser+and+H%2E+Ney%2E+1991%2E+Forming+Word+Classes+by+Statistical+Clustering+for+Statistical+Language+Modelling%2E+In+1%2E+Quantitative+Linguistics+Conference%2E)
7. R. Kneser and H. Ney. 1993. Improved Clustering Techniques for Class-Based Statistical Language Modelling. In European Conference on Speech Communication and Technology, pages 973-976. [find](https://scholar.google.com/scholar?q=R%2E+Kneser+and+H%2E+Ney%2E+1993%2E+Improved+Clustering+Techniques+for+Class%2DBased+Statistical+Language+Modelling%2E+In+European+Conference+on+Speech+Communication+and+Technology%2C+pages+973%2D976%2E)
8. Sven Martin, JSrg Liermann, and Hermann Ney. 1998. Algorithms for bigram and trigram word clustering. Speech Communication, 24(1):19-37. [find](https://scholar.google.com/scholar?q=Sven+Martin%2C+JSrg+Liermann%2C+and+Hermann+Ney%2E+1998%2E+Algorithms+for+bigram+and+trigram+word+clustering%2E+Speech+Communication%2C+24%281%29%3A19%2D37%2E)
9. Franz Josef Och and Hermann Ney. 1999. The alignment template approach to statistical machine translation. To appear. [find](https://scholar.google.com/scholar?q=Franz+Josef+Och+and+Hermann+Ney%2E+1999%2E+The+alignment+template+approach+to+statistical+machine+translation%2E+To+appear%2E)
10. Franz Josef Och and Hans Weber. 1998. Improving statistical natural language translation with categories and rules. In Proceedings of the 35th Annual Conference of the Association for Computational Linguistics and the 17th International Conference on Computational Linguistics, pages 985-989, Montrea… [find](https://scholar.google.com/scholar?q=Franz+Josef+Och+and+Hans+Weber%2E+1998%2E+Improving+statistical+natural+language+translation+with+categories+and+rules%2E+In+Proceedings+of+the+35th+Annual+Conference+of+the+Association+for+Computational+Li)
11. Enrique Vidal. 1997. Finite-state speech-to-speech translation. In Proc. Int. Conf. on Acoustics, Speech, and Signal Processing, volume 1, pages 111-114. [find](https://scholar.google.com/scholar?q=Enrique+Vidal%2E+1997%2E+Finite%2Dstate+speech%2Dto%2Dspeech+translation%2E+In+Proc%2E+Int%2E+Conf%2E+on+Acoustics%2C+Speech%2C+and+Signal+Processing%2C+volume+1%2C+pages+111%2D114%2E)
12. Stephan Vogel, Hermann Ney, and Christoph Tillmann. 1996. HMM-based word alignment in statistical translation. In COLING '96: The 16th Int. Conf. on Computational Linguistics, pages 836-841, Copenhagen, August. [find](https://scholar.google.com/scholar?q=Stephan+Vogel%2C+Hermann+Ney%2C+and+Christoph+Tillmann%2E+1996%2E+HMM%2Dbased+word+alignment+in+statistical+translation%2E+In+COLING+%2796%3A+The+16th+Int%2E+Conf%2E+on+Computational+Linguistics%2C+pages+836%2D841%2C+Copenhage)
13. Ye-Yi Wang, John Laiferty, and Alex Waibel. 1996. Word clustering with parallel spoken language corpora. In Proceedings of the ~th International Conference on Spoken Language Procesing (ICSLP'96), pages 2364-2367. [find](https://scholar.google.com/scholar?q=Ye%2DYi+Wang%2C+John+Laiferty%2C+and+Alex+Waibel%2E+1996%2E+Word+clustering+with+parallel+spoken+language+corpora%2E+In+Proceedings+of+the+%7Eth+International+Conference+on+Spoken+Language+Procesing+%28ICSLP%2796%29%2C+pag)