Word embeddings: word2vec and GloVe

A word embedding is a short list of numbers that stands for a word, learned so that words used in similar ways get similar lists. word2vec learns these vectors by predicting the words around each word, and GloVe fits the same kind of vectors to counts of which words appear together. We'll work through both on the sentence "we sat on the bank of the river", then look at what the finished vectors capture, including associations we would rather they didn't.

Keep the vectors, drop the expensive parts

Words that appear in similar contexts tend to have similar meanings. "Bank" and "shore" both fit the gap in "we sat on the ___ of the river", so a good description of each word should place them close together.

A neural language model already learns such descriptions [1]. It reads the last few words through a lookup table of word vectors, combines them in a hidden layer, and scores every word in the vocabulary to predict the next one. The rows of the lookup table become word embeddings as a by-product. Most of the computation, though, goes into the hidden layer and into scoring the whole vocabulary for every prediction.

word2vec keeps the lookup table and removes the hidden layer [2]. It also changes the task. Instead of predicting the next word from the words before it, it predicts words on both sides from each other. On the same 6 billion words of Google News, a neural language model with 100-dimensional vectors took 14 days on 180 CPU cores and answered 50.8% of a set of analogy questions correctly. word2vec's skip-gram model, with 1,000-dimensional vectors, took 2.5 days on 125 cores and answered 65.6%.

Skip-gram predicts the neighbors

The training examples come from a context window that slides over the text. With two words on each side, the window around "bank" covers "on", "the", "of" and "the", and each of those words makes one training pair with "bank":

Moving the window across all eight words gives 26 pairs. Each pair asks the model to predict the second word, the context word $c$, from the first, the input word $w$. This model is called skip-gram.

Every word gets two vectors: an input vector $\mathbf{v}_w$, used when the word is read, and an output vector $\mathbf{u}_c$, used when it is predicted. The score for a pair is the dot product of the two, and softmax turns the scores for every word in the vocabulary $V$ into probabilities:

$$P(c \mid w) = \frac{e^{\mathbf{u}_c \cdot \mathbf{v}_w}}{\sum_{j \in V} e^{\mathbf{u}_j \cdot \mathbf{v}_w}}$$

With four numbers per vector, say $\mathbf{v}_{\text{bank}} = (0.8, 0.6, -0.4, 1.0)$ and $\mathbf{u}_{\text{of}} = (1.0, 0.5, -0.5, 0.7)$, the score for the pair (bank, of) is

$${\mathbf{u}_{\text{of}} \cdot \mathbf{v}_{\text{bank}}} = {0.8 + 0.3 + 0.2 + 0.7} = 2.0$$

Training raises $P(c \mid w)$ for every pair in the text. Words that keep appearing near the same neighbors get input vectors that score those neighbors highly, so "bank" and "shore" end up with similar input vectors. Those input vectors are the embeddings we keep.

There is no hidden layer between the two vectors, only a dot product. The cost that remains is the denominator, which needs one score for every word in the vocabulary.

CBOW predicts the word from its neighbors

The continuous bag-of-words model, CBOW, turns the prediction around. It averages the input vectors of the words in the window and predicts the word in the middle:

$$\bar{\mathbf{v}} = \tfrac{1}{4}\,\big(\mathbf{v}_{\text{on}} + \mathbf{v}_{\text{the}} + \mathbf{v}_{\text{of}} + \mathbf{v}_{\text{the}}\big)$$

It then scores each candidate center word $w$ against that average, the same way skip-gram scores a neighbor:

$$P(w \mid \bar{\mathbf{v}}) = \frac{e^{\mathbf{u}_w \cdot \bar{\mathbf{v}}}}{\sum_{j \in V} e^{\mathbf{u}_j \cdot \bar{\mathbf{v}}}}$$

Training raises this probability for $w = \text{bank}$. Averaging ignores the order of the four words, as a bag of words does, which is where the name comes from. CBOW makes one prediction per position, while skip-gram makes one per pair, so CBOW is faster. Trained three times over the same 783 million words, CBOW took about a day and skip-gram about three, and skip-gram's vectors answered 50.0% of the analogy questions about meaning against CBOW's 15.5% [2].

Negative sampling skips the full softmax

A vocabulary can hold hundreds of thousands of words, and the softmax needs a score for each of them for every training pair. Negative sampling replaces that prediction with a cheaper question: is this pair real, or was the second word picked at random [3]? For each real pair the model draws $k$ random words $n_1, \dots, n_k$ and treats them as fake neighbors. The sigmoid turns a dot product into the probability that a pair is real:

$$\sigma(x) = \frac{1}{1 + e^{-x}}$$

The loss rewards a high probability for the real pair and a low one for each random pair, using $1 - \sigma(x) = \sigma(-x)$:

$$L = -\log \sigma(\mathbf{u}_c \cdot \mathbf{v}_w) \;-\; \sum_{i=1}^{k} \log \sigma(-\mathbf{u}_{n_i} \cdot \mathbf{v}_w)$$

Take the real pair (bank, of), with the score of 2.0 from before, and $k = 2$ random words, "car" with a score of $-1.0$ and "sang" with a score of $0.5$. The probabilities that each pair is real are $\sigma(2.0) = 0.881$, $\sigma(-1.0) = 0.269$ and $\sigma(0.5) = 0.622$, so

$$L = -\log 0.881 - {\log(1 - 0.269)} - {\log(1 - 0.622)} \approx 1.41$$

Most of the loss comes from "sang", which the model still rates as a likely neighbor. The gradient pushes $\mathbf{u}_{\text{of}}$ toward $\mathbf{v}_{\text{bank}}$ and pushes $\mathbf{u}_{\text{sang}}$ and $\mathbf{u}_{\text{car}}$ away from it. Each pair now costs $k + 1$ dot products instead of one per vocabulary word. The paper used $k$ between 5 and 20 for small datasets and as few as 2 to 5 for large ones, and drew the random words in proportion to their frequency raised to the power $3/4$, which picks rare words a little more often than their raw frequency would.

The same paper also discards very frequent words such as "the" at random during training. A word like "the" appears next to almost everything, so dropping most of its pairs loses little information and made training 2 to 10 times faster.

Directions carry relations

After training, distances between vectors reflect how words are used, and so do differences. The step from "man" to "woman" points roughly the same way as the step from "king" to "queen":

So we can answer "man is to woman as king is to what?" with arithmetic. We take the vector for "king", subtract "man", add "woman", and look for the nearest word by cosine similarity, leaving out the three words in the question:

$$\mathbf{v}_{\text{king}} - \mathbf{v}_{\text{man}} + \mathbf{v}_{\text{woman}} \approx \mathbf{v}_{\text{queen}}$$

The word2vec paper built a test of 19,544 such questions, 8,869 about meaning ("Athens is to Greece as Oslo is to ?") and 10,675 about grammar ("walking is to walked as swimming is to ?"). A question counts only if the nearest word is exactly right, so synonyms count as mistakes. This is the test behind the accuracies above, where skip-gram's 1,000-dimensional vectors scored 65.6% [2]. Nothing in training mentions capitals, tenses or gender. The relations come from the windows alone.

GloVe fits the counts directly

Skip-gram learns from one window at a time. The same information can be collected first, as a co-occurrence matrix $X$, where $X_{ij}$ counts how often word $j$ appears within the window of word $i$. With two words on each side, the row for "bank" in our sentence has 1 for "on", 2 for "the" and 1 for "of".

GloVe, for global vectors, learns from this matrix [4]. Its starting observation is that the ratio of two co-occurrence probabilities says more than either one. Over 6 billion words, "solid" appears near "ice" 8.9 times as often as near "steam", "gas" only 0.085 times as often, and "water" and "fashion", which relate to both or neither, about equally often. The table gives the ratio ${P(k \mid \text{ice}) / P(k \mid \text{steam})}$ for each context word $k$:

context word $k$	ice / steam ratio
solid	8.9
gas	0.085
water	1.36
fashion	0.96

A ratio like this is a difference of logarithms, so GloVe asks the dot product of two vectors to match the logarithm of their count. Each word gets a word vector $\mathbf{w}_i$, a context vector $\tilde{\mathbf{w}}_j$ and a bias for each role:

$$\mathbf{w}_i^{\top}\tilde{\mathbf{w}}_j + b_i + \tilde{b}_j \approx \log X_{ij}$$

For "bank" and "the", the target is $\log 2 \approx 0.69$. The fit is a weighted least-squares problem. We write the error for one pair as the difference between the two sides,

$$e_{ij} = \mathbf{w}_i^{\top}\tilde{\mathbf{w}}_j + b_i + \tilde{b}_j - \log X_{ij}$$

and GloVe minimizes the weighted sum of squared errors over all pairs with a non-zero count:

$$J = \sum_{i,j} f(X_{ij})\, e_{ij}^2$$ $$f(x) = \begin{cases} (x / 100)^{3/4} & x < 100 \\ 1 & \text{otherwise} \end{cases}$$

The weight $f$ keeps rare pairs, whose counts are noisy, from counting as much as frequent ones, and caps the weight of very frequent pairs. Our pair (bank, the), seen twice, gets $f(2) = (2/100)^{3/4} \approx 0.053$. Pairs that never occur have $f(0) = 0$ and drop out, which matters because 75 to 95% of a real co-occurrence matrix is zeros. In the paper's own counts a neighbor $d$ words away adds $1/d$ rather than 1, so the closer "the" counts fully and the farther one counts half. The final embedding of a word is the sum $\mathbf{w}_i + \tilde{\mathbf{w}}_i$.

Trained on the same 6 billion words with 300 dimensions, GloVe answered 71.7% of the analogy questions, against 69.1% for skip-gram and 65.7% for CBOW [4]. The two approaches are closer than they look: the GloVe paper shows that skip-gram's objective, summed over a corpus, is itself a weighted sum over the same co-occurrence counts.

The vectors learn the text's stereotypes

Embeddings learn every regularity in their training text, including the ones we would not want a system to repeat. In the publicly released word2vec vectors trained on Google News, 3 million words and phrases in 300 dimensions, the analogy "man is to computer programmer as woman is to ?" returns "homemaker", and "father is to doctor as mother is to ?" returns "nurse" [5].

The same arithmetic finds the direction from "she" to "he" and measures where other words fall along it. The occupations at the two ends were these:

closest to she	closest to he
homemaker	maestro
nurse	skipper
receptionist	protege
librarian	philosopher
socialite	captain
hairdresser	architect

None of these occupation words marks gender in its spelling. The direction comes from how news text uses them. A search engine or classifier that takes these vectors as input inherits the associations, which is why the same paper proposed removing the gender direction from words that should be neutral.

Still no reader for a whole sentence

Every word now has a vector that places it near words used the same way, and these vectors are cheap to train on billions of words. A sentence, though, is still a sequence of separate vectors. To read "we sat on the bank of the river", a model has to combine eight vectors in order. Averaging them gives the same result for any ordering of the words, and joining them side by side, as a neural language model does, works only for a fixed number of words. The model that reads a sentence of any length, one word after another, is still missing.

References

1. Bengio, Y., et al. (2003). A neural probabilistic language model. Journal of Machine Learning Research 3. jmlr.org ↩
2. Mikolov, T., et al. (2013). Efficient estimation of word representations in vector space. ICLR Workshop. arXiv:1301.3781 ↩
3. Mikolov, T., et al. (2013). Distributed representations of words and phrases and their compositionality. Advances in Neural Information Processing Systems 26. arXiv:1310.4546 ↩
4. Pennington, J., Socher, R., & Manning, C. D. (2014). GloVe: Global vectors for word representation. Proceedings of EMNLP 2014. aclanthology.org ↩
5. Bolukbasi, T., et al. (2016). Man is to computer programmer as woman is to homemaker? Debiasing word embeddings. Advances in Neural Information Processing Systems 29. arXiv:1607.06520 ↩