GloVe & Co-occurrence Statistics

The problem, from first principles

Skip-gram learns from one pair at a time. GloVe first counts, over the whole corpus, how often each word j appears near each word i, giving a co-occurrence matrix X. It then fits vectors so that the dot product of two word vectors (plus biases) approximates the logarithm of their co-occurrence count. Two details make it work. Rare pairs have noisy counts and very frequent pairs ("the" with "of") would dominate, so each term is weighted by a function f(x) = (x / x_max)^alpha, capped at 1: small counts get small weight and large counts stop growing in importance. And pairs that never co-occur (X = 0) are skipped, because log 0 is undefined.

From theory to code

Implement cooccurrence_matrix, glove_weight and glove_loss.

Constraints

• cooccurrence_matrix(token_ids, V, window) returns a (V, V) float array. For every position i and every j with 1 <= |i - j| <= window inside the sequence, add 1 / |i - j| to X[token_ids[i], token_ids[j]] (nearer words count more).
• glove_weight(x, x_max, alpha) is (x / x_max) ** alpha where x < x_max, else 1.0, elementwise.
• glove_loss(W, W_tilde, b, b_tilde, X, x_max, alpha): the sum over all (i, j) with X[i, j] > 0 of f(X[i, j]) * (W[i] @ W_tilde[j] + b[i] + b_tilde[j] - log X[i, j]) ** 2. Return a float (sum, not mean).

Hints