A First Taste of Algorithms · Lab 9: The Engine

hold out 15% of names as a test set the model never trains on

✦ ✦ ✦

perm = rng.permutation(len(names)); split = int(0.85 * len(names)) train_names = [names[i] for i in perm[:split]] test_names = [names[i] for i in perm[split:]]

def make(nms): X, Y = [], [] for name in nms: cs = [“.”] * CONTEXT + list(name) + [“.”] for i in range(len(cs) - CONTEXT): X.append([stoi[c] for c in cs[i:i+CONTEXT]]); Y.append(stoi[cs[i+CONTEXT]]) return np.array(X), np.array(Y) X, Y = make(train_names); Xte, Yte = make(test_names)

E, H = 12, 128 C = rng.standard_normal((V, E)) * 0.1 W1 = rng.standard_normal((CONTEXT * E, H)) * 0.1; b1 = np.zeros(H) W2 = rng.standard_normal((H, V)) * 0.1; b2 = np.zeros(V)

def forward(Xb): emb = C[Xb].reshape(len(Xb), -1) h = np.tanh(emb @ W1 + b1) return emb, h, h @ W2 + b2

def loss_on(Xb, Yb): , , logits = forward(Xb); n = len(Xb) logits = logits - logits.max(1, keepdims=True) p = np.exp(logits); p /= p.sum(1, keepdims=True) return -np.log(p[np.arange(n), Yb] + 1e-9).mean()

train_curve, test_curve = [], [] for step in range(8000): emb, h, logits = forward(X); n = len(X) logits = logits - logits.max(1, keepdims=True) p = np.exp(logits); p /= p.sum(1, keepdims=True) # backprop, by hand in numpy — the same blame-rules, batched dlogits = p.copy(); dlogits[np.arange(n), Y] -= 1; dlogits /= n dW2 = h.T @ dlogits + 0.001 * 2 * W2; db2 = dlogits.sum(0) dh = dlogits @ W2.T; dhraw = (1 - h**2) * dh dW1 = emb.T @ dhraw + 0.001 * 2 * W1; db1 = dhraw.sum(0) demb = (dhraw @ W1.T).reshape(n, CONTEXT, E) dC = np.zeros_like(C); np.add.at(dC, X.reshape(-1), demb.reshape(-1, E)) for param, grad in [(C, dC), (W1, dW1), (b1, db1), (W2, dW2), (b2, db2)]: param -= 0.3 * grad if step % 400 == 0: tr, te = loss_on(X, Y), loss_on(Xte, Yte) train_curve.append(tr); test_curve.append(te) print(f”step {step:4d} train {tr:.3f} held-out {te:.3f}”)

Watch the two columns. Early on both fall. Then they *part*: train keeps dropping while held-out bottoms out and turns upward. That divergence is the parrot exam catching the model beginning to memorize — and you are seeing, on your laptop in under a minute, the single most consequential phenomenon in modern machine learning. Plot it:

```python
import matplotlib.pyplot as plt
steps = [400 * i for i in range(len(train_curve))]
plt.plot(steps, train_curve, label="training loss")
plt.plot(steps, test_curve, label="held-out loss")
plt.xlabel("step"); plt.ylabel("loss"); plt.legend(); plt.show()

All 32 chapters of A First Taste of Algorithms · Foundations · All courses