SVD, word2vec and GloVe factorising the same count matrix, and disagreeing about it.
The notebook carries the source, the install step and every run below, so nothing has to be on your machine. Open it, then choose Runtime › Run all.
Colab opens it read only. Click Copy to Drive to keep
your changes. You can also download
factorisation.ipynb, or run it
locally: python3 factorisation.py.
python3 factorisation.py
All three, side by side.
python3 factorisation.py --sgns
Skip-gram with negative sampling has an optimum, and it is PMI minus log k. The learned dot products land on it to within 0.0024. Nothing in the loop mentions PMI.
python3 factorisation.py --compare
GloVe gets all four queries wrong while its fit to log X stays good. Every fact separating an animal from a vehicle lives in a zero cell, and f(0) = 0 drops those cells.
python3 factorisation.py --compare --fill 1
No cell is empty now, and GloVe agrees with the other two.
Download factorisation.py
· served verbatim at https://nlp.jcrlabz.com/code/factorisation.py
"""SVD, word2vec and GloVe are three ways to factorise one matrix.
Chapter 9 claims that all three produce dense vectors by solving
w_i . c_j ~ M_ij
for some association matrix M built from the same co-occurrence counts. This
script demonstrates it on the eight-word matrix from Chapter 7, so the counts
and the SVD spectrum match what the book already printed.
python3 factorisation.py # all four steps
python3 factorisation.py --pmi # counts and PMI
python3 factorisation.py --sgns # train SGNS, compare to PMI - log k
python3 factorisation.py --k 1 # a different number of negatives
python3 factorisation.py --glove # train GloVe, compare to log X
python3 factorisation.py --compare # nearest neighbours, three methods
python3 factorisation.py --compare --fill 1 # and with no structural zeros
Two things to watch. In step 2 nobody tells the network about PMI and it
arrives there anyway. In step 4 one of the three methods fails, for a reason
worth more than the two successes.
Install: pip install numpy
"""
import argparse
import math
try:
import numpy as np
except ImportError:
raise SystemExit("this one needs numpy: pip install numpy")
WORDS = ["dog", "cat", "car", "truck", "pet", "vet", "drive", "fuel"]
CONTEXTS = ["pet", "feed", "fur", "vet", "drive", "fuel", "road", "tyre"]
# The same matrix svd.py and svd_rank.py use. Four animal words, four vehicle
# words, and the two groups share no context at all.
BASE = np.array([
[4, 3, 3, 2, 0, 0, 0, 0], # dog
[4, 3, 4, 2, 0, 0, 0, 0], # cat
[0, 0, 0, 0, 4, 3, 3, 2], # car
[0, 0, 0, 0, 4, 3, 4, 2], # truck
[3, 2, 2, 3, 0, 0, 0, 0], # pet
[2, 1, 1, 4, 0, 0, 0, 0], # vet
[0, 0, 0, 0, 3, 2, 3, 2], # drive
[0, 0, 0, 0, 2, 3, 2, 3], # fuel
], dtype=float)
def counts(fill=0):
"""The matrix, optionally with the structural zeros filled in.
fill=0 is the matrix as Chapter 7 prints it. Any other value replaces
every zero, which is what a real corpus looks like: almost nothing is a
true zero, only a small number.
"""
return BASE if fill == 0 else np.where(BASE == 0, float(fill), BASE)
def pmi_matrices(X):
"""PMI and PPMI, natural log. Chapter 7 Equations 7.2 and 7.3."""
p_wc = X / X.sum()
p_w = p_wc.sum(axis=1, keepdims=True)
p_c = p_wc.sum(axis=0, keepdims=True)
with np.errstate(divide="ignore", invalid="ignore"):
pmi = np.log(p_wc / (p_w * p_c))
ppmi = np.nan_to_num(np.maximum(pmi, 0.0), neginf=0.0, posinf=0.0)
return pmi, ppmi
def cosine(u, v):
n = np.linalg.norm(u) * np.linalg.norm(v)
return float(u @ v / n) if n else 0.0
def neighbours(vectors, target, top=2):
i = WORDS.index(target)
scored = [(w, cosine(vectors[i], vectors[j]))
for j, w in enumerate(WORDS) if j != i]
return sorted(scored, key=lambda p: -p[1])[:top]
ANIMALS = {"dog", "cat", "pet", "vet"}
VEHICLES = {"car", "truck", "drive", "fuel"}
def same_group(a, b):
return (a in ANIMALS) == (b in ANIMALS)
# ------------------------------------------------------------------ step one
def show_pmi(X):
pmi, _ = pmi_matrices(X)
print("\nSTEP 1 the association matrix that everything factorises\n")
print(" counts X, then PMI in nats (--- where the pair never occurs)\n")
head = " " + " " * 8 + "".join(f"{c[:5]:>8}" for c in CONTEXTS)
print(head)
for i, w in enumerate(WORDS):
print(f" {w:<8}" + "".join(f"{v:>8.0f}" for v in X[i]))
print()
print(head)
for i, w in enumerate(WORDS):
print(f" {w:<8}" + "".join(
" ---" if X[i][j] == 0 else f"{pmi[i][j]:>+8.3f}"
for j in range(len(CONTEXTS))))
seen = X > 0
print(f"\n {int(seen.sum())} of {X.size} cells are nonzero.")
print(f" PMI on those cells runs from {pmi[seen].min():+.3f}"
f" to {pmi[seen].max():+.3f}.")
print(" The zero cells are where the three methods part company. PMI")
print(" there is minus infinity. PPMI clips it to zero, GloVe drops the")
print(" cell, and word2vec pushes it down through negative sampling.")
# ------------------------------------------------------------------ step two
def train_sgns(X, k, dim, steps=20000, eta=0.05, seed=0):
"""Skip-gram with negative sampling, written as its expected objective.
Drawing negatives one at a time gives, in expectation, this loss over the
whole matrix. Optimising it directly removes the sampling noise, so the
optimum shows through in a few seconds:
L = sum_ij X_ij log sigma(w_i.c_j)
+ k * X_i. * P(j) * log sigma(-w_i.c_j)
Levy and Goldberg's result says the optimum is w_i.c_j = PMI_ij - log k.
"""
rng = np.random.default_rng(seed)
W = rng.normal(0, 0.1, (len(WORDS), dim))
C = rng.normal(0, 0.1, (len(CONTEXTS), dim))
total = X.sum()
row = X.sum(axis=1, keepdims=True) # #(w)
p_c = X.sum(axis=0, keepdims=True) / total # unigram context distribution
neg = k * row * p_c # expected negative count
for _ in range(steps):
s = 1 / (1 + np.exp(-(W @ C.T)))
# d/dz of [X log sigma(z) + neg log sigma(-z)] is X(1-s) - neg*s
G = X * (1 - s) - neg * s
Wg, Cg = G @ C, G.T @ W
W += eta * Wg / total
C += eta * Cg / total
return W, C
def show_sgns(X, k, dim):
pmi, _ = pmi_matrices(X)
W, C = train_sgns(X, k, dim)
fit = W @ C.T
target = pmi - math.log(k)
print(f"\n\nSTEP 2 word2vec arrives at PMI on its own"
f" (k = {k} negatives, d = {dim})\n")
print(f" {'pair':<20}{'w.c learned':>13}{'PMI - log k':>14}"
f"{'difference':>13}")
print(" " + "-" * 60)
rows = sorted((abs(fit[i][j] - target[i][j]),
f"{WORDS[i]}, {CONTEXTS[j]}", fit[i][j], target[i][j])
for i in range(len(WORDS)) for j in range(len(CONTEXTS))
if X[i][j] > 0)
for _, name, got, want in rows[:6]:
print(f" {name:<20}{got:>+13.3f}{want:>+14.3f}{got - want:>+13.3f}")
if len(rows) > 8:
print(" ...")
for _, name, got, want in rows[-2:]:
print(f" {name:<20}{got:>+13.3f}{want:>+14.3f}"
f"{got - want:>+13.3f}")
seen = X > 0
err = np.abs(fit - target)[seen]
print(f"\n mean absolute difference over the {int(seen.sum())} observed"
f" pairs: {err.mean():.4f}")
print(f" largest difference: {err.max():.4f}")
print("\n Nothing in the training loop mentions PMI. The objective only")
print(" says 'score real pairs high, sampled pairs low'. The arithmetic")
print(" that satisfies it is PMI, shifted down by log k.")
print(f"\n log k = {math.log(k):.4f}. Every value moves down by that")
print(" amount, so more negatives means a harsher threshold for calling")
print(" a pair associated.")
if seen.sum() < X.size:
print(f"\n On the {int((~seen).sum())} zero cells the target is minus")
print(f" infinity, and the fit obliges: mean {fit[~seen].mean():.2f},")
print(f" highest {fit[~seen].max():.2f}. That is the negative sampling")
print(" term doing work no other method here does for free.")
# ---------------------------------------------------------------- step three
def train_glove(X, dim, steps=20000, eta=0.05, x_max=10.0, alpha=0.75, seed=0):
"""GloVe, Equation 8.14, by full-batch AdaGrad as the paper uses."""
rng = np.random.default_rng(seed)
n, m = X.shape
W = rng.normal(0, 0.5, (n, dim))
C = rng.normal(0, 0.5, (m, dim))
bw = np.zeros((n, 1))
bc = np.zeros((1, m))
seen = X > 0
f = np.where(seen, np.minimum(X / x_max, 1.0) ** alpha, 0.0)
logX = np.where(seen, np.log(np.maximum(X, 1e-12)), 0.0)
acc = [np.ones_like(p) for p in (W, C, bw, bc)]
for _ in range(steps):
G = 2 * f * ((W @ C.T + bw + bc - logX) * seen)
grads = (G @ C, G.T @ W,
G.sum(axis=1, keepdims=True), G.sum(axis=0, keepdims=True))
for p, g, a in zip((W, C, bw, bc), grads, acc):
a += g * g
p -= eta * g / np.sqrt(a)
return W, C, bw, bc, f, logX, seen
def show_glove(X, dim):
W, C, bw, bc, f, logX, seen = train_glove(X, dim)
fit = W @ C.T + bw + bc
print(f"\n\nSTEP 3 GloVe fits log X, and the biases carry the frequency"
f" (d = {dim})\n")
print(f" {'pair':<20}{'X':>5}{'fitted':>10}{'log X':>10}{'weight f':>11}")
print(" " + "-" * 56)
for i in range(3):
for j in range(len(CONTEXTS)):
if X[i][j] > 0:
print(f" {WORDS[i] + ', ' + CONTEXTS[j]:<20}{X[i][j]:>5.0f}"
f"{fit[i][j]:>10.3f}{logX[i][j]:>10.3f}{f[i][j]:>11.3f}")
print(f"\n mean absolute error on the {int(seen.sum())} observed pairs:"
f" {np.abs(fit - logX)[seen].mean():.4f}")
print(f"\n {'word':<8}{'bias b_i':>10}{'row total':>12}")
print(" " + "-" * 30)
for i, w in enumerate(WORDS):
print(f" {w:<8}{float(bw[i][0]):>+10.3f}{X[i].sum():>12.0f}")
print("\n The bias tracks how common the word is. That is its whole job.")
print(" Move both biases to the other side and the dot product is left")
print(" fitting log X minus a row effect and a column effect. That")
print(" difference is PMI up to a constant, which is step 2's target.")
# ----------------------------------------------------------------- step four
def show_compare(X, k, dim, fill):
_, ppmi = pmi_matrices(X)
U, S, _ = np.linalg.svd(ppmi)
methods = [
("SVD of PPMI", U[:, :dim] @ np.diag(S[:dim])),
("word2vec", train_sgns(X, k, dim)[0]),
("GloVe", train_glove(X, dim)[0]),
]
state = "as printed" if fill == 0 else f"zeros filled with {fill}"
print(f"\n\nSTEP 4 three factorisations, one geometry?"
f" (d = {dim}, matrix {state})\n")
print(f" {'query':<8}" + "".join(f"{n:<26}" for n, _ in methods))
print(" " + "-" * 84)
verdict = {}
for q in ["dog", "car", "vet", "fuel"]:
cells = []
for name, vecs in methods:
top = neighbours(vecs, q)
cells.append(", ".join(f"{w} {s:+.2f}" for w, s in top))
verdict.setdefault(name, []).append(same_group(q, top[0][0]))
print(f" {q:<8}" + "".join(f"{c:<26}" for c in cells))
print()
for name, hits in verdict.items():
mark = "all four" if all(hits) else f"{sum(hits)} of {len(hits)}"
print(f" {name:<14}nearest neighbour in the right group: {mark}")
if fill == 0 and not all(verdict["GloVe"]):
print("\n GloVe is the odd one out, and the reason is in step 1.")
print(" Animals and vehicles share no context here, so every cell")
print(" linking the two groups is zero. f(0) = 0 drops those cells,")
print(" and GloVe never sees a single fact that separates a dog from")
print(" a truck. PPMI writes an explicit zero there and the SVD fits")
print(" it. Negative sampling pushes those pairs apart. GloVe alone")
print(" learns only from what it observed.")
print("\n Run again with --fill 1 and the disagreement disappears.")
print(" Real corpora have almost no structural zeros, which is why")
print(" this never showed up as a problem in practice.")
def main():
ap = argparse.ArgumentParser(description=__doc__)
ap.add_argument("--pmi", action="store_true")
ap.add_argument("--sgns", action="store_true")
ap.add_argument("--glove", action="store_true")
ap.add_argument("--compare", action="store_true")
ap.add_argument("--k", type=int, default=5, help="negative samples")
ap.add_argument("--dim", type=int, default=8, help="d for the SGNS check")
ap.add_argument("--fill", type=int, default=0,
help="replace every structural zero with this count")
a = ap.parse_args()
X = counts(a.fill)
picked = a.pmi or a.sgns or a.glove or a.compare
if a.pmi or not picked:
show_pmi(X)
if a.sgns or not picked:
show_sgns(X, a.k, a.dim)
if a.glove or not picked:
show_glove(X, 2)
if a.compare or not picked:
show_compare(X, a.k, 2, a.fill)
print()
if __name__ == "__main__":
main()