{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# BLEU, ROUGE and their blind spots\n",
    "\n",
    "Clipped precision, the brevity penalty, and a correct paraphrase that scores zero.\n",
    "\n",
    "From chapter 21, [Evaluating Generated Text](https://nlp.jcrlabz.com/book/evaluation/), of the course notes.\n",
    "\n",
    "Source: `book/code/worked_examples/bleu.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": [
    "\"\"\"Generation metrics, worked as Chapter 21 works them.\n",
    "\n",
    "Four things, all reproducing the chapter's tables:\n",
    "\n",
    "    modified precision  why plain n-gram precision is gameable\n",
    "    the brevity penalty why BLEU needs a length term, and what it costs\n",
    "    BLEU end to end     all four n, the geometric mean, the final score\n",
    "    ROUGE and the gap   recall instead of precision, and what neither sees\n",
    "\n",
    "    python3 bleu.py               # all four\n",
    "    python3 bleu.py --clip        # the clipping counter-example\n",
    "    python3 bleu.py --brevity     # the length term\n",
    "    python3 bleu.py --bleu        # a full score, step by step\n",
    "    python3 bleu.py --rouge       # ROUGE, and where both metrics fail\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",
    "\n",
    "def ngrams(tokens, n):\n",
    "    return Counter(tuple(tokens[i:i + n]) for i in range(len(tokens) - n + 1))\n",
    "\n",
    "\n",
    "def modified_precision(cand, refs, n):\n",
    "    \"\"\"Clipped precision: no n-gram may be credited more often than the\n",
    "    best single reference contains it.\"\"\"\n",
    "    c = ngrams(cand, n)\n",
    "    if not c:\n",
    "        return 0, 0\n",
    "    ceiling = Counter()\n",
    "    for r in refs:\n",
    "        rc = ngrams(r, n)\n",
    "        for g in rc:\n",
    "            ceiling[g] = max(ceiling[g], rc[g])\n",
    "    kept = sum(min(count, ceiling[g]) for g, count in c.items())\n",
    "    return kept, sum(c.values())\n",
    "\n",
    "\n",
    "def brevity_penalty(cand, refs):\n",
    "    c = len(cand)\n",
    "    r = min((len(x) for x in refs), key=lambda L: (abs(L - c), L))\n",
    "    return (1.0 if c > r else math.exp(1 - r / c) if c else 0.0), c, r\n",
    "\n",
    "\n",
    "def bleu(cand, refs, N=4):\n",
    "    ps = []\n",
    "    for n in range(1, N + 1):\n",
    "        kept, total = modified_precision(cand, refs, n)\n",
    "        ps.append((kept, total, kept / total if total else 0.0))\n",
    "    bp, c, r = brevity_penalty(cand, refs)\n",
    "    if any(p == 0 for _, _, p in ps):\n",
    "        return 0.0, ps, bp, c, r\n",
    "    logmean = sum(math.log(p) for _, _, p in ps) / N\n",
    "    return bp * math.exp(logmean), ps, bp, c, r\n",
    "\n",
    "\n",
    "# ---------------------------------------------------------------- clipping\n",
    "\n",
    "def show_clip():\n",
    "    print(\"\\nSTEP 1  why precision has to be clipped\\n\")\n",
    "    refs = [\"the cat is on the mat\".split(),\n",
    "            \"there is a cat on the mat\".split()]\n",
    "    print(\"  references:\")\n",
    "    for r in refs:\n",
    "        print(f\"    '{' '.join(r)}'\")\n",
    "\n",
    "    cheat = \"the the the the the the the\".split()\n",
    "    honest = \"the cat is on the mat\".split()\n",
    "\n",
    "    print(f\"\\n  A degenerate candidate: '{' '.join(cheat)}'\\n\")\n",
    "    c = ngrams(cheat, 1)\n",
    "    print(f\"  It contains 'the' {c[('the',)]} times, and every one of them\")\n",
    "    print(f\"  does appear in a reference. Unclipped unigram precision is\")\n",
    "    print(f\"  {c[('the',)]}/{sum(c.values())} = 1.0000, a perfect score for\")\n",
    "    print(f\"  a sentence that says nothing.\\n\")\n",
    "\n",
    "    kept, total = modified_precision(cheat, refs, 1)\n",
    "    print(f\"  Clipping caps each n-gram at the most any single reference\")\n",
    "    print(f\"  contains. Reference 1 has 'the' twice, so the ceiling is 2.\\n\")\n",
    "    print(f\"  {'candidate':<32}{'clipped':>9}{'total':>8}{'p_1':>9}\")\n",
    "    print(\"  \" + \"-\" * 60)\n",
    "    for name, cand in ((\"the the the ... (7 times)\", cheat),\n",
    "                       (\"the cat is on the mat\", honest)):\n",
    "        k, t = modified_precision(cand, refs, 1)\n",
    "        print(f\"  {name:<32}{k:>9}{t:>8}{k / t:>9.4f}\")\n",
    "\n",
    "    print(f\"\\n  The degenerate candidate drops to {kept}/{total} =\"\n",
    "          f\" {kept / total:.4f}.\")\n",
    "    print(f\"  Clipping is not a refinement. Without it the metric can be won\")\n",
    "    print(f\"  by repeating one word, so it would measure nothing at all.\")\n",
    "\n",
    "\n",
    "# ---------------------------------------------------------- brevity penalty\n",
    "\n",
    "def show_brevity():\n",
    "    print(\"\\n\\nSTEP 2  precision alone rewards saying less\\n\")\n",
    "    refs = [\"the cat is on the mat\".split()]\n",
    "    print(f\"  reference: '{' '.join(refs[0])}'   length {len(refs[0])}\\n\")\n",
    "    print(f\"  {'candidate':<26}{'len':>5}{'p_1':>9}{'BP':>9}\"\n",
    "          f\"{'p_1 x BP':>11}\")\n",
    "    print(\"  \" + \"-\" * 60)\n",
    "    for cand in (\"the\", \"the cat\", \"the cat is on\", \"the cat is on the mat\",\n",
    "                 \"the cat is on the mat today for a while\"):\n",
    "        toks = cand.split()\n",
    "        k, t = modified_precision(toks, refs, 1)\n",
    "        bp, c, r = brevity_penalty(toks, refs)\n",
    "        p = k / t if t else 0.0\n",
    "        print(f\"  {cand:<26}{len(toks):>5}{p:>9.4f}{bp:>9.4f}{p * bp:>11.4f}\")\n",
    "\n",
    "    print(f\"\\n  Look at the first row. One word, perfectly precise, and\")\n",
    "    print(f\"  useless. Precision alone would rank it top.\")\n",
    "    print(f\"\\n  The brevity penalty is exp(1 - r/c) when the candidate is\")\n",
    "    print(f\"  shorter than the reference, and 1 otherwise:\\n\")\n",
    "    print(f\"    BP = 1               if c > r\")\n",
    "    print(f\"    BP = exp(1 - r/c)    if c <= r\\n\")\n",
    "    print(f\"  It is deliberately asymmetric. Too short is punished, too long\")\n",
    "    print(f\"  is not, because a long candidate is already punished by\")\n",
    "    print(f\"  precision: the extra tokens are unmatched and dilute the ratio.\")\n",
    "    print(f\"\\n  Read the last row. Nine tokens against six, BP stays at 1.00,\")\n",
    "    print(f\"  and the score falls anyway because precision fell.\")\n",
    "\n",
    "\n",
    "# --------------------------------------------------------------- full BLEU\n",
    "\n",
    "def show_bleu():\n",
    "    refs = [\"the cat is on the mat\".split(),\n",
    "            \"there is a cat on the mat\".split()]\n",
    "    cands = {\n",
    "        \"the cat is on the mat\": \"the cat is on the mat\",\n",
    "        \"a cat is on the mat\": \"a cat is on the mat\",\n",
    "        \"the cat sat on the mat\": \"the cat sat on the mat\",\n",
    "        \"on mat the cat is the\": \"on mat the cat is the\",\n",
    "    }\n",
    "\n",
    "    print(\"\\n\\nSTEP 3  BLEU end to end\\n\")\n",
    "    print(\"  references:\")\n",
    "    for r in refs:\n",
    "        print(f\"    '{' '.join(r)}'\")\n",
    "    print()\n",
    "\n",
    "    for label, text in cands.items():\n",
    "        cand = text.split()\n",
    "        score, ps, bp, c, r = bleu(cand, refs)\n",
    "        print(f\"  candidate '{label}'\")\n",
    "        print(f\"    {'n':>3}{'clipped':>9}{'total':>7}{'p_n':>9}\")\n",
    "        print(\"    \" + \"-\" * 30)\n",
    "        for n, (kept, total, p) in enumerate(ps, start=1):\n",
    "            print(f\"    {n:>3}{kept:>9}{total:>7}{p:>9.4f}\")\n",
    "        print(f\"    candidate length {c}, closest reference {r}, BP {bp:.4f}\")\n",
    "        print(f\"    BLEU-4 = {score:.4f}\\n\")\n",
    "\n",
    "    print(\"  Three things that table shows.\\n\")\n",
    "    print(\"  BLEU uses the GEOMETRIC mean of the four precisions. One zero\")\n",
    "    print(\"  anywhere sends the whole score to zero, which is why the last\")\n",
    "    print(\"  candidate scores 0 despite getting most unigrams right.\")\n",
    "    print(\"\\n  That is severe on short texts and it is the reason BLEU is\")\n",
    "    print(\"  reported over a corpus rather than a sentence.\")\n",
    "    print(\"\\n  The scrambled candidate contains exactly the right words in\")\n",
    "    print(\"  the wrong order. Its unigram precision is high and its higher\")\n",
    "    print(\"  n-grams collapse, which is the only way BLEU sees word order.\")\n",
    "\n",
    "\n",
    "# ------------------------------------------------------------------- ROUGE\n",
    "\n",
    "def rouge_n(cand, refs, n):\n",
    "    c = ngrams(cand, n)\n",
    "    best = 0.0\n",
    "    for r in refs:\n",
    "        rc = ngrams(r, n)\n",
    "        if not rc:\n",
    "            continue\n",
    "        overlap = sum(min(c[g], rc[g]) for g in rc)\n",
    "        best = max(best, overlap / sum(rc.values()))\n",
    "    return best\n",
    "\n",
    "\n",
    "def show_rouge():\n",
    "    refs = [\"the cat is on the mat\".split()]\n",
    "    print(\"\\n\\nSTEP 4  ROUGE measures the other direction\\n\")\n",
    "    print(f\"  reference: '{' '.join(refs[0])}'\\n\")\n",
    "    print(\"  BLEU asks: how much of what I said was in the reference?\")\n",
    "    print(\"  ROUGE asks: how much of the reference did I say?\\n\")\n",
    "    print(\"  Precision against recall, and summarisation cares about the\")\n",
    "    print(\"  second one, because leaving things out is the failure mode.\\n\")\n",
    "\n",
    "    print(f\"  {'candidate':<44}{'BLEU-4':>9}{'ROUGE-1':>10}{'ROUGE-2':>10}\")\n",
    "    print(\"  \" + \"-\" * 74)\n",
    "    for text in (\"the cat is on the mat\",\n",
    "                 \"the cat\",\n",
    "                 \"the cat is on the mat and also on a fine rug\",\n",
    "                 \"the feline rests upon the rug\"):\n",
    "        cand = text.split()\n",
    "        score, *_ = bleu(cand, refs)\n",
    "        print(f\"  {text:<44}{score:>9.4f}{rouge_n(cand, refs, 1):>10.4f}\"\n",
    "              f\"{rouge_n(cand, refs, 2):>10.4f}\")\n",
    "\n",
    "    print(f\"\\n  Row 2 is short. BLEU tolerates it less than ROUGE does,\")\n",
    "    print(f\"  because ROUGE-1 still counts the two words it did recover.\")\n",
    "    print(f\"\\n  Row 3 is padded. ROUGE gives it a perfect 1.0000, because\")\n",
    "    print(f\"  every reference n-gram is present. BLEU does not, because the\")\n",
    "    print(f\"  padding is unmatched. Recall alone can be gamed by saying\")\n",
    "    print(f\"  everything, which is why ROUGE is usually reported with its\")\n",
    "    print(f\"  F-measure variant.\")\n",
    "    print(f\"\\n  Row 4 is the one that matters. It is a correct paraphrase.\")\n",
    "    print(f\"  BLEU gives it 0.0000 and ROUGE-2 gives it 0.0000. ROUGE-1\")\n",
    "    print(f\"  gives it 0.3333, and every point of that comes from the word\")\n",
    "    print(f\"  'the'. Not one content word was credited.\")\n",
    "    print(f\"\\n  Neither metric has any notion of meaning. They count string\")\n",
    "    print(f\"  overlap, and a paraphrase overlaps in the wrong places.\")\n",
    "    print(f\"\\n  That single row is the argument for everything that came\")\n",
    "    print(f\"  after: embedding-based metrics, learned metrics, and human\")\n",
    "    print(f\"  evaluation.\")\n",
    "\n",
    "\n",
    "def main():\n",
    "    ap = argparse.ArgumentParser(description=__doc__)\n",
    "    for f in (\"clip\", \"brevity\", \"bleu\", \"rouge\"):\n",
    "        ap.add_argument(f\"--{f}\", action=\"store_true\")\n",
    "    a = ap.parse_args()\n",
    "    picked = a.clip or a.brevity or a.bleu or a.rouge\n",
    "    if a.clip or not picked:\n",
    "        show_clip()\n",
    "    if a.brevity or not picked:\n",
    "        show_brevity()\n",
    "    if a.bleu or not picked:\n",
    "        show_bleu()\n",
    "    if a.rouge or not picked:\n",
    "        show_rouge()\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 = [\"bleu.py\", *args]\n",
    "    main()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `python3 bleu.py`\n",
    "\n",
    "Both metrics, computed in full."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "run()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `python3 bleu.py --clip`\n",
    "\n",
    "the the the the the the the scores a perfect 1.0 on unclipped unigram precision. Clipping drops it to 0.2857, which is the only reason the metric measures anything."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "run(\"--clip\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `python3 bleu.py --rouge`\n",
    "\n",
    "A correct paraphrase gets 0.0000 from BLEU-4 and 0.0000 from ROUGE-2, and its ROUGE-1 of 0.3333 comes entirely from the word the. Not one content word was credited."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "run(\"--rouge\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "Read the chapter this comes from: [Evaluating Generated Text](https://nlp.jcrlabz.com/book/evaluation/)."
   ]
  }
 ],
 "metadata": {
  "colab": {
   "name": "bleu.ipynb",
   "provenance": [],
   "toc_visible": true
  },
  "kernelspec": {
   "display_name": "Python 3",
   "name": "python3"
  },
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}