Word Embeddings

Dense vectors for words, learned from which words occur near which. Skip-gram with negative sampling is stated and its gradient derived, and the theorem of Levy and Goldberg is proved with its conditions made explicit, that the objective is maximized when every dot product of a word vector with a context vector equals the pair's pointwise mutual information less the logarithm of the number of negative samples. The article then covers what a low dimension changes, the explicit factorization by singular value decomposition, GloVe's objective, and an experiment on the Brown corpus in which the objective is maximized from 30 seeds, full-batch and not by word2vec's procedure, and compared with the explicit factorization. Five worked problems carry out an update, the theorem on a three-word corpus and the weights of the factorization by hand.

The library's natural language processing article built vectors for the 10,000 most frequent words of the Brown corpus with nothing but counting and linear algebra. It counted which words occur within two positions of which, reweighted the counts, and compressed the table with a singular value decomposition. The nearest neighbors of monday in those vectors are friday, tuesday, wednesday, sunday and night. The method that made word vectors famous, word2vec, does none of this. It trains a small network, one pair of nearby words at a time, to tell pairs that occurred from pairs that did not. Are the two routes different in kind? They are not. Under conditions made exact below, the network's objective is maximized exactly when the dot product of each word vector with each context vector equals an entry of a reweighted count table, so training the network is a way of factorizing that table. This article proves that statement and tests it.

A word embedding is a vector of a few dozen to a few hundred real numbers assigned to a word, chosen so that words used in similar contexts receive similar vectors. It is the first dense representation in this unit, and the simplest: one fixed vector for each word of a vocabulary. The later articles of the unit replace the word by a passage and the lookup table by a network that reads the passage, but the training signal and the geometry are already here.

Here is the route. First the corpus is turned into a collection of word and context pairs, and pointwise mutual information is defined on it. Then the skip-gram model and negative sampling are stated and the gradient derived. Next comes the theorem of Levy and Goldberg (2014), with its conditions and a full proof, a check on a corpus of three words, and what changes when the dimension is small. Then the explicit route by singular value decomposition, an experiment on Brown that compares the two, and GloVe. The article assumes the singular value decomposition as latent semantic indexing develops it, and uses cosine similarity to compare vectors.

Pairs and counts

Both routes start from the same data, a collection of pairs. Take each word of the corpus in turn as the word $w$, and each word within a window around it as a context $c$. The collection of all such pairs $(w, c)$ is called $D$. Following Levy and Goldberg (2014, §2), write $\#(w, c)$ for the number of times the pair occurs in $D$, $\#(w) = \sum_{c'} \#(w, c')$ and $\#(c) = \sum_{w'} \#(w', c)$ for the totals of a word and of a context, and $\lvert D \rvert$ for the number of pairs. The words come from a vocabulary $V_W$ and the contexts from a vocabulary $V_C$. Here the two are the same list of words, but a word plays two different parts, and the model will give it two different vectors.

The running example is the Brown corpus as the natural language processing article reads it: 56,766 sentences with at least one alphabetic word, holding 981,716 lowercased alphabetic words of 40,234 distinct types. The vocabulary is the 10,000 most frequent words, the least frequent of which occurs 7 times. With a window of two positions on each side, inside sentences, there are 3,142,602 pairs in 969,270 distinct cells $(w, c)$.

One preprocessing step is added. The pair (of, the) alone occurs 21,527 times, and pairs of function words would dominate everything that follows. Mikolov et al. (2013b, §2.3) deal with this by subsampling: each token of a word whose share $f$ of the corpus exceeds a threshold $t$ is discarded with probability $1 - \sqrt{t/f}$, and so kept with probability $\sqrt{t/f}$. They report that this speeds up training and improves the vectors of rarer words. Here $t = 10^{-4}$, which touches the 1,040 words that occur more than 98.2 times. A token of the, which occurs 69,971 times, survives with probability 0.037. A pair survives when both of its tokens do. Instead of drawing the surviving tokens at random, the counts used on this page are the expected ones: each raw count is multiplied by the survival probabilities of its two words. Counts are therefore not whole numbers. This is the expected-value form of what Levy, Goldberg and Dagan (2015, §3.1) call clean subsampling, in which a removed token leaves the windows of the other tokens as they were. word2vec itself removes the tokens first and forms the windows afterwards. The total is $\lvert D \rvert = 573{,}661$ expected pairs.

Two cells will be followed through the article.

(united, states) (of, the)
Raw count 393 21,527
$\#(w, c)$ after subsampling 71.6 41.9
$\#(w)$ 235.9 3,595.0
$\#(c)$ 305.3 4,745.0

A raw count says little by itself, since frequent words co-occur with everything. What matters is how the count compares with what the two totals would produce by chance. If word and context were drawn independently, the share of pairs in cell $(w, c)$ would be the product of the two shares, $(\#(w)/\lvert D \rvert)(\#(c)/\lvert D \rvert)$. The pointwise mutual information is the logarithm of the ratio of the observed share to that product:

$$\mathrm{PMI}(w, c) = \ln \frac{\#(w, c)/\lvert D \rvert}{(\#(w)/\lvert D \rvert)\,(\#(c)/\lvert D \rvert)} = \ln \frac{\#(w, c)\, \lvert D \rvert}{\#(w)\, \#(c)}.$$

It is positive when the pair occurs more often than independence predicts, zero when it occurs exactly as often, and negative when less. Levy and Goldberg (2014, §3.3) trace its use as a measure of word association to Church and Hanks (1990), who proposed it under the name association ratio, estimated from counts of words occurring within a few words of each other (their §4). Logarithms on this page are natural logarithms, written $\ln$. The natural language processing article used base 2, which multiplies every value by the same constant and changes no cosine.

For the two cells, $\mathrm{PMI}(\textit{united}, \textit{states}) = \ln(71.6 \times 573{,}661 / (235.9 \times 305.3)) = 6.35$, and $\mathrm{PMI}(\textit{of}, \textit{the}) = 0.34$. The first pair is about 570 times as frequent as chance would make it. The second, for all its 21,527 occurrences, is only about 1.4 times as frequent as chance.

Most cells are empty. A pair that never occurs has $\#(w, c) = 0$ and a pointwise mutual information of $\ln 0$, which is $-\infty$. The standard repair is to keep only the positive part: positive PMI is $\max(\mathrm{PMI}, 0)$, with empty cells set to 0. The table of pointwise mutual information values, in this form or shifted by a constant, is the "reweighted count table" of the opening paragraph.

The skip-gram model

The count table grows with the square of the vocabulary. Mikolov, Chen, Corrado and Dean (2013a) proposed to learn word vectors directly by prediction, with two architectures. The one that matters here is skip-gram: given a word, predict the words around it.

Here is the idea in one sentence: give every word a vector $\vec{w}$ for its part as the center word and a vector $\vec{c}$ for its part as a context, and make $\vec{w} \cdot \vec{c}$ large for the pairs that occur.

In the formulation of Mikolov et al. (2013b, eq. 1 and 2), the model maximizes the average over the corpus of $\ln p(c \mid w)$ for every context $c$ in the window of every word $w$, with the probability given by a softmax over the whole context vocabulary:

$$p(c \mid w) = \frac{\exp(\vec{w} \cdot \vec{c})}{\sum_{c' \in V_C} \exp(\vec{w} \cdot \vec{c}\,')}.$$

Both sets of vectors lie in $\mathbb{R}^m$, where $m$ is the dimension of the embedding, and both are parameters to be learned. The trouble is the denominator. Every training pair requires a sum over the whole vocabulary, which the authors note makes the formulation impractical for vocabularies of $10^5$ to $10^7$ words.

Negative sampling

Negative sampling replaces the question "which of all the contexts is the right one?" by a cheaper one: "did this pair come from the corpus, or was it made up?"

For a pair $(w, c)$, model the probability that it came from the corpus by the logistic function of the dot product,

$$P(\text{observed} \mid w, c) = \sigma(\vec{w} \cdot \vec{c}), \qquad \sigma(x) = \frac{1}{1 + e^{-x}}.$$

For each pair that did occur, draw $k$ contexts $c_1, \dots, c_k$ at random from a noise distribution $P_n$ and treat the pairs $(w, c_j)$ as made up. These are the negative samples. The objective of Mikolov et al. (2013b, eq. 4) for one observed pair is

$$\ell(w, c) = \ln \sigma(\vec{w} \cdot \vec{c}) + \sum_{j=1}^{k} \ln \sigma(-\vec{w} \cdot \vec{c}_j), \qquad c_j \sim P_n.$$

The first term is the logarithm of the probability the model gives to "observed" for the real pair. Since $\sigma(-x) = 1 - \sigma(x)$, each term of the sum is the logarithm of the probability it gives to "made up" for a sampled pair. Maximizing $\ell$ pushes $\vec{w} \cdot \vec{c}$ up for real pairs and down for sampled ones, and each update touches $k + 2$ vectors instead of the whole vocabulary. The symbol $k$ is the papers' own. This page keeps it and uses no cutoff called $k$.

The method has two settings beyond the dimension. One is $k$: the authors found values of 5 to 20 useful for small training sets and 2 to 5 enough for large ones (2013b, §2.2). The other is the noise distribution. They tried several and found that the unigram distribution raised to the power 3/4, that is, $P_n(c)$ proportional to $\#(c)^{3/4}$, worked better than both the plain unigram distribution and the uniform one. Skip-gram trained with this objective is abbreviated SGNS.

Nothing in the definition says what the dot products should converge to. The gradient gives the first hint.

The gradient

Here is the plan of the derivation: differentiate the logarithm of the logistic function once, then apply the chain rule to each vector in turn.

The formal version. Since $\ln \sigma(x) = -\ln(1 + e^{-x})$,

$$\frac{d}{dx} \ln \sigma(x) = \frac{e^{-x}}{1 + e^{-x}} = \frac{1}{e^{x} + 1} = \sigma(-x), \qquad \frac{d}{dx} \ln \sigma(-x) = -\sigma(x).$$

The second follows from the first by the chain rule with inner function $-x$. In $\ell(w, c)$ the vector $\vec{w}$ occurs in every term, $\vec{c}$ in the first only, and each $\vec{c}_j$ in one term of the sum. The derivative of $\vec{w} \cdot \vec{c}$ with respect to $\vec{w}$ is $\vec{c}$, and with respect to $\vec{c}$ it is $\vec{w}$. So

$$\frac{\partial \ell}{\partial \vec{w}} = \sigma(-\vec{w} \cdot \vec{c})\; \vec{c} - \sum_{j=1}^{k} \sigma(\vec{w} \cdot \vec{c}_j)\; \vec{c}_j,$$

$$\frac{\partial \ell}{\partial \vec{c}} = \sigma(-\vec{w} \cdot \vec{c})\; \vec{w}, \qquad \frac{\partial \ell}{\partial \vec{c}_j} = -\sigma(\vec{w} \cdot \vec{c}_j)\; \vec{w}.$$

If a sampled context happens to equal $c$, or the same context is drawn twice, the contributions to that vector add.

Each coefficient is the model's error on one pair. The model says the real pair is real with probability $\sigma(\vec{w} \cdot \vec{c})$, so $\sigma(-\vec{w} \cdot \vec{c}) = 1 - \sigma(\vec{w} \cdot \vec{c})$ is how far it falls short of certainty. It says a sampled pair is real with probability $\sigma(\vec{w} \cdot \vec{c}_j)$, which is its error on that pair. Training by stochastic gradient ascent with a learning rate $\eta$ adds $\eta$ times each gradient to its vector:

  • $\vec{w}$ moves toward $\vec{c}$ and away from each $\vec{c}_j$, each in proportion to the error on that pair;
  • $\vec{c}$ moves toward $\vec{w}$;
  • each $\vec{c}_j$ moves away from $\vec{w}$.

When the model is already right about a pair the coefficient is near zero and nothing moves. Problem 1 carries out one update by hand. The script behind this page checks the three formulas against finite differences of $\ell$, to eight decimal places.

Two words that occur with the same contexts are pulled toward the same context vectors and pushed from the same sampled ones, and that is how words used alike come to have similar vectors. The mechanism never compares two word vectors with each other. Every term involves one word vector and one context vector.

The objective over the whole corpus

The update looks at one pair. To see where training is heading, add up the objective over all of $D$ and replace each sampled term by its expectation. This is the form Levy and Goldberg (2014, eq. 2) analyze, with the negative contexts drawn from the unigram distribution of contexts, $P_D(c) = \#(c) / \lvert D \rvert$:

$$\ell = \sum_{w \in V_W} \sum_{c \in V_C} \#(w, c) \left[ \ln \sigma(\vec{w} \cdot \vec{c}) + k\; \mathbb{E}_{c_N \sim P_D}\, \ln \sigma(-\vec{w} \cdot \vec{c}_N) \right].$$

Here is the idea of the next step in one sentence: the expectation does not depend on $c$, so the negative samples of a word can be pooled and then sorted by the context they landed on.

The formal version. In the second term the expectation depends on $w$ only, and $\sum_c \#(w, c) = \#(w)$, so that term is $k\, \#(w)\, \mathbb{E}_{c_N \sim P_D} \ln \sigma(-\vec{w} \cdot \vec{c}_N)$. Writing the expectation as a sum over contexts,

$$\mathbb{E}_{c_N \sim P_D}\, \ln \sigma(-\vec{w} \cdot \vec{c}_N) = \sum_{c \in V_C} \frac{\#(c)}{\lvert D \rvert}\, \ln \sigma(-\vec{w} \cdot \vec{c}).$$

Both terms are now sums over the same cells, and

$$\ell = \sum_{w \in V_W} \sum_{c \in V_C} \left[ \#(w, c)\, \ln \sigma(\vec{w} \cdot \vec{c}) + \frac{k\, \#(w)\, \#(c)}{\lvert D \rvert}\, \ln \sigma(-\vec{w} \cdot \vec{c}) \right].$$

Each cell contributes a term that depends on the vectors only through the one number $x = \vec{w} \cdot \vec{c}$. Write it

$$f_{wc}(x) = a \ln \sigma(x) + b \ln \sigma(-x), \qquad a = \#(w, c), \quad b = \frac{k\, \#(w)\, \#(c)}{\lvert D \rvert}.$$

The number $a$ is how often the pair was presented as real. The number $b$ is how often, on average, it is presented as made up: the word is visited $\#(w)$ times, each visit draws $k$ negatives, and each lands on $c$ with probability $\#(c)/\lvert D \rvert$. For (of, the) with $k = 5$, $b = 5 \times 3{,}595.0 \times 4{,}745.0 / 573{,}661 = 148.7$ against $a = 41.9$: the pair is offered as a negative more than three times as often as it occurs. For (united, states), $b = 5 \times 235.9 \times 305.3 / 573{,}661 = 0.63$ against $a = 71.6$.

What the objective is maximized by

Here is the idea in one sentence: each cell's term is a concave function of its own dot product with a single peak, the peak sits where the model's probability equals the share of real presentations among all presentations of the pair, and that point is the pointwise mutual information less $\ln k$.

Two lemmas carry the proof. The first is about one cell.

Lemma 1 (one cell). Let $f(x) = a \ln \sigma(x) + b \ln \sigma(-x)$ with $a \ge 0$ and $b > 0$.

  1. If $a > 0$, $f$ has exactly one maximizer, $x^* = \ln(a/b)$, and $f(x) < f(x^*)$ for every other $x$.
  2. If $a = 0$, $f$ has no maximizer: it is negative everywhere, strictly decreasing, and tends to 0 as $x \to -\infty$.

Proof. By the derivatives above, $f'(x) = a\, \sigma(-x) - b\, \sigma(x)$. The derivative of $\sigma$ is $\sigma'(x) = e^{-x}/(1 + e^{-x})^2 = \sigma(x)\, \sigma(-x)$, and by the chain rule the derivative of $\sigma(-x)$ is $-\sigma(x)\, \sigma(-x)$. So

$$f''(x) = -(a + b)\, \sigma(x)\, \sigma(-x) < 0,$$

and $f$ is strictly concave. If $a > 0$, set $f'(x) = 0$: $a\, \sigma(-x) = b\, \sigma(x)$, that is, $\sigma(x)/\sigma(-x) = a/b$. The ratio on the left is $(1 + e^{x})/(1 + e^{-x}) = e^{x}$, so $e^{x} = a/b$ and $x = \ln(a/b)$. A strictly concave function has at most one point of zero derivative, and that point is its strict maximum. If $a = 0$, $f(x) = b \ln \sigma(-x)$. It is negative because $\sigma(-x) < 1$, its derivative $-b\, \sigma(x)$ is negative, and $\sigma(-x) \to 1$ as $x \to -\infty$, so $f \to 0$ without reaching it. $\blacksquare$

At the maximizer, $\sigma(x^*) = 1/(1 + e^{-x^*}) = 1/(1 + b/a) = a/(a + b)$. The model's probability that the pair is real equals the fraction of the pair's presentations that were real. The second lemma says when the cells can be set independently.

Lemma 2 (enough dimensions). If $m \ge \min(\lvert V_W \rvert, \lvert V_C \rvert)$, then for every real matrix $X$ with one row for each word and one column for each context there are vectors with $\vec{w} \cdot \vec{c} = X_{wc}$ for all $w$ and $c$.

Proof. Stack the word vectors as the rows of a matrix $W$ and the context vectors as the rows of $C$, so that the matrix of all dot products is $W C^{\mathsf{T}}$. Suppose $m \ge \lvert V_C \rvert$. Let the context vector of the $j$-th context be the $j$-th standard basis vector of $\mathbb{R}^m$, and let the word vector of $w$ hold row $w$ of $X$ in its first $\lvert V_C \rvert$ coordinates and zeros after. Then $\vec{w} \cdot \vec{c}_j$ is the $j$-th coordinate of $\vec{w}$, which is $X_{wj}$. If instead $m \ge \lvert V_W \rvert$, exchange the parts: word vectors are standard basis vectors and each context vector holds a column of $X$. $\blacksquare$

Theorem (after Levy and Goldberg, 2014). Consider the objective $\ell$ above: the expected objective of skip-gram with $k$ negative samples per pair, drawn from the unigram distribution of contexts $P_D(c) = \#(c)/\lvert D \rvert$. Assume $m \ge \min(\lvert V_W \rvert, \lvert V_C \rvert)$, and that every word and every context occurs at least once.

  1. If every pair occurs, $\#(w, c) > 0$ for all $w$ and $c$, then vectors maximize $\ell$ if and only if $$\vec{w} \cdot \vec{c} = \mathrm{PMI}(w, c) - \ln k \quad \text{for every } w \text{ and } c.$$
  2. If some pairs never occur, $\ell$ has no maximizer. Its least upper bound is the sum of $f_{wc}(\mathrm{PMI}(w, c) - \ln k)$ over the pairs that occur. A sequence of vectors approaches it exactly when $\vec{w} \cdot \vec{c}$ converges to $\mathrm{PMI}(w, c) - \ln k$ on every pair that occurs and to $-\infty$ on every pair that does not.

Proof. The objective is $\ell = \sum_{w, c} f_{wc}(\vec{w} \cdot \vec{c})$ with $b > 0$ in every cell, since every word and context occurs. For part 1, Lemma 1 gives $f_{wc}(x) \le f_{wc}(x^*_{wc})$ with equality only at $x^*_{wc} = \ln(a/b)$, so $\ell \le \sum_{w,c} f_{wc}(x^*_{wc})$, with equality exactly when every dot product is at its cell's maximizer. By Lemma 2 there are vectors with those dot products, so the bound is attained, and attained only by such vectors. The maximizer is

$$x^*_{wc} = \ln \frac{a}{b} = \ln \frac{\#(w, c)\, \lvert D \rvert}{k\, \#(w)\, \#(c)} = \ln \frac{\#(w, c)\, \lvert D \rvert}{\#(w)\, \#(c)} - \ln k = \mathrm{PMI}(w, c) - \ln k.$$

For part 2, let $O$ be the set of pairs that occur and $s = \sum_{(w,c) \in O} f_{wc}(x^*_{wc})$. For any vectors, the cells in $O$ contribute at most $s$ and each cell outside $O$ contributes a negative number, by Lemma 1, so $\ell < s$ and no vectors attain $s$. For each $t > 0$, Lemma 2 gives vectors whose dot products are $x^*_{wc}$ on $O$ and $-t$ elsewhere. Their objective is $s$ plus the sum of $b \ln \sigma(t)$ over the empty cells, which tends to $s$ as $t \to \infty$. So $s$ is the least upper bound.

For the last claim, suppose a sequence of vectors has $\ell \to s$. Every cell's shortfall from its own least upper bound, $f_{wc}(x^*_{wc})$ on $O$ and 0 outside it, is nonnegative, and the shortfalls add up to $s - \ell$, so each tends to zero. On a cell of $O$, $f_{wc}$ is continuous and strictly concave with its peak at $x^*_{wc}$. Fix $\varepsilon > 0$. For $x \ge x^* + \varepsilon$, concavity gives $f(x) \le f(x^* + \varepsilon)$, and for $x \le x^* - \varepsilon$ it gives $f(x) \le f(x^* - \varepsilon)$, and both of these values are strictly below $f(x^*)$. So once the shortfall is smaller than both gaps, the dot product is within $\varepsilon$ of $x^*_{wc}$. On a cell outside $O$, the shortfall is $-b \ln \sigma(-x)$, which tends to zero only if $\sigma(-x) \to 1$, that is, $x \to -\infty$. Conversely, if the dot products converge as stated, each cell's term converges to its least upper bound by continuity, and $\ell \to s$. $\blacksquare$

Three remarks fix what the theorem does and does not say.

The conditions. Levy and Goldberg state the dimension condition in words: "for sufficiently large dimensionality $d$ (i.e. allowing for a perfect reconstruction of $M$), each product $\vec{w} \cdot \vec{c}$ can assume a value independently of the others" (§3.1). Lemma 2 gives a number that is sufficient. The exact condition for part 1 is weaker. The proof needs only that the one matrix with entries $\mathrm{PMI}(w, c) - \ln k$ can be written as $W C^{\mathsf{T}}$, which is possible exactly when $m$ is at least the rank of that matrix, and that is their "perfect reconstruction". Lemma 2's bound guarantees it whatever the matrix is. Part 2 uses that generality, since it needs a whole family of matrices. Their derivation sets the derivative of the cell's term to zero and solves a quadratic equation in $e^x$ (their eq. 5 and 6). The concavity argument used here reaches the same point and adds that the point is the only maximizer, which is what turns a stationary point into a theorem. They note separately that the matrix of pointwise mutual information is not well defined on pairs that never occur (§3.3). Part 2 says what the objective does there: it pushes those dot products down without limit. On real text most pairs never occur, so part 2 is the case that applies. The result that every dot product equals $\mathrm{PMI} - \ln k$ at the optimum is the paper's. The uniqueness of the maximizer, part 2 and the version for a general noise distribution below are worked out on this page.

What is determined. The theorem determines the matrix of dot products $W C^{\mathsf{T}}$. It does not determine $W$. If $A$ is any invertible matrix, $W A$ and $C (A^{-1})^{\mathsf{T}}$ have the same dot products and the same objective. The next article proves that this freedom changes the cosine between two word vectors, which is the quantity word vectors are usually compared by. So the theorem is a statement about what the model predicts, not about the neighbors of a word.

The noise distribution. The same proof covers any noise distribution $P_n$ that gives every context a positive probability. The second coefficient becomes $b = k\, \#(w)\, P_n(c)$ and the maximizer becomes

$$x^*_{wc} = \ln \frac{\#(w, c)}{\#(w)\, P_n(c)} - \ln k = \ln \frac{\#(w, c)/\lvert D \rvert}{(\#(w)/\lvert D \rvert)\, P_n(c)} - \ln k.$$

With the 3/4 power of word2vec, $P_n(c) = \#(c)^{3/4} / \sum_{c'} \#(c')^{3/4}$, this is a pointwise mutual information in which the share of the context is replaced by its smoothed share. Levy, Goldberg and Dagan (2015, eq. 3) define that variant and call it context distribution smoothing. Levy and Goldberg (2014, footnote 1) note the modification and report results with the unigram distribution. The experiment below uses the unigram distribution, so that the theorem applies as stated.

For the two cells of the running example with $k = 5$, where $\ln 5 = 1.609$: the theorem's value is $6.35 - 1.609 = 4.74$ for (united, states) and $0.34 - 1.609 = -1.27$ for (of, the). A model at the optimum would say that an occurrence of states after united is real with probability $\sigma(4.74)$, about 0.99, and that the after of is real with probability $\sigma(-1.27)$, about 0.22. The second number looks wrong for one of the commonest pairs in English until one recalls what "real" is measured against: the pair is offered as a negative 148.7 times for every 41.9 times it occurs, and $41.9/(41.9 + 148.7) = 0.22$.

A corpus small enough to check

The theorem is about an optimum that training on real text never reaches, because the dimension is far below the vocabulary size and most pairs never occur. On a corpus of three words every condition can be met and the result checked to the last digit.

Let the vocabulary be $\{a, b, c\}$ and the pair counts

$\#(w, c)$ $a$ $b$ $c$
$a$ 4 8 2
$b$ 8 2 4
$c$ 2 4 6

The totals are 14, 14 and 12, and $\lvert D \rvert = 40$. Every pair occurs. Take $k = 2$, so $\ln k = 0.693$. The six different values of the pointwise mutual information and of the theorem's target are:

Pair $\mathrm{PMI}$ $\mathrm{PMI} - \ln 2$
$(a, a)$ $\ln \tfrac{40}{49} = -0.203$ $-0.896$
$(a, b)$ $\ln \tfrac{80}{49} = 0.490$ $-0.203$
$(a, c)$ $\ln \tfrac{10}{21} = -0.742$ $-1.435$
$(b, b)$ $\ln \tfrac{20}{49} = -0.896$ $-1.589$
$(b, c)$ $\ln \tfrac{20}{21} = -0.049$ $-0.742$
$(c, c)$ $\ln \tfrac{5}{3} = 0.511$ $-0.182$

Problem 2 computes them. With $m = 3$, the condition of Lemma 2 holds. Plain gradient ascent on the exact objective, from small random vectors, brings every dot product to its target: after 60,000 steps the largest difference between any $\vec{w} \cdot \vec{c}$ and its $\mathrm{PMI} - \ln 2$ is below $10^{-6}$. The objective there is $-73.043$.

Example (one dimension). With $m = 1$ the condition fails, since every word and every context is a single number and the matrix of products has rank 1. Gradient ascent then converges, from each of six starting points, to the same objective, $-76.382$, which is 4.6% further from zero than the optimum. The matrix it finds has $-0.693$ in every cell. That is $-\ln 2$: the model has given up on the differences between pairs and predicts a pointwise mutual information of zero everywhere. It is also what Lemma 1 gives when all cells are forced to share one value, since the nine $a$'s add to $\lvert D \rvert$ and the nine $b$'s to $k \lvert D \rvert$, and $\ln(\lvert D \rvert / k \lvert D \rvert) = -\ln k$.

Example (a pair that never occurs). Set the count of $(c, c)$ to zero and keep $m = 3$. Part 2 of the theorem now applies. Under gradient ascent the dot product of that cell is $-2.88$ after 100 steps, $-7.02$ after 1,000, $-9.80$ after 10,000 and $-12.37$ after 100,000. It keeps falling, more and more slowly, while the objective creeps up to its least upper bound: $-61.5914$ after 100,000 steps against a bound of $-61.5913$. The other eight dot products settle within 0.05 of their targets. There is no optimum to arrive at, only a direction to keep moving in.

When the dimension is too small

On real data $m$ is a few hundred and the vocabulary is tens of thousands, so not every cell can sit at its peak. The cells then compete, and what matters is how much each one loses by missing.

Here is the idea in one sentence: near its peak each cell's term is a parabola whose steepness is $ab/(a + b)$, so the model is fitting the shifted PMI table by least squares with those weights.

The formal version. Expand $f_{wc}$ around $x^*$ to second order. The first derivative vanishes there. The second is $f''(x^*) = -(a + b)\, \sigma(x^*)\, \sigma(-x^*)$, and $\sigma(x^*) = a/(a + b)$, $\sigma(-x^*) = b/(a + b)$ from the proof of Lemma 1, so

$$f''(x^*) = -\frac{ab}{a + b}, \qquad f_{wc}(x) \approx f_{wc}(x^*) - \frac{1}{2}\, \frac{ab}{a + b}\, (x - x^*)^2.$$

To this order, maximizing $\ell$ over vectors of a given dimension is minimizing

$$\sum_{(w, c)\ \text{observed}} \frac{ab}{a + b}\, \left( \vec{w} \cdot \vec{c} - (\mathrm{PMI}(w, c) - \ln k) \right)^2,$$

together with the terms of the empty cells, each of which costs $-b \ln \sigma(-\vec{w} \cdot \vec{c})$ and so penalizes a dot product for being anything but very negative, in proportion to $b$.

The weight $ab/(a + b)$ is smaller than both $a$ and $b$. It is large only for pairs that are both observed often and expected often as negatives. Levy and Goldberg (2014, §3.2) describe the same thing in words, as a weighted matrix factorization that pays more for deviations on frequent pairs. In the 2,000-word collection of the experiment below, the weight of (of, the) is 31.77 and the weight of (united, states) is 0.84, although the second pair has the larger count: it is almost never drawn as a negative, so the model loses little by leaving its dot product short of the target. Problem 4 works both out and compares the approximation with the exact loss.

The approximation is local. Far below its peak a cell's term falls like $a x$, and far above like $-b x$, linearly and not quadratically. The statement that survives at any distance is Lemma 1: each cell pulls its dot product toward $\mathrm{PMI} - \ln k$, or toward $-\infty$ if the pair never occurs.

Factorizing the table directly

If the network is implicitly factorizing a table, the table can also be factorized explicitly. Levy and Goldberg (2014, §4) propose two such representations.

The shifted positive PMI matrix has entries

$$\mathrm{SPPMI}_k(w, c) = \max\left(\mathrm{PMI}(w, c) - \ln k,\ 0\right),$$

with empty cells set to 0 (their eq. 12). Its rows can be used as word vectors as they are: sparse vectors with one coordinate for each context. With $k = 1$ it is the positive PMI matrix of the count-based tradition. It differs from the theorem's matrix in the cells that are negative or empty, which it sets to zero instead of a negative number or $-\infty$.

The second representation compresses that matrix with a truncated singular value decomposition. Latent semantic indexing is this site's home for the decomposition and proves the result that justifies its use: keeping the $m$ largest singular values of $M = U \Sigma V^{\mathsf{T}}$ gives the matrix $M_m = U_m \Sigma_m V_m^{\mathsf{T}}$ of rank $m$ that is closest to $M$ in the sum of squared differences over all cells (the Eckart–Young theorem). The word vectors are then rows of $U_m \Sigma_m$, or, in the variant Levy and Goldberg recommend, of

$$W = U_m \sqrt{\Sigma_m}, \qquad C = V_m \sqrt{\Sigma_m},$$

which splits the singular values evenly between words and contexts (their eq. 13). Either way $W C^{\mathsf{T}} = M_m$. The two choices differ by a rescaling of the coordinates, exactly the freedom the theorem leaves open. Of the symmetric variant the authors write: "While it is not theoretically clear why the symmetric approach is better for semantic tasks, it does work much better empirically."

Set beside each other, the two routes differ in three ways.

SGNS SVD of SPPMI
Target in each cell $\mathrm{PMI} - \ln k$, or $-\infty$ if empty $\max(\mathrm{PMI} - \ln k, 0)$, or 0 if empty
Loss logistic, $-f_{wc}$ squared difference
Weight of a cell about $ab/(a + b)$ 1 for every cell

The vectors of the natural language processing article are one member of the explicit family: positive PMI of the raw counts, which is $k = 1$ with no subsampling, compressed to 100 dimensions, with word vectors $U_m \Sigma_m$. And latent semantic indexing is the same computation on a different table. It decomposes a term-document matrix, in which a term's context is the whole document it occurs in. Word vectors come from a word-context matrix, in which the context is a window of a few words. A narrow window makes two words similar when they can replace each other, and a document-wide context makes them similar when they belong to the same topic.

The experiment on Brown

The theorem says what the two routes share at the optimum. The experiment asks how close a trained model comes, and whether the trained and the explicit vectors are equally good at the thing word vectors are used for.

Setup

Training runs on the 2,000 most frequent words of the vocabulary, as words and as contexts, in $m = 50$ dimensions with $k = 5$. The least frequent of those words, create, occurs 54 times. Restricted to them the collection has $\lvert D \rvert = 240{,}983$ expected pairs, and 389,160 of its 4,000,000 cells are observed, 9.7%. The reduction from 10,000 words is a matter of computing time, stated plainly: the machine this was run on is shared, and 30 runs on the full vocabulary did not fit.

What is trained here is not word2vec. It is the objective $\ell$ of the theorem on this collection, maximized by full-batch steps. It differs from word2vec as released in four ways, the first three of which Levy, Goldberg and Dagan (2015, §3.1 and §3.2) describe.

  • Noise distribution. word2vec draws negatives from the unigram distribution raised to the power 3/4. Here they come from the plain unigram distribution of contexts, which is the theorem's condition.
  • Window. word2vec draws the size of each token's window at random between 1 and the maximum, which gives near contexts more weight. Here every pair within two positions counts once.
  • Subsampling. word2vec removes subsampled tokens before it forms windows, which brings more distant words into a window. Here the windows are formed first and the counts are multiplied by survival probabilities.
  • Steps. word2vec updates the vectors after every pair. Here one step processes a whole epoch at once.

A faithful run would stream the corpus's tokens with random subsampling and a sampled window, draw negatives from the smoothed distribution and update after every pair, on the full vocabulary. In NumPy on the machine used here that is a matter of hours for 30 seeds, and it was not done.

In each step the positive pairs enter through their counts. That epoch's negative pairs are sampled: a Poisson-distributed number of pairs with mean $k \lvert D \rvert$, each with its word drawn in proportion to $\#(w)$ and its context drawn independently from $P_D$, which is what drawing $k$ negatives for every positive pair amounts to when the positives are counted and not listed. The gradient with respect to the matrix of dot products $X = W C^{\mathsf{T}}$ is then the matrix $G$ with entries $\#(w, c)\, \sigma(-X_{wc}) - N_{wc}\, \sigma(X_{wc})$, where $N_{wc}$ is the number of sampled negatives in the cell, and the gradients with respect to the vectors are $G C$ and $G^{\mathsf{T}} W$, the formulas of the gradient section summed over an epoch. Each run takes 80 such steps with the Adam update rule (Kingma and Ba, 2015). The 30 runs use seeds 1 to 30, which set both the starting vectors and the sampled negatives.

Three things are measured on each set of vectors.

  • The objective. The expected objective $\ell$ is computed exactly over all four million cells, and reported as its deviation from the least upper bound $s$ of the theorem, $(\ell - s)/s$, the measure Levy and Goldberg use in their Table 1. Zero means the bound is reached.
  • The fit. On the observed cells, the correlation between $\vec{w} \cdot \vec{c}$ and $\mathrm{PMI} - \ln k$, and the mean of their difference.
  • Word similarity. WordSim-353 (Finkelstein et al., 2002) is a list of 353 word pairs, each with the mean of human ratings of how related the two words are on a scale from 0 to 10. SimLex-999 (Hill, Reichart and Korhonen, 2015) is a list of 999 pairs rated for similarity in the strict sense, so that related but dissimilar words score low. The score of a set of vectors is Spearman's rank correlation between the cosine of the two words' vectors and the human rating, over the pairs with both words in the vocabulary, the evaluation Levy and Goldberg use (§5.2). The 2,000 words cover 81 pairs of WordSim-353 and 209 of SimLex-999.

How close training comes to the optimum

Representation, $k = 5$, 2,000 words Deviation from the optimum
SGNS objective, full batch, 80 steps, 50 dimensions, 30 seeds 52.4% [52.3, 52.6]
SPPMI matrix 195.8%
SVD of SPPMI, 50 dimensions 207.7%

For the 30 seeds the table gives the median and, in brackets, the first and third quartiles. Every trained model is far closer to the optimum than either explicit matrix, and the 30 runs agree with each other to within a fraction of a percentage point. The explicit matrices score badly on this measure for a reason visible in the comparison table above: they put 0 in every empty cell, where the objective wants a very negative number, and each such cell costs $b \ln 2$. The trained models put −3.98 [−4.02, −3.98] there on average, and the SVD puts 0.04.

Levy and Goldberg's Table 1 has the same order between SVD and SGNS on their corpus of 1.5 billion words: with $k = 5$ and 100 dimensions, a deviation of 95.8% for SVD and 39.3% for SGNS.

Their figure for the SPPMI matrix, 0.00004%, cannot be obtained from the definition they state. They define the deviation as $(\ell - \ell_{\mathrm{Opt}})/\ell_{\mathrm{Opt}}$ with $\ell_{\mathrm{Opt}}$ "the objective when setting $\vec{w} \cdot \vec{c} = \mathrm{PMI}(w, c) - \log k$" (§5.1), and do not say what that means for a pair never observed, where the pointwise mutual information is $-\infty$ by their own §3.3. Read as a limit, it is the least upper bound used here. Under that reading every empty cell costs the SPPMI matrix $b \ln 2$, so its deviation is at least $\ln 2$ times the sum of $b$ over the empty cells, divided by the size of the bound. On this collection 62% of the negative term falls on empty cells, that floor is 159%, and the deviation is 195.8%. Two other readings were computed. Valuing empty cells at 0 in both $\ell$ and $\ell_{\mathrm{Opt}}$ gives 14.3%, and leaving them out of both gives 37.0%. In all three readings the deviation grows with $k$ (under the first it is 74.5%, 195.8% and 426.2% for $k$ = 1, 5 and 15), while their Table 1 has it falling, from 0.00009% at $k = 1$ to 0.00002% at $k = 15$. They estimated the objective from ten million sampled pairs with one sampled negative each (their footnote 5). Under the first reading, sampling alone cannot explain their column: an estimate whose expectation is the objective targets the deviation defined above, which is no smaller than the floor the same argument gives on their counts, and sampling error has no tendency to make the figures fall as $k$ grows. What remains possible, and cannot be decided from the paper, is that their far larger corpus or a convention the paper does not state (for the empty cells, or for the objective itself), alone or together with the sampling, accounts for it; neither was tested here. Their SPPMI figures are therefore not comparable with the ones on this page, and their SVD and SGNS figures may rest on the same unstated convention, so the agreement in order noted above should be read with that caution.

On the observed cells, the trained dot products follow the theorem's values more closely the more often a pair occurs. Because of subsampling, expected counts run below 1, and the cells are grouped by them.

Cells with expected count $a$ Number of cells Correlation of $\vec{w} \cdot \vec{c}$ with $\mathrm{PMI} - \ln 5$ Mean of $\vec{w} \cdot \vec{c} - (\mathrm{PMI} - \ln 5)$
$a \ge 10$ 258 0.939 [0.935, 0.945] −0.95 [−0.97, −0.94]
$1 \le a < 10$ 52,967 0.776 [0.774, 0.777] −1.11 [−1.11, −1.10]
$a < 1$ 335,935 0.464 [0.463, 0.465] −0.89 [−0.89, −0.88]
Dot products against the theorem's value over the observed cells of the 2,000-word collection, for the trained model of seed 1 (top row) and the SVD of the shifted positive PMI matrix (bottom row), by expected count; lighter hexagons hold more cells, on a logarithmic scale. Notice that the trained products follow the dashed line y = x but sit about one unit below it, that the cloud widens as the evidence thins, and that the SVD's products stay near zero or above, since it was fitted to a table with no negative entries.
Dot products against the theorem's value over the observed cells of the 2,000-word collection, for the trained model of seed 1 (top row) and the SVD of the shifted positive PMI matrix (bottom row), by expected count; lighter hexagons hold more cells, on a logarithmic scale. Notice that the trained products follow the dashed line y = x but sit about one unit below it, that the cloud widens as the evidence thins, and that the SVD's products stay near zero or above, since it was fitted to a table with no negative entries.

The correlation is high where there is evidence and falls where there is little. Weighted by $ab/(a + b)$, the root mean square difference over the observed cells is 1.25 [1.24, 1.25]. The SVD's products, for comparison, correlate with the same targets at 0.571, 0.698 and 0.648 in the three groups; it was fitted to a different table, the shifted positive one, in which 148,185 cells are nonzero. The dot products are also too low throughout, by about 1. For the two cells followed through the article, whose targets in this smaller collection are 4.43 and $-1.15$, the trained values are 3.46 [3.28, 3.60] for (united, states) and −1.86 [−1.88, −1.85] for (of, the). The previous section gives a reason for the first: a pair with a large count and almost no negatives has a small weight, and its dot product can stay short of a large target at little cost.

A run of the first seed with three times as many steps, 240, shows how much of this is unfinished training. Its deviation is 46.0%, against 52.6% for the same seed at 80 steps, so the 80-step models had not converged: the objective was still rising. The shortfall on the well-observed cells did not shrink, however. On the cells with $a \ge 10$ the longer run has a correlation of 0.938 and a mean difference of −1.03. The gain went to the cells with little or no evidence. Of the 21,656 by which the objective rose between 80 and 240 steps, the cells with $a \ge 10$ contributed −186, those with $1 \le a < 10$ contributed 3,460, those with $a < 1$ contributed 11,352 and the empty cells 7,031. On word similarity, the next measurement, this one longer run moved in both directions: on WordSim-353 its word vectors score 0.089 against 0.055 for the same seed at 80 steps, and with context vectors added 0.285 against 0.364.

Word similarity

Representation, 2,000 words, 50 dimensions WordSim-353 (81 pairs) SimLex-999 (209 pairs)
Trained word vectors $\vec{w}$, 30 seeds 0.183 [0.140, 0.246] 0.031 [0.007, 0.049]
Trained $\vec{w} + \vec{c}$, 30 seeds 0.303 [0.263, 0.341] 0.011 [−0.015, 0.030]
SPPMI rows, $k = 5$ 0.246 0.114
SVD of SPPMI, $U \sqrt{\Sigma}$, $k = 5$ 0.322 0.082
SVD of SPPMI, $U \Sigma$, $k = 5$ 0.286 0.094

With other shifts the explicit methods score, on WordSim-353, 0.270 for the sparse rows, 0.349 for $U\sqrt{\Sigma}$ and 0.299 for $U\Sigma$ at $k = 1$, and 0.179, 0.185 and 0.158 at $k = 15$. On SimLex-999 the same six are 0.047, 0.067, 0.074 and 0.086, 0.013, 0.031.

The trained word vectors alone are the weakest and the least stable representation in the table: across seeds their correlation with WordSim-353 has quartiles 0.140 and 0.246. Adding each word's context vector to its word vector, a step Pennington, Socher and Manning (2014, §4.2) introduced for their own model, brings the trained vectors close to the SVD. Levy, Goldberg and Dagan (2015, §3.3) explain what the sum does. The dot product of two such sums is

$$(\vec{w}_x + \vec{c}_x) \cdot (\vec{w}_y + \vec{c}_y) = \vec{w}_x \cdot \vec{w}_y + \vec{c}_x \cdot \vec{c}_y + \vec{w}_x \cdot \vec{c}_y + \vec{c}_x \cdot \vec{w}_y.$$

The last two terms are dot products of a word vector with a context vector, the quantities the objective fits directly. The first two are comparisons the objective never makes.

All of these correlations are low. Levy and Goldberg report correlations between 0.605 and 0.691 on WordSim-353 for the same three methods (their Table 2, 1,000 dimensions), from a corpus about 1,500 times the size of Brown. With 81 pairs the scores are also imprecise: resampling the 81 pairs with replacement 1,000 times gives the SVD score a standard deviation of 0.11. On SimLex-999 no representation here is clearly different from zero. What the table supports is modest. On this corpus the explicit factorization is at least as good as the trained model at word similarity, which is what Levy and Goldberg found on theirs, and a model can be much closer to the optimum of the objective without being better at the task. They observed the same gap between optimizing the objective and performing well (their §5).

The seeds agree on the dot products of well-observed pairs and not on the rest. Between seed 1 and each of seeds 2 to 30, the dot products correlate at 0.96 [0.96, 0.97] on the 258 cells with $a \ge 10$, at 0.75 [0.75, 0.75] over all observed cells, and at 0.58 [0.58, 0.58] over all four million cells. The neighbors disagree accordingly. Take each word's ten nearest neighbors by cosine among the word vectors of seed 1, and the same for another seed: the two lists share 2.03 [2.01, 2.05] words out of ten. The freedom in $W$ that the theorem leaves open is not the cause. Replacing each model's word vectors by $U \sqrt{\Sigma}$ from the singular value decomposition of its own matrix of dot products gives vectors whose cosines depend on the dot products alone, and the lists then share 2.05 [2.02, 2.06] words. The models differ in the products themselves, on the many pairs with little evidence, where 80 steps had not converged (the 240-step run above gained most on those cells); whether longer training would bring the seeds together was not measured. It is a caution against reading much into any single neighbor list from a model of this size:

Word Trained, seed 1, $\vec{w}$ Trained, seed 1, $\vec{w} + \vec{c}$ SVD of SPPMI, $U\sqrt{\Sigma}$
monday senate 0.64, sunday 0.61, afternoon 0.56, report 0.54, wilson 0.53 sunday 0.65, tuesday 0.62, senate 0.56, afternoon 0.56, saturday 0.51 sunday 0.85, evening 0.79, friday 0.72, morning 0.69, night 0.67
money coffee 0.57, trying 0.55, willing 0.55, employees 0.55, khrushchev 0.54 buy 0.54, wanted 0.51, vital 0.50, credit 0.50, pay 0.49 likely 0.61, production 0.60, help 0.60, trying 0.54, try 0.52
church part 0.58, sunday 0.57, every 0.55, republican 0.55, college 0.54 attend 0.56, catholic 0.55, sunday 0.54, american 0.52, san 0.51 catholic 0.66, roman 0.59, hospital 0.58, tomorrow 0.57, local 0.55
red white 0.63, old 0.60, river 0.57, blue 0.55, west 0.54 white 0.64, river 0.62, blue 0.53, wood 0.52, sky 0.52 blue 0.69, white 0.64, yellow 0.61, green 0.59, bright 0.57

Each cell lists the five nearest of the 2,000 words with their cosines.

One more measurement connects to the next article. In the trained models the length of a word vector falls with the word's frequency: the rank correlation between length and the logarithm of the count is −0.83 [−0.84, −0.83]. In the SVD vectors of the full vocabulary it rises with frequency. Length is something each method sets in its own way, and a measure that ignores it and a measure that uses it will treat the two sets of vectors differently.

The explicit methods on the full vocabulary

The explicit methods need no training runs, so they can be computed for all 10,000 words, in 100 dimensions, where 248 pairs of WordSim-353 and 869 of SimLex-999 are covered.

Shift SPPMI rows SVD, $U \sqrt{\Sigma}$ SVD, $U \Sigma$
$k = 1$ 0.296 0.356 0.329
$k = 5$ 0.264 0.414 0.387
$k = 15$ 0.261 0.443 0.412

The entries are correlations with WordSim-353. The matrix with $k = 5$ has 548,255 nonzero cells. On SimLex-999 the same nine are 0.105, 0.142, 0.129 for $k = 1$; 0.131, 0.139, 0.139 for $k = 5$; and 0.126, 0.094, 0.101 for $k = 15$. The symmetric split is ahead of $U \Sigma$ on WordSim-353 at every shift, as its authors found. A larger shift helps the SVD here and hurts the sparse rows. On WordSim-353, Levy and Goldberg's Table 2 has the sparse rows improving with the shift (0.605, 0.670 and 0.687 for $k$ = 1, 5 and 15) and the SVD best at $k = 5$ (0.652, 0.691 and 0.661), although their summary over four tasks is that both prefer a small shift. The configuration of the natural language processing article, which is raw counts, $k = 1$ and $U \Sigma$, scores 0.316 on WordSim-353 and 0.119 on SimLex-999. The vectors with $k = 5$ and the symmetric split are the ones the next article takes as its running example.

GloVe

A third method arrived at the same table from another direction. GloVe (Pennington, Socher and Manning, 2014) fits the counts directly by least squares.

Let $X_{ij}$ be the number of times word $j$ occurs in the context of word $i$. The model gives each word a vector $\vec{w}_i$ and a number $b_i$ for its part as the center word, and a second vector $\tilde{w}_j$ and number $\tilde{b}_j$ for its part as a context, and asks that

$$\vec{w}_i \cdot \tilde{w}_j + b_i + \tilde{b}_j = \ln X_{ij}$$

(their eq. 7). The authors reach this form from an argument about ratios of co-occurrence probabilities. A word such as solid occurs with ice far more often than with steam, and gas the other way around, while water occurs with both: the ratio $P(k \mid \textit{ice})/P(k \mid \textit{steam})$ separates the three kinds of probe word $k$ where the probabilities themselves do not (their Table 1). Requiring differences of word vectors to encode such ratios leads to a model that is linear in the logarithm of the count.

The equation cannot hold where $X_{ij} = 0$, and rare pairs are noisy. So the model is fitted by weighted least squares (their eq. 8 and 9):

$$J = \sum_{i, j} g(X_{ij}) \left( \vec{w}_i \cdot \tilde{w}_j + b_i + \tilde{b}_j - \ln X_{ij} \right)^2, \qquad g(x) = \begin{cases} (x / x_{\max})^{\alpha} & x < x_{\max} \\ 1 & \text{otherwise.} \end{cases}$$

The weighting function is written $g$ here because $f$ is taken on this page; the paper calls it $f$. It is zero at zero, so empty cells drop out of the sum, it rises with the count, and it is capped at 1 so that the commonest pairs do not dominate. The authors fix $x_{\max} = 100$ and $\alpha = 3/4$ in all their experiments, and note that the same power of 3/4 had been found best for the noise distribution of word2vec. With those values a pair seen once has weight 0.0316, a pair seen ten times 0.1778, a pair seen fifty times 0.5946, and any pair seen a hundred times or more has weight 1. They train with the AdaGrad method on the nonzero cells and use the sum $\vec{w}_i + \tilde{w}_i$ as the final word vector (§4.2).

The relation to the theorem is one substitution. Suppose the two numbers were not learned but fixed at $b_i = \ln \#(w_i)$ and $\tilde{b}_j = \ln \#(c_j) - \ln \lvert D \rvert$. Then the model equation reads $\vec{w}_i \cdot \tilde{w}_j = \ln X_{ij} - \ln \#(w_i) - \ln \#(c_j) + \ln \lvert D \rvert$, which is $\mathrm{PMI}(w_i, c_j)$. GloVe with those values is a weighted least-squares factorization of the pointwise mutual information matrix over the observed cells. Levy, Goldberg and Dagan (2015, §2.4) make this observation, and add the two differences: GloVe learns the two numbers, which gives it more freedom, and it ignores the cells that are empty, where SGNS pushes them down through its negative samples.

So the three methods factorize nearly the same table and differ in the loss, the weights and the treatment of empty cells:

Table fitted Loss and weights Empty cells
SVD of SPPMI $\max(\mathrm{PMI} - \ln k, 0)$ squared error, equal weights fitted as 0
SGNS $\mathrm{PMI} - \ln k$ logistic, about $ab/(a+b)$ near the optimum pushed toward $-\infty$
GloVe $\ln X$ with learned offsets squared error, weights $g(X)$ left out

GloVe is not run in this article's experiment. On which method is best the published evidence does not agree. Pennington et al. (2014, Table 2) report higher accuracy for GloVe than for skip-gram on a word analogy test. Levy, Goldberg and Dagan (2015, §5.3) repeated the comparison with the hyperparameters of every method tuned and the same corpus for all, and found that SGNS outperformed GloVe on every task they tried. Their broader conclusion is that much of the difference between methods comes from such settings as subsampling, the smoothed noise distribution and the addition of context vectors, which can be carried over to the count-based methods, and not from the methods themselves.

From word vectors to retrieval

A word embedding gives one vector to each word type. That has two consequences for retrieval, and both shape the rest of the unit.

The first is that a word with several senses gets one vector. The natural language processing article makes the point with bank. Representing a word in its sentence takes a model that reads the sentence, and Sentence and Passage Encoders takes that up.

The second is that a query or a passage is not a word. The simplest way to get one vector from many is to average them, and the encoders article begins with that operation, applied to the token vectors of a network. What carries over unchanged is the training signal. Negative sampling trains a model to score observed pairs above sampled ones, with a logistic loss on a dot product. Replace the word by a query, the context by a passage that answers it, and the sampled contexts by other passages, and the result is the contrastive training of a retriever, which Contrastive Training for Retrieval derives. The weakness of randomly sampled negatives, visible above in how little the model is asked about pairs that are rarely drawn, returns there as the problem of hard negatives.

What is proved, what is cited, what the experiment shows

Proved on this page: the gradient of the negative-sampling objective; Lemmas 1 and 2; the theorem of Levy and Goldberg in the two-part form above, including the behavior on pairs that never occur and the version for a general noise distribution; the second-order weight $ab/(a + b)$; that the symmetric and the plain SVD vectors have the same dot products with their context vectors; that GloVe's model with fixed offsets is a factorization of the pointwise mutual information.

Cited, not proved: the Eckart–Young theorem, which latent semantic indexing proves; every empirical statement of Mikolov et al. (2013b), Levy and Goldberg (2014), Levy, Goldberg and Dagan (2015) and Pennington et al. (2014), each given with its section or table.

Measured, on one corpus of about a million words: everything in the experiment. The trained models maximize the skip-gram negative-sampling objective with the unigram noise distribution, full-batch, for 80 steps, on 2,000 words in 50 dimensions, a setting chosen to meet the theorem's conditions and a time limit. The setup section lists how that differs from word2vec. Their numbers say how this implementation behaves on Brown. They are not measurements of word2vec.

Worked problems

These problems were written for this article; the unit has no assignments. The first is a single update on vectors small enough to follow, the second and third use the three-word corpus above, and the last two use numbers from the Brown experiment and from GloVe's weighting function. The script checks every number.

Problem 1 (one update by hand). Let $\vec{w} = (1, 0)$, $\vec{c} = (0.5, 0.5)$, one negative sample with $\vec{c}_1 = (1, -1)$, and learning rate $\eta = 0.1$. Compute the three gradients, the updated vectors, and the objective before and after.

Solution. The update raises the objective from $-1.7873$ to $-1.6144$. The dot products are $\vec{w} \cdot \vec{c} = 0.5$ and $\vec{w} \cdot \vec{c}_1 = 1$. The errors are $\sigma(-0.5) = 0.3775$ on the real pair and $\sigma(1) = 0.7311$ on the sampled one. The objective is $\ln \sigma(0.5) + \ln \sigma(-1) = -0.4741 - 1.3133 = -1.7873$ (the sum is taken before rounding). The gradients are

$$\frac{\partial \ell}{\partial \vec{w}} = 0.3775\,(0.5, 0.5) - 0.7311\,(1, -1) = (-0.5423,\ 0.9198),$$

$\partial \ell / \partial \vec{c} = 0.3775\,(1, 0)$ and $\partial \ell / \partial \vec{c}_1 = -0.7311\,(1, 0)$. Adding $\eta$ times each: $\vec{w}$ becomes $(0.9458, 0.0920)$, $\vec{c}$ becomes $(0.5378, 0.5000)$ and $\vec{c}_1$ becomes $(0.9269, -1.0000)$. The new dot products are 0.5546 with the real context, up from 0.5, and 0.7846 with the sampled one, down from 1. The sampled pair moved more because the model's error on it was larger.

Problem 2 (the theorem on three words). For the three-word corpus above with $k = 2$, compute the value the theorem gives for the pairs $(a, b)$ and $(c, c)$.

Solution. They are $-0.203$ and $-0.182$. For $(a, b)$: $\#(a, b) = 8$, $\#(a) = \#(b) = 14$ and $\lvert D \rvert = 40$, so the ratio of observed to expected is $8 \times 40 / (14 \times 14) = 320/196 = 80/49$, and $\mathrm{PMI} = \ln(80/49) = 0.490$. Subtracting $\ln 2 = 0.693$ gives $-0.203$. For $(c, c)$: $6 \times 40/(12 \times 12) = 240/144 = 5/3$, $\mathrm{PMI} = \ln(5/3) = 0.511$, and the target is $-0.182$. Both pairs occur more often than chance, and both targets are negative, because with two negatives for every positive a pair must occur at more than twice the chance rate before the model should call a presentation of it real. Directly: for $(a, b)$, $a = 8$ and $b = 2 \times 14 \times 14/40 = 9.8$, and $\ln(8/9.8) = -0.203$.

Problem 3 (why one dimension gives a constant). In the one-dimensional example above, gradient ascent found the matrix with $-\ln 2$ in every cell. Show that this is the best matrix among those with the same value in every cell, and that it is a stationary point of the one-dimensional problem, for any counts and any $k$. Say what is known about whether it is the best matrix of rank 1.

Solution. If every cell holds the same $x$, the objective is $\sum_{w,c} [a \ln \sigma(x) + b \ln \sigma(-x)] = A \ln \sigma(x) + B \ln \sigma(-x)$ with $A = \sum \#(w, c) = \lvert D \rvert$ and $B = \sum k\, \#(w)\, \#(c)/\lvert D \rvert = k \lvert D \rvert^2 / \lvert D \rvert = k \lvert D \rvert$. By Lemma 1 its only maximizer is $x = \ln(A/B) = \ln(1/k) = -\ln k$. For $k = 2$ that is $-0.693$. A constant matrix has rank 1, so it is available in one dimension: give every word the number 1 and every context the number $-\ln k$.

The constant matrix is also a stationary point of the one-dimensional problem, for any counts. At $x = -\ln k$, $\sigma(x) = 1/(k + 1)$ and $\sigma(-x) = k/(k + 1)$, so the derivative of the objective with respect to the dot product of cell $(w, c)$ is $g_{wc} = a\, \sigma(-x) - b\, \sigma(x) = (k\, \#(w, c) - b_{wc})/(k + 1)$. Summed over the contexts of one word, the numerator is $k\, \#(w) - k\, \#(w) \sum_c \#(c)/\lvert D \rvert = 0$, and summed over the words of one context it is 0 in the same way. In one dimension the derivative with respect to a word's number is $\sum_c g_{wc}$ times the contexts' common number, and the derivative with respect to a context's number is $\sum_w g_{wc}$ times the words' common number. Both vanish.

That the constant matrix is the best rank-1 matrix for the three-word counts is not proved here. The evidence is numerical. Of 300 runs of a quasi-Newton optimizer from random starting points, 298 end at it and none ends higher. The constant matrix is reached by a whole family of points, since multiplying every word's number by $t$ and dividing every context's by $t$ leaves the products unchanged. The other two runs drifted to badly scaled points, with word numbers above 1,400 in size and context numbers below 0.0005, and stopped there on the optimizer's test of relative progress, a little below the constant's objective, with every product already between −0.83 and −0.52. They are unfinished runs, not other stationary points: rescaled so that words and contexts have equal length, which leaves every product as it was, and restarted, both reach the constant matrix. At the point where every word has the number 1 and every context $-\ln 2$, the matrix of second derivatives has one zero eigenvalue, for that rescaling, and all its other eigenvalues are negative, the largest of them −1.88. Their sizes depend on which point of the family is taken (at words 2 and contexts $-\ln 2/2$ the largest nonzero one is −0.59); their signs were the same at every point tried.

Problem 4 (the weights of two cells). In the 2,000-word collection, (united, states) has $a = 71.56$ and $b = 0.85$, and (of, the) has $a = 41.87$ and $b = 131.75$. Compute each pair's target and weight. Then compute what the model loses by leaving the dot product of (united, states) at 3.46, the median trained value, exactly and by the quadratic approximation.

Solution. The targets are $\ln(71.56/0.85) = 4.43$ and $\ln(41.87/131.75) = -1.15$. The weights are $ab/(a+b) = 71.56 \times 0.85 / 72.41 = 0.84$ and $41.87 \times 131.75 / 173.62 = 31.77$. (The displayed $b$ is rounded; the weights are computed from unrounded values.) For the loss, the exact value is $f(x^*) - f(3.46)$ with $f(x) = 71.56 \ln \sigma(x) + 0.85 \ln \sigma(-x)$, which is 0.56. The quadratic approximation is $\tfrac{1}{2} \times 0.84 \times (4.43 - 3.46)^2 = 0.40$, which is rough this far from the peak. A shortfall of nearly a whole unit in the dot product of a pair seen 71.56 times costs the objective less than one unit, out of a total of $-327{,}078$ at the optimum. The same shortfall on (of, the) would cost about $\tfrac{1}{2} \times 31.77 \times 0.97^2$, nearly forty times as much by the same approximation.

Problem 5 (GloVe with fixed offsets). Show that GloVe's model equation with $b_i = \ln \#(w_i)$ and $\tilde{b}_j = \ln \#(c_j) - \ln \lvert D \rvert$ asks for $\vec{w}_i \cdot \tilde{w}_j = \mathrm{PMI}(w_i, c_j)$, and give the weight GloVe puts on a pair seen 10 times relative to one seen 100 times.

Solution. Substituting into $\vec{w}_i \cdot \tilde{w}_j + b_i + \tilde{b}_j = \ln X_{ij}$ and moving the offsets to the right, $\vec{w}_i \cdot \tilde{w}_j = \ln X_{ij} - \ln \#(w_i) - \ln \#(c_j) + \ln \lvert D \rvert = \ln \left( X_{ij} \lvert D \rvert / (\#(w_i)\, \#(c_j)) \right)$, which is the definition of the pointwise mutual information with $X_{ij} = \#(w_i, c_j)$. The weights are $g(10) = (10/100)^{3/4} = 0.1778$ and $g(100) = 1$, a ratio of 0.1778. The second-order weight of SGNS for the same two pairs would depend on how often each is drawn as a negative as well, which GloVe's weight ignores.

What we have learned

Skip-gram with negative sampling trains word and context vectors to tell observed pairs from sampled ones, and its gradient moves each vector in proportion to the model's error on one pair. Summed over the corpus, its objective splits into one concave term for each cell of the word-context table, and that term peaks where the dot product equals the pair's pointwise mutual information less $\ln k$. With enough dimensions and every pair observed, that is the unique optimum. With unobserved pairs there is no optimum, only dot products driven toward $-\infty$. With too few dimensions the model makes a weighted compromise that favors pairs both seen and sampled often. On Brown, 30 full-batch runs of that objective, which are not runs of word2vec, ended with an objective 52% further from zero than the least upper bound, against about 200% for the explicit matrices, and were no better than a singular value decomposition at ranking word pairs as people do. From seed to seed the dot products of well-observed pairs agreed, those of the many pairs with little evidence did not, and the neighbors of a word changed with them.

The theorem fixes only the products of word vectors with context vectors, which raises the question of how two word vectors should be compared at all. The next article, Similarity Measures for Embeddings, takes the vectors computed here and compares the dot product, the cosine and the Euclidean distance on them.

Every number on this page is computed by tools/experiments/dense/word-embeddings.py in the site's repository, with the corpus, the counts and the trainer in brown_sgns.py beside it. The script fails if the page shows a number it did not compute.

References

  • Church, K. W., and Hanks, P. (1990). Word association norms, mutual information, and lexicography. Computational Linguistics, 16(1), 22–29. record
  • Finkelstein, L., Gabrilovich, E., Matias, Y., Rivlin, E., Solan, Z., Wolfman, G., and Ruppin, E. (2002). Placing search in context: The concept revisited. ACM Transactions on Information Systems, 20(1), 116–131. record · 2 pages
  • Hill, F., Reichart, R., and Korhonen, A. (2015). SimLex-999: Evaluating semantic models with (genuine) similarity estimation. Computational Linguistics, 41(4), 665–695. record
  • Kingma, D. P., and Ba, J. (2015). Adam: A method for stochastic optimization. In Proceedings of the 3rd International Conference on Learning Representations (ICLR 2015). arXiv:1412.6980. record · 2 pages
  • Levy, O., and Goldberg, Y. (2014). Neural word embedding as implicit matrix factorization. In Advances in Neural Information Processing Systems 27, 2177–2185. record · 3 pages
  • Levy, O., Goldberg, Y., and Dagan, I. (2015). Improving distributional similarity with lessons learned from word embeddings. Transactions of the Association for Computational Linguistics, 3, 211–225. record
  • Mikolov, T., Chen, K., Corrado, G., and Dean, J. (2013a). Efficient estimation of word representations in vector space. arXiv:1301.3781. record · 3 pages
  • Mikolov, T., Sutskever, I., Chen, K., Corrado, G., and Dean, J. (2013b). Distributed representations of words and phrases and their compositionality. In Advances in Neural Information Processing Systems 26, 3111–3119. arXiv:1310.4546. record · 2 pages
  • Pennington, J., Socher, R., and Manning, C. D. (2014). GloVe: Global vectors for word representation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), 1532–1543. record · 5 pages