GloVe

GloVe: Global Vectors for Word Representation

A co-occurrence matrix $X$ over a fixed vocabulary is built by scanning the corpus once with a context window of some fixed size, and incrementing $X_{ij}$ every time word $j$ appears within that window of word $i$. Let $X_i = \sum_k X_{ik}$ be the total count of words that ever co-occur with $i$, and let $P_{ij} = X_{ij}/X_i$ be the probability that word $j$ appears in the context of word $i$. This matrix is exactly the "distributional profile" underlying Distributional Semantics: two words are similar if their rows of $P$ look alike. GloVe's central empirical observation is that raw probabilities $P_{ij}$ are dominated by frequency effects and are not very informative alone, but ratios $P_{ik}/P_{jk}$ across a third "probe" word $k$ discriminate meaning sharply. Consider $i = \text{ice}$, $j = \text{steam}$. For $k = \text{solid}$, the ratio $P_{ik}/P_{jk}$ is large, since "solid" co-occurs much more with "ice" than "steam". For $k = \text{gas}$, the ratio is small. For $k = \text{water}$, a word related to both, or $k = \text{fashion}$, a word related to neither, the ratio is near 1. This behavior is exactly the signal needed to place "ice" and "steam" correctly relative to "solid" and "gas" in vector space, and it motivates modeling this ratio directly rather than modeling $P_{ij}$ alone. GloVe therefore posits a function $F$ of word vectors $w_i, w_j$ and context vector $\tilde w_k$ such that

Through a sequence of well-motivated simplifications — requiring $F$ to depend only on the vector difference $w_i - w_j$ (so that vector space is linear in the relevant direction), requiring the arguments to combine via a dot product (so that the function is invariant to how we split the difference across dimensions), and requiring symmetry between a word and a context word (so word and context vectors play interchangeable roles) — the derivation collapses to

with scalar bias terms $b_i, \tilde b_k$ absorbing marginal frequency effects (including $\log X_i$). This is the GloVe model equation: it says the dot product of a word vector and a context vector, plus two biases, should reconstruct the log co-occurrence count. Fitting all vectors to satisfy this equation, weighted appropriately, is the entire training objective.

Step 1 — Build the co-occurrence matrix. Scan the corpus once with a symmetric context window of size $L$ (e.g., 10 words on each side). For each center word $i$ and each context word $j$ found within the window at distance $d$, increment $X_{ij}$ by $1/d$ (distance weighting reduces the influence of far-away words). This produces a large but very sparse $|V| \times |V|$ matrix, since most word pairs never co-occur.

Step 2 — Define the weighted least-squares loss. The full objective sums over all nonzero entries of $X$:

Here $w_i$ is the "word vector" for word $i$, $\tilde w_j$ is the separate "context vector" for word $j$, and $f$ is a weighting function that must satisfy three properties: $f(0) = 0$ (so the sum over the sparse matrix stays finite as $X_{ij}\to 0$), $f$ non-decreasing (so frequent co-occurrences are not down-weighted relative to rare ones), and $f$ bounded / eventually small for very large $X_{ij}$ (so extremely common pairs like "the"/"of" do not dominate the loss). GloVe uses

with typical values $x_{\max}=100$, $\alpha = 0.75$.

Step 3 — Optimize with stochastic gradient descent (or AdaGrad). Each training step samples one nonzero entry $(i,j,X_{ij})$ and updates $w_i, \tilde w_j, b_i, \tilde b_j$ by gradient descent on the per-pair squared error, scaled by $f(X_{ij})$. AdaGrad is preferred in the original implementation because co-occurrence counts span many orders of magnitude, and per-parameter adaptive learning rates handle this scale variation better than a single fixed rate.

Step 4 — Combine word and context vectors. After training, GloVe forms the final embedding for a word as $w_i + \tilde w_i$ (sum of the word vector and its own context vector), which empirically works slightly better than using $w_i$ alone, acting as a form of implicit ensembling over the two nearly-redundant vector sets. ```

# GloVe training algorithm Input: corpus, vocabulary V, window size L, embedding dim d, x_max, alpha, learning_rate, num_epochs

# ---- Step 1: build sparse co-occurrence counts ---- X = empty sparse map from (i, j) -> float, default 0 for each position p in corpus: i = word at position p for each position q in [p - L, p + L], q != p, within corpus bounds: j = word at position q d = |p - q| X[(i, j)] += 1.0 / d # closer context words weigh more pairs = list of (i, j, X[(i,j)]) for all nonzero entries # O(nnz) pairs

# ---- Step 2 & 3: initialize parameters and train ---- for each word k in V: w[k] = random small vector in R^d w_tilde[k] = random small vector in R^d b[k] = 0.0 b_tilde[k] = 0.0 grad_sq_w[k] = ones(d) # AdaGrad accumulators grad_sq_wt[k] = ones(d) grad_sq_b[k] = 1.0 grad_sq_bt[k] = 1.0 def weight(x): if x < x_max: return (x / x_max) ** alpha else: return 1.0 for epoch in 1..num_epochs: shuffle(pairs) total_loss = 0 for (i, j, Xij) in pairs: pred = dot(w[i], w_tilde[j]) + b[i] + b_tilde[j] diff = pred - log(Xij) fij = weight(Xij) loss = fij diff diff total_loss += loss

# gradient of f diff^2 w.r.t. each parameter grad_common = 2 fij diff # scalar factor shared below g_w = grad_common w_tilde[j] # d(loss)/d(w[i]) g_wt = grad_common * w[i] # d(loss)/d(w_tilde[j]) g_b = grad_common # d(loss)/d(b[i]) g_bt = grad_common # d(loss)/d(b_tilde[j])

# AdaGrad updates grad_sq_w[i] += g_w g_w grad_sq_wt[j] += g_wt g_wt grad_sq_b[i] += g_b g_b grad_sq_bt[j] += g_bt g_bt w[i] -= learning_rate g_w / sqrt(grad_sq_w[i]) w_tilde[j] -= learning_rate g_wt / sqrt(grad_sq_wt[j]) b[i] -= learning_rate g_b / sqrt(grad_sq_b[i]) b_tilde[j] -= learning_rate g_bt / sqrt(grad_sq_bt[j]) report(epoch, total_loss)

# ---- Step 4: final embedding ---- for each word k in V: embedding[k] = w[k] + w_tilde[k] return embedding ``` Every gradient in the pseudocode is a direct application of the chain rule to $J_{ij} = f(X_{ij})(w_i^\top \tilde w_j + b_i + \tilde b_j - \log X_{ij})^2$: differentiating the square gives the factor $2 f(X_{ij}) \cdot \text{diff}$, and differentiating the linear inner term with respect to $w_i$ leaves exactly $\tilde w_j$ (and symmetrically for $\tilde w_j$), while the bias derivatives are $1$.

Building the co-occurrence matrix requires one pass over a corpus of $T$ tokens with a window of size $L$, giving $O(T \cdot L)$ time — linear in corpus size, exactly like Skip-gram's window scan. The resulting matrix has at most $O(|V|^2)$ entries but in practice has $\text{nnz} \ll |V|^2$ nonzero entries, since co-occurrence follows a heavy-tailed (roughly Zipfian) distribution: most word pairs simply never appear together in any window.

Training performs a constant amount of work — one dot product, one squared-error gradient, four AdaGrad updates, each $O(d)$ for embedding dimension $d$ — per nonzero entry, per epoch. Total training time is therefore

which is independent of raw corpus length once the co-occurrence matrix is built: a corpus can be scanned once, its statistics cached, and then GloVe trained repeatedly at a cost governed only by the matrix's sparsity, not by how many tokens the corpus contained. This is the practical efficiency argument for global-count methods: expensive corpus scanning happens once, and the optimization reuses compressed statistics ($\text{nnz}$ pairs) as many times as needed, whereas Skip-gram's stochastic training must revisit the raw token stream (or its negative-sampling equivalent) on every epoch.

Space is $O(\text{nnz})$ for the sparse matrix plus $O(|V| \cdot d)$ for the two vector sets (word and context) and biases — the same order as the vocabulary times embedding dimension needed by any embedding method.

Correctness argument. The claim to justify is not "GloVe converges" in a generic optimization sense — the loss is a sum of smooth non-convex terms in the joint parameters (since it involves a product $w_i^\top \tilde w_j$), so standard gradient descent on $J$ only guarantees convergence to a stationary point, exactly as with matrix factorization objectives in general. The deeper correctness claim is about why the model equation is the right one to fit. The derivation proceeds by these logical steps: 1. Start from the requirement that some function of vectors reproduces the informative ratio: $F(w_i, w_j, \tilde w_k) = P_{ik}/P_{jk}$. 2. Since vector spaces are naturally linear, restrict $F$ to depend on the vector difference: $F(w_i - w_j, \tilde w_k) = P_{ik}/P_{jk}$. This encodes the idea that the direction "$i$ minus $j$" should carry the meaning distinguishing them relative to any probe $k$. 3. The arguments of $F$ are vectors but the right-hand side is scalar; a dot product is the natural scalar-valued bilinear map, giving $F((w_i-w_j)^\top \tilde w_k) = P_{ik}/P_{jk}$. 4. Requiring $F$ to be a group homomorphism between $(\mathbb{R}, +)$ and $(\mathbb{R}_{>0}, \times)$ — because swapping the roles of $i \leftrightarrow j$ should invert the ratio, and the difference $w_i - w_j$ negates — forces $F = \exp$, giving

5. Expanding $\log P_{ik} = \log X_{ik} - \log X_i$ and absorbing $-\log X_i$ (a function of $i$ alone) plus a symmetrizing bias $\log X_k$ into learned bias terms $b_i, \tilde b_k$ yields exactly the GloVe model equation $w_i^\top \tilde w_k + b_i + \tilde b_k = \log X_{ik}$. So the model equation is not an arbitrary regression target — it is the unique consequence (under the stated, individually well-motivated restrictions) of requiring the vector space to linearly encode co-occurrence-probability ratios. The weighted least-squares loss $J$ is then simply the natural way to fit this equation robustly across a matrix whose entries vary over many orders of magnitude, with $f$ preventing the few very large counts (mostly involving function words) from dominating the squared-error sum, and preventing zero-count pairs (which are not even summed) from being treated as informative negative evidence, unlike Skip-gram's explicit negative sampling.

Tradeoffs. GloVe requires materializing and storing the co-occurrence matrix, which costs memory upfront and does not scale as gracefully to streaming or online settings as Skip-gram's token-by-token training. It also treats co-occurrence counts within a fixed window as the only signal, discarding word order beyond that window in a way that both GloVe and vanilla Skip-gram share. Both methods produce static embeddings — one vector per word type — which cannot represent polysemy (e.g., "bank" the river edge vs. "bank" the institution get one blended vector), a limitation that later motivated contextual embeddings.

Consider a tiny toy corpus (ignoring window-distance weighting for clarity, using window size 1, unweighted counts) over four words: `ice`, `steam`, `solid`, `water`. Suppose the resulting co-occurrence counts (already symmetrized) are:

With $x_{\max} = 10, \alpha = 0.75$: weights are

Suppose after some epochs of training the (illustrative, rounded) fitted 2-dimensional vectors are:

with word biases $b_{\text{ice}} = 0.05$, $b_{\text{steam}} = -0.10$. Check the model equation on (ice, solid):

Compare to $\log X_{\text{ice,solid}} = 3.00$: the residual is $1.83 - 3.00 = -1.17$, so gradient updates would push $w_{\text{ice}}$ and $\tilde w_{\text{solid}}$ further apart in the direction that raises their dot product, weighted heavily since $f(20)=1$ gives full weight to this correction. Now check (steam, solid):

Compare to $\log 2 = 0.69$: residual $-0.83$, but this pair only contributes weight $f(2) \approx 0.299$, so its gradient contribution is damped relative to (ice, solid) even though the raw residual is smaller in magnitude — this is precisely the weighting function doing its job, since a count of 2 is noisier evidence than a count of 20 and should influence the fit less per unit of squared error. After many such updates across all pairs, the fitting pressure pulls `ice` toward directions shared with `solid` and away from directions shared with `gas`-like words, and symmetrically for `steam`. The final embedding for "ice" is $w_{\text{ice}} + \tilde w_{\text{ice}}$, combining its role as a center word and (if it also appears as a context word for other centers) its role as a context word.

Pretrained GloVe vectors (trained on corpora such as Wikipedia, Gigaword, and Common Crawl, at scales up to 840 billion tokens) were, for years, a default initialization layer in production NLP systems: sentiment analysis, part-of-speech tagging, named-entity recognition, and early neural machine translation encoders all commonly loaded GloVe vectors as a frozen or fine-tunable embedding layer. Recommendation systems and search engines have adapted the same global co-occurrence factorization idea to user–item and query–document matrices, since the underlying mathematical structure (sparse count matrix, weighted least-squares factorization) transfers directly. The core lesson — that ratios of co-occurrence statistics, not raw counts, carry semantic signal, and that a carefully weighted regression can recover that signal efficiently — continues to inform how practitioners think about the geometry of embedding spaces, a topic developed further under Embedding Geometry and Analogies. GloVe also remains a standard pedagogical bridge between classical count-based Distributional Semantics and the neural prediction objectives used in Word2Vec Skip-gram and its descendants.

Ask the tutor: Why does requiring the function $F$ to be a group homomorphism force it to be the exponential function in the GloVe derivation?