Learning skip-gram embeddings with negative sampling

Take a vocabulary of 10,000 words and embeddings of dimension d = 300. How many numbers does Skip-gram learn? The natural guess is one vector per word, so 3,000,000. The real answer is twice that, 6,000,000, because every word owns two rows.

The parameters θ are two matrices stacked on top of each other. The top block W has one row per vocabulary word, indexed 1 to |V|; these are the target embeddings, used when a word sits at the center of a window. The bottom block C has another row per word, indexed |V| + 1 to 2|V|; these are the context embeddings, used when a word appears as a neighbor or is drawn as a noise word. So apricot has a row w_apricot in W and a separate row c_apricot in C, and together these are the Target and context matrices. SLP3 (Fig. 5.6) calls the W rows the input embeddings and the C rows the output embeddings, which is also the vocabulary of Mikolov et al. and of Rong's derivation notes.

The reason for two tables becomes clear once you look at what the classifier from part 07 actually computes. It only ever takes a Dot product between a context row and a target row, c · w. A target never meets another target, and a context never meets another context. W and C are therefore two different roles, and the model is free to learn different coordinates for each role. Every row is a Dense vector of length d; nothing here is sparse or counted.

Take the sentence fragment "lemon, a tablespoon of apricot jam, a pinch" with apricot as the target and a ±2 window. The four words inside the window give four positive pairs: (apricot, tablespoon), (apricot, of), (apricot, jam) and (apricot, a). No human labeled them; the corpus did, which is the Self-supervision idea from part 07.

A classifier trained only on positives would learn to say "yes" to everything. So each positive pair is matched with k negative pairs, built by keeping the target and replacing the context with a noise word drawn at random from the lexicon. With k = 2 the four positives above get eight negatives, for example aardvark, my, where, coaxial, seven, forever, dear and if. The slide lists these eight as one pool, so the way the table below assigns two to each positive is only illustrative. This is Negative sampling: the model learns to tell real neighbors from random words, rather than to predict the exact neighbor out of all |V| words.

Which random words? The flattened unigram

Noise words are not drawn uniformly, and not quite in proportion to frequency either. They are drawn from the unigram distribution raised to the power α = 0.75 and renormalized, the same Alpha-weighted context probability trick part 06 used to stop Pointwise mutual information from overrating rare contexts. The only constraint SLP3 imposes is that the noise word is not the target itself.

Raising probabilities to a power below one compresses their range. Frequent words lose a little mass, rare words gain proportionally much more, so the model sees rare words as negatives often enough to learn something about them, while frequent function words still dominate. The two-word example from part 06 (slide 60, SLP3 eq. 5.20) applies unchanged: with P(a) = 0.99 and P(b) = 0.01, the rare word roughly triples its chance of being drawn, to about 0.03, while a drops only to 0.97. The arithmetic is identical; what changes is the role. In part 06 the flattened distribution sat in a PMI denominator, here it decides which words are sampled as noise.

Mikolov et al. (2013) report that U(w)^{3/4} / Z "outperformed significantly" both the raw unigram and the uniform distribution. They recommend k between 5 and 20 for small datasets and 2 to 5 for large ones. The reference C code and gensim both default to negative = 5 and an exponent of 0.75 (gensim calls it ns_exponent). Levy, Goldberg and Dagan (2015) named the same move context distribution smoothing and showed it consistently improves count-based PMI vectors too, not just word2vec.

Fix one training instance: target w = apricot, positive context c_pos = jam, and k = 2 noise words matrix and Tolstoy. The loss for this instance is

The first term is small when the classifier is confident that jam is a neighbor. Each of the other two is small when the classifier is confident that the noise word is not. Where does this shape come from? We want the classifier to give high probability to the correct label of every pair in the instance: label + for the positive and label − for each noise word. Treating the k + 1 decisions as independent, and minimizing the negative log of their joint probability, gives the cross-entropy loss in four short steps.

1. Independence turns the joint probability of the k + 1 labels into a product, and the minus log turns maximizing probability into minimizing a loss.
2. The log of a product is a sum of logs.
3. A pair is either a neighbor or not, so P(− | w, c) = 1 − P(+ | w, c).
4. Plug in P(+ | w, c) = σ(c · w) from part 07 and use the Sigmoid identity 1 − σ(x) = σ(−x).

The negative terms are not decoration. Goldberg and Levy (2014) point out that with positives alone the objective has a trivial solution: make every vector the same, with a large enough norm that every dot product is huge, and every positive gets probability 1 (they note this happens once the dot product reaches about 40). Such vectors are useless, since every word looks like every other. The noise terms make that collapse expensive, because identical vectors would also give every noise pair probability 1.

Take the instance from the previous concept, "...apricot jam..." with k = 2 noise words matrix and Tolstoy. One learning step does three things at once. It moves apricot's target vector w and jam's context vector c_jam toward each other, so c_pos · w rises. It moves w and c_matrix apart, and w and c_Tolstoy apart, so both c_neg · w values fall. Every other row of θ, including aardvark and zebra in both W and C, is left exactly as it was.

The rule behind the picture is gradient descent. The gradient ∇_θ L is the vector of partial derivatives of the loss with respect to every parameter; it points in the direction in which the loss grows fastest. To reduce the loss, step the opposite way, by an amount scaled by the Learning rate η.

"Stochastic" means the gradient is computed from one training instance (or a small batch) at a time, not from the whole corpus. The training loop walks through the corpus, takes each target and each of its window positives, samples k noise words, computes the loss for that small instance, and steps. Because the loss of one instance involves only w, c_pos and the k noise contexts, the gradient is zero for every other row, and the update touches just 2 + k rows out of 2|V|. That sparsity is what makes word2vec fast enough to train on billions of tokens.

The fastest way to trust the update equations is to run one by hand. Use tiny vectors so every number is visible, then read the general rule off the arithmetic.

Where the gradients come from

Two derivative facts do all the work, both about the Sigmoid derivative. From dσ/dz = σ(z)(1 − σ(z)) it follows that d/dz log σ(z) = 1 − σ(z) and d/dz log σ(−z) = −σ(z). Apply them with the chain rule, remembering that z = c · w has derivative w with respect to c and c with respect to w, and the minus sign in front of the loss flips the signs.

All three have the same shape: (prediction minus label) times the other vector. Write y = 1 for a positive pair and y = 0 for a noise pair; each gradient is (σ(c · w) − y) times the partner vector. The reference word2vec.c computes exactly this as g = (label − sigmoid) * alpha, folding the learning rate and the sign into one number. Plugging the gradients into θ^{t+1} = θ^t − η ∇L gives the three update rules.

When training ends, apricot still has two rows, w_apricot and c_apricot. SLP3 says the common choice is to add them and represent apricot by w_apricot + c_apricot; the alternative is to keep only w_apricot and throw C away. Either way the result is a Static embedding: one fixed vector per word type, compared with Cosine similarity.

Why keep the tables apart during training at all? Goldberg and Levy (2014) give the argument. Suppose dog had a single vector v used in both roles. Then the score for the pair (dog, dog) would be v · v = |v|², which is large for any vector with a large norm, so the model would believe dog is its own most likely neighbor. Real text rarely says "dog dog", so the model would have to keep word norms small to avoid that, fighting its own objective. Two tables remove the conflict.

Why does adding them afterwards help? Levy, Goldberg and Dagan (2015) show that the cosine of two summed vectors includes terms like w_x · c_y, which measure whether x and y appear in each other's contexts. Adding context vectors therefore adds first-order similarity (co-occurrence) to the second-order similarity (shared neighbors) that W alone captures. The trick comes from GloVe, whose authors summed the two sets of vectors as a cheap way of combining two models, much like an ensemble.

The whole recipe

1. Initialize W and C randomly: 2|V| vectors of dimension d. (word2vec.c draws W uniformly in ±0.5 / d and starts C at zeros.)
2. Slide a window over the corpus. Each (target, neighbor) pair is a positive; for each, draw k noise words from P_α as negatives.
3. Train the logistic classifier σ(c · w) to separate positives from negatives, minimizing L_CE with SGD.
4. Throw the classifier away and keep the learned rows as the embeddings, summed or W only.

Step 4 is the heart of Self-supervision: the yes-or-no prediction task was never the goal. It was a pretext that forced the model to place words with similar contexts close together, and the Embedding is the by-product we wanted.