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