"""The feed-forward neural language model, worked as Chapter 11 works it. Four things, all reproducing the chapter's numbers: the parameter count where the 1.5 million sit, and why W_o holds most one forward pass lookup, concatenate, tanh, softmax, cross-entropy one backward pass and the prediction improving generalisation the claim that a neural LM beats a counter on word combinations it never saw, actually tested python3 neural_lm.py # all four python3 neural_lm.py --params # the parameter table python3 neural_lm.py --forward # the forward and backward pass python3 neural_lm.py --generalise # train both models and compare python3 neural_lm.py --generalise --seeds 10 # repeat over seeds Install: pip install numpy """ import argparse import math from collections import Counter from itertools import product try: import numpy as np except ImportError: raise SystemExit("this one needs numpy: pip install numpy") # ------------------------------------------------------------- the parameters def show_params(V=10000, d=50, ctx=3, H=100): E = V * d Wh = ctx * d * H Wo = H * V biases = H + V total = E + Wh + Wo + biases print(f"\nSTEP 1 where the parameters live\n") print(f" |V| = {V}, d = {d}, context = {ctx} words, H = {H}\n") print(f" {'matrix':<10}{'shape':<20}{'parameters':>14}{'share':>9}") print(" " + "-" * 54) rows = [("E", f"{V} x {d}", E), ("W_h", f"{ctx * d} x {H}", Wh), ("W_o", f"{H} x {V}", Wo), ("biases", f"{H} + {V}", biases)] for name, shape, n in rows: print(f" {name:<10}{shape:<20}{n:>14,}{n / total:>8.1%}") print(" " + "-" * 54) print(f" {'total':<30}{total:>14,}") table = V ** ctx print(f"\n A trigram count table over the same vocabulary would need") print(f" |V|^2 x (|V|-1) = {V ** 2 * (V - 1):.3e} cells.") ratio = V ** 2 * (V - 1) / total print(f"\n The network uses {ratio:,.0f} times fewer numbers, which is") print(f" {math.log10(ratio):.1f} orders of magnitude.") print(f"\n And it shares them. Every context word is looked up in the same") print(f" E, so what the model learns about 'dog' is available wherever") print(f" 'dog' appears. A count table shares nothing between cells.") print(f"\n Note the share column. W_o alone holds {Wo / total:.0%} of the") print(f" parameters, and its size is H x |V|. Every training step must") print(f" compute the softmax denominator over all {V} words.") print(f" That is the bottleneck hierarchical softmax and negative") print(f" sampling exist to dodge.") # ---------------------------------------------------------- one forward pass def show_forward(eta=0.5): """A model small enough to print in full: |V| = 5, d = 2, context = 2.""" words = ["the", "cat", "dog", "sat", "ran"] V, d, H = len(words), 2, 3 rng = np.random.default_rng(0) E = np.array([[0.20, -0.10], # the [0.80, 0.30], # cat [0.75, 0.35], # dog [-0.40, 0.60], # sat [-0.35, 0.65]]) # ran Wh = rng.normal(0, 0.5, (4, H)) # (context 2 x d 2) -> H bh = np.zeros(H) Wo = rng.normal(0, 0.5, (H, V)) bo = np.zeros(V) ctx, target = ["the", "cat"], "sat" ti = words.index(target) print(f"\n\nSTEP 2 one forward pass, every number shown\n") print(f" context: {ctx} target: '{target}'") print(f" |V| = {V}, d = {d}, H = {H}\n") print(" LOOK UP. Each context word selects its row of E.") for w in ctx: print(f" E[{w}] = {np.round(E[words.index(w)], 3)}") x = np.concatenate([E[words.index(w)] for w in ctx]) print(f"\n CONCATENATE. x = {np.round(x, 3)} length {len(x)} = 2 x d") print(" This is the whole memory of the past. Its length is frozen") print(" the moment the context size is chosen.") h = np.tanh(Wh.T @ x + bh) print(f"\n MIX. h = tanh(W_h x + b_h) = {np.round(h, 4)}") z = Wo.T @ h + bo p = np.exp(z - z.max()) p /= p.sum() print(f"\n SCORE AND NORMALISE.\n") print(f" {'word':<8}{'score z':>10}{'exp(z)':>10}{'p = softmax':>14}") print(" " + "-" * 44) for i, w in enumerate(words): mark = " <- target" if i == ti else "" print(f" {w:<8}{z[i]:>+10.4f}{math.exp(z[i] - z.max()):>10.4f}" f"{p[i]:>14.4f}{mark}") print(" " + "-" * 44) print(f" {'':<8}{'':>10}{'':>10}{p.sum():>14.4f}") loss = -math.log(p[ti]) print(f"\n LOSS. y is one-hot at '{target}', so the sum collapses:") print(f" L = -log p['{target}'] = -log({p[ti]:.4f}) = {loss:.4f} nats") print(f"\n In bits that is {loss / math.log(2):.4f}, and a model scoring") print(f" every token this way would have perplexity" f" {math.exp(loss):.4f}.") print(" Cross-entropy and perplexity are the same objective.") # one gradient step print(f"\n\nSTEP 3 one backward pass (eta = {eta})\n") dz = p.copy() dz[ti] -= 1.0 # prediction minus target, again print(f" The gradient at the output is p - y:") for i, w in enumerate(words): print(f" {w:<6}{dz[i]:>+9.4f}" + (" push down" if i != ti else " pull up")) dh = Wo @ dz * (1 - h ** 2) dx = Wh @ dh Wo_new = Wo - eta * np.outer(h, dz) bo_new = bo - eta * dz Wh_new = Wh - eta * np.outer(x, dh) bh_new = bh - eta * dh E_new = E.copy() for j, w in enumerate(ctx): E_new[words.index(w)] -= eta * dx[j * d:(j + 1) * d] print(f"\n That gradient flows back into E as well, which is the point.") for w in ctx: i = words.index(w) print(f" E[{w}] {np.round(E[i], 4)} -> {np.round(E_new[i], 4)}") print("\n The word vectors are not given to the model. They are learned,") print(" as a by-product of learning to predict the next word.") h2 = np.tanh(Wh_new.T @ x + bh_new) z2 = Wo_new.T @ h2 + bo_new p2 = np.exp(z2 - z2.max()) p2 /= p2.sum() print(f"\n DID IT WORK?\n") print(f" {'word':<8}{'p before':>11}{'p after':>11}{'change':>10}") print(" " + "-" * 42) for i, w in enumerate(words): mark = " <- target" if i == ti else "" print(f" {w:<8}{p[i]:>11.4f}{p2[i]:>11.4f}{p2[i] - p[i]:>+10.4f}" f"{mark}") print(f"\n loss {loss:.4f} -> {-math.log(p2[ti]):.4f}") # ------------------------------------------------------------ generalisation # Two families of animals, each at home in its own family of places. Nobody # tells the model that the families exist. The structure is only in the data. PETS = ["cat", "dog", "puppy", "kitten", "hamster"] INDOOR = ["sofa", "carpet", "cushion", "basket"] FARM = ["horse", "cow", "goat", "sheep", "donkey"] OUTDOOR = ["meadow", "barn", "paddock", "pasture"] PLACES = set(INDOOR + OUTDOOR) def build_corpus(seed=0, hold=8, dev=6): """Every (animal, place) pair inside a family. Split three ways. The template is 'the ANIMAL rests PLACE', so the animal sits inside a trigram context. Both models can see it. The only question is whether they can transfer what they know about one animal to another. """ every = [f"the {a} rests {r}" for a, r in list(product(PETS, INDOOR)) + list(product(FARM, OUTDOOR))] idx = np.random.default_rng(seed).permutation(len(every)) held = [every[i] for i in idx[:hold]] dev_s = [every[i] for i in idx[hold:hold + dev]] train = [every[i] for i in idx[hold + dev:]] return train, dev_s, held class TrigramLM: """Add-alpha trigram counter, the baseline being tested against.""" def __init__(self, alpha=0.1): self.alpha = alpha self.ng, self.ctx, self.vocab = Counter(), Counter(), set() def train(self, sents): for s in sents: self.vocab.update(s.split()) self.vocab.add("") for s in sents: t = ["", ""] + s.split() + [""] for i in range(2, len(t)): self.ng[(t[i - 2], t[i - 1], t[i])] += 1 self.ctx[(t[i - 2], t[i - 1])] += 1 return self def place_perplexity(self, sents): """Score only the place slot. That is where the question lives.""" lp = n = 0.0 for s in sents: t = ["", ""] + s.split() + [""] for i in range(2, len(t)): if t[i] not in PLACES: continue c = (t[i - 2], t[i - 1]) num = self.ng[c + (t[i],)] + self.alpha den = self.ctx[c] + self.alpha * len(self.vocab) lp += math.log(num / den) n += 1 return math.exp(-lp / n) class NeuralLM: """The lookup, concatenate, mix, softmax model of this chapter.""" def __init__(self, vocab, d=12, H=24, ctx=2, seed=0): self.words = sorted(vocab) self.idx = {w: i for i, w in enumerate(self.words)} self.V, self.d, self.H, self.ctx = len(self.words), d, H, ctx rng = np.random.default_rng(seed) self.E = rng.normal(0, 0.1, (self.V, d)) self.Wh = rng.normal(0, 0.1, (ctx * d, H)) self.bh = np.zeros(H) self.Wo = rng.normal(0, 0.1, (H, self.V)) self.bo = np.zeros(self.V) def examples(self, sents): X, Y = [], [] for s in sents: t = [""] * self.ctx + s.split() + [""] for i in range(self.ctx, len(t)): X.append([self.idx[w] for w in t[i - self.ctx:i]]) Y.append(self.idx[t[i]]) return np.array(X), np.array(Y) def _forward(self, X): x = self.E[X].reshape(len(X), -1) h = np.tanh(x @ self.Wh + self.bh) z = h @ self.Wo + self.bo z -= z.max(axis=1, keepdims=True) p = np.exp(z) return x, h, p / p.sum(axis=1, keepdims=True) def fit(self, sents, steps=300, eta=0.5): X, Y = self.examples(sents) n = len(X) for _ in range(steps): x, h, p = self._forward(X) dz = p.copy() dz[np.arange(n), Y] -= 1.0 dz /= n dh = (dz @ self.Wo.T) * (1 - h ** 2) dx = dh @ self.Wh.T self.Wo -= eta * (h.T @ dz) self.bo -= eta * dz.sum(axis=0) self.Wh -= eta * (x.T @ dh) self.bh -= eta * dh.sum(axis=0) grad = dx.reshape(n, self.ctx, self.d) for j in range(self.ctx): np.add.at(self.E, X[:, j], -eta * grad[:, j]) return self def snapshot(self): return tuple(a.copy() for a in (self.E, self.Wh, self.bh, self.Wo, self.bo)) def restore(self, snap): self.E, self.Wh, self.bh, self.Wo, self.bo = snap def place_perplexity(self, sents): lp = n = 0.0 for s in sents: X, Y = self.examples([s]) _, _, p = self._forward(X) for i, t in enumerate(s.split()): if t in PLACES: lp += math.log(p[i, Y[i]]) n += 1 return math.exp(-lp / n) def train_with_early_stop(train, dev, seed, budget=2000, every=100): vocab = set(w for t in train for w in t.split()) | {"", ""} net = NeuralLM(vocab, seed=seed) best = (float("inf"), 0, net.snapshot()) for step in range(0, budget + 1, every): if step: net.fit(train, steps=every) d = net.place_perplexity(dev) if d < best[0]: best = (d, step, net.snapshot()) net.restore(best[2]) return net, best[1] def show_generalise(seeds=6): print("\n\nSTEP 4 does the neural model really generalise?\n") print(" Two families, and each animal rests in its own kind of place.") print(f" pets {PETS}") print(f" indoor {INDOOR}") print(f" farm {FARM}") print(f" outdoor {OUTDOOR}") print("\n Template: 'the ANIMAL rests PLACE'. The animal sits inside the") print(" trigram context, so the counter can see it too. Nothing is") print(" hidden from the baseline.") print("\n 40 sentences. 8 held out, 6 kept for early stopping, 26 to") print(" train on. We score only the place slot, which is the slot the") print(" animal is supposed to determine.\n") train, dev, held = build_corpus(0) print(" First, what overfitting looks like. Seed 0, place perplexity:\n") vocab = set(w for t in train for w in t.split()) | {"", ""} net = NeuralLM(vocab, seed=0) print(f" {'steps':>7}{'train':>10}{'held out':>11}") print(" " + "-" * 30) for step in range(0, 2001, 200): if step: net.fit(train, steps=200) print(f" {step:>7}{net.place_perplexity(train):>10.3f}" f"{net.place_perplexity(held):>11.3f}") print("\n Training perplexity falls the whole way and never looks back.") print(" Held-out perplexity bottoms early, then climbs by a factor of") print(" more than ten. The model stops learning the pattern and starts") print(" memorising the pairs it was given.") print("\n So we need a third split to tell us when to stop. That is what") print(" the dev set is for, and it is the only honest way to use it.\n") print(f" {'seed':>5}{'stopped at':>12}{'trigram':>10}{'neural':>9}" f"{'ratio':>8}") print(" " + "-" * 46) tri_tot = net_tot = 0.0 for s in range(seeds): train, dev, held = build_corpus(s) tri = TrigramLM(0.1).train(train) model, stop = train_with_early_stop(train, dev, s) a, b = tri.place_perplexity(held), model.place_perplexity(held) tri_tot, net_tot = tri_tot + a, net_tot + b print(f" {s:>5}{stop:>12}{a:>10.3f}{b:>9.3f}{a / b:>7.2f}x") print(" " + "-" * 46) print(f" The neural model wins on every seed, by" f" {tri_tot / net_tot:.2f} times overall.") print("\n Now the mechanism. Nobody told the model that 'kitten' and") print(" 'cat' are alike, or that a sofa is not a meadow. Two matrices") print(" hold what it worked out. E is where a word goes in. W_o is") print(" where a word comes out.\n") train, dev, held = build_corpus(0) model, _ = train_with_early_stop(train, dev, 0) def cos(M, a, b): u, v = M[a], M[b] return float(u @ v / (np.linalg.norm(u) * np.linalg.norm(v))) E, O = model.E, model.Wo.T i = model.idx pairs = [("cat", "puppy"), ("cat", "kitten"), ("horse", "cow"), ("cat", "horse"), ("sofa", "cushion"), ("meadow", "barn"), ("sofa", "meadow")] print(f" {'pair':<20}{'in E':>9}{'in W_o':>10}") print(" " + "-" * 40) for a, b in pairs: print(f" {a + ' / ' + b:<20}{cos(E, i[a], i[b]):>+9.3f}" f"{cos(O, i[a], i[b]):>+10.3f}") print("\n Read the two columns separately.") print("\n In E the animals separate cleanly. 'cat' and 'puppy' score") print(" +0.783, 'cat' and 'horse' score -0.336. The places do not") print(" separate at all: 'sofa' and 'cushion' score +0.271 while 'sofa'") print(" and 'meadow' score +0.225, which is no distinction.") print("\n In W_o it is the exact reverse. The places separate, +0.650") print(" for 'sofa' and 'cushion' against -0.051 for 'sofa' and 'meadow'.") print(" The animals stop separating: 'cat' and 'horse' reach +0.652.") print("\n The cause is the template. An animal only ever appears as") print(" context, so only its row of E is trained. A place only ever") print(" appears as a target, so only its column of W_o is trained.") print(" Each word learned structure in exactly the matrix it was used in.") print("\n This is why word2vec keeps two vectors per word, and why GloVe") print(" keeps w and w-tilde. Being a context and being a target are") print(" different jobs, and one vector cannot hold both.") print("\n The generalisation follows. A held-out animal lands near an") print(" animal the model has seen, so its prediction transfers. A count") print(" table has no such geometry, and every unseen pair drops to the") print(" smoothing floor.") def main(): ap = argparse.ArgumentParser(description=__doc__) ap.add_argument("--params", action="store_true") ap.add_argument("--forward", action="store_true") ap.add_argument("--generalise", action="store_true") ap.add_argument("--seeds", type=int, default=3) a = ap.parse_args() picked = a.params or a.forward or a.generalise if a.params or not picked: show_params() if a.forward or not picked: show_forward() if a.generalise or not picked: show_generalise(a.seeds) print() if __name__ == "__main__": main()