Linear Algebraic Structure of Word Senses, with Applications to Polysemy

Linear Algebraic Structure of Word Senses, with Applications to Polysemy Sanjeev Arora, Yuanzhi Li, Yingyu Liang, Tengyu Ma, Andrej Risteski Computer Science Department, Princeton University 35 Olden St, Princeton, NJ 08540 {arora,yuanzhil,yingyul,tengyu,risteski}@cs.princeton.edu Abstract 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 re- side in linear superposition within the word embedding and simple sparse coding can re- cover 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 tech- nique is that each extracted word sense is ac- companied 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 indepen- dent interest, and make the method potentially more useful. Empirical tests are used to verify and support the theory. 1 Introduction Word embeddings are constructed using Firth’s hy- pothesis that a word’s sense is captured by the distri- bution of other words around it (Firth, 1957). Clas- sical vector space models (see the survey by Tur- ney and Pantel (2010)) use simple linear algebra on the matrix of word-word co-occurrence counts, whereas recent neural network and energy-based models such as word2vec use an objective that in- volves a nonconvex (thus, also nonlinear) function of the word co-occurrences (Bengio et al., 2003; Mikolov et al., 2013a; Mikolov et al., 2013b). This nonlinearity makes it hard to discern how these modern embeddings capture the different senses of a polysemous word. The monolithic view of embeddings, with the internal information ex- tracted only via inner product, is felt to fail in cap- turing word senses (Griffiths et al., 2007; Reisinger and Mooney, 2010; Iacobacci et al., 2015). Re- searchers have instead sought to capture polysemy using more complicated representations, e.g., by in- ducing separate embeddings for each sense (Murphy et al., 2012; Huang et al., 2012). These embedding- per-sense representations grow naturally out of classic Word Sense Induction or WSI (Yarowsky, 1995; Schutze, 1998; Reisinger and Mooney, 2010; Di Marco and Navigli, 2013) techniques that per- form clustering on neighboring words. The current paper goes beyond this mono- lithic view, by describing how multiple senses of a word actually reside in linear superposi- tion within the standard word embeddings (e.g., word2vec (Mikolov et al., 2013a) and GloVe (Pen- nington et al., 2014)). By this we mean the follow- ing: consider a polysemous word, say tie, which can refer to an article of clothing, or a drawn match, or a physical act. Let’s take the usual viewpoint that tie is a single token that represents monosemous words tie1, tie2, .... The theory and experiments in this paper strongly suggest that word embeddings com- puted using modern techniques such as GloVe and word2vec satisfy: vtie ≈ α1 vtie1 + α2 …

Content truncated to 500 words