{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# EM learning an alignment\n", "\n", "Four sentence pairs, and a translation table that arrives without anyone labelling a single word.\n", "\n", "From chapter 24, [Machine Translation](https://nlp.jcrlabz.com/book/translation/), of the course notes.\n", "\n", "Source: `book/code/worked_examples/ibm_model1.py`" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## What you need\n", "\n", "Nothing. This example uses only the Python standard library." ] }, { "cell_type": "code", "metadata": {}, "execution_count": null, "outputs": [], "source": [ "# Nothing to install: this example uses only the Python standard library.\n", "import sys; print(sys.version.split()[0])" ] }, { "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": [ "\"\"\"IBM Model 1, worked as Chapter 24 works it.\n", "\n", "The translation model that learns word alignment from nothing but sentence\n", "pairs. No dictionary, no alignment annotation, four sentences.\n", "\n", " the corpus four English and Swahili pairs, from the lectures\n", " one EM iteration every posterior and every count, by hand\n", " convergence the table at iterations 1, 5 and 10\n", " what it learned the alignments nobody supplied, and the one tie it\n", " refuses to break\n", " one more sentence what that tie needed, and what it also fixed\n", "\n", " python3 ibm_model1.py # all five\n", " python3 ibm_model1.py --step # one iteration in full detail\n", " python3 ibm_model1.py --learned # the table, and the honest tie\n", " python3 ibm_model1.py --extra # add a fifth pair, watch it resolve\n", " python3 ibm_model1.py --iters 50 # the tie is still there at 50\n", " python3 ibm_model1.py --pair \"my dog\" \"mbwa wangu\"\n", "\n", "Install: nothing, the Python standard library is enough\n", "\"\"\"\n", "\n", "import argparse\n", "from collections import defaultdict\n", "\n", "# The lecture corpus. English on the left, Swahili on the right. Nobody has\n", "# said which word translates which; that is exactly what has to be learned.\n", "PAIRS = [\n", " ([\"my\", \"dog\"], [\"mbwa\", \"wangu\"]),\n", " ([\"my\", \"house\"], [\"nyumba\", \"yangu\"]),\n", " ([\"my\", \"cycle\"], [\"mzunguko\", \"wangu\"]),\n", " ([\"his\", \"dog\"], [\"mbwa\", \"wake\"]),\n", "]\n", "\n", "# One more pair, held back on purpose. Section 4 shows what it fixes.\n", "EXTRA = ([\"his\", \"house\"], [\"nyumba\", \"wake\"])\n", "\n", "EN = [\"my\", \"house\", \"cycle\", \"his\", \"dog\"]\n", "SW = [\"mbwa\", \"wangu\", \"nyumba\", \"yangu\", \"mzunguko\", \"wake\"]\n", "\n", "\n", "def init_table():\n", " \"\"\"Uniform. Every Swahili word is equally likely for every English word.\"\"\"\n", " return {e: {f: 1.0 / len(SW) for f in SW} for e in EN}\n", "\n", "\n", "def em_step(t):\n", " \"\"\"One expectation-maximisation pass over the whole corpus.\n", "\n", " E-step: for each Swahili word in a pair, split one unit of count across\n", " the English words in that pair, in proportion to the current t(f|e).\n", " That split is the posterior over alignments, and Model 1 makes it this\n", " simple because it assumes all alignments are a priori equally likely.\n", "\n", " M-step: renormalise the collected counts into probabilities.\n", " \"\"\"\n", " count = defaultdict(float) # count[(e, f)]\n", " total = defaultdict(float) # total[e]\n", " detail = []\n", "\n", " for en, sw in PAIRS:\n", " for f in sw:\n", " z = sum(t[e][f] for e in en) # the normaliser\n", " for e in en:\n", " delta = t[e][f] / z\n", " count[(e, f)] += delta\n", " total[e] += delta\n", " detail.append((en, sw, f, e, t[e][f], z, delta))\n", "\n", " new = {e: {f: 0.0 for f in SW} for e in EN}\n", " for (e, f), c in count.items():\n", " new[e][f] = c / total[e]\n", " return new, detail, count, total\n", "\n", "\n", "def table(t, title, top=None):\n", " print(f\"\\n {title}\\n\")\n", " print(\" \" + \" \" * 9 + \"\".join(f\"{f[:8]:>10}\" for f in SW))\n", " print(\" \" + \"-\" * (9 + 10 * len(SW)))\n", " for e in EN:\n", " row = \"\".join(f\"{t[e][f]:>10.4f}\" for f in SW)\n", " best = max(SW, key=lambda f: t[e][f])\n", " mark = f\" -> {best}\" if top else \"\"\n", " print(f\" {e:<9}{row}{mark}\")\n", "\n", "\n", "# ------------------------------------------------------------------ the corpus\n", "\n", "def show_corpus():\n", " print(\"\\nSTEP 1 four sentence pairs, and nothing else\\n\")\n", " for i, (en, sw) in enumerate(PAIRS, start=1):\n", " print(f\" {i}. {' '.join(en):<12} {' '.join(sw)}\")\n", " print(f\"\\n English vocabulary: {EN}\")\n", " print(f\" Swahili vocabulary: {SW}\")\n", " print(\"\\n Nobody has said which word translates which. There is no\")\n", " print(\" dictionary and no alignment annotation. The only signal is that\")\n", " print(\" these sentences mean the same thing.\")\n", " print(\"\\n Two things make it solvable. 'my' appears in three pairs and\")\n", " print(\" 'dog' in two, so the words that travel with them are visible.\")\n", " print(\" And 'wangu' appears with 'my' twice, which is the wedge.\")\n", " print(\"\\n One wrinkle worth noticing. Swahili marks possession by noun\")\n", " print(\" class, so 'my' is 'wangu' with dog and cycle but 'yangu' with\")\n", " print(\" house. A model that assumed one translation per word would be\")\n", " print(\" wrong, and Model 1 does not assume that.\")\n", "\n", "\n", "# --------------------------------------------------------------- one iteration\n", "\n", "def show_step():\n", " t = init_table()\n", " print(\"\\n\\nSTEP 2 one iteration, every number\\n\")\n", " print(f\" Start uniform: every t(f|e) = 1/{len(SW)} =\"\n", " f\" {1/len(SW):.4f}\\n\")\n", " print(\" E-STEP. For each Swahili word, split one unit of count over the\")\n", " print(\" English words in its pair, in proportion to t(f|e).\\n\")\n", "\n", " new, detail, count, total = em_step(t)\n", " seen = set()\n", " print(f\" {'pair':<24}{'f':<11}{'e':<8}{'t(f|e)':>9}{'sum':>9}\"\n", " f\"{'delta':>9}\")\n", " print(\" \" + \"-\" * 72)\n", " for en, sw, f, e, tv, z, d in detail:\n", " key = \" \".join(en)\n", " label = f\"{' '.join(en)} / {' '.join(sw)}\" if key not in seen else \"\"\n", " seen.add(key)\n", " print(f\" {label:<24}{f:<11}{e:<8}{tv:>9.4f}{z:>9.4f}{d:>9.4f}\")\n", "\n", " print(\"\\n Every delta is 0.5000, because the table is still uniform and\")\n", " print(\" each pair has two English words. The first iteration cannot\")\n", " print(\" prefer anything. What it can do is count.\\n\")\n", "\n", " print(\" M-STEP. Collect the counts and renormalise.\\n\")\n", " print(f\" {'e':<9}{'f':<11}{'count(e,f)':>12}{'total(e)':>11}\"\n", " f\"{'t(f|e)':>10}\")\n", " print(\" \" + \"-\" * 55)\n", " for (e, f), c in sorted(count.items()):\n", " print(f\" {e:<9}{f:<11}{c:>12.4f}{total[e]:>11.4f}\"\n", " f\"{c/total[e]:>10.4f}\")\n", "\n", " print(\"\\n Read the rows for 'my'. It occurred in three pairs, so it\")\n", " print(\" collected 3.0 units of count spread over six Swahili words.\")\n", " print(\" 'wangu' got 1.0 of that and every other word got 0.5.\")\n", " print(\"\\n That asymmetry is the entire seed. 'wangu' appeared alongside\")\n", " print(\" 'my' twice and everything else once, and one pass of counting\")\n", " print(\" is enough to notice.\")\n", "\n", "\n", "# ---------------------------------------------------------------- convergence\n", "\n", "def show_convergence(iters=10, checkpoints=(1, 5, 10)):\n", " print(f\"\\n\\nSTEP 3 what repetition does\\n\")\n", " t = init_table()\n", " for i in range(1, iters + 1):\n", " t, _, _, _ = em_step(t)\n", " if i in checkpoints:\n", " table(t, f\"after iteration {i}\")\n", "\n", " print(\"\\n Follow one cell across the three tables. t(mbwa | dog) goes\")\n", " for i, tt in enumerate([init_table()], start=0):\n", " pass\n", " t2 = init_table()\n", " row = []\n", " for i in range(1, iters + 1):\n", " t2, _, _, _ = em_step(t2)\n", " if i in (1, 5, 10):\n", " row.append((i, t2[\"dog\"][\"mbwa\"], t2[\"my\"][\"wangu\"],\n", " t2[\"house\"][\"yangu\"]))\n", " print(f\"\\n {'iteration':>10}{'t(mbwa|dog)':>14}{'t(wangu|my)':>14}\"\n", " f\"{'t(yangu|house)':>16}\")\n", " print(\" \" + \"-\" * 56)\n", " print(f\" {'0 uniform':>10}{1/len(SW):>14.4f}{1/len(SW):>14.4f}\"\n", " f\"{1/len(SW):>16.4f}\")\n", " for i, a, b, c in row:\n", " print(f\" {i:>10}{a:>14.4f}{b:>14.4f}{c:>16.4f}\")\n", "\n", " print(\"\\n Nothing pushed those numbers except counting and\")\n", " print(\" renormalising, repeated. That is all EM is here.\")\n", "\n", "\n", "# ------------------------------------------------------------- what it learned\n", "\n", "def show_learned(iters=10):\n", " t = init_table()\n", " for _ in range(iters):\n", " t, _, _, _ = em_step(t)\n", "\n", " print(f\"\\n\\nSTEP 4 the alignment nobody supplied (after {iters}\"\n", " f\" iterations)\\n\")\n", " print(f\" {'English':<10}{'best Swahili':<12}{'p':>9}\"\n", " f\"{'runner up':>12}{'p':>9}\")\n", " print(\" \" + \"-\" * 54)\n", " for e in EN:\n", " ranked = sorted(SW, key=lambda f: -t[e][f])\n", " print(f\" {e:<10}{ranked[0]:<12}{t[e][ranked[0]]:>9.4f}\"\n", " f\"{ranked[1]:>12}{t[e][ranked[1]]:>9.4f}\")\n", "\n", " print(\"\\n Four of the five are settled. 'dog' went to 'mbwa' at\"\n", " f\" {t['dog']['mbwa']:.4f},\")\n", " print(f\" 'cycle' to 'mzunguko' at {t['cycle']['mzunguko']:.4f}, 'his' to\"\n", " f\" 'wake' at {t['his']['wake']:.4f},\")\n", " print(f\" and 'my' to 'wangu' at {t['my']['wangu']:.4f}. Nobody supplied\"\n", " \" any of that.\")\n", "\n", " print(\"\\n\\n NOW LOOK AT 'house'.\\n\")\n", " print(f\" t(nyumba | house) = {t['house']['nyumba']:.4f}\")\n", " print(f\" t(yangu | house) = {t['house']['yangu']:.4f}\")\n", " t50 = init_table()\n", " for _ in range(50):\n", " t50, _, _, _ = em_step(t50)\n", " print(f\"\\n Exactly tied, and it stays tied. After 50 iterations it is\"\n", " f\" still\")\n", " print(f\" {t50['house']['nyumba']:.4f} and {t50['house']['yangu']:.4f}.\")\n", " print(\"\\n This is not a failure of EM. It is EM being honest.\")\n", " print(\"\\n 'house' occurs in exactly one sentence pair, beside 'nyumba'\")\n", " print(\" and 'yangu'. Nothing anywhere else in the corpus distinguishes\")\n", " print(\" those two words. 'my' correctly pushes both of them down, and\")\n", " print(f\" pushes them down equally: {t50['my']['nyumba']:.4f} each.\")\n", " print(\"\\n So 'house' inherits both, in equal measure. The data contains\")\n", " print(\" a tie, and the model reports a tie rather than inventing a\")\n", " print(\" preference. A model that broke it would be making something up.\")\n", "\n", "\n", "def show_extra(iters=10):\n", " \"\"\"Add one sentence pair and watch the tie resolve.\"\"\"\n", " global PAIRS\n", " base = list(PAIRS)\n", " t = init_table()\n", " for _ in range(iters):\n", " t, _, _, _ = em_step(t)\n", " before = dict(t[\"house\"])\n", "\n", " PAIRS = base + [EXTRA]\n", " t2 = init_table()\n", " for _ in range(iters):\n", " t2, _, _, _ = em_step(t2)\n", " PAIRS = base\n", "\n", " print(\"\\n\\nSTEP 5 one more sentence, and the tie breaks\\n\")\n", " print(f\" Add a fifth pair: {' '.join(EXTRA[0]):<12}\"\n", " f\"{' '.join(EXTRA[1])}\")\n", " print(\"\\n 'house' now meets 'nyumba' twice and 'yangu' once. That is\")\n", " print(\" the only new information, and it is enough.\\n\")\n", " print(f\" {'':<10}{'4 pairs':>12}{'5 pairs':>12}\")\n", " print(\" \" + \"-\" * 36)\n", " for f in (\"nyumba\", \"yangu\"):\n", " print(f\" t({f[:6]}|house){before[f]:>10.4f}{t2['house'][f]:>12.4f}\")\n", "\n", " print(f\"\\n 'house' resolves to 'nyumba' at {t2['house']['nyumba']:.4f}.\")\n", " print(\"\\n Something else moved too. Watch 'my':\\n\")\n", " print(f\" {'':<12}{'4 pairs':>12}{'5 pairs':>12}\")\n", " print(\" \" + \"-\" * 36)\n", " for f in (\"wangu\", \"yangu\"):\n", " print(f\" t({f}|my){t['my'][f]:>12.4f}{t2['my'][f]:>12.4f}\")\n", "\n", " print(f\"\\n t(yangu|my) rose from {t['my']['yangu']:.4f} to\"\n", " f\" {t2['my']['yangu']:.4f}, which is more correct.\")\n", " print(\" 'yangu' really is Swahili for 'my', in the noun class that\")\n", " print(\" 'house' belongs to. Freeing 'house' from the tie let the\")\n", " print(\" evidence for that reach 'my'.\")\n", " print(\"\\n One sentence pair. That is the argument for parallel corpus\")\n", " print(\" size, and it is why statistical MT waited for the Canadian\")\n", " print(\" Hansard and the European Parliament proceedings.\")\n", "\n", "\n", "def trace_pair(en_s, sw_s, iters=10):\n", " t = init_table()\n", " for _ in range(iters):\n", " t, _, _, _ = em_step(t)\n", " en, sw = en_s.split(), sw_s.split()\n", " print(f\"\\n\\nALIGNMENT for '{en_s}' / '{sw_s}' (after {iters} iterations)\\n\")\n", " print(f\" {'Swahili':<12}\" + \"\".join(f\"{e:>10}\" for e in en)\n", " + f\"{' most likely':>16}\")\n", " print(\" \" + \"-\" * (12 + 10 * len(en) + 16))\n", " for f in sw:\n", " if f not in SW:\n", " print(f\" {f:<12}not in the vocabulary\")\n", " continue\n", " z = sum(t[e][f] for e in en if e in EN)\n", " post = {e: (t[e][f] / z if z else 0.0) for e in en if e in EN}\n", " cells = \"\".join(f\"{post.get(e, 0.0):>10.4f}\" for e in en)\n", " best = max(post, key=post.get) if post else \"?\"\n", " print(f\" {f:<12}{cells}{best:>16}\")\n", " print(\"\\n Each row is a posterior over alignments for one target word.\")\n", " print(\" Model 1 has no notion of position, so this is decided entirely\")\n", " print(\" by the translation table.\")\n", "\n", "\n", "def main():\n", " ap = argparse.ArgumentParser(description=__doc__)\n", " ap.add_argument(\"--corpus\", action=\"store_true\")\n", " ap.add_argument(\"--step\", action=\"store_true\")\n", " ap.add_argument(\"--converge\", action=\"store_true\")\n", " ap.add_argument(\"--learned\", action=\"store_true\")\n", " ap.add_argument(\"--extra\", action=\"store_true\",\n", " help=\"add a fifth pair and watch the tie break\")\n", " ap.add_argument(\"--iters\", type=int, default=10)\n", " ap.add_argument(\"--pair\", nargs=2, metavar=(\"ENGLISH\", \"SWAHILI\"))\n", " a = ap.parse_args()\n", "\n", " if a.pair:\n", " trace_pair(a.pair[0], a.pair[1], a.iters)\n", " print()\n", " return\n", "\n", " picked = a.corpus or a.step or a.converge or a.learned or a.extra\n", " if a.corpus or not picked:\n", " show_corpus()\n", " if a.step or not picked:\n", " show_step()\n", " if a.converge or not picked:\n", " show_convergence(a.iters)\n", " if a.learned or not picked:\n", " show_learned(a.iters)\n", " if a.extra or not picked:\n", " show_extra(a.iters)\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 = [\"ibm_model1.py\", *args]\n", " main()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### `python3 ibm_model1.py`\n", "\n", "The corpus, the steps and what was learned." ] }, { "cell_type": "code", "metadata": {}, "execution_count": null, "outputs": [], "source": [ "run()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### `python3 ibm_model1.py --step`\n", "\n", "One EM iteration in full, from uniform probabilities to updated counts." ] }, { "cell_type": "code", "metadata": {}, "execution_count": null, "outputs": [], "source": [ "run(\"--step\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### `python3 ibm_model1.py --learned`\n", "\n", "The table after convergence, and the alignments it implies." ] }, { "cell_type": "code", "metadata": {}, "execution_count": null, "outputs": [], "source": [ "run(\"--learned\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "\n", "Read the chapter this comes from: [Machine Translation](https://nlp.jcrlabz.com/book/translation/)." ] } ], "metadata": { "colab": { "name": "ibm_model1.ipynb", "provenance": [], "toc_visible": true }, "kernelspec": { "display_name": "Python 3", "name": "python3" }, "language_info": { "name": "python" } }, "nbformat": 4, "nbformat_minor": 0 }