Chapter 4: Word Embeddings

Skip-gram reverses CBOW: the center word $w_t$ predicts each context word $w_{t+j}$ separately. Its input embedding $v_{w_t}$ is dotted with the output embedding $v'_w$ of every vocabulary word, and the softmax in the formula turns those scores into a distribution over possible neighbors. The training objective sums $\log P(w_{t+j} \mid w_t)$ over all positions and all offsets in the window, so each position contributes up to $2c$ separate predictions instead of one averaged one. That gives every occurrence of a rare word $2c$ gradient updates, which is why skip-gram learns rare words better than CBOW, at the cost of more computation per pass over the corpus.

Instead of computing softmax over the full vocabulary, negative sampling turns the problem into binary classification. For each positive (center, context) pair, sample $k$ random "negative" words that are not in the context. The model learns to assign high similarity to real pairs and low similarity to random pairs. The noise distribution $P_n(w) \propto f(w)^{3/4}$ upsamples rare words relative to their frequency. Typical values are $k = 5\text{-}20$ for small datasets and $k = 2\text{-}5$ for large ones.

Negative words are sampled according to a smoothed unigram distribution raised to the 3/4 power. The exponent 0.75 was found empirically to work better than the raw unigram distribution ($f(w)^1$) or uniform sampling ($f(w)^0$). The smoothing increases the sampling probability of rare words relative to their corpus frequency, ensuring the model sees a diverse set of negatives. Without this smoothing, very frequent words like "the" and "a" would dominate the negative samples.

The co-occurrence matrix $X$ has entries $X_{ij}$ counting how many times word $j$ appears in the context of word $i$ across the entire corpus. Context is defined by a window, and closer words can be weighted more heavily (e.g., distance weighting: a word 3 positions away contributes 1/3 as much as an adjacent word). The matrix is symmetric: $X_{ij} = X_{ji}$. Its construction requires one pass over the corpus and is $O(V^2)$ in memory, though in practice only nonzero entries are stored.

GloVe minimizes a weighted least-squares loss that makes the dot product of word embeddings approximate the log co-occurrence count. Each word has two vectors ($w_i$ and $\tilde{w}_j$) and two bias terms ($b_i$ and $\tilde{b}_j$). The weighting function $f(X_{ij})$ prevents very frequent co-occurrences from dominating the loss. The sum runs over all nonzero entries of $X$. After training, the final embedding is typically $w_i + \tilde{w}_i$ (sum of the two vectors).

The weighting function $f$ controls how much each non-zero matrix entry contributes to the GloVe loss. Very frequent pairs such as ("the", "of") would otherwise dominate, and very rare pairs with counts of 1 or 2 are noisy. As the formula shows, $f$ rises as $(x/x_{\max})^\alpha$ for counts below $x_{\max}$ and is capped at 1 above it; the paper uses $x_{\max} = 100$ and $\alpha = 3/4$, noting that 3/4 gave a modest improvement over a linear weight. Because $f(0) = 0$, zero entries contribute nothing, so training iterates only over the non-zero entries of $X$ and never needs the log of zero.

The theoretical motivation for GloVe starts with the observation that ratios of co-occurrence probabilities distinguish between related and unrelated words better than raw probabilities. Given probe words $k$, the ratio $P(k \mid \text{ice}) / P(k \mid \text{steam})$ is large for $k = \text{solid}$ (related to ice), small for $k = \text{gas}$ (related to steam), and close to 1 for $k = \text{water}$ (related to both) or $k = \text{fashion}$ (unrelated to both). GloVe is designed so that $w_{\text{ice}} - w_{\text{steam}}$ captures this discriminative direction.

FastText represents each word as the set of its character n-grams (typically $n \in [3, 6]$) plus the whole word itself. Special boundary markers < and > are added to distinguish prefixes and suffixes from internal substrings. The word embedding is the sum of the whole-word vector and all its n-gram vectors: $v_w = z_w + \sum_{g \in G(w)} z_g$, where $G(w)$ is the set of n-grams and $z_w$ is the word-level vector.

When encountering a word not in the training vocabulary, FastText computes its embedding by summing the vectors of its character n-grams (falling back to any n-grams that were seen during training). Even novel compound words, misspellings, and domain-specific terms get reasonable representations because they share substrings with known words. The embedding for an OOV word is $v_{\text{OOV}} = \sum_{g \in G(w)} z_g$ (no word-level vector since the word was not seen).

Character n-grams of lengths 3 to 6 across a large vocabulary produce millions of distinct strings, and storing a separate vector for each would make memory grow without bound. FastText instead hashes every n-gram into one of a fixed number of buckets, 2 million by default, and all n-grams that land in the same bucket share one vector. Memory becomes 2 million rows of 300 float32 values, 2.4 GB, however many n-grams exist. The price is collisions, where unrelated n-grams are forced to share parameters. Training absorbs most of this, because each word sums many n-gram vectors, and a collision affects only one of them.

The analogy task tests whether embedding arithmetic captures semantic relationships. Given "a is to b as c is to ?", the answer should be $d = \text{argmax} \cos(v_d, v_b - v_a + v_c)$, excluding $a$, $b$, and $c$ from candidates. The Google Analogy Test Set contains ~19,500 questions across syntactic ("walk" : "walked" :: "swim" : ?) and semantic ("Paris" : "France" :: "Tokyo" : ?) categories. Accuracy on this benchmark ranges from 30% (early models) to 75%+ (well-tuned Word2Vec/GloVe).

Cosine similarity, as in the formula, divides the dot product of two vectors by the product of their norms, so it measures the angle between them and ignores length. That suits embeddings because vector norms vary with word frequency and training dynamics, while meaning is mostly carried by direction. Values range from -1 to 1. In practice, related words score well above unrelated ones, but negative values do not mark antonyms: antonyms share contexts, so "hot" and "cold" have a GloVe cosine of 0.73. Euclidean distance mixes direction and length, and the raw dot product rewards long vectors. After normalizing vectors to unit length, all three give the same ranking.

Intrinsic evaluation probes the vector space itself: analogy accuracy on the Google and MSR sets, Spearman correlation with human similarity ratings, or how well categories cluster. These tests are cheap and help diagnose what a space encodes. Extrinsic evaluation plugs the vectors into a downstream system, such as named-entity recognition, sentiment analysis, or parsing, and measures task accuracy. That is the score that matters, but it is slow and mixes embedding quality with the architecture and tuning of the downstream model. The two often disagree. Schnabel et al. found that intrinsic rankings of embeddings did not consistently predict extrinsic rankings, so choose by the target task whenever possible.

Similarity benchmarks pair words with human ratings, such as 0 to 10, and score an embedding by the Spearman rank correlation between its cosine similarities and those ratings. Spearman compares rankings, not raw values, so it ignores any monotonic rescaling of cosines. WordSim-353 mixes similarity with relatedness, MEN has 3,000 pairs, and SimLex-999 rates genuine similarity only, so "coast" and "shore" score high while related but different words score lower. Embeddings trained on context windows tend to capture relatedness, which makes SimLex-999 hard: its authors reported a best model correlation of 0.414 against inter-annotator agreement of 0.67, so the human ceiling is well below 1.

BPE starts with a character-level vocabulary and iteratively merges the most frequent adjacent pair of tokens. After $k$ merges, you have a vocabulary of size $|\text{characters}| + k$. The merge rules are learned from a training corpus and applied deterministically at inference time. BPE captures common subwords: after merging, a vocabulary might contain tokens like "un", "ing", "tion", "##able" alongside full words like "the" and "and". The algorithm is greedy --- it always merges the globally most frequent pair, which is simple but effective.

SentencePiece (Kudo & Richardson, 2018) is a language-agnostic tokenizer that works directly on raw text without pre-tokenization (no need for language-specific word splitting). It treats the input as a sequence of Unicode characters (or bytes) and can apply either BPE or Unigram language model tokenization. The Unigram model starts with a large vocabulary and iteratively removes tokens whose removal causes the smallest increase in corpus likelihood. SentencePiece handles whitespace as a special character (\u2581), enabling it to reconstruct the original text from tokens without ambiguity.

Subword vocabularies are learned from frequency, not from linguistic rules, so frequent affixes such as "un", "able", and "ful" often become tokens of their own. When "un" consistently starts words whose meaning is negated, its embedding can carry part of that signal, and a model can compose pieces for words it rarely saw whole. The alignment with real morphemes is partial, though. GPT-2 splits "unbreakable" into un, break, and able, a clean morphological parse, but "unhappiness" into un, h, and appiness, and BERT gives un, ##ha, ##pp, and ##iness. Studies of morphologically rich languages report that unigram tokenizers tend to align better with morphemes than BPE does.

Vocabulary size is a critical hyperparameter for subword tokenizers. A small vocabulary (e.g., 8,000) splits most words into many subwords, increasing sequence length and computational cost but reducing the embedding table size. A large vocabulary (e.g., 128,000) keeps more words intact, shortening sequences but requiring a larger embedding matrix. The optimal size depends on the language, domain, and model architecture. Multilingual models (mBERT, XLM-R) need larger vocabularies to cover multiple writing systems. GPT-2 uses ~50,257 tokens; Llama uses 32,000; GPT-4 uses ~100,000.