Deconstructing word embedding algorithms (2020)

Abstract: Word embeddings are reliable feature representations of words used to obtain high quality results for various NLP applications. Uncontextualized word embeddings are used in many NLP tasks today, especially in resource-limited settings where high memory capacity and GPUs are not available. Given the historical success of word embeddings in NLP, we propose a retrospective on some of the most well-known word embedding algorithms. In this work, we deconstruct Word2vec, GloVe, and others, into a common form, unveiling some of the common conditions that seem to be required for making performant word embeddings. We believe that the theoretical findings in this paper can provide a basis for more informed development of future models.

## introduction the advent of efficient uncontextualized word embedding algorithms (e.g., word2vec @xcite and glove @xcite ) marked a historical breakthrough in nlp. countless researchers employed word embeddings in new models to improve results on a multitude of nlp problems. in this work, we provide a retrospective analysis of these groundbreaking models of the past, which simultaneously offers theoretical insights for how future models can be developed and understood. we build on the theoretical work of @xcite , proving that their findings on the relationship between pointwise mutual information (pmi) and word embeddings go beyond word2vec and singular value decomposition. in particular, we generalize several word embedding algorithms into a common form by proposing the low rank embedder framework. we deconstruct each algorithm into its constituent parts, and find that, despite their many different hyperparameters, the algorithms collectively intersect upon the following two key design features. first, vectorcovector dot products are learned to approximate pmi statistics in the corpus. second, modulation of the loss gradient, directly or indirectly, is necessary to balance weak and strong signals arising from the highly imbalanced distribution of corpus statistics. these findings can provide an informed basis for future development of both new embedding algorithms and deep contextualized models. ## fundamental concepts we begin by formally defining embeddings, their vectors and covectors (also known as "input" and "output" vectors @xcite ), and pointwise mutual information (pmi). embedding. in general topology, an embedding is understood as an injective structure preserving map, f : @xmath0, between two mathematical structures x and y . a word embedding algorithm (f ) learns an inner-product space (y ) to preserve a linguistic structure within a reference corpus of text, d (x), based on a vocabulary, v. the structure in d is analyzed in terms of the relationships between words induced by their co-appearances, according to a certain definition of context. in such an analysis, each word figures dually: (1) as a focal element inducing a local context; and (2) as elements of the local contexts induced by focal elements. to make these dual roles explicit, we distinguish two copies of the vocabulary: the focal, or term, words v t , and the context words v c . word embedding consists of two maps: we use dirac notation to distinguish vectors |j , associated to focal words, from covectors i|, asso-ciated to context words. in matrix notation, |j corresponds to a column vector and i| to a row vector. their inner product is i|j . we later demonstrate that many word embedding algorithms, intentionally or not, learn a vector space where the inner product between a focal word j and context word i aims to approximate their pmi in the reference corpus: i|j ≈ pmi(i, j). ## word embedding algorithms we will now introduce the low rank embedder framework for deconstructing word embedding algorithms, inspired by the theory of generalized low rank models @xcite . we unify several word embedding algorithms by observing them all from the common vantage point of their global loss function. note that this framework is used for theoretical analysis, not necessarily implementation. the global loss function for a low rank embedder takes the following form: the design variable φ ij is some function of corpus statistics, and its purpose is to quantitatively measure some relationship between words i and j. the design variable ψ ij is a function of model parameters that aims to approximate φ ij ; i.e., an embedder's fundamental objective is to learn ψ ij ≈ φ ij , and thus to train embeddings that capture the statistical relationships measured by φ ij . the simplest choice for the kernel function ψ ij , is to take ψ @xmath1. but the framework allows any function that is symmetric and positive definite, allowing the inclusion of bias parameters (e.g. in glove) and subword parameterization (e.g. in fasttext). we later demostrate that skip-gram with negative sampling takes φ ij := pmi(i, j) -ln k and ψ ij := i|j , and then learns parameter values that approximate i|j ≈ pmi(i, j) -ln k. to understand the range of models encompassed, it is helpful to see how the framework relates (but is not limited) to matrix factorization. consider φ ij as providing the entries of a matrix: m := [φ ij ] ij . for models that take ψ @xmath2, we can write @xmath3, where w is defined as having row i equal to i|, and v as having column j equal to |j . then, the loss function can be rewritten as: this loss function can be interpreted as matrix reconstruction error, because the constraint in eq. 3 means that the gradient goes to zero as wv ≈ m. selecting a particular low rank embedder instance requires key design choices to be made: we must chose the embedding dimension d, the form of the loss terms f ij , the kernel function ψ ij , and the association function φ ij . the derivative of f ij with respect to ψ ij , which we call the characteristic gradient, helps compare models because it exhibits the action of the gradient yet is symmetric in the parameters. in the appendix we show how this derivative relates to gradient descent. in the following subsections, we present the derivations of ∂f ij ∂ψ ij , ψ ij , and φ ij for svd @xcite , sgns @xcite , fasttext @xcite , glove @xcite , and lds @xcite . the derivation for swivel (shazeer ## related work our derivation of sgns's solution is inspired by the work of @xcite , who proved that skip-gram with negative sampling (sgns) @xcite was implicitly factorizing the pmi -ln k matrix. however, they required additional assumptions for their derivation to hold. @xcite explored relations between sgns and matrix factorization, but their derivation diverges from levy and goldberg's result and masks the connection between sgns and other low rank embedders. other works have also explored theoretical or empirical relationships between sgns and glove @xcite @xcite . ## discussion we observe common features between each of the algorithms ( for each algorithm, φ ij is equal to pmi or a scaled log of n ij . yet, the choice of ψ ij in combination with φ ij provides that every model is optimized when i|j tends toward pmi(i, j) (with or without a constant shift or scaling). we demonstrated that the optimum for sgns (and fasttest) is equivalent to the shifted pmi ( §3.2). for glove, we showed that incorporation of the bias terms captures the unigram counts needed for pmi ( §3.4). a similar property is found in lds with regards to the l2 norm in its learning objective @xcite . thus, these algorithms all converge on two key points: (1) an optimum in which model parameters are bilinearly related to pmi; and, (2) the weighting of ∂f ij ∂ψ ij by some tempered form of n ij . ## conclusion our low rank embedder framework has evoked the commonalities between many word embedding algorithms. we believe a robust understanding of these algorithms is a prerequisite for theoretically motivated development of deeper models. indeed, we offer the following conjectures: deep embedding models would benefit by incorporating pmi statistics into their training objective; such models will also benefit from sub-linear scaling of frequent word pairs during training; and, lastly, such models would benefit by learning representations with a dual character, as all of the embedding algorithms we described do by learning vectors and covectors.