Skip-Gram − Zipf + Uniform = Vector Additivity

Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, pages 69–76 Vancouver, Canada, July 30 - August 4, 2017. c⃝2017 Association for Computational Linguistics https://doi.org/10.18653/v1/P17-1007 Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, pages 69–76 Vancouver, Canada, July 30 - August 4, 2017. c⃝2017 Association for Computational Linguistics https://doi.org/10.18653/v1/P17-1007 Skip-Gram – Zipf + Uniform = Vector Additivity Alex Gittens Dept. of Computer Science Rensselaer Polytechnic Institute gittea@rpi.edu Dimitris Achlioptas Dept. of Computer Science UC Santa Cruz optas@soe.ucsc.edu Michael W. Mahoney ICSI and Dept. of Statistics UC Berkeley mmahoney@stat.berkeley.edu Abstract In recent years word-embedding models have gained great popularity due to their remarkable performance on several tasks, including word analogy questions and cap- tion generation. An unexpected “side- effect” of such models is that their vectors often exhibit compositionality, i.e., adding two word-vectors results in a vector that is only a small angle away from the vector of a word representing the semantic com- posite of the original words, e.g., “man” + “royal” = “king”. This work provides a theoretical justifica- tion for the presence of additive composi- tionality in word vectors learned using the Skip-Gram model. In particular, it shows that additive compositionality holds in an even stricter sense (small distance rather than small angle) under certain assump- tions on the process generating the corpus. As a corollary, it explains the success of vector calculus in solving word analogies. When these assumptions do not hold, this work describes the correct non-linear com- position operator. Finally, this work establishes a con- nection between the Skip-Gram model and the Sufficient Dimensionality Reduc- tion (SDR) framework of Globerson and Tishby: the parameters of SDR models can be obtained from those of Skip-Gram models simply by adding information on symbol frequencies. This shows that Skip- Gram embeddings are optimal in the sense of Globerson and Tishby and, further, im- plies that the heuristics commonly used to approximately fit Skip-Gram models can be used to fit SDR models. 1 Introduction The strategy of representing words as vectors has a long history in computational linguistics and machine learning. The general idea is to find a map from words to vectors such that word- similarity and vector-similarity are in correspon- dence. Whilst vector-similarity can be readily quantified in terms of distances and angles, quan- tifying word-similarity is a more ambiguous task. A key insight in that regard is to posit that the meaning of a word is captured by “the company it keeps” (Firth, 1957) and, therefore, that two words that keep company with similar words are likely to be similar themselves. In the simplest case, one seeks vectors whose inner products approximate the co-occurrence fre- quencies. In more sophisticated methods co- occurrences are reweighed to suppress the effect of more frequent words (Rohde et al., 2006) and/or to emphasize pairs of words whose co-occurrence frequency maximally deviates from the indepen- dence assumption (Church and Hanks, 1990). An alternative to seeking word-embeddings that reflect co-occurrence statistics is to extract the …

Content truncated to 500 words