Distributed Representations of Words and Phrases and Their Compositionality

The simplest way to feed a word to a neural network is one-hot encoding: a vector of zeros with a single 1 at the word's index. If the vocabulary has 100,000 words, every word becomes a 100,000-dimensional vector — enormous, sparse, and completely blind to similarity. "Cat" and "kitten" are as far apart as "cat" and "parliament".

Full neural language models (Bengio et al., 2003) solved this by learning dense embeddings, but their output layer computed a softmax over the entire vocabulary at every training step. For a vocabulary of V words, that means V dot products plus a normalization — an operation that scales linearly with V and becomes a bottleneck when V reaches hundreds of thousands.

The Skip-gram model flips the typical language model around. Instead of predicting the next word from its history, it takes a center word and tries to predict the surrounding context words within a window of size $c$. Think of it as a spotlight: the center word asks, "Who usually stands near me?"

Given a sequence of training words $w_1, w_2, \ldots, w_T$, the objective is to maximize the average log probability:

$\frac{1}{T} \sum_{t=1}^{T} \sum_{\substack{-c \le j \le c \\ j \ne 0}} \log p(w_{t+j} \mid w_t)$

Each word has two roles — and therefore two vectors. As a center word it uses its input vector $v_w$; as a context word it uses its output vector $v'_w$. The probability of seeing context word $w_O$ given center word $w_I$ is defined via softmax over the full vocabulary.

The expensive part of Skip-gram is the softmax denominator — summing $\exp(v'_w{}^\top v_{w_I})$ over every word in the vocabulary. Negative Sampling (NEG) replaces this with a far cheaper surrogate objective.

The idea is elegant: instead of asking "what is the probability of this context word among all V words?", ask a binary question — "did this word-context pair come from real data, or is it noise?" For each real $(w_I, w_O)$ pair the model should output high probability. Then draw $k$ random "negative" words from a noise distribution and the model should output low probability for each of them.

Imagine a customs officer. Instead of checking every passenger on the plane (full softmax), she checks the ticket of the arriving passenger (the positive pair) and then spot-checks $k$ random people from the airport crowd (negative samples). Much faster, and still catches counterfeits.

Words like "the", "a", and "in" appear millions of times in any large corpus. They provide much less information than rare words — seeing "the" next to "France" tells you almost nothing, while "Paris" next to "France" is highly informative. Yet without correction, the model spends most of its compute on these uninformative pairs.

The paper introduces a simple subsampling formula: each word $w_i$ in the training data is discarded with a probability that grows with its frequency.

Some word combinations carry meaning that their parts alone do not convey. "New York" is a city, not something new and something called York. "Ice cream" is a dessert, not frozen cream. Treating these as separate tokens loses critical meaning.

The paper uses a data-driven scoring function based on pointwise mutual information to identify such phrases:

$\text{score}(w_i, w_j) = \frac{\text{count}(w_i\, w_j) - \delta} {\text{count}(w_i) \times \text{count}(w_j)}$

When the score exceeds a threshold, the bigram is merged into a single token. Running this process multiple times discovers longer phrases like "New_York_Times". The approach is simple but effective — no linguistic rules, purely statistical co-occurrence.

The most celebrated result of Word2Vec is that its vector space encodes semantic relationships as directions. The classic demonstration:

$\vec{\text{king}} - \vec{\text{man}} + \vec{\text{woman}} \approx \vec{\text{queen}}$

This is not a trick or cherry-picked example — it works across many relationship types. The direction from "man" to "woman" captures a gender axis; the direction from "Paris" to "France" captures a capital-country axis. These directions are consistent: the same offset that maps "Paris" → "France" also maps "Berlin" → "Germany".

This compositionality arises because the Skip-gram objective implicitly factorizes a word-context co-occurrence matrix. Words that share similar contexts end up at similar positions, and systematic relationships in language create systematic geometric patterns in the embedding space.

Before Negative Sampling, the paper also discusses Hierarchical Softmax — an earlier approach to avoiding the full-vocabulary sum. The idea: arrange all words as leaves of a binary tree. Instead of computing one V-way softmax, the model makes a series of binary decisions as it walks down the tree from root to the target word's leaf.

Each internal node has a learned vector, and at each branch the model computes a sigmoid to decide left or right. The total path length is $\log_2 V$ — so the cost drops from $O(V)$ to $O(\log V)$. A Huffman tree assigns shorter paths to frequent words, further speeding up common predictions.

The paper found that Negative Sampling outperformed Hierarchical Softmax on analogy tasks, particularly for frequent words, while being simpler to implement. This is why Negative Sampling became the default training method for Word2Vec.

The complete Word2Vec training pipeline combines all three contributions into a streamlined process:

Step 1 — Phrase detection. Scan the corpus and merge high-scoring bigrams into single tokens. Run multiple passes for longer phrases.

Step 2 — Build vocabulary. Count all (merged) tokens. Discard any below a minimum frequency threshold.

Step 3 — Subsample frequent words. For each training sentence, randomly drop words with probability tied to their frequency. This both accelerates training and improves representation quality.

Step 4 — Train with Negative Sampling. For each surviving center-context pair: push their vectors closer together; sample $k$ noise words and push their vectors apart from the center word. Update via stochastic gradient descent.

The result: a matrix of dense vectors — one per word — where geometric relationships encode semantic meaning. Training on a billion-word corpus takes hours, not weeks.

It may seem magical that vector addition captures semantic analogies. The paper offers an intuitive explanation rooted in the training objective.

Skip-gram's probability is defined via exponentiated dot products. Taking logs converts multiplication to addition. If words that share a relationship consistently appear in similar contexts, the offset vector between them points in a consistent direction. Adding and subtracting these offsets navigates the space along meaningful axes.

This is not a guaranteed property of any embedding — it emerges because the Skip-gram objective implicitly captures log-probability ratios of co-occurrence statistics. Later work (Levy & Goldberg, 2014) showed this connection rigorously: Skip-gram with negative sampling implicitly factorizes a shifted PMI (pointwise mutual information) matrix.

Word2Vec's most enduring contribution is not any particular set of vectors — it is the idea that unsupervised co-occurrence prediction creates structured representations. Every modern pre-trained model, from BERT to GPT, is a descendant of this insight: learn from context, and meaning emerges in the geometry of the learned space.