Elamur Research⌕
☰
home / papers / 2011 / Deciphering Foreign Language

Deciphering Foreign Language

Paper · 2011 · Sujith Ravi and Kevin Knight

Summary

The paper asks whether a translation model can be learned without any sentence-aligned bilingual data. The authors treat foreign text as an encoded version of English. Training maximizes the likelihood of the foreign corpus alone, with both the English translation and the word alignment hidden. An independently trained English language model steers the search, so it acts in training, not only in decoding.

They first solve a simpler problem, word substitution ciphers, where vocabularies are large. For this they propose two scalable methods:

  • Iterative EM, which grows the vocabulary step by step.
  • Bayesian decipherment, a Gibbs sampler with CRP priors, pruned candidate lists and Map-Reduce parallelism.

They then apply EM and Bayesian decipherment to an IBM Model 3 style model for Spanish→English, tested on a temporal-expression corpus and OPUS movie subtitles. Decipherment trails parallel-trained systems such as MOSES, which reaches an edit distance of 4.7 versus 28.7 for the best decipherment on the Time corpus. Still, it produces usable translations from monolingual data alone. This makes it relevant for language pairs and domains that lack parallel corpora.

Key points

  • Problem framing. Training sums over hidden English strings, weighted by an English LM, as well as over hidden alignments. The free parameters are the same as in standard IBM-style training.
  • Iterative EM procedure.
    • It starts with the K most frequent word types and maps everything else to Unknown.
    • It then repeatedly adds the next K types.
    • Any mapping whose probability exceeded 0.5 is frozen, and rival entries for that plaintext word are removed.
    • Final decoding uses Viterbi with the channel probabilities raised to the third power.
  • Bayesian sampler settings.
    • The LM prior is α = 10⁴, which keeps the LM effectively fixed.
    • The channel prior is a sparse β = 0.01.
    • Only K = 100 candidate words are considered per position.
    • The sampler runs for 2000 iterations with linear annealing.
    • Parallel sampling took 3.1 hours on 10 nodes, versus 11 hours for the sequential sampler.
  • MT setup.
    • The baselines are MOSES and IBM Model 3 without distortion, both trained on parallel data.
    • Evaluation uses normalized edit distance (including local swaps) and BLEU.
    • The OPUS data was filtered to sentences occurring more than 10 times.
  • Effect of the LM and of data size.
    • Replacing a 2-gram LM with a whole-segment LM cut EM decipherment edit distance by 24% and raised BLEU by 9%.
    • More training data helps every system, but parallel training benefits more than decipherment.

Interesting ideas

  • I1. Curriculum over vocabulary. Train on frequent types first, then freeze confident mappings before enlarging the model. This keeps EM tractable on huge parameter spaces and could suit any large latent mapping problem, such as lexicon induction or transliteration.
  • I2. Context-based candidate pruning. Restrict each Gibbs step to the top-K words that fit the neighboring words under a bigram LM, falling back to random candidates if none fit. This turns sampling over a vocabulary of millions into sampling over about 100 options, and could speed up other unsupervised taggers or decoders.
  • I3. Pragmatic approximation check. The authors measured that proposals were accepted over 99% of the time and therefore skipped the Metropolis-Hastings correction. Measuring how often the correction would matter, before paying for it, is a useful habit for approximate samplers.
  • I4. Chunked parallel Gibbs sampling. Sample corpus chunks independently, then merge the counts after each iteration. This is a simple Map-Reduce recipe that scales Bayesian inference with little code complexity.
  • I5. Blocked sampling over repeated sentences. Give all copies of an identical foreign sentence a single shared derivation. This enforces consistency and cuts work, which is attractive for repetitive data such as subtitles, templates or trade documents.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓University of Southern CaliforniaLos Angeles · United States104 works · 33,876 citations

📚 Shelves 4 Computer Science · 9,086 works Artificial Intelligence · 8,889 works Arts and Humanities · 9,296 works Language and Linguistics · 9,206 works

Cite

Cite as Sujith Ravi and Kevin Knight. 2011. Deciphering Foreign Language. Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies.

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

@inproceedings{ravi2011deciphering,
  title = {{Deciphering Foreign Language}},
  author = {Sujith Ravi and Kevin Knight},
  booktitle = {Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies},
  year = {2011},
  url = {https://aclanthology.org/P11-1002/}
}

References

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

  1. Friedrich L. Bauer. 2006. Decrypted Secrets: Methods and Maxims of Cryptology. Springer-Verlag. find
  2. Phil Blunsom, Trevor Cohn, Chris Dyer, and Miles Osborne. 2009. A Gibbs sampler for phrasal synchronous grammar induction. In 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 Asian Federation of… find
  3. Peter Brown, Vincent Della Pietra, Stephen Della Pietra, and Robert Mercer. 1993. The mathematics of statistical machine translation: Parameter estimation. Computational linguistics, 19(2):263–311. find
  4. David Chiang, Jonathan Graehl, Kevin Knight, Adam Pauls, and Sujith Ravi. 2010. Bayesian inference for finite-state transducers. In Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics - Human Language Technologies (NAACL/HLT), pages 447–455. find
  5. Arthur P. Dempster, Nan M. Laird, and Donald B. Rubin. 1977. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society, Series B, 39(1):1–38. find
  6. Jenny Finkel, Trond Grenager, and Christopher Manning. 2005. Incorporating non-local information into information extraction systems by Gibbs sampling. In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL), pages 363– 370. our card
  7. Pascal Fung and Kathleen McKeown. 1997. Finding terminology translations from non-parallel corpora. In Proceedings of the Fifth Annual Workshop on Very Large Corpora, pages 192–202. find
  8. Stuart Geman and Donald Geman. 1984. Stochastic relaxation, Gibbs distributions and the Bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6(6):721–741. find
  9. Ulrich Germann, Michael Jahr, Kevin Knight, Daniel Marcu, and Kenji Yamada. 2001. Fast decoding and optimal decoding for machine translation. In Proceedings of the 39th Annual Meeting on Association for Computational Linguistics, pages 228–235. our card
  10. Sharon Goldwater and Thomas Griffiths. 2007. A fully Bayesian approach to unsupervised part-of-speech tagging. In Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 744– 751. our card
  11. Aria Haghighi, Percy Liang, Taylor Berg-Kirkpatrick, and Dan Klein. 2008. Learning bilingual lexicons from monolingual corpora. In Proceedings of the Annual Meeting of the Association for Computational Linguistics - Human Language Technologies (ACL/HLT), pages 771–779. our card
  12. Kevin Knight and Yaser Al-Onaizan. 1998. Translation with finite-state devices. In David Farwell, Laurie Gerber, and Eduard Hovy, editors, Machine Translation and the Information Soup, volume 1529 of Lecture Notes in Computer Science, pages 421–437. Springer Berlin / Heidelberg. find
  13. Kevin Knight, Anish Nair, Nishit Rathod, and Kenji Yamada. 2006. Unsupervised analysis for decipherment problems. In Proceedings of the Joint Conference of the International Committee on Computational Linguistics and the Association for Computational Linguistics, pages 499–506. find
  14. Philipp Koehn and Kevin Knight. 2000. Estimating word translation probabilities from unrelated monolingual corpora using the EM algorithm. In Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, pa… find
  15. Philipp Koehn, Hieu Hoang, Alexandra Birch, Chris Callison-Burch, Marcello Federico, Nicola Bertoldi, Brooke Cowan, Wade Shen, Christine Moran, Richard Zens, Chris Dyer, Ondřej Bojar, Alexandra Constantin, and Evan Herbst. 2007. Moses: open source toolkit for statistical machine translation. In Pro… find
  16. Philip Koehn. 2009. Statistical Machine Translation. Cambridge University Press. find
  17. David McClosky, Eugene Charniak, and Mark Johnson. 2006. Effective self-training for parsing. In Proceedings of the main conference on Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics, pages 152–159. our card
  18. Gonzalo Navarro. 2001. A guided tour to approximate string matching. ACM Computing Surveys, 33:31–88, March. find
  19. David Newman, Arthur Asuncion, Padhraic Smyth, and Max Welling. 2009. Distributed algorithms for topic models. Journal of Machine Learning Research, 10:1801–1828. 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 the 40th Annual Meeting on Association for Computational Linguistics, pages 311–318. our card
  21. Reinhard Rapp. 1995. Identifying word translations in non-parallel texts. In Proceedings of the Conference of the Association for Computational Linguistics, pages 320–322. our card
  22. Benjamin Snyder, Regina Barzilay, and Kevin Knight. 2010. A statistical model for lost language decipherment. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 1048–1057. find
  23. Jörg Tiedemann. 2009. News from OPUS - A collection of multilingual parallel corpora with tools and interfaces. In N. Nicolov, K. Bontcheva, G. Angelova, and R. Mitkov, editors, Recent Advances in Natural Language Processing, volume V, pages 237–248. John Benjamins, Amsterdam/Philadelphia. find
  24. Translation (1949). Reproduced in W.N. Locke, A.D. Booth (eds.). In Machine Translation of Languages, pages 15–23. MIT Press. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/ravi-2011-deciphering-foreign-language/