---
title: "Linear Algebraic Structure of Word Senses, with Applications to Polysemy — Arora 2018"
description: "The authors argue that standard embeddings such as word2vec and GloVe store a polysemous word as a… 65% precision. 35 references, cited by 70 papers here."
authors: ["Sanjeev Arora", "Yuanzhi Li", "Yingyu Liang", "Tengyu Ma", "Andrej Risteski"]
year: 2018
venue: "Transactions of the Association for Computational Linguistics"
source: "https://aclanthology.org/Q18-1034/"
doi: "10.1162/tacl_a_00034"
licence: "CC BY 4.0 (ACL Anthology)"
licence_url: "https://creativecommons.org/licenses/by/4.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/arora-2018-linear-algebraic-structure-word-senses/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/arora-2018-linear-algebraic-structure-word-senses/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2018](https://md.research.elamur.ai/free/en/papers/2018/page/2/) / Linear Algebraic Structure of Word Senses, with Applications to Polysemy

# Linear Algebraic Structure of Word Senses, with Applications to Polysemy

**Authors:** [Sanjeev Arora](https://md.research.elamur.ai/free/en/authors/sanjeev-arora/), [Yuanzhi Li](https://md.research.elamur.ai/free/en/authors/yuanzhi-li/), [Yingyu Liang](https://md.research.elamur.ai/free/en/authors/yingyu-liang/), [Tengyu Ma](https://md.research.elamur.ai/free/en/authors/tengyu-ma/) and [Andrej Risteski](https://md.research.elamur.ai/free/en/authors/andrej-risteski/) · **Year:** 2018 · **Venue:** Transactions of the Association for Computational Linguistics · **Licence:** [CC BY 4.0 (ACL Anthology)](https://creativecommons.org/licenses/by/4.0/)

**Links:** [Publisher's page](https://aclanthology.org/Q18-1034/) · [PDF](https://aclanthology.org/Q18-1034.pdf) · [DOI 10.1162/tacl\_a\_00034](https://doi.org/10.1162/tacl_a_00034) · [OpenAlex](https://openalex.org/W2295508206)

**Citations:** 177 citations (OpenAlex, 2026-10-14) · [70](https://md.research.elamur.ai/free/en/papers/arora-2018-linear-algebraic-structure-word-senses/cited-by/) in our library, of the 140,884 papers whose bibliographies we read

## Summary
The paper asks what a single word vector encodes when the word has several meanings. The authors argue that standard embeddings such as word2vec and GloVe store a polysemous word as a weighted, nonnegative sum of vectors for its individual senses. They support this "Linearity Assertion" with theory. They modify the random-walk-on-discourses generative model into a Gaussian walk variant and prove that a word's vector is a linear transform of the averaged context (SIF) embeddings around it.

Building on this, they run sparse coding over the embedding space to recover about 2000 "discourse atoms." Each word is expressed through a few atoms, and each atom corresponds to one sense. Because atoms are shared across the vocabulary, senses of different words become automatically linked.

They also introduce a "police lineup" evaluation, in which a system must pick a word's true senses from a pool that includes distractors. Their method beats competing approaches and roughly matches non-native English speakers. This matters because it explains polysemy in ordinary embeddings without needing separate per-sense vectors.

## Key points
- The theory rests on a Gaussian random walk model of discourse. In this model, the linear map between a word vector and its averaged context vectors damps the directions linked to frequent words such as "the," "with," and "as."
- Word senses are extracted by sparse coding into roughly 2000 discourse atoms. The approach works on word2vec, GloVe and PMI-based vectors, and SIF weighting gives better downstream WSI results.
- On the police lineup test with n = 20 candidate senses and t = 4 returned senses, the method reaches about 65% precision and 75% recall. Performance stays reasonable at n = 50.
- In the same lineup setting, GloVe-based runs score slightly lower, by 2.3% in precision and 5.76% in recall. NNSE vectors score much lower, by 25% and 28%.
- Human baselines were graduate students, and the algorithm performed on par with the non-native speakers among them.

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

Topics: [🔀 Word sense disambiguation](https://md.research.elamur.ai/free/en/topics/word-sense-disambiguation/) · [📖 Lexical semantics & word embeddings](https://md.research.elamur.ai/free/en/topics/lexical-semantics/)

## Institutions

- [Princeton University](https://md.research.elamur.ai/free/en/universities/princeton-university/) — University, Princeton, United States · 45 works · 34,022 citations

## Cite

Cite as: Sanjeev Arora, Yuanzhi Li, Yingyu Liang, Tengyu Ma and Andrej Risteski. 2018. Linear Algebraic Structure of Word Senses, with Applications to Polysemy. Transactions of the Association for Computational Linguistics.

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

```bibtex
@article{arora2018linear,
  title = {{Linear Algebraic Structure of Word Senses, with Applications to Polysemy}},
  author = {Sanjeev Arora, Yuanzhi Li, Yingyu Liang, Tengyu Ma and Andrej Risteski},
  journal = {Transactions of the Association for Computational Linguistics},
  year = {2018},
  doi = {10.1162/tacl\_a\_00034},
  url = {https://doi.org/10.1162/tacl_a_00034}
}
```

- [← previous Tied Multitask Learning for Neural Speech Translation](https://md.research.elamur.ai/free/en/papers/anastasopoulos-2018-tied-multitask-learning-neural-speech/)
- [next → Neural Cross-Lingual Named Entity Recognition with Minimal Resources](https://md.research.elamur.ai/free/en/papers/xie-2018-neural-cross-lingual-named-entity/)
- [↑ back to papers of 2018](https://md.research.elamur.ai/free/en/papers/2018/page/2/)

## References

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

1. Sanjeev Arora, Yuanzhi Li, Yingyu Liang, Tengyu Ma, and Andrej Risteski. 2016. A latent variable model approach to PMI-based word embeddings. Transaction of Association for Computational Linguistics, pages 385–399. [our card](https://md.research.elamur.ai/free/en/papers/arora-2016-latent-variable-model-approach-pmi/)
2. Sanjeev Arora, Yingyu Liang, and Tengyu Ma. 2017. A simple but tough-to-beat baseline for sentence embeddings. In In Proceedings of International Conference on Learning Representations. Javier Artiles, Enrique Amigó, and Julio Gonzalo. 2009. The role of named entities in web people search. In Proce… [find](https://scholar.google.com/scholar?q=Sanjeev+Arora%2C+Yingyu+Liang%2C+and+Tengyu+Ma%2E+2017%2E+A+simple+but+tough%2Dto%2Dbeat+baseline+for+sentence+embeddings%2E+In+In+Proceedings+of+International+Conference+on+Learning+Representations%2E+Javier+Artiles)
3. David M. Blei. 2012. Probabilistic topic models. Communication of the Association for Computing Machinery, pages 77–84. [find](https://scholar.google.com/scholar?q=David+M%2E+Blei%2E+2012%2E+Probabilistic+topic+models%2E+Communication+of+the+Association+for+Computing+Machinery%2C+pages+77%E2%80%9384%2E)
4. Samuel Brody and Mirella Lapata. 2009. Bayesian word sense induction. In Proceedings of the 12th Conference of the European Chapter of the Association for Computational Linguistics, pages 103–111. [our card](https://md.research.elamur.ai/free/en/papers/brody-2009-bayesian-word-sense-induction/)
5. Jonathan Chang, Sean Gerrish, Chong Wang, Jordan L. Boyd-Graber, and David M. Blei. 2009. Reading tea leaves: How humans interpret topic models. In Advances in Neural Information Processing Systems, pages 288–296. [our card](https://md.research.elamur.ai/free/en/papers/chang-2009-reading-tea-leaves-humans-interpret-topic/)
6. Kenneth Ward Church and Patrick Hanks. 1990. Word association norms, mutual information, and lexicography. Computational linguistics, pages 22–29. [our card](https://md.research.elamur.ai/free/en/papers/church-1990-word-association-norms-mutual-information/)
7. Ivan Damnjanovic, Matthew Davies, and Mark Plumbley. 2010. SMALLbox – an evaluation framework for sparse representations and dictionary learning algorithms. In International Conference on Latent Variable Analysis and Signal Separation, pages 418–425. [find](https://scholar.google.com/scholar?q=Ivan+Damnjanovic%2C+Matthew+Davies%2C+and+Mark+Plumbley%2E+2010%2E+SMALLbox+%E2%80%93+an+evaluation+framework+for+sparse+representations+and+dictionary+learning+algorithms%2E+In+International+Conference+on+Latent+Varia)
8. Antonio Di Marco and Roberto Navigli. 2013. Clustering and diversifying web search results with graph-based word sense induction. Computational Linguistics, pages 709–754. [our card](https://md.research.elamur.ai/free/en/papers/marco-2013-clustering-diversifying-web-search-results/)
9. Manaal Faruqui, Yulia Tsvetkov, Dani Yogatama, Chris Dyer, and Noah A. Smith. 2015. Sparse overcomplete word vector representations. In Proceedings of Association for Computational Linguistics, pages 1491– 1500. [find](https://scholar.google.com/scholar?q=Manaal+Faruqui%2C+Yulia+Tsvetkov%2C+Dani+Yogatama%2C+Chris+Dyer%2C+and+Noah+A%2E+Smith%2E+2015%2E+Sparse+overcomplete+word+vector+representations%2E+In+Proceedings+of+Association+for+Computational+Linguistics%2C+pages+)
10. Christiane Fellbaum. 1998. [find](https://scholar.google.com/scholar?q=Christiane+Fellbaum%2E+1998%2E)
11. WordNet: An Electronic Lexical Database. MIT Press. John Rupert Firth. 1957. A synopsis of linguistic theory, 1930-1955. Studies in Linguistic Analysis. [find](https://scholar.google.com/scholar?q=WordNet%3A+An+Electronic+Lexical+Database%2E+MIT+Press%2E+John+Rupert+Firth%2E+1957%2E+A+synopsis+of+linguistic+theory%2C+1930%2D1955%2E+Studies+in+Linguistic+Analysis%2E)
12. Alex Gittens, Dimitris Achlioptas, and Michael W Mahoney. 2017. Skip-gram – Zipf + Uniform = Vector Additivity. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), volume 1, pages 69–76. [find](https://scholar.google.com/scholar?q=Alex+Gittens%2C+Dimitris+Achlioptas%2C+and+Michael+W+Mahoney%2E+2017%2E+Skip%2Dgram+%E2%80%93+Zipf+%2B+Uniform+%3D+Vector+Additivity%2E+In+Proceedings+of+the+55th+Annual+Meeting+of+the+Association+for+Computational+Linguisti)
13. Thomas L. Griffiths, Mark Steyvers, and Joshua B. Tenenbaum. 2007. Topics in semantic representation. Psychological review, pages 211–244. [find](https://scholar.google.com/scholar?q=Thomas+L%2E+Griffiths%2C+Mark+Steyvers%2C+and+Joshua+B%2E+Tenenbaum%2E+2007%2E+Topics+in+semantic+representation%2E+Psychological+review%2C+pages+211%E2%80%93244%2E)
14. Eric H. Huang, Richard Socher, Christopher D. Manning, and Andrew Y. Ng. 2012. Improving word representations via global context and multiple word prototypes. In Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics, pages 873–882. [our card](https://md.research.elamur.ai/free/en/papers/huang-2012-improving-word-representations-global-context/)
15. Ignacio Iacobacci, Mohammad Taher Pilehvar, and Roberto Navigli. 2015. SensEmbed: Learning sense embeddings for word and relational similarity. In Proceedings of Association for Computational Linguistics, pages 95–105. [our card](https://md.research.elamur.ai/free/en/papers/iacobacci-2015-sensembed-learning-sense-embeddings-word/)
16. Omer Levy and Yoav Goldberg. 2014. Neural word embedding as implicit matrix factorization. In Advances in Neural Information Processing Systems, pages 2177–2185. [find](https://scholar.google.com/scholar?q=Omer+Levy+and+Yoav+Goldberg%2E+2014%2E+Neural+word+embedding+as+implicit+matrix+factorization%2E+In+Advances+in+Neural+Information+Processing+Systems%2C+pages+2177%E2%80%932185%2E)
17. Suresh Manandhar, Ioannis P Klapaftis, Dmitriy Dligach, and Sameer S Pradhan. 2010. [find](https://scholar.google.com/scholar?q=Suresh+Manandhar%2C+Ioannis+P+Klapaftis%2C+Dmitriy+Dligach%2C+and+Sameer+S+Pradhan%2E+2010%2E)
18. SemEval 2010: Task 14: Word sense induction & disambiguation. In Proceedings of the 5th International Workshop on Semantic Evaluation, pages 63–68. [our card](https://md.research.elamur.ai/free/en/papers/manandhar-2010-semeval-2010-task-14-word/)
19. Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S. Corrado, and Jeff Dean. 2013a. Distributed representations of words and phrases and their compositionality. In Advances in Neural Information Processing Systems, pages 3111–3119. [our card](https://md.research.elamur.ai/free/en/papers/mikolov-2013-distributed-representations-words-phrases-their/)
20. Tomas Mikolov, Wen-tau Yih, and Geoffrey Zweig. 2013b. 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, pages 746–751. [our card](https://md.research.elamur.ai/free/en/papers/mikolov-2013-linguistic-regularities-continuous-space-word/)
21. Andriy Mnih and Geoffrey Hinton. 2007. Three new graphical models for statistical language modelling. In Proceedings of the 24th International Conference on Machine Learning, pages 641–648. [find](https://scholar.google.com/scholar?q=Andriy+Mnih+and+Geoffrey+Hinton%2E+2007%2E+Three+new+graphical+models+for+statistical+language+modelling%2E+In+Proceedings+of+the+24th+International+Conference+on+Machine+Learning%2C+pages+641%E2%80%93648%2E)
22. Jiaqi Mu, Suma Bhat, and Pramod Viswanath. 2017. Geometry of polysemy. In Proceedings of International Conference on Learning Representations. [find](https://scholar.google.com/scholar?q=Jiaqi+Mu%2C+Suma+Bhat%2C+and+Pramod+Viswanath%2E+2017%2E+Geometry+of+polysemy%2E+In+Proceedings+of+International+Conference+on+Learning+Representations%2E)
23. Brian Murphy, Partha Pratim Talukdar, and Tom M. Mitchell. 2012. Learning effective and interpretable semantic models using non-negative sparse embedding. In Proceedings of the 24th International Conference on Computational Linguistics, pages 1933–1950. [find](https://scholar.google.com/scholar?q=Brian+Murphy%2C+Partha+Pratim+Talukdar%2C+and+Tom+M%2E+Mitchell%2E+2012%2E+Learning+effective+and+interpretable+semantic+models+using+non%2Dnegative+sparse+embedding%2E+In+Proceedings+of+the+24th+International+Conf)
24. Roberto Navigli and Daniele Vannella. 2013. [find](https://scholar.google.com/scholar?q=Roberto+Navigli+and+Daniele+Vannella%2E+2013%2E)
25. SemEval 2013: Task 11: Word sense induction and disambiguation within an end-user application. In Second Joint Conference on Lexical and Computational Semantics, pages 193–201. [find](https://scholar.google.com/scholar?q=SemEval+2013%3A+Task+11%3A+Word+sense+induction+and+disambiguation+within+an+end%2Duser+application%2E+In+Second+Joint+Conference+on+Lexical+and+Computational+Semantics%2C+pages+193%E2%80%93201%2E)
26. Arvind Neelakantan, Jeevan Shankar, Re Passos, and Andrew Mccallum. 2014. Efficient nonparametric estimation of multiple embeddings per word in vector space. In Proceedings of Conference on Empirical Methods in Natural Language Processing, pages 1059–1069. [find](https://scholar.google.com/scholar?q=Arvind+Neelakantan%2C+Jeevan+Shankar%2C+Re+Passos%2C+and+Andrew+Mccallum%2E+2014%2E+Efficient+nonparametric+estimation+of+multiple+embeddings+per+word+in+vector+space%2E+In+Proceedings+of+Conference+on+Empirical+)
27. Bruno Olshausen and David Field. 1997. Sparse coding with an overcomplete basis set: A strategy employed by V1? Vision Research, pages 3311–3325. [find](https://scholar.google.com/scholar?q=Bruno+Olshausen+and+David+Field%2E+1997%2E+Sparse+coding+with+an+overcomplete+basis+set%3A+A+strategy+employed+by+V1%3F+Vision+Research%2C+pages+3311%E2%80%933325%2E)
28. Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014. GloVe: Global Vectors for word representation. In Proceedings of the Empiricial Methods in Natural Language Processing, pages 1532–1543. [our card](https://md.research.elamur.ai/free/en/papers/pennington-2014-glove-global-vectors-word-representation/)
29. Joseph Reisinger and Raymond Mooney. 2010. Multi-prototype vector-space models of word meaning. In Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 107–117. [our card](https://md.research.elamur.ai/free/en/papers/reisinger-2010-multi-prototype-vector-space-models/)
30. Andrew Rosenberg and Julia Hirschberg. 2007. V-measure: A conditional entropy-based external cluster evaluation measure. In Conference on Empirical Methods in Natural Language Processing and Conference on Computational Natural Language Learning, pages 410–420. [our card](https://md.research.elamur.ai/free/en/papers/rosenberg-2007-vmeasure-conditional-entropy-cluster-evaluation/)
31. Hinrich Schutze. 1998. Automatic word sense discrimination. Computational Linguistics, pages 97–123. [our card](https://md.research.elamur.ai/free/en/papers/schutze-1998-automatic-word-sense-discrimination/)
32. Ran Tian, Naoaki Okazaki, and Kentaro Inui. 2017. The mechanism of additive composition. Machine Learning, 106(7):1083–1130. [find](https://scholar.google.com/scholar?q=Ran+Tian%2C+Naoaki+Okazaki%2C+and+Kentaro+Inui%2E+2017%2E+The+mechanism+of+additive+composition%2E+Machine+Learning%2C+106%287%29%3A1083%E2%80%931130%2E)
33. Peter D. Turney and Patrick Pantel. 2010. From frequency to meaning: Vector space models of semantics. Journal of Artificial Intelligence Research, pages 141–188. [our card](https://md.research.elamur.ai/free/en/papers/turney-2010-frequency-meaning-vector-space-models/)
34. Wikimedia. 2012. English Wikipedia dump. Accessed March 2015. [find](https://scholar.google.com/scholar?q=Wikimedia%2E+2012%2E+English+Wikipedia+dump%2E+Accessed+March+2015%2E)
35. David Yarowsky. 1995. Unsupervised word sense disambiguation rivaling supervised methods. In Proceedings of the 33rd Annual Meeting on Association for Computational Linguistics, pages 189–196. [our card](https://md.research.elamur.ai/free/en/papers/yarowsky-1995-unsupervised-word-sense-disambiguation-rivaling/)