{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Smoothing, perplexity and the U-curve\n",
"\n",
"Add-alpha smoothing, held-out perplexity and interpolation, on three sentences of training data.\n",
"\n",
"From chapter 10, [n-gram Language Models and Perplexity](https://nlp.jcrlabz.com/book/ngram-lm/), of the course notes.\n",
"\n",
"Source: `book/code/worked_examples/ngram_lm.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": [
"\"\"\"n-gram language models, worked as Chapter 10 works them.\n",
"\n",
"Every table in the chapter comes from this file. The conventions match\n",
"`autograder/ngram_reference.py` exactly, so the numbers here are the numbers\n",
"Assignment 4 grades against:\n",
"\n",
" pad with (n-1) copies of and one \n",
" V holds every training word, plus and \n",
" is context only, never predicted, never mapped to \n",
" perplexity is over the predicted tokens: the words plus \n",
"\n",
" python3 ngram_lm.py # every step\n",
" python3 ngram_lm.py --counts # counts, MLE, add-one, side by side\n",
" python3 ngram_lm.py --perplexity # the four-row perplexity table\n",
" python3 ngram_lm.py --alpha # the U shape that picks alpha\n",
" python3 ngram_lm.py --params # why n = 5 is not an option\n",
" python3 ngram_lm.py --interpolate # backoff and interpolation\n",
" python3 ngram_lm.py --unk # what happens to an unseen word\n",
"\n",
"Install: nothing, the Python standard library is enough\n",
"\"\"\"\n",
"\n",
"import argparse\n",
"import math\n",
"from collections import Counter\n",
"\n",
"BOS, EOS, UNK = \"\", \"\", \"\"\n",
"\n",
"TRAIN = [\"the cat sat\", \"the cat ran\", \"the dog sat\"]\n",
"\n",
"# A second corpus for interpolation, where the trigram counts run out but the\n",
"# bigram counts do not.\n",
"TRAIN3 = [\n",
" \"the cat sat on the mat\",\n",
" \"the cat sat on the rug\",\n",
" \"the dog sat on the mat\",\n",
" \"a cat ran to the mat\",\n",
"]\n",
"\n",
"\n",
"def tokenize(text):\n",
" return text.lower().split()\n",
"\n",
"\n",
"def padded(tokens, n):\n",
" return [BOS] * (n - 1) + list(tokens) + [EOS]\n",
"\n",
"\n",
"class NGramLM:\n",
" \"\"\"Add-alpha smoothed n-gram model. Same arithmetic as the autograder.\"\"\"\n",
"\n",
" def __init__(self, n=2, alpha=1.0):\n",
" self.n, self.alpha = n, alpha\n",
" self.vocab = set()\n",
" self.ngram = Counter()\n",
" self.context = Counter()\n",
"\n",
" def train(self, sentences):\n",
" for s in sentences:\n",
" self.vocab.update(tokenize(s))\n",
" self.vocab.update([EOS, UNK])\n",
" for s in sentences:\n",
" p = padded(tokenize(s), self.n)\n",
" for i in range(self.n - 1, len(p)):\n",
" ctx = tuple(p[i - self.n + 1:i])\n",
" self.ngram[ctx + (p[i],)] += 1\n",
" self.context[ctx] += 1\n",
" return self\n",
"\n",
" def _map(self, w):\n",
" # is padding, not a word. It is deliberately outside V, so sending\n",
" # it to would throw away every start-of-sentence statistic.\n",
" return w if w == BOS or w in self.vocab else UNK\n",
"\n",
" def prob(self, word, context):\n",
" ctx = tuple(self._map(c) for c in context)\n",
" num = self.ngram.get(ctx + (self._map(word),), 0) + self.alpha\n",
" den = self.context.get(ctx, 0) + self.alpha * len(self.vocab)\n",
" return num / den if den else 0.0\n",
"\n",
" def scored(self, sentence):\n",
" \"\"\"Every (context, word, probability) the sentence is scored on.\"\"\"\n",
" p = padded(tokenize(sentence), self.n)\n",
" out = []\n",
" for i in range(self.n - 1, len(p)):\n",
" ctx = tuple(p[i - self.n + 1:i])\n",
" out.append((ctx, p[i], self.prob(p[i], ctx)))\n",
" return out\n",
"\n",
" def perplexity(self, sentence):\n",
" rows = self.scored(sentence)\n",
" lp = sum(math.log2(p) for _, _, p in rows)\n",
" return 2 ** (-lp / len(rows))\n",
"\n",
" def corpus_perplexity(self, sentences):\n",
" lp = n = 0.0\n",
" for s in sentences:\n",
" rows = self.scored(s)\n",
" lp += sum(math.log2(p) for _, _, p in rows)\n",
" n += len(rows)\n",
" return 2 ** (-lp / n)\n",
"\n",
"\n",
"def mle(sentences, word, given, n=2):\n",
" \"\"\"Unsmoothed maximum likelihood estimate, straight from the counts.\"\"\"\n",
" ng, ctx = Counter(), Counter()\n",
" for s in sentences:\n",
" p = padded(tokenize(s), n)\n",
" for i in range(n - 1, len(p)):\n",
" c = tuple(p[i - n + 1:i])\n",
" ng[c + (p[i],)] += 1\n",
" ctx[c] += 1\n",
" g = given if isinstance(given, tuple) else (given,)\n",
" return ng[g + (word,)] / ctx[g] if ctx[g] else 0.0\n",
"\n",
"\n",
"def raw_counts(sentences, n=2):\n",
" ng, ctx = Counter(), Counter()\n",
" for s in sentences:\n",
" p = padded(tokenize(s), n)\n",
" for i in range(n - 1, len(p)):\n",
" c = tuple(p[i - n + 1:i])\n",
" ng[c + (p[i],)] += 1\n",
" ctx[c] += 1\n",
" return ng, ctx\n",
"\n",
"\n",
"# ------------------------------------------------------------------ step one\n",
"\n",
"def show_counts():\n",
" m = NGramLM(2, 1.0).train(TRAIN)\n",
" ng, ctx = raw_counts(TRAIN)\n",
" V = sorted(m.vocab)\n",
"\n",
" print(\"\\nSTEP 1 three sentences, and what they say about 'the'\\n\")\n",
" print(\" training: \" + \" \".join(f\"'{s}'\" for s in TRAIN))\n",
" print(f\"\\n vocabulary V = {V}\")\n",
" print(f\" |V| = {len(m.vocab)}. is not in V. It is context, never a\"\n",
" \" prediction.\")\n",
"\n",
" print(\"\\n contexts and how often each was seen:\")\n",
" print(\" \" + \" \".join(f\"{c[0]}: {n}\" for c, n in sorted(ctx.items())))\n",
"\n",
" for given in (\"the\", \"dog\"):\n",
" print(f\"\\n\\n CONTEXT '{given}' seen {ctx[(given,)]} times\\n\")\n",
" print(f\" {'next word':<12}{'count':>7}{'MLE':>10}{'add-1':>10}\"\n",
" f\"{' what add-1 did'}\")\n",
" print(\" \" + \"-\" * 62)\n",
" tm = ta = 0.0\n",
" for w in V:\n",
" c = ng[(given, w)]\n",
" a, b = mle(TRAIN, w, given), m.prob(w, (given,))\n",
" tm, ta = tm + a, ta + b\n",
" note = \"gave it mass\" if a == 0 else f\"took {a - b:+.4f}\"\n",
" print(f\" {w:<12}{c:>7}{a:>10.4f}{b:>10.4f} {note}\")\n",
" print(\" \" + \"-\" * 62)\n",
" print(f\" {'total':<12}{ctx[(given,)]:>7}{tm:>10.4f}{ta:>10.4f}\")\n",
"\n",
" print(\"\\n Both columns sum to 1, which is the point of the alpha|V| term\")\n",
" print(\" in the denominator. The counts did not change. The belief did.\")\n",
" print(\"\\n Read the 'dog' table again. MLE says p(sat|dog) = 1, so the\")\n",
" print(\" model believes 'the dog ran' is impossible. Add-1 drops that\")\n",
" print(\" certainty to 0.25 and hands 0.125 to every other word.\")\n",
"\n",
"\n",
"# ------------------------------------------------------------------ step two\n",
"\n",
"def show_perplexity(sentence=\"the cat sat\", alpha=1.0):\n",
" m = NGramLM(2, alpha).train(TRAIN)\n",
" ng, ctx = raw_counts(TRAIN)\n",
" rows = m.scored(sentence)\n",
"\n",
" print(f\"\\n\\nSTEP 2 perplexity of '{sentence}' (bigram, alpha = {alpha})\\n\")\n",
" print(f\" {'predicted':<12}{'context':<10}{'count':>7}{'of':>5}\"\n",
" f\"{'p add-1':>10}{'log2 p':>10}\")\n",
" print(\" \" + \"-\" * 56)\n",
" total = 0.0\n",
" for c, w, p in rows:\n",
" total += math.log2(p)\n",
" print(f\" {w:<12}{c[0]:<10}{ng[c + (w,)]:>7}{ctx[c]:>5}\"\n",
" f\"{p:>10.4f}{math.log2(p):>10.4f}\")\n",
" n = len(rows)\n",
" h = -total / n\n",
" print(\" \" + \"-\" * 56)\n",
" print(f\" {'sum':<34}{'':>10}{total:>10.4f}\")\n",
" print(f\"\\n N = {n} predicted tokens. The words, plus one .\")\n",
" print(f\" was context for the first row and was never predicted.\")\n",
" print(f\"\\n H = -({total:.4f}) / {n} = {h:.4f} bits per token\")\n",
" print(f\" PP = 2^{h:.4f} = {2 ** h:.4f}\")\n",
" print(f\"\\n So the model is about as unsure at each step as if it were\")\n",
" print(f\" choosing uniformly among {2 ** h:.2f} words. The vocabulary has\"\n",
" f\" {len(m.vocab)}.\")\n",
"\n",
"\n",
"# ---------------------------------------------------------------- step three\n",
"\n",
"def show_alpha():\n",
" seen, held = \"the cat sat\", \"the dog ran\"\n",
" grid = [0.01, 0.02, 0.05, 0.1, 0.15, 0.2, 0.3, 0.5, 1.0, 2.0]\n",
"\n",
" print(\"\\n\\nSTEP 3 choosing alpha, and why the test set has to be new\\n\")\n",
" print(f\" '{seen}' appears in training. '{held}' does not.\")\n",
" print(f\" Every word of '{held}' does. Only the bigram (dog, ran) is new.\\n\")\n",
" print(f\" {'alpha':>7}{'PP seen':>12}{'PP held out':>14}\"\n",
" f\"{'p(cat|the)':>13}\")\n",
" print(\" \" + \"-\" * 46)\n",
" best = (float(\"inf\"), None)\n",
" for a in grid:\n",
" m = NGramLM(2, a).train(TRAIN)\n",
" p_seen, p_held = m.perplexity(seen), m.perplexity(held)\n",
" if p_held < best[0]:\n",
" best = (p_held, a)\n",
" print(f\" {a:>7}{p_seen:>12.4f}{p_held:>14.4f}\"\n",
" f\"{m.prob('cat', ('the',)):>13.4f}\")\n",
"\n",
" print(f\"\\n The seen column falls all the way down. Less smoothing always\")\n",
" print(f\" looks better on text the model memorised.\")\n",
" print(f\"\\n The held out column is a U. It bottoms at alpha = {best[1]},\")\n",
" print(f\" PP = {best[0]:.4f}, and rises on both sides.\")\n",
" print(f\"\\n Too little smoothing and the one unseen bigram is crushed.\")\n",
" print(f\" Too much and the seen bigrams are robbed to pay for it.\")\n",
" worst = NGramLM(2, grid[0]).train(TRAIN).perplexity(held)\n",
" print(f\"\\n Tuning alpha on training text would have picked {grid[0]}, the\")\n",
" print(f\" bottom of the seen column. On held out text that scores\"\n",
" f\" {worst:.4f}\")\n",
" print(f\" against the best available {best[0]:.4f}, so it is\"\n",
" f\" {worst / best[0]:.2f} times worse.\")\n",
"\n",
"\n",
"# ----------------------------------------------------------------- step four\n",
"\n",
"def show_params():\n",
" print(\"\\n\\nSTEP 4 the curse of dimensionality, in one table\\n\")\n",
" print(\" An n-gram model needs one number per (history, word) pair.\")\n",
" print(\" There are |V|^(n-1) histories and |V|-1 free choices in each.\\n\")\n",
" print(f\" {'|V|':>8}{'n=1':>12}{'n=2':>12}{'n=3':>12}{'n=4':>12}\"\n",
" f\"{'n=5':>12}\")\n",
" print(\" \" + \"-\" * 68)\n",
" for V in (1000, 10000, 50000):\n",
" cells = \"\".join(f\"{V ** (n - 1) * (V - 1):>12.1e}\" for n in range(1, 6))\n",
" print(f\" {V:>8}\" + cells)\n",
"\n",
" V, n = 50000, 5\n",
" params = V ** (n - 1) * (V - 1)\n",
" corpus = 1e12 # a trillion tokens, a large corpus\n",
" print(f\"\\n At |V| = {V} a 5-gram model has {params:.3e} parameters.\")\n",
" print(f\"\\n Now count what could ever fill them. A corpus of {corpus:.0e}\")\n",
" print(f\" tokens contains at most {corpus:.0e} distinct 5-grams, one per\")\n",
" print(f\" position. So at most {corpus / params:.1e} of the cells can hold\")\n",
" print(f\" a nonzero count. That is about one cell in\"\n",
" f\" {params / corpus:.0e}.\")\n",
" print(\"\\n The counts do not merely get thin. Almost every cell is empty,\")\n",
" print(\" and no corpus that will ever exist can fill them.\")\n",
" print(\"\\n This is the wall Chapter 11 walks into, and the reason neural\")\n",
" print(\" language models exist. They do not store a cell per history.\")\n",
"\n",
"\n",
"# ----------------------------------------------------------------- step five\n",
"\n",
"def show_interpolate():\n",
" ng3, ctx3 = raw_counts(TRAIN3, 3)\n",
" ng2, ctx2 = raw_counts(TRAIN3, 2)\n",
" ng1, ctx1 = raw_counts(TRAIN3, 1)\n",
" lam = (0.1, 0.3, 0.6) # unigram, bigram, trigram\n",
"\n",
" print(\"\\n\\nSTEP 5 backoff and interpolation\\n\")\n",
" print(\" training:\")\n",
" for s in TRAIN3:\n",
" print(f\" '{s}'\")\n",
" print(f\"\\n weights: lambda1 = {lam[0]} unigram, lambda2 = {lam[1]}\"\n",
" f\" bigram, lambda3 = {lam[2]} trigram\")\n",
" print(f\" they sum to {sum(lam)}, which is the one constraint.\\n\")\n",
"\n",
" # Four queries chosen to walk down the staircase: all orders agree, then\n",
" # the trigram sharpens, then the trigram fails, then the bigram fails too.\n",
" queries = [(\"on\", (\"cat\", \"sat\")), (\"mat\", (\"on\", \"the\")),\n",
" (\"cat\", (\"on\", \"the\")), (\"ran\", (\"on\", \"the\"))]\n",
" print(f\" {'query':<22}{'p3 tri':>9}{'p2 bi':>9}{'p1 uni':>9}\"\n",
" f\"{'mixed':>10} seen as\")\n",
" print(\" \" + \"-\" * 74)\n",
" for w, ctx in queries:\n",
" p3 = mle(TRAIN3, w, ctx, 3)\n",
" p2 = mle(TRAIN3, w, ctx[-1], 2)\n",
" p1 = ng1[(w,)] / sum(ctx1.values())\n",
" mix = lam[0] * p1 + lam[1] * p2 + lam[2] * p3\n",
" note = (f\"trigram {ng3[ctx + (w,)]}x, bigram {ng2[(ctx[-1], w)]}x\")\n",
" print(f\" {'p(' + w + ' | ' + ' '.join(ctx) + ')':<22}\"\n",
" f\"{p3:>9.4f}{p2:>9.4f}{p1:>9.4f}{mix:>10.4f} {note}\")\n",
"\n",
" print(\"\\n Row 1, 'cat sat on'. Every order is certain and the mix is high.\")\n",
" print(\" Row 2, 'on the mat'. The trigram is sharper than the bigram,\")\n",
" print(\" because it has the extra word of context, and the mix lands\")\n",
" print(\" between them.\")\n",
" print(\"\\n Row 3 is the one that matters. 'on the cat' never occurred, so\")\n",
" print(\" the trigram says impossible. The bigram has seen 'the cat' twice\")\n",
" print(\" and says 0.2857. The mix keeps the sentence alive.\")\n",
" print(\"\\n Row 4, 'ran' never follows 'the' at all. Both higher orders\")\n",
" print(\" fail and only the unigram is left. The answer is small but not\")\n",
" print(\" zero, which is the entire purpose.\")\n",
" print(\"\\n Backoff does the same job with a switch instead of a blend.\")\n",
" print(\" Use the trigram if you have seen it, otherwise drop an order.\")\n",
"\n",
"\n",
"# ------------------------------------------------------------------ step six\n",
"\n",
"def show_unk():\n",
" m = NGramLM(2, 1.0).train(TRAIN)\n",
" print(\"\\n\\nSTEP 6 a word the model has never met\\n\")\n",
" tests = [\"the cat sat\", \"the dog ran\", \"the cat slept\", \"a zebra danced\"]\n",
" print(f\" {'sentence':<18}{'maps to':<34}{'PP':>9}\")\n",
" print(\" \" + \"-\" * 62)\n",
" for s in tests:\n",
" mapped = \" \".join(m._map(w) for w in tokenize(s))\n",
" print(f\" {s:<18}{mapped:<34}{m.perplexity(s):>9.4f}\")\n",
" print(\"\\n Unseen words become , which is an ordinary member of V.\")\n",
" print(\" So the model has a probability for them and never returns zero.\")\n",
" print(\" Perplexity still rises, and it should. The model really is more\")\n",
" print(\" surprised by a sentence it cannot read.\")\n",
"\n",
"\n",
"def main():\n",
" ap = argparse.ArgumentParser(description=__doc__)\n",
" for flag in (\"counts\", \"perplexity\", \"alpha\", \"params\", \"interpolate\",\n",
" \"unk\"):\n",
" ap.add_argument(f\"--{flag}\", action=\"store_true\")\n",
" ap.add_argument(\"--sentence\", default=\"the cat sat\")\n",
" ap.add_argument(\"--alpha-value\", type=float, default=1.0)\n",
" a = ap.parse_args()\n",
"\n",
" picked = any([a.counts, a.perplexity, a.alpha, a.params, a.interpolate,\n",
" a.unk])\n",
" if a.counts or not picked:\n",
" show_counts()\n",
" if a.perplexity or not picked:\n",
" show_perplexity(a.sentence, a.alpha_value)\n",
" if a.alpha or not picked:\n",
" show_alpha()\n",
" if a.params or not picked:\n",
" show_params()\n",
" if a.interpolate or not picked:\n",
" show_interpolate()\n",
" if a.unk or not picked:\n",
" show_unk()\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 = [\"ngram_lm.py\", *args]\n",
" main()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### `python3 ngram_lm.py`\n",
"\n",
"The counts, the smoothing and the perplexity in one pass."
]
},
{
"cell_type": "code",
"metadata": {},
"execution_count": null,
"outputs": [],
"source": [
"run()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### `python3 ngram_lm.py --counts`\n",
"\n",
"Add-one moves p(cat|the) from 0.6667 to 0.3000 and hands 0.1 to five words that never appeared. Both columns still sum to 1."
]
},
{
"cell_type": "code",
"metadata": {},
"execution_count": null,
"outputs": [],
"source": [
"run(\"--counts\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### `python3 ngram_lm.py --alpha`\n",
"\n",
"On memorised text perplexity falls all the way down. On held-out text it is a U bottoming at 0.10. Tuning on the training text picks 0.01 and scores 1.35 times worse."
]
},
{
"cell_type": "code",
"metadata": {},
"execution_count": null,
"outputs": [],
"source": [
"run(\"--alpha\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### `python3 ngram_lm.py --interpolate`\n",
"\n",
"The trigram on the cat never occurred, so a pure trigram model calls the phrase impossible. The blend returns 0.0964 and the sentence survives."
]
},
{
"cell_type": "code",
"metadata": {},
"execution_count": null,
"outputs": [],
"source": [
"run(\"--interpolate\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"\n",
"Read the chapter this comes from: [n-gram Language Models and Perplexity](https://nlp.jcrlabz.com/book/ngram-lm/)."
]
}
],
"metadata": {
"colab": {
"name": "ngram_lm.ipynb",
"provenance": [],
"toc_visible": true
},
"kernelspec": {
"display_name": "Python 3",
"name": "python3"
},
"language_info": {
"name": "python"
}
},
"nbformat": 4,
"nbformat_minor": 0
}