Elamur Research⌕
☰
home / papers / 2018 / Gromov-Wasserstein Alignment of Word Embedding Spaces

Gromov-Wasserstein Alignment of Word Embedding Spaces

Paper · 2018 · David Alvarez-Melis and Tommi Jaakkola

Summary

The paper addresses unsupervised bilingual lexical induction: matching words across two languages using only monolingual embeddings, with no parallel data. Earlier fully unsupervised systems chain several stages, such as adversarial initialization, Procrustes fitting and heuristic refinement, and they can be hard to tune. The authors observe that embeddings mostly encode relations between words, not absolute positions. They therefore frame alignment as a Gromov-Wasserstein optimal transport problem, which compares within-language distance structures directly. The problem is solved with an entropy-regularized, Sinkhorn-style procedure. To handle large vocabularies, the coupling learned on a subset of words is used to fit an orthogonal Procrustes map, which then covers the remaining words. On standard word translation benchmarks, including the Dinu et al. (2014) dataset, the method comes close to state-of-the-art accuracy. It does so in a single optimization step, with little hyperparameter tuning, using only CPU computation and far less compute than adversarial alternatives. The optimal GW value also serves as a geometric distance between languages.

Key points

  • The core objective is the Gromov-Wasserstein distance (Mémoli, 2011), a quadratic transport problem over pairs of words. It is optimized with entropic regularization following Cuturi (2013) and needs no post-hoc refinement.
  • The method scales by learning a single orthogonal Procrustes mapping from the GW coupling and applying it to out-of-sample words.
  • Its runtimes are CPU-minutes. The baselines reported by Artetxe et al. (2018) were run on a Titan XP GPU, so the authors note the timings are not strictly comparable.
  • The authors computed pairwise language distances on the FastText embeddings of Conneau et al. (2018), using the 2000 most frequent words for DE, EN, ES, FR, IT, RU and ZH.
  • In those distances, Romance languages cluster closely and ZH is farthest from all others. RU is unexpectedly near the Romance group, with ES its closest neighbour, while EN sits roughly equidistant from DE and FR.

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

🎓Massachusetts Institute of TechnologyCambridge · United States159 works · 65,157 citations🔬MIT Computer Science and Artificial Intelligence LaboratoryCambridge · United States54 works · 29,441 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 David Alvarez-Melis and Tommi Jaakkola. 2018. Gromov-Wasserstein Alignment of Word Embedding Spaces. Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/d18-1214

@inproceedings{alvarezmelis2018gromov,
  title = {{Gromov-Wasserstein Alignment of Word Embedding Spaces}},
  author = {David Alvarez-Melis and Tommi Jaakkola},
  booktitle = {Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing},
  year = {2018},
  doi = {10.18653/v1/d18-1214},
  url = {https://doi.org/10.18653/v1/d18-1214}
}

References

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

  1. Mikel Artetxe, Gorka Labaka, and Eneko Agirre. 2016. Learning principled bilingual mappings of word embeddings while preserving monolingual invariance. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 2289–2294. our card
  2. Mikel Artetxe, Gorka Labaka, and Eneko Agirre. 2018. A robust self-learning method for fully unsupervised cross-lingual mappings of word embeddings. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 789—-798. Association for Com… our card
  3. Piotr Bojanowski, Edouard Grave, Armand Joulin, and Tomas Mikolov. 2017. Enriching Word Vectors with Subword Information. Transactions of the Association for Computational Linguistics, 5:135–146. our card
  4. Georg Bossong. 1991. Differential object marking in Romance and beyond. New analyses in Romance linguistics, pages 143–170. find
  5. Alexis Conneau, Guillaume Lample, Marc’Aurelio Ranzato, Ludovic Denoyer, and Hervé Jégou. 2018. Word Translation Without Parallel Data. In International Conference on Learning Representations. find
  6. Marco Cuturi. 2013. Sinkhorn distances: Lightspeed computation of optimal transport. In Advances in Neural Information Processing Systems, pages 2292—-2300. find
  7. Georgiana Dinu, Angeliki Lazaridou, and Marco Baroni. 2014. Improving zero-shot learning by mitigating the hubness problem. arXiv preprint arXiv:1412.6568. — [arXiv:1412.6568](https://arxiv.org/abs/1412.6568) find
  8. Manaal Faruqui and Chris Dyer. 2014. Improving vector space word representations using multilingual correlation. In Proceedings of the 14th Conference of the European Chapter of the Association for Computational Linguistics, pages 462–471. our card
  9. Pascale Fung. 1995. Compiling bilingual lexicon entries from a non-parallel English-Chinese corpus. In Third Workshop on Very Large Corpora. find
  10. Jiang Guo, Wanxiang Che, David Yarowsky, Haifeng Wang, and Ting Liu. 2015. Cross-lingual dependency parsing based on distributed representations. our card
  11. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), volume 1, pages 1234–1244. find
  12. Tatsunori B Hashimoto, David Alvarez-Melis, and Tommi S Jaakkola. 2016. Word Embeddings as Metric Recovery in Semantic Spaces. Transactions of the Association for Computational Linguistics, 4:273–286. find
  13. Martin Haspelmath. 2001. The European linguistic area: Standard Average European. In Language typology and language universals: An international handbook, volume 2, pages 1492–1510. de Gruyter. find
  14. Guillaume Lample, Ludovic Denoyer, and Marc’Aurelio Ranzato. 2018. Unsupervised Machine Translation Using Monolingual Corpora Only. International Conference on Learning Representations. our card
  15. Ang Lu, Weiran Wang, Mohit Bansal, Kevin Gimpel, and Karen Livescu. 2015. Deep multilingual correlation for improved word embeddings. In Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 250–256. find
  16. Chantal Melis, Marcela Flores, and A Holvoet. 2013. On the historical expansion of non-canonically marked ‘subjects’ in Spanish. The diachronic Typology of Non-Canonical Subjects, Amsterdam/Philadelphia, Benjamins, pages 163–184. find
  17. Facundo Mémoli. 2011. Gromov–Wasserstein distances and the metric approach to object matching. Foundations of computational mathematics, 11(4):417–487. find
  18. Tomas Mikolov, Quoc V Le, and Ilya Sutskever. 2013. Exploiting Similarities among Languages for Machine Translation. arXiv preprint arXiv:1309.4168v1, pages 1–10. find
  19. John Moore and David M. Perlmutter. 2000. What does it take to be a dative subject? Natural Language and Linguistic Theory, 18(2):373–416. find
  20. Gabriel Peyré and Marco Cuturi. 2018. Computational Optimal Transport. Technical report. find
  21. Gabriel Peyré, Marco Cuturi, and Justin Solomon. 2016. Gromov-Wasserstein averaging of kernel and distance matrices. In International Conference on Machine Learning, pages 2664–2672. find
  22. Anand Rangarajan, Haili Chui, and Fred L Bookstein. 1997. The Softassign Procrustes Matching Algorithm. Lecture Notes in Computer Science, 1230:29–42. find
  23. Reinhard Rapp. 1995. Identifying word translations in non-parallel texts. In Proceedings of the 33rd annual meeting on Association for Computational Linguistics, pages 320–322. Association for Computational Linguistics. our card
  24. Reinhard Rapp. 1999. Automatic identification of word translations from unrelated English and German corpora. In Proceedings of the 37th annual meeting of the Association for Computational Linguistics on Computational Linguistics, pages 519– 526. Association for Computational Linguistics. our card
  25. Sebastian Ruder, Ivan Vulić, and Anders Søgaard. 2017. A survey of cross-lingual embedding models. arXiv preprint arXiv:1706.04902. find
  26. Peter H. Schönemann. 1966. A generalized solution of the orthogonal procrustes problem. Psychometrika, 31(1):1–10. find
  27. Samuel L Smith, David H P Turban, Steven Hamblin, and Nils Y Hammerla. 2017. Offline bilingual word vectors, orthogonal transformations and the inverted softmax. International Conference on Learning Representations. our card
  28. Shyam Upadhyay, Manaal Faruqui, Chris Dyer, and Dan Roth. 2016. Cross-lingual models of word embeddings: An empirical comparison. arXiv preprint arXiv:1604.00425. our card
  29. Meng Zhang, Yang Liu, Huanbo Luan, and Maosong Sun. 2017a. Adversarial training for unsupervised bilingual lexicon induction. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), volume 1, pages 1959–1970. our card
  30. Meng Zhang, Yang Liu, Huanbo Luan, and Maosong Sun. 2017b. Earth Mover’s Distance Minimization for Unsupervised Bilingual Lexicon Induction. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 1934–1945. find
  31. Yuan Zhang, David Gaddy, Regina Barzilay, and Tommi Jaakkola. 2016. Ten Pairs to Tag – Multilingual POS Tagging via Coarse Mapping between Embeddings. In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pa… find
  32. Steven T Piantadosi. 2014. Zipf’s word frequency law in natural language: A critical review and future directions. Psychonomic Bulletin & Review, 21(5):1112–1130. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/melis-2018-gromov-wasserstein-alignment-word-embedding/