Source-linked AI summary
Linear Algebraic Structure of Word Senses, with Applications to Polysemy
Sanjeev Arora, Yuanzhi Li, Yingyu Liang, Tengyu Ma, Andrej Risteski
TL;DR
Polysemous word embeddings are difficult to interpret because a single vector may encode multiple senses. The paper models those senses as linear superpositions, recovers them with sparse coding and discourse atoms, and reports competitive WSI performance, including human-level similarity on a distractor-based test. Its interpretation depends on modeling assumptions and does not fully explain all observed co-occurrences.
Problem
It is unclear what standard word embeddings represent for polysemous words, motivating alternatives that induce separate embeddings for each sense.
Method
The paper uses a random-walk discourse model to justify linear superposition, then applies sparse coding with about 2000 discourse atoms to recover and interrelate word senses.
Results
The method achieves competitive performance on standard WSI testbeds and performance similar to non-native speakers on a distractor-based police lineup test.
Takeaways & Limitations
Word senses can be represented as approximately recoverable linear components of standard embeddings, while discourse atoms provide succinct links to co-occurring words.
Takeaways & Limitations
The approach relies on a simple language model that cannot explain all observed co-occurrences, requiring semantically meaningless smoothing atoms for effects such as grammar and stopwords.
Abstract
from arXiv · showhide
Word embeddings are ubiquitous in NLP and information retrieval, but it is unclear what they represent when the word is polysemous. Here it is shown that multiple word senses reside in linear superposition within the word embedding and simple sparse coding can recover vectors that approximately capture the senses. The success of our approach, which applies to several embedding methods, is mathematically explained using a variant of the random walk on discourses model (Arora et al., 2016). A novel aspect of our technique is that each extracted word sense is accompanied by one of about 2000 "discourse atoms" that gives a succinct description of which other words co-occur with that word sense. Discourse atoms can be of independent interest, and make the method potentially more useful. Empirical tests are used to verify and support the theory.
1 Introduction
The paper argues that polysemous word embeddings contain multiple senses in linear superposition and develops sparse-coding WSI to recover them with discourse-based links.
- Motivation: Modern embeddings make it difficult to determine how a polysemous word represents its different senses.Their nonlinear objectives obscure internal structure, while a monolithic embedding accessed through inner products may fail to capture word senses.
- Linearity Assertion: Multiple senses are proposed to reside in linear superposition within standard word2vec and GloVe embeddings.For tie, the embedding is approximately a nonnegative weighted combination of hypothetical embeddings for its distinct senses.
- Method: Sparse coding turns the Linearity Assertion into a WSI method with overlapping, rather than exclusively clustered, sense representations.The approach is described as a linear-algebraic analogue of classic clustering-based WSI.
- Discourse Atoms: The method links senses across words through about 2000 discourse atoms that summarize neighboring-word co-occurrence patterns.This addresses the need to connect senses such as tie’s clothing sense with related words including shoe and jacket.
- Evaluation and Scope: The WSI procedure applies to word2vec, GloVe, and older vector-space methods, with competitive performance on standard testbeds.The paper motivates the approach using word analogies, sparse coding, and a modified random-walk-on-discourses model.
2 Justification for Linearity Assertion
A Gaussian random-walk discourse model explains why context vectors linearly predict word embeddings, supporting the paper’s linearity claim and its use of sparse coding.
- Gaussian Walk Model: The generative model represents each corpus location with a discourse vector and emits nearby words through a log-linear distribution.Discourse vectors undergo a slow random walk, and maximum-likelihood or moment estimates correspond to methods such as GloVe and word2vec.
- Gaussian Walk Model: The modified Gaussian model draws a discourse vector from a zero-mean Gaussian and generates a window of words from it.The modification supports the theoretical analysis of polysemy and yields a linear transformation relating context information to word embeddings.
- Theorem 1: Theorem 1 states that a word embedding is approximately a word-independent linear transformation of the expected average context vector.The interpretation constructs context averages over windows containing the word, then maps their average to the word vector.
- Theorem 1: The transformation depends on the discourse covariance and smooths directions associated with common discourses and common words.In a covariance-diagonal coordinate system, the transformation shrinks directions with larger covariance eigenvalues relatively more.
- SIF Embeddings: Replacing average context vectors with SIF embeddings preserves similar theoretical results and improves downstream WSI performance.SIF uses weighted neighboring-word averages with smaller weights for more frequent words, and is adopted in the experiments.
- Linearity Assertion: The linearity assertion follows because windows containing different senses provide subpopulation estimates that combine according to their occurrence frequencies.In the two-sense thought experiment, the transformed context estimates converge to the separate sense embeddings and combine linearly.
- Interpretive Caveat: A non-identity transformation is practically necessary because raw cluster centers can be semantically uninformative, whereas applying the transformation makes them meaningful again.The paper presents this as a limitation of older clustering-based approaches that treated cluster centers as sense representations.
3 Towards WSI: Atoms of Discourse
The paper uses the Linearity Assertion to formulate unsupervised word-sense induction as sparse coding, jointly discovering sense vectors and reusable discourse atoms.
- The method induces senses for all words simultaneously from embeddings, without supervision, and assigns each sense a vector representation.The approach uses the Linearity Assertion as its foundation.
- For access, 5-means clustering of estimated discourse vectors from 1000 Wikipedia windows yields cluster centers whose nearest words become meaningful after the theorem’s linear transformation.
- Sparse coding represents each word vector using at most k of m learned unit-vector atoms plus an error vector, minimizing ℓ2 reconstruction error.The atoms and coefficients are learned jointly through a nonconvex optimization.
- The optimization links senses across words because a clothing-related atom can represent the clothing sense of tie and also align with words such as shoe and jacket.Restricting m below the vocabulary size encourages atoms to be reused across multiple words.
- The learned atoms are intended to approximate discourse directions, with typical textual discourses represented as linear combinations of roughly 3–4 atoms.The paper calls these learned directions atoms of discourse.
4 Experimental Tests of Theory
Experiments test whether context-derived vectors can be linearly mapped to standard embeddings and whether polysemous or pseudoword embeddings follow the predicted linear structure. The reported results support both predictions across several embedding settings and evaluation constructions.
- 4.1 Test of Gaussian Walk Model: Induced Embeddings: The induced-embedding test regresses GloVe vectors from SIF embeddings of 20-word contexts, then evaluates cosine similarity on randomly held-out words.The same procedure is described as applicable, with similar results, to word2vec and SN vectors.
- 4.1 Test of Gaussian Walk Model: Induced Embeddings: The average cosine similarity between induced and GloVe vectors is large, whereas average discourse vectors without the learned transformation achieve only about 0.58.This contrast illustrates the need for a non-identity linear transformation.
- 4.2 Test of Linearity Assertion: The pseudoword experiment replaces paired words with artificial tokens, whose learned embeddings are compared with linear combinations predicted from the original sense vectors.The construction provides two distinct senses and ground-truth vectors for each pseudoword.
- 4.2 Test of Linearity Assertion: When the number of pseudoword pairs is small, prediction error is small and cosine similarity reaches 0.9; even with m = 3·10^4, cosine similarity remains above 0.7.The latter setting replaces about 90% of the vocabulary with pseudowords.
- 4.2 Test of Linearity Assertion: The WordNet proxy test evaluates whether word embeddings lie near the subspaces spanned by vector representations of their listed senses, using SemEval 2010 WSI words.Sense vectors are obtained by applying SIF sentence embedding followed by the learned linear transformation.
5 Experiments with Atoms of Discourse
Sparse coding produced a basis of about 2000 discourse atoms, with each word represented by at most five atoms that usually capture distinct senses, though some noise remains. The atoms’ nearest words provide thematic interpretations, and similar results extend to word2vec and GloVe.
- Experimental setup: 300-dimensional embeddings were created from a 3-billion-token Wikipedia corpus, and sparse coding used the standard k-SVD algorithm.The experiments used the SN objective from Arora et al. (2016).
- Parameter selection: The best sparsity parameter was k = 5, while the best number of discourse atoms was about 2000.Allowing more senses often introduces atoms with small coefficients that are indistinguishable from noise.
- Atom quality: About 100 atoms appeared semantically meaningless and were excluded because they were widely reused or lacked nearby words.The authors attribute such atoms to unexplained co-occurrences arising from grammar, stopwords, and related effects, requiring smoothing terms.
- Recovered senses: Each word used at most five atoms, which usually captured distinct senses but sometimes included noise or mistakes.The senses recovered for tie and spring illustrate this behavior, and similar results were obtained with word2vec and GloVe.
- Coefficient behavior: Most sparse-coding coefficients were nonnegative even when unrestricted, likely because word appearances are explained by active discourse rather than absent discourse.This interpretation treats coefficients as indicating which discourses generate a word’s appearances.
- Relation to topic models: Discourse atoms resemble topic-model outputs, but sparse coding yields a linear-algebraic alternative with fairly fine-grained topics.The paper’s novelty is interpreting these sparse-coding results as discourse atoms and using them to capture word senses.
6 Testing WSI in Applications
The paper evaluates its sparse-coding WSI method on SemEval clustering, word similarity in context, and a police lineup test, using discourse-based Bayesian decoding and context vectors. Across these applications, the method is competitive with earlier sense-embedding approaches and performs strongly on the new lineup evaluation.
- Method: The method computes context-specific word vectors through Bayesian posterior decoding over discourse atoms, then clusters those vectors using k-means with inner-product assignment.The posterior combines estimated atom usage, context compatibility, and atom priors; the resulting vectors support soft or hard sense decoding.
- Word Sense Induction: On SemEval 2010 WSI, the method outperforms Huang et al. (2012) and Neelakantan et al. (2014).Against Mu et al. (2017), it has higher V-Measure but lower F-score with 2 centers, and the reverse pattern with 5 centers.
- Word Similarity in Context: On word similarity in context, the method beats GloVe/skip-gram baselines and Mu et al. (2017), but is slightly worse than Huang et al. (2012).The evaluation uses around 2000 word pairs with ground-truth similarity scores and measures correlation between predicted and ground-truth scores.
- Police Lineup: The police lineup test presents a polysemous word with true-sense clusters and distractor clusters from other words, requiring identification of the clusters belonging to the target word.The test was proposed as an easily understandable evaluation that can also be administered to human subjects.
- Police Lineup: For the police lineup test with n = 20 and t = 4, the method reaches 65% precision and 75% recall.It outperforms the two selected competitors and performs similarly to non-native speakers; with other embeddings, performance decreases by 2.3%/5.76% for GloVe and 25%/28% for NNSE.
7 Conclusions
The paper concludes that word senses occupy linear superposition within standard embeddings and that sparse coding can recover useful sense representations. Its discourse atoms connect senses across words and provide fine-grained thematic structure, while the police lineup test offers a new evaluation setting.
- Conclusions: Different senses of polysemous words are shown to lie in linear superposition inside standard word2vec and GloVe embeddings.The paper supports this claim theoretically and with empirical tests, despite the nonconvex optimization used to produce modern embeddings.
- Conclusions: Sparse coding extracts word-sense vectors from existing embeddings and achieves very competitive performance on some WSI benchmarks.The approach is presented as a linear-algebraic analogue of clustering and as a source of fine-grained thematic structure.
- Conclusions: About 2000 discourse vectors interrelate senses by succinctly describing which other words occur near each sense.The method uses these discourse vectors to connect senses of different words rather than treating each sense independently.
- Conclusions: The police lineup test evaluates whether a system can distinguish a word’s true senses from distractor senses belonging to other words.The authors report that their method performs similarly to non-native speakers on this test.