GloVe: embeddings from global co-occurrence counts

Word2Vec slides a window over the corpus and updates two vectors for every pair it sees, millions of small stochastic steps. Every pair of words that occurs together a thousand times is visited a thousand times. GloVe (Pennington, Socher and Manning, 2014) starts from the opposite end: count every pair once into a co-occurrence matrix, then fit vectors to that matrix directly. Training then costs time proportional to the number of distinct pairs, not to the length of the corpus, and the objective says explicitly what the dot products are supposed to equal.

Notation. $V$ is the vocabulary. $X_{ik}$ is the (weighted) number of times word $k$ occurs in the context of word $i$; $X_i = \sum_k X_{ik}$; $P_{ik} = P(k \mid i) = X_{ik} / X_i$. Each word has a word vector $w_i \in \mathbb R^d$, a context vector $\tilde w_k \in \mathbb R^d$ and two biases $b_i$, $\tilde b_k$.

Baseline: factorize the count matrix#

Methods older than Word2Vec already worked with the co-occurrence matrix: latent semantic analysis (Deerwester et al., 1990) reduces a word–document matrix with a truncated SVD, and HAL-style models reduce a word–word matrix. Applied to raw counts, they inherit two problems. The most frequent words (the, and, ?) co-occur with everything, so their counts dominate any least-squares fit while carrying little meaning; and a single squared error treats a difference of 10 between counts of 20 and 30 like the same difference between 10,020 and 10,030. Transforms such as the logarithm or square root help, and in the GloVe paper an SVD of log counts reaches 60.1% on word analogies where GloVe reaches 71.7% (both 300-dimensional, 6 billion tokens). The question is which function of the counts the vectors should reproduce, and with which weights.

Ratios carry the meaning#

The paper’s example compares ice and steam on 6 billion tokens. $P(\textit{solid} \mid \textit{ice}) / P(\textit{solid} \mid \textit{steam}) = 8.9$, $P(\textit{gas} \mid \cdot)$ gives $0.085$, while water, related to both, gives $1.36$ and fashion, related to neither, $0.96$. On 537,272 Quora questions, counted as described in the Code section, the same pattern appears for tea and coffee:

Context $k$	$P(k \mid \textit{tea})$	$P(k \mid \textit{coffee})$	Ratio
green	$9.33 \cdot 10^{-2}$	$7.68 \cdot 10^{-3}$	12.2
starbucks	$1.42 \cdot 10^{-3}$	$1.10 \cdot 10^{-2}$	0.129
drink	$2.02 \cdot 10^{-2}$	$2.02 \cdot 10^{-2}$	1.00
india	$1.96 \cdot 10^{-3}$	$1.68 \cdot 10^{-3}$	1.16

Green is about tea, Starbucks about coffee, drink about both and India about neither, and the ratio sorts them, while the raw probabilities of drink (0.020) and India (0.002) differ by an order of magnitude for reasons of frequency alone. The corpus decides the senses: on Quora, $P(\textit{games} \mid \textit{steam})$ is 63 times $P(\textit{games} \mid \textit{ice})$, because most questions about Steam are about the game store.

Figure

Probability ratios and pair weights in GloVe

From ratios to a model#

GloVe asks for vectors such that some function $F$ of the difference $w_i - w_j$ and a context vector reproduces the ratio. Taking the difference compares the two words, taking the dot product with $\tilde w_k$ turns vectors into a number, and asking that a difference of vectors map to a ratio of probabilities, $F(a - b) = F(a) / F(b)$, leaves $F = \exp$:

$$\exp\big((w_i - w_j) \cdot \tilde w_k\big) = \frac{P_{ik}}{P_{jk}} \quad\Longleftarrow\quad w_i \cdot \tilde w_k = \log P_{ik} = \log X_{ik} - \log X_i .$$

The term $\log X_i$ depends on $i$ alone and becomes a bias $b_i$; a context bias $\tilde b_k$ restores the symmetry. The model is

$$w_i \cdot \tilde w_k + b_i + \tilde b_k = \log X_{ik} .$$

A dot product plus two biases should equal the log count. Differences of vectors then encode log ratios, which is where the linear analogy structure of the embeddings note comes from.

Weighted least squares#

The model is fitted by least squares over the pairs that occur, with a weight per pair:

$$J = \sum_{i,k:\, X_{ik} > 0} f(X_{ik}) \big(w_i \cdot \tilde w_k + b_i + \tilde b_k - \log X_{ik}\big)^2, \qquad f(x) = \begin{cases} (x / x_{\max})^{\alpha}, & x < x_{\max}, \\ 1, & \text{otherwise}, \end{cases}$$

with $x_{\max} = 100$ and $\alpha = 3/4$ in all experiments of the paper. The weight does three jobs. Pairs that never occur have $\log 0 = -\infty$ and are left out, so the sum runs over the nonzero entries only. Rare pairs are noisy and get small weights: $f(1) = 0.032$, $f(10) = 0.178$. Frequent pairs are capped at weight 1, so the pairs of ? with everything cannot take over the fit.

Worked example. Take a pair with $X_{ik} = 50$, so $\log X_{ik} = 3.912$ and $f(50) = 0.5^{3/4} = 0.595$. If the current vectors give $w_i \cdot \tilde w_k + b_i + \tilde b_k = 3.0$, the error is $-0.912$ and the pair contributes $0.595 \times 0.912^2 = 0.495$ to $J$. The gradient with respect to $w_i$ is $2 \times 0.595 \times (-0.912)\, \tilde w_k$: the update moves $w_i$ toward $\tilde w_k$ until their dot product, with the biases, matches the log count.

Training follows from the form of $J$. The matrix is built in one pass over the corpus; the paper uses a window of ten words on each side, with a pair at distance $d$ adding $1/d$ to the count. Then AdaGrad samples nonzero entries for 50 passes (100 for 300-dimensional vectors), with initial learning rate 0.05. Words and contexts play symmetric roles, so the two sets of vectors differ only through their random initialization, and the final vector of a word is $w_i + \tilde w_i$, which the paper finds slightly better than either.

A run on Quora questions#

To see GloVe next to the Word2Vec model of the previous note, train both on the same text: 537,272 Quora questions, lower-cased, split into words and punctuation, with English stopwords removed, 3.9 million tokens. Words seen fewer than 5 times are dropped, which leaves $|V| = 27{,}789$. The co-occurrence matrix, window 10 with $1/d$ weighting, has 6,781,251 nonzero entries, 0.88% of the $|V|^2$ possible pairs; only 0.15% of the entries reach $x_{\max}$. Fifty AdaGrad passes with $d = 32$ take about a minute on a laptop CPU, and the weighted loss per entry falls from 0.082 after the first pass to 0.036, 0.030, 0.023 and 0.020 after passes 5, 10, 25 and 50.

Nearest neighbours by cosine, GloVe against CBOW Word2Vec with $d = 32$ and a 5-word window on the same tokens:

Word	GloVe	Word2Vec (CBOW)
python	java 0.891, php 0.847, django 0.842	javascript 0.967, java 0.942, php 0.937
coffee	tea 0.834, starbucks 0.802, drinking 0.769	tea 0.900, beer 0.875, starbucks 0.857
word	meaning 0.888, ’? 0.880, origin 0.874	words 0.806, sentence 0.803, pronounce 0.797
learn	programming 0.840, learning 0.821, easy 0.812	learning 0.817, beginner 0.750, teach 0.743

Both models find the same topics. GloVe’s neighbours lean toward what the word appears with in a question (learn → programming, python), Word2Vec’s toward what can replace it (learn → teach, beginner), partly because GloVe’s window here is twice as wide. GloVe also lets punctuation tokens such as ’? into the neighbour lists: it has no subsampling of frequent tokens, and the cap $x_{\max}$ limits their weight per pair but not the number of pairs they appear in.

GloVe and skip-gram#

The two methods are closer than their training procedures suggest. The Word2Vec note shows that skip-gram with negative sampling drives $u_o \cdot v_c$ toward the shifted pointwise mutual information $\log \frac{P(c, o)}{P(c) P(o)} - \log k$; GloVe drives $w_i \cdot \tilde w_k + b_i + \tilde b_k$ toward $\log X_{ik}$, and the biases can absorb the $\log X_i$ and $\log X_k$ terms that turn a log count into a PMI. Both factorize a log co-occurrence matrix with dot products. They differ in the weighting of pairs, in whether the matrix is built explicitly, and in the cost: GloVe pays once per corpus for counting and then per nonzero entry, Word2Vec per token per epoch.

The GloVe paper reports analogy accuracies of 71.7% for GloVe against 65.7% for CBOW and 69.1% for skip-gram (300 dimensions, 6 billion tokens), and 75.0% for GloVe on 42 billion tokens. Levy, Goldberg and Dagan (2015) later showed that much of such differences comes from choices outside the algorithm (window size, subsampling, smoothing of the context distribution, how the two sets of vectors are combined) and that with these matched no method is consistently better. Today GloVe is used mostly through its downloadable vectors, such as the Twitter vectors used in the embeddings note.

What changed#

	Word2Vec (SGNS)	GloVe
Input	windows streamed over the corpus	co-occurrence counts, built once
Objective	logistic loss on positive and sampled pairs	weighted least squares on $\log X_{ik}$
What dot products approximate	shifted PMI (implicitly)	log count minus biases (explicitly)
Training cost	proportional to corpus length × epochs	proportional to nonzero pairs × passes
Memory	two vector tables	the count matrix too (6.8 M entries for 27,789 words here)
Frequent words	subsampled	capped by $f$

Limitations#

• One vector per word type. Like Word2Vec, GloVe gives bank one compromise vector; contextual vectors come with BERT.
• Closed vocabulary. A word absent from the counts has no vector, and a word seen five times gets a vector fitted to a handful of pairs. The next note builds vectors from parts of words.
• The count matrix. Its size grows with the vocabulary and window; for large vocabularies counting needs care with memory, which Word2Vec never pays.
• Hyperparameters beyond the algorithm. Window, weighting, $x_{\max}$, $\alpha$ and the combination $w + \tilde w$ change the result as much as the choice between GloVe and Word2Vec.

What you should remember#

• GloVe fits $w_i \cdot \tilde w_k + b_i + \tilde b_k = \log X_{ik}$ over the nonzero co-occurrence counts, by weighted least squares.
• The motivation is the ratio $P(k \mid i) / P(k \mid j)$: it separates what distinguishes two words from what they share, and log-linear dot products turn it into a vector difference.
• The weight $f(x) = \min(1, (x/100)^{3/4})$ ignores zeros, damps rare pairs and caps frequent ones.
• Skip-gram and GloVe both factorize a log co-occurrence matrix; their differences are in weighting and cost, and in practice smaller than the hyperparameters around them.

Notebook#

No course notebook trains GloVe. week01_word_embeddings.ipynb downloads the pretrained 100-dimensional GloVe Twitter vectors (cell 62; cell numbers count every cell from 1) and runs the analogies discussed in the embeddings note. The numbers of this note come from the run in the Code section, on the course’s own Quora file (seminars/data/quora.txt).

Code#

GloVe in about forty lines of NumPy and PyTorch, on the Quora questions:

import re, collections, numpy as np, torch
from sklearn.feature_extraction.text import ENGLISH_STOP_WORDS

tok = re.compile(r"\w+|[^\w\s]+")
lines = [l.strip() for l in open('quora.txt', encoding='utf-8') if l.strip()]
sents = [[t for t in tok.findall(l.lower()) if t not in ENGLISH_STOP_WORDS] for l in lines]
cnt = collections.Counter(t for s in sents for t in s)
vocab = [w for w, c in sorted(cnt.items(), key=lambda x: (-x[1], x[0])) if c >= 5]
idx = {w: i for i, w in enumerate(vocab)}; V = len(vocab)
print(len(sents), sum(map(len, sents)), V)

# co-occurrence counts: window 10 on each side, a pair at distance d adds 1/d
ids = [np.array([idx[t] for t in s if t in idx]) for s in sents]
ids = [a for a in ids if len(a)]
flat = np.concatenate(ids); sid = np.repeat(np.arange(len(ids)), [len(a) for a in ids])
keys, vals = [], []
for d in range(1, 11):
    same = sid[:-d] == sid[d:]                       # both words in the same question
    a, b = flat[:-d][same], flat[d:][same]
    keys += [a * V + b, b * V + a]; vals += [np.full(len(a), 1 / d)] * 2
uk, inv = np.unique(np.concatenate(keys), return_inverse=True)
X = torch.tensor(np.bincount(inv, weights=np.concatenate(vals)), dtype=torch.float32)
I, J = torch.from_numpy(uk // V), torch.from_numpy(uk % V)
print(len(X), (X >= 100).float().mean().item())

# weighted least squares with AdaGrad
torch.manual_seed(0)
dim = 32
W = torch.nn.Parameter((torch.rand(V, dim) - 0.5) / dim); Wt = torch.nn.Parameter((torch.rand(V, dim) - 0.5) / dim)
b = torch.nn.Parameter(torch.zeros(V)); bt = torch.nn.Parameter(torch.zeros(V))
opt = torch.optim.Adagrad([W, Wt, b, bt], lr=0.05)
f = torch.clamp(X / 100, max=1.0) ** 0.75; logX = torch.log(X)
for epoch in range(50):
    perm, total = torch.randperm(len(X)), 0.0
    for s in range(0, len(X), 100_000):
        p = perm[s:s + 100_000]; i, j = I[p], J[p]
        err = (W[i] * Wt[j]).sum(1) + b[i] + bt[j] - logX[p]
        loss = (f[p] * err ** 2).sum()
        opt.zero_grad(); loss.backward(); opt.step(); total += loss.item()
    print(epoch + 1, total / len(X))

E = (W + Wt).detach().numpy()                      # final vectors: w + w~
E /= np.linalg.norm(E, axis=1, keepdims=True)
sim = E @ E[idx['python']]
print([(vocab[k], round(float(sim[k]), 3)) for k in np.argsort(-sim)[1:4]])

The run prints 537,272 questions, 3,883,212 tokens and $|V| = 27{,}789$, then 6,781,251 nonzero entries of which 0.15% reach $x_{\max}$, the losses quoted above (0.082 after the first pass, 0.020 after the fiftieth) and java 0.891, php 0.847, django 0.842 for python. The tea and coffee rows come from the same X: $P(k \mid i)$ is $X_{ik}$ divided by the row sum $X_i$, 1,702.8 for tea and 1,954.4 for coffee.

Next#

GloVe and Word2Vec both stop at the edge of their vocabulary: a misspelling, a rare inflection or a new word gets nothing. The next note keeps the skip-gram objective and builds every word’s vector from the vectors of its character n-grams, so related forms share parameters and unseen words still get a vector.

References#

• J. Pennington, R. Socher, C. D. Manning. GloVe: Global Vectors for Word Representation. EMNLP, 2014. Table 1 (ice and steam), §3 (the model and the weighting function), §4.2 (training), Table 2 (analogies).
• O. Levy, Y. Goldberg, I. Dagan. Improving Distributional Similarity with Lessons Learned from Word Embeddings. TACL, 3, 2015.
• S. Deerwester, S. T. Dumais, G. W. Furnas, T. K. Landauer, R. Harshman. Indexing by Latent Semantic Analysis. JASIS, 41(6), 1990.