Word2Vec Skip-gram

Skip-gram is a self-supervised objective for learning word embeddings from raw text, with no human-provided labels. The supervision signal is generated automatically from co-occurrence: for every word $w_t$ in the corpus, the words within a small window around it — say $w_{t-2}, w_{t-1}, w_{t+1}, w_{t+2}$ — are treated as the "correct answers" the model should predict given $w_t$ as input. This is the mirror image of Continuous Bag-of-Words (CBOW), which instead predicts the center word from its context; skip-gram predicts outward from the center. Formally, each word type $w$ in the vocabulary $V$ is assigned two vectors: a target (center) embedding $\mathbf{v}_w \in \mathbb{R}^d$, and a context embedding $\mathbf{u}_w \in \mathbb{R}^d$. These live in two separate weight matrices, $W \in \mathbb{R}^{|V|\times d}$ (rows are target vectors) and $W' \in \mathbb{R}^{|V|\times d}$ (rows are context vectors). The model defines the conditional probability of a context word $c$ given a center word $w$ via a softmax over a dot-product score, exactly the same log-bilinear form used in multinomial logistic regression:

There is deliberately no hidden nonlinearity — the architecture is a linear projection into a shared embedding space followed directly by a softmax classifier. This is what makes the model cheap enough (in principle) to train on web-scale corpora, and it is also why the induced geometry is so linear: the score is literally an inner product, so directions in the embedding space correspond to consistent semantic/syntactic shifts.

Training proceeds by maximum likelihood: for every (center, context) pair observed within a window in the corpus, increase $P(c\mid w)$. Concretely, given a corpus of $T$ tokens $w_1, \ldots, w_T$ and window size $m$, the corpus log-likelihood objective is

and we perform gradient ascent on $J$ (equivalently, descent on $-J$) with respect to all entries of $W$ and $W'$.

Deriving the gradient. Fix one training pair $(w, c)$. Let $z = \mathbf{v}_w$ be the center vector and write the score of context word $c'$ as $s_{c'} = \mathbf{u}_{c'} \cdot z$. The per-example loss is

Differentiating with respect to the score vector $\mathbf{s} = (s_1, \ldots, s_{|V|})$ gives the classic softmax-cross-entropy gradient,

i.e. the model's predicted probability minus the one-hot true label — the same "error signal" you derive for ordinary softmax regression. Since $s_{c'} = \mathbf{u}_{c'}\cdot \mathbf{v}_w$, the chain rule gives update directions for every context vector and for the center vector:

Note the second equation sums over the entire vocabulary — this is the crux of the efficiency problem discussed below.

Training loop. At the corpus level, we slide a window over the text, generate all (center, context) pairs inside it, and take a stochastic gradient step per pair (or a mini-batch of pairs). ``` function TRAIN_SKIPGRAM(corpus, V, d, window_size m, learning_rate eta, epochs E): initialize W as |V| x d matrix of small random values # target embeddings initialize W' as |V| x d matrix of small random values # context embeddings for epoch in 1..E: for t in 1..length(corpus): w := corpus[t] # center word context_positions := [t-m, ..., t-1, t+1, ..., t+m] ∩ valid indices for t' in context_positions: c := corpus[t'] # true context word v_w := W[w] # center vector, length d

# forward pass: softmax over full vocabulary scores := [ dot(W'[c'], v_w) for c' in 1..|V| ] probs := softmax(scores) # length |V|

# backward pass error := probs # copy error[c] := error[c] - 1 # probs - one_hot(c) grad_v_w := zeros(d) for c' in 1..|V|: grad_v_w += error[c'] W'[c'] W'[c'] := W'[c'] - eta error[c'] v_w # update context vector c' W[w] := W[w] - eta grad_v_w # update center vector w return W, W' # keep W (or (W+W')/2) as the final word embeddings ``` Two implementation notes matter. First, updates to $W'$ touch every row on every single training pair, because the softmax denominator involves all vocabulary words — this is what negative sampling later replaces with a handful of rows. Second, the two matrices are usually not tied; after training, practitioners typically discard $W'$ and use $W$ (or the average $\tfrac{1}{2}(W+W')$) as the final embedding table, since $W$ is the representation that every word plays the "input" role for.

Time complexity. For a single (center, context) training pair, the forward pass computes $|V|$ dot products of length $d$ to build the softmax scores, costing $O(|V|\,d)$; the backward pass touches every row of $W'$ again for the same cost, $O(|V|\,d)$. Over a corpus of $T$ tokens with window size $m$, there are $O(T\,m)$ training pairs, so one epoch of naive skip-gram costs

With realistic settings ($|V|$ in the hundreds of thousands, $d \sim 300$), this is the dominant cost and is prohibitive at web scale — this is exactly why practical word2vec systems never use the plain softmax described above, and instead use negative sampling (each update touches only $k+1 \ll |V|$ rows, giving $O(T\,m\,k\,d)$) or hierarchical softmax (a binary tree reduces the per-example cost to $O(T\,m\,d\log|V|)$). Those are the subjects of the companion article; the pseudocode above is the reference objective they approximate.

Space complexity is $O(|V|\,d)$ for each of $W$ and $W'$, i.e. $O(|V|\,d)$ total, independent of corpus size — the parameter count depends only on vocabulary size and embedding dimension, which is what makes embeddings reusable across downstream tasks regardless of how large the training corpus was.

Correctness argument. Skip-gram is exact maximum-likelihood estimation of a well-defined probabilistic model, so "correctness" reduces to two claims: (1) the objective is a valid log-likelihood, and (2) gradient ascent on it is a sound optimization procedure. For (1): $P(c\mid w)$ as defined is a genuine categorical distribution over $V$ for each $w$ (nonnegative, sums to 1 by construction of softmax), so $J(\theta)$ is precisely the average log-likelihood of the observed (center, context) pairs under this model — the same object one maximizes in any softmax classifier. Because $J$ is a sum of log-likelihoods of i.i.d.-style observations (treating each window pair as a sample), maximizing it is the standard MLE recipe; consistent parameter estimation follows under the usual regularity conditions, modulo the fact that the "labels" here are自generated from co-occurrence rather than ground truth. For (2): the per-pair loss $\ell$ is convex in the score vector $\mathbf{s}$ (softmax cross-entropy is a convex function of its input logits), which is why the softmax gradient has the clean, well-behaved form $\text{probs} - \text{one-hot}$ derived above — this is the same gradient identity used in multinomial logistic regression, and it guarantees that each SGD step moves scores in a direction that provably decreases the per-example loss for a small enough step size. The full objective $J(\theta)$ is not jointly convex in $(W, W')$ because the score is a bilinear (product) function of the two embedding matrices, so global convergence is not guaranteed — like most deep learning objectives, we only get convergence to a stationary point of a non-convex landscape. Empirically this stationary point is good: the vectors that come out satisfy analogical linear structure ($\mathbf{v}_{\text{king}} - \mathbf{v}_{\text{man}} + \mathbf{v}_{\text{woman}} \approx \mathbf{v}_{\text{queen}}$), which can be explained heuristically because the loss encourages $\mathbf{u}_c \cdot \mathbf{v}_w$ to track $\log \frac{P(c\mid w)}{Z(w)}$, i.e. embeddings end up organized around log co-occurrence ratios — the same statistical quantity that GloVe optimizes for directly and explicitly.

Honest tradeoff. Skip-gram (with negative sampling) tends to do better on rare words than CBOW, because it generates one training example per context word rather than averaging context vectors together, giving rare words more individual gradient signal — at the cost of more training pairs (and thus more compute) per pass over the same corpus.

Take the toy sentence, window size $m=1$, vocabulary $V = \{\text{the, cat, sat, on, mat}\}$, $|V|=5$, embedding dim $d=2$: > the cat sat on the mat Tokenized with positions: `[the(1), cat(2), sat(3), on(4), the(5), mat(6)]`.

Step 1 — generate (center, context) pairs with $m=1$ (each word paired with its immediate left/right neighbor):

This yields 10 training pairs total from a 6-token sentence — illustrating the $O(Tm)$ pair count.

Step 2 — one gradient step in detail. Take the pair (center = "cat", context = "the"). Suppose after random initialization the relevant rows are:

Compute raw scores $s_{c'} = \mathbf{u}_{c'} \cdot \mathbf{v}_{\text{cat}}$:

Softmax (using $\exp$ and normalizing; exponentials rounded to 4 dp): $\exp(s)$: the $=0.9465$, cat $=1.0000$, sat $=0.9802$, on $=0.9704$, mat $=1.0356$. Sum $= 4.8327$.

True label is "the", so the error vector (probs minus one-hot) is:

The loss $\ell = -\log P(\text{the}\mid\text{cat}) = -\log(0.1959) \approx 1.6304$ — high, as expected before training, since the model has not yet learned that "the" should follow "cat". Gradient w.r.t. $\mathbf{v}_{\text{cat}}$ is $\sum_{c'} \text{error}_{c'}\, \mathbf{u}_{c'}$, which (working through the sum) points mostly in the $-\mathbf{u}_{\text{the}}$ direction because that error term dominates. Applying the update with $\eta = 0.1$ pushes $\mathbf{v}_{\text{cat}}$ toward $\mathbf{u}_{\text{the}}$'s direction and pushes $\mathbf{u}_{\text{the}}$ toward $\mathbf{v}_{\text{cat}}$ — exactly the intended effect: repeated exposure to "cat" and "the" co-occurring nudges their vectors closer, while $\mathbf{u}_{\text{mat}}$ and the others (which had positive error, i.e. over-predicted) are nudged slightly away. Over thousands of such updates across the whole corpus, words sharing many context partners converge to nearby vectors.

Skip-gram embeddings (and the broader word2vec toolkit) became a near-universal preprocessing step in NLP pipelines throughout the mid-2010s: search engines used them for query expansion and semantic matching, recommendation systems embedded item and user tokens with the same architecture, and countless text-classification and named-entity-recognition systems bootstrapped their input layer from pretrained word2vec vectors rather than learning embeddings from scratch on small labeled datasets. The core idea — learn a representation by solving an auxiliary prediction task on unlabeled data — is the direct ancestor of pretraining objectives in modern contextual encoders and large language models, even though those models replace the shallow log-bilinear score with deep Transformer-style attention. Understanding skip-gram is the cleanest way to see the distributional hypothesis turned into a concrete, trainable, differentiable objective, which is why it remains the canonical worked example before moving on to Continuous Bag-of-Words (CBOW), Negative Sampling and Training Word2Vec, and GloVe.

Ask the tutor: How exactly does negative sampling replace the full softmax while still approximating the same probabilistic objective?