Elamur Research⌕
☰
home / papers / 2016 / A Latent Variable Model Approach to PMI-based Word Embeddings

A Latent Variable Model Approach to PMI-based Word Embeddings

Paper · 2016 · Sanjeev Arora, Yuanzhi Li, Yingyu Liang et al.

Summary

Embeddings derived from co-occurrence statistics, such as PMI matrices, word2vec and GloVe, work well in practice. Two things lacked a theoretical explanation: why the PMI matrix is closely matched by inner products of low-dimensional vectors, and why analogies can be solved with simple vector arithmetic. Arora and colleagues propose a generative account. They add dynamics to the log-linear topic modeling approach introduced by Mnih and Hinton (2007): a latent discourse vector drifts slowly as a random walk, and at each step a word is emitted with probability exponential in its inner product with that vector. They assume the latent word vectors are spread isotropically, with no preferred direction. Under this prior they integrate out the hidden variables and derive closed-form links between co-occurrence statistics and vector norms and inner products (Theorem 2.2). This justifies PMI-, word2vec- and GloVe-style objectives and some GloVe hyperparameter choices. It also shows how low dimensionality and isotropy suppress approximation noise, so linear analogy solving still works. Experiments support the isotropy assumption and show that relations align with dominant directions. The result matters because it replaces heuristic tuning with an interpretable, almost parameter-free model.

Key points

  • Model: Emission follows Pr[w | c_t] ∝ exp(⟨c_t, v_w⟩), where c_t performs a slow random walk whose stationary distribution is uniform on the unit sphere. Word vectors are modeled as a scalar times a spherical Gaussian draw, and the scalar is bounded by a constant κ (around 5).
  • Main theoretical result: Low-dimensional vectors can reproduce PMI (e.g., about 300 dimensions versus a vocabulary of many thousands of words). Unlike the earlier SGNS analysis by Levy and Goldberg (2014b), this argument covers the low-dimensional case.
  • Relations are directions: For differences v_a − v_b within an analogy relation, the average cosine with the first singular vector is 0.51 (0.58 semantic, 0.46 syntactic). With the second singular vector it is only 0.035. GloVe and word2vec vectors show the same pattern.
  • "Cheating" RD solver: This solver clusters word pairs and uses each cluster's relation direction. On the GOOGLE analogy testbed it raises accuracy substantially, e.g., SN vectors go from 0.71 to 0.79 with k = 30, and CBOW goes from 0.74 to 0.82. The authors therefore advise testbed designers not to test the same relation too often.
  • Non-cheating RD-nn solver: This variant estimates the relation direction from nearest-neighbor pairs (300 neighbors). It improves accuracy for SN, GloVe, CBOW and skip-gram by about 3%. One noted limitation is that the model ignores local word order.

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

🎓Princeton UniversityPrinceton · United States61 works · 36,471 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 Sanjeev Arora, Yuanzhi Li, Yingyu Liang, Tengyu Ma and Andrej Risteski. 2016. A Latent Variable Model Approach to PMI-based Word Embeddings. Transactions of the Association for Computational Linguistics.

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

@article{arora2016latent,
  title = {{A Latent Variable Model Approach to PMI-based Word Embeddings}},
  author = {Sanjeev Arora, Yuanzhi Li, Yingyu Liang, Tengyu Ma and Andrej Risteski},
  journal = {Transactions of the Association for Computational Linguistics},
  year = {2016},
  doi = {10.1162/tacl\_a\_00106},
  url = {https://doi.org/10.1162/tacl_a_00106}
}

References

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

  1. Jacob Andreas and Dan Klein. 2014. When and why are log-linear models self-normalizing? In Proceedings of the Annual Meeting of the North American Chapter of the Association for Computational Linguistics. find
  2. Sanjeev Arora, Yuanzhi Li, Yingyu Liang, Tengyu Ma, and Andrej Risteski. 2015. A latent variable model approach to PMI-based word embeddings. Technical report, ArXiV. http://arxiv.org/abs/1502.03520. — [arXiv:1502.03520](https://arxiv.org/abs/1502.03520) ↗
  3. Sanjeev Arora, Yuanzhi Li, Yingyu Liang, Tengyu Ma, and Andrej Risteski. 2016. Linear algebraic structure of word senses, with applications to polysemy. Technical report, ArXiV. http://arxiv.org/abs/1502.03520. ↗ our card
  4. David Belanger and Sham M. Kakade. 2015. A linear dynamical system model for text. In Proceedings of the 32nd International Conference on Machine Learning. Yoshua Bengio, Holger Schwenk, Jean-Sébastien Senécal, Fréderic Morin, and Jean-Luc Gauvain. 2006. Neural probabilistic language models. In I… find
  5. Fischer Black and Myron Scholes. 1973. The pricing of options and corporate liabilities. Journal of Political Economy. find
  6. David M. Blei and John D. Lafferty. 2006. Dynamic topic models. In Proceedings of the 23rd International Conference on Machine Learning. our card
  7. David M. Blei. 2012. Probabilistic topic models. Communication of the Association for Computing Machinery. find
  8. Kenneth Ward Church and Patrick Hanks. 1990. Word association norms, mutual information, and lexicography. Computational linguistics. our card
  9. Shay B. Cohen, Karl Stratos, Michael Collins, Dean P. Foster, and Lyle Ungar. 2012. Spectral learning of latent-variable PCFGs. In Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics: Long Papers-Volume 1. find
  10. Ronan Collobert and Jason Weston. 2008a. A unified architecture for natural language processing: Deep neural networks with multitask learning. In Proceedings of the 25th International Conference on Machine Learning. find
  11. Ronan Collobert and Jason Weston. 2008b. A unified architecture for natural language processing: Deep neural networks with multitask learning. In Proceedings of the 25th International Conference on Machine Learning. find
  12. Scott C. Deerwester, Susan T Dumais, Thomas K. Landauer, George W. Furnas, and Richard A. Harshman. 1990. Indexing by latent semantic analysis. Journal of the American Society for Information Science. find
  13. John Duchi, Elad Hazan, and Yoram Singer. 2011. Adaptive subgradient methods for online learning and stochastic optimization. The Journal of Machine Learning Research. find
  14. John Rupert Firth. 1957. A synopsis of linguistic theory. find
  15. Amir Globerson, Gal Chechik, Fernando Pereira, and Naftali Tishby. 2007. Euclidean embedding of co-occurrence data. Journal of Machine Learning Research. find
  16. 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. find
  17. Thomas Hofmann. 1999. Probabilistic latent semantic analysis. In Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence. our card
  18. Daniel Hsu, Sham M. Kakade, and Tong Zhang. 2012. A spectral algorithm for learning hidden markov models. Journal of Computer and System Sciences. find
  19. Omer Levy and Yoav Goldberg. 2014a. Linguistic regularities in sparse and explicit word representations. In Proceedings of the Eighteenth Conference on Computational Natural Language Learning. our card
  20. Omer Levy and Yoav Goldberg. 2014b. Neural word embedding as implicit matrix factorization. In Advances in Neural Information Processing Systems. find
  21. Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts. 2011. Learning word vectors for sentiment analysis. In The 49th Annual Meeting of the Association for Computational Linguistics. our card
  22. Yariv Maron, Michael Lamar, and Elie Bienenstock. 2010. Sphere embedding: An application to part-of-speech induction. In Advances in Neural Information Processing Systems. find
  23. Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013a. Efficient estimation of word representations in vector space. Proceedings of the International Conference on Learning Representations. our card
  24. Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S. Corrado, and Jeff Dean. 2013b. Distributed representations of words and phrases and their compositionality. In Advances in Neural Information Processing Systems. our card
  25. Tomas Mikolov, Wen-tau Yih, and Geoffrey Zweig. 2013c. Linguistic regularities in continuous space word representations. In Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. our card
  26. Andriy Mnih and Geoffrey Hinton. 2007. Three new graphical models for statistical language modelling. In Proceedings of the 24th International Conference on Machine Learning. find
  27. Christos H. Papadimitriou, Hisao Tamaki, Prabhakar Raghavan, and Santosh Vempala. 1998. Latent semantic indexing: A probabilistic analysis. In Proceedings of the 7th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. find
  28. Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014. Glove: Global vectors for word representation. Proceedings of the Empiricial Methods in Natural Language Processing. our card
  29. Douglas L. T. Rohde, Laura M. Gonnerman, and David C. Plaut. 2006. An improved model of semantic similarity based on lexical co-occurence. Communication of the Association for Computing Machinery. David E. Rumelhart, Geoffrey E. Hinton, and James L. McClelland, editors. 1986. Parallel Distributed Pr… find
  30. David E. Rumelhart, Geoffrey E. Hinton, and Ronald J. Williams. 1988. Learning representations by backpropagating errors. Cognitive modeling. find
  31. Peter D. Turney and Patrick Pantel. 2010. From frequency to meaning: Vector space models of semantics. Journal of Artificial Intelligence Research. our card

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/arora-2016-latent-variable-model-approach-pmi/