word2vec: learning from a word's neighbors

1Order, and n-grams

A bag of words x counts each word of the vocabulary in a text, as the note on linear models counted the words of each speech. Write w₁, …, w_N for the N words of a text in their order (in this note w is always a word, never a weight). Reordering them leaves every count as it was:

for any permutation π of the words. At the windmills, in chapter VIII of part I of Don Quixote, Sancho warns his master: “what we see there are not giants but windmills”. Swap giants and windmills and the same words say what Don Quixote believes. The two orders give the same x, so a model that reads only x treats them alike, however well trained. For telling Sancho from Don Quixote, as the note on linear models did, that cost little, since worship and thou give each away wherever they stand; here the order is the whole point, since it decides which of the two things is denied.

Counting short runs of words keeps a little of the order. A run of n words in a row is an n-gram: slide a window n words wide along the text, one word per step, and at each position i it frames one,

one position for each word that still has n − 1 words after it. Runs of two words are called bigrams and runs of three, trigrams; with n = 1 the runs are the single words again. In the figure, pick the order of Sancho's line and the length n.

The bigrams that tell the two orders apart are the one that starts at not and the two around but: “not giants” is Sancho's denial. The price is the vocabulary. Each different n-gram needs a coordinate of its own: the book has 143,448 different bigrams, almost ten times its 14,921 different words, and the longer the runs, the more of them come up only once:

A coordinate seen once says little about the next text, where the same run of words will rarely come back: the order won back is paid for with the repetition that made counts informative.

2Skip-grams: a word and its neighbors

word2vec keeps the window, but what it frames no longer becomes coordinates: it becomes examples to learn each word's vector from, so the vocabulary stays at the book's 14,921 words. The window centers on one word, the target, and pairs it with every word up to m positions away on either side, its context words:

a window of 2m + 1 words. A pair is written (o, c), o for the target and c for the context word, and S is the set of all the pairs, |S| their number. With m = 2, the word see pairs with we and there beside it and with what and are one word further off; the pair (see, what) leaves out we, the skipped word that gives skip-grams their name. In the figure, pick a target in Sancho's line and the radius m.

Over the whole book, with m = 2, its N = 404,923 tokens give 1,619,686 pairs, the examples the opening promised. The original word2vec program does not use the same radius for every target: it draws one from 1 to m for each, so that nearer words make more pairs. The classifier of the next section ignores j: it guesses which words appear within m of the target, not where.

3Guessing the neighbors

word2vec has two models, and this note follows the skip-gram, which guesses the neighbors from the word (the other, CBOW, for continuous bag of words, guesses the word from its neighbors). Given a target o, it gives every word c of the vocabulary a probability of appearing around it: it is the softmax of the note on linear models with one class per word, V classes in all:

Each word w has two vectors of d numbers, v_w for when it is the target and u_w for when it is a context word, so a pair (o, c) is scored by u_c^Tv_o, as a speech was scored in the note on linear models, weights times counts: u_c takes the place of class c's weights and v_o that of the counts.

The vectors fill two tables, the weights of a small network: a model built in layers, each multiplying what it receives by a table of weights and often passing the result through a fixed function; here the first layer only multiplies and the second adds the softmax. W_in ∈ ℝ^V×d, V rows of d numbers, holds the targets' vectors, row o being v_o; W_out ∈ ℝ^d×V, V columns of d numbers, holds the context words' vectors, column c being u_c.

The target enters as a one-hot vector x, 1 at o and 0 everywhere else: the bag of words of a text one word long. The network's forward pass takes it through the two layers in three equations, which select a row, score every word and normalize the scores:

W_in^Tx adds up the rows of W_in weighted by the entries of x, and a one-hot x keeps only row o: the vector passed from one layer to the next, the hidden layer (hidden because no data supplies it), is v_o itself. Each entry of z is one word's score, z_c = u_c^Tv_o, and y holds p(c | o) for every word c. Training changes the numbers of both tables by gradient descent, as in the note on linear models, to make that note's −log p small, with p now the probability the model gave the word that really appeared; averaged over the pairs, it is the cross-entropy

The figure shows a model trained this way on the 30 pairs of Sancho's line, with V = 9 words and vectors of d = 3 numbers. Pick a target and follow the three steps.

A word inside the line gives about a quarter to each of its four neighbors and much less to the other words. The guess that makes ℒ smallest gives each word the share of the target's pairs that it appears in, a quarter to each neighbor and nothing to the others, which on these pairs puts ℒ at 1.24; the model's loss, 1.29, comes close to it. Training keeps W_in: its rows are the vectors this note is after. The columns of W_out could serve as word vectors as well, and some systems add the two tables, but the original program saves only W_in.

On the collections of text, or corpora, that word2vec was made for, d is a few hundred and V hundreds of thousands or more. With a few hundred numbers for each of so many words, the model cannot store a separate guess for every word, as the figure's nine words nearly could with three: words with similar neighbors end up with similar numbers, which the next note looks at.

4Negative sampling

To normalize, every pair needs all V scores, 14,921 for this book alone, and the sum of their exponentials. Negative sampling does away with them. Take the pair (giants, windmills) of Sancho's line. Negative sampling sets beside it k pairs of giants with words drawn at random from the book, such as (giants, habit): the negatives. It labels the observed pair y = 1 and the drawn ones y = 0, and asks of each pair only whether the text produced it, answering with the probability that it did, written P(+ | o, c): the logistic function of its score,

where σ is the logistic function that the note on linear models wrote θ. With S now holding both kinds of pairs, the loss is that note's binary cross-entropy:

Each observed pair now needs k + 1 scores instead of V. Mikolov and his colleagues introduced the method late in 2013, in their second paper on word2vec, where k from 5 to 20 worked on small corpora, while on large ones k could be as small as 2 to 5; the paper tested negative sampling on a billion words of news, with a vocabulary of 692,000 words. Each pair contributes the (h − y)x of the note on linear models, with the other vector as x: (h − y)v_o to its context vector and (h − y)u_c to the target's; averaged over the pairs, as that note averaged over the speeches, these give ℒ's gradient.

A dot product reads the same from either side, so the roles of section 3 can swap: seen from the target, negative sampling is logistic regression with v_o as the weights and each context vector as a point. The line where u^Tv_o = 0 splits the points whose pairs look real from the rest, and unlike in the note on linear models, the points move too.

The figure follows the pair (giants, windmills) and three words drawn from the book, with vectors of two numbers so that they can be plotted, each word labeled with its pair's h. It repeats that example's step ten times, with the same drawn words, to show where the steps lead; in training, each pair takes a single step per reading of the text, with new drawn words every time: stochastic gradient descent, one step per example rather than one on the average of all of them. Take steps of gradient descent with a learning rate η = 1.2.

The observed pair's h climbs toward 1 and the drawn words' fall toward 0: the target's vector turns toward windmills and away from the drawn words, which step away from it as well. Over the book, each of the 1,619,686 pairs takes such steps, and the vectors settle where all those pulls balance.

5How the negatives are drawn

Which words to draw? If every word of the vocabulary had the same chance, more than a third of the draws would be words seen only once in the whole book: easy negatives, since such a word is almost never near any target, and rejecting it teaches the model little. Drawing by frequency instead would make a quarter of the draws one of the ten most frequent words, led by the, and, to and of, which appear next to any word and so do not help tell words apart either. word2vec draws by the frequency raised to a power β between 0 and 1:

where f(w) is the number of times w appears in the text it trains on (in the figure, the book) and the sum runs over the vocabulary; β = 0 gives every word the same chance and β = 1 draws by frequency. Mikolov and his colleagues chose ¾ by experiment, because it worked better than either. In the figure, pick β and draw ten words from the book; the faint curve is β = 1, kept for comparison.

On the log–log axes of the first note, the book's frequencies fall along a nearly straight line, Zipf's law. Raising them to the power β multiplies its slope by β, so β = ¾ makes the line flatter: frequent words lose and rare ones gain. The two lines cross at the words seen about 262 times, and dulcinea, at rank 172, is the first word that β = ¾ draws more often than β = 1 does. The word the falls from 5.1% of the draws to 1.7%, and windmills, seen 10 times, more than doubles its chance.

6Summary

The note's ideas in NumPy. words is a text as a list of words; w_in and w_out are the two matrices, a row of w_in and a column of w_out per word of the vocabulary; o and c are words' positions in the vocabulary, and neg those of the k drawn words; f holds the words' counts, beta is β and rng is a NumPy random generator.