{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "414cd8dd",
   "metadata": {},
   "source": [
    "# How a Model is Fitted · L3 — A search that cannot go back\n",
    "\n",
    "`decision-trees` built a tree by taking the best question available at each\n",
    "step. It never asked what else it could have built.\n",
    "\n",
    "Twenty-four films and five questions is small enough to ask. Restrict to trees\n",
    "two questions deep and there are **125** of them, so every one can be built and\n",
    "scored. This notebook builds all 125 and puts the greedy tree in both rankings:\n",
    "by total impurity, and by films it gets right.\n",
    "\n",
    "Every figure and number this notebook produces is what the lesson prints.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "5ff231f0",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-20T13:49:06.380480Z",
     "iopub.status.busy": "2026-08-20T13:49:06.380328Z",
     "iopub.status.idle": "2026-08-20T13:49:06.632885Z",
     "shell.execute_reply": "2026-08-20T13:49:06.631499Z"
    }
   },
   "outputs": [],
   "source": [
    "# hide — plumbing so this file runs both in the repo and in Colab.\n",
    "try:\n",
    "    from _figkit import save_fig, record\n",
    "except ImportError:  # Colab — no repo, no problem\n",
    "    def save_fig(name, plot, **kw):\n",
    "        import matplotlib.pyplot as plt\n",
    "        fig, ax = plt.subplots(figsize=kw.get('figsize', (7, 4.2))); plot(ax); plt.show()\n",
    "    def record(key, value):\n",
    "        print(f'{key} = {value}'); return value\n",
    "\n",
    "import numpy as np\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "e6769d75",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-20T13:49:06.635550Z",
     "iopub.status.busy": "2026-08-20T13:49:06.635377Z",
     "iopub.status.idle": "2026-08-20T13:49:06.643349Z",
     "shell.execute_reply": "2026-08-20T13:49:06.642921Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "n_films = 24\n",
      "n_questions = 5\n",
      "24 films, 12 of them hits\n"
     ]
    }
   ],
   "source": [
    "#| caption: The same 24 films decision-trees used\n",
    "QUESTIONS = {\n",
    "    'star':   'Is there a star the audience turns up for?',\n",
    "    'summer': 'Did it open in summer?',\n",
    "    'sequel': 'Is it a sequel?',\n",
    "    'wide':   'Did it open on 3,000 screens or more?',\n",
    "    'budget': 'Did it cost over $100 million?',\n",
    "}\n",
    "KEYS = list(QUESTIONS)\n",
    "SHORT = {'star': 'A star?', 'summer': 'Opened in summer?', 'sequel': 'A sequel?',\n",
    "         'wide': '3,000+ screens?', 'budget': 'Over $100m?'}\n",
    "\n",
    "#                          star summer sequel wide budget  hit\n",
    "FILMS = {\n",
    "    'Harbour Lights':       (1,   1,     0,     0,   0,     1),\n",
    "    'Ironwake II':          (1,   1,     1,     1,   0,     1),\n",
    "    'The Quiet Ledger II':  (1,   0,     1,     0,   0,     1),\n",
    "    'Nightfall Divide':     (1,   1,     0,     1,   1,     1),\n",
    "    'Ironwake III':         (1,   0,     1,     1,   1,     1),\n",
    "    'Cinder Coast II':      (1,   0,     1,     1,   1,     1),\n",
    "    'Redline Returns':      (1,   0,     1,     1,   1,     1),\n",
    "    'Paper Kingdoms':       (1,   1,     0,     1,   0,     1),\n",
    "    'Glass Monsoon':        (1,   1,     0,     0,   1,     0),\n",
    "    'Cinder Coast III':     (1,   0,     1,     1,   0,     0),\n",
    "    'Vermilion Rising II':  (0,   0,     1,     1,   1,     1),\n",
    "    'Saltwater Sunday':     (0,   1,     0,     1,   1,     1),\n",
    "    'Field of Static II':   (0,   0,     1,     0,   0,     1),\n",
    "    'Wildflower County':    (0,   1,     0,     1,   0,     1),\n",
    "    'Tin Sky':              (0,   1,     0,     0,   0,     0),\n",
    "    'The Cartographer':     (0,   0,     0,     0,   0,     0),\n",
    "    'Neon Bazaar':          (0,   1,     0,     0,   1,     0),\n",
    "    'Ash & Ivory II':       (0,   0,     1,     1,   0,     0),\n",
    "    'Slow River':           (0,   0,     0,     0,   0,     0),\n",
    "    'The Understudy':       (0,   1,     0,     0,   0,     0),\n",
    "    'Meridian':             (0,   0,     0,     1,   1,     0),\n",
    "    'Copper Harbour':       (0,   1,     0,     1,   1,     0),\n",
    "    'The Winter Post':      (0,   0,     0,     0,   0,     0),\n",
    "    'Little Eden':          (0,   1,     0,     0,   1,     0),\n",
    "}\n",
    "ALL = list(FILMS)\n",
    "answers = lambda f: FILMS[f][:len(KEYS)]\n",
    "hit = lambda f: FILMS[f][-1]\n",
    "record('n_films', len(ALL))\n",
    "record('n_questions', len(KEYS))\n",
    "print(f'{len(ALL)} films, {sum(hit(f) for f in ALL)} of them hits')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bfe83f48",
   "metadata": {},
   "source": [
    "## 1. Gini, and the greedy rule, exactly as `decision-trees` left them\n",
    "\n",
    "Gini impurity is the chance that two films drawn from a pile disagree about\n",
    "being a hit. The gain of a question is the impurity it removes, weighted by how\n",
    "many films land on each side.\n",
    "\n",
    "The greedy rule: score every question, take the best one, then start again on\n",
    "each side with the questions that are left.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "003f9e2c",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-20T13:49:06.645370Z",
     "iopub.status.busy": "2026-08-20T13:49:06.645171Z",
     "iopub.status.idle": "2026-08-20T13:49:06.650622Z",
     "shell.execute_reply": "2026-08-20T13:49:06.649833Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "root_gini = 0.5\n",
      "Is there a star the audience turns up for? gain 0.129\n",
      "Is it a sequel?                            gain 0.093\n",
      "Did it open on 3,000 screens or more?      gain 0.087\n",
      "Did it cost over $100 million?             gain 0.003\n",
      "Did it open in summer?                     gain 0.000\n"
     ]
    }
   ],
   "source": [
    "#| caption: Impurity, gain, and the greedy rule\n",
    "def split(films, q):\n",
    "    i = KEYS.index(q)\n",
    "    return [f for f in films if answers(f)[i]], [f for f in films if not answers(f)[i]]\n",
    "\n",
    "def gini(films):\n",
    "    if not films:\n",
    "        return 0.0\n",
    "    p = sum(hit(f) for f in films) / len(films)\n",
    "    return 1 - p * p - (1 - p) ** 2\n",
    "\n",
    "def gain(films, q):\n",
    "    a, b = split(films, q)\n",
    "    return gini(films) - (len(a) * gini(a) + len(b) * gini(b)) / len(films)\n",
    "\n",
    "record('root_gini', round(gini(ALL), 3))\n",
    "for q in sorted(KEYS, key=lambda q: -gain(ALL, q)):\n",
    "    print(f'{QUESTIONS[q]:<42} gain {gain(ALL, q):.3f}')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "a5042881",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-20T13:49:06.652888Z",
     "iopub.status.busy": "2026-08-20T13:49:06.652586Z",
     "iopub.status.idle": "2026-08-20T13:49:06.674092Z",
     "shell.execute_reply": "2026-08-20T13:49:06.673616Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "greedy_question = Is there a star the audience turns up for?\n",
      "greedy_gain = 0.129\n",
      "greedy_right = 19\n",
      "greedy_gini = 0.319\n",
      "greedy_tree = {'q': 'A star?', 'note': '24 films - 12 hit', 'yes': {'q': '3,000+ screens?', 'note': '10 films - 8 hit', 'yes': {'leaf': 'hit', 'note': '7 films - 6 hit'}, 'no': {'leaf': 'hit', 'note': '3 films - 2 hit'}}, 'no': {'q': 'A sequel?', 'note': '14 films - 4 hit', 'yes': {'leaf': 'hit', 'note': '3 films - 2 hit'}, 'no': {'leaf': 'flop', 'note': '11 films - 2 hit'}}}\n",
      "greedy: Is there a star the audience turns up for? -> 19/24, total gini 0.3189\n"
     ]
    }
   ],
   "source": [
    "#| caption: The tree greedy builds, restricted to two questions\n",
    "greedy_root = max(KEYS, key=lambda q: gain(ALL, q))\n",
    "g_yes, g_no = split(ALL, greedy_root)\n",
    "greedy_l = max([q for q in KEYS if q != greedy_root], key=lambda q: gain(g_yes, q))\n",
    "greedy_r = max([q for q in KEYS if q != greedy_root], key=lambda q: gain(g_no, q))\n",
    "\n",
    "def leaves_of(root, ql, qr):\n",
    "    yes, no = split(ALL, root)\n",
    "    out = []\n",
    "    for side, q in ((yes, ql), (no, qr)):\n",
    "        if q is None:\n",
    "            out.append(side)\n",
    "        else:\n",
    "            a, b = split(side, q)\n",
    "            out += [a, b]\n",
    "    return out\n",
    "\n",
    "def right(films):\n",
    "    return max(sum(hit(f) for f in films), len(films) - sum(hit(f) for f in films))\n",
    "\n",
    "score = lambda root, ql, qr: sum(right(l) for l in leaves_of(root, ql, qr))\n",
    "total_gini = lambda root, ql, qr: sum(len(l) * gini(l) for l in leaves_of(root, ql, qr)) / len(ALL)\n",
    "\n",
    "def as_tree(root, ql, qr):\n",
    "    yes, no = split(ALL, root)\n",
    "    def side(films, q):\n",
    "        if q is None:\n",
    "            return leaf(films)\n",
    "        a, b = split(films, q)\n",
    "        return {'q': SHORT[q], 'note': f'{len(films)} films - {sum(hit(f) for f in films)} hit',\n",
    "                'yes': leaf(a), 'no': leaf(b)}\n",
    "    def leaf(films):\n",
    "        return {'leaf': 'hit' if sum(hit(f) for f in films) * 2 > len(films) else 'flop',\n",
    "                'note': f'{len(films)} films - {sum(hit(f) for f in films)} hit'}\n",
    "    return {'q': SHORT[root], 'note': f'{len(ALL)} films - {sum(hit(f) for f in ALL)} hit',\n",
    "            'yes': side(yes, ql), 'no': side(no, qr)}\n",
    "\n",
    "greedy_score = score(greedy_root, greedy_l, greedy_r)\n",
    "greedy_gini = total_gini(greedy_root, greedy_l, greedy_r)\n",
    "record('greedy_question', QUESTIONS[greedy_root])\n",
    "record('greedy_gain', round(gain(ALL, greedy_root), 3))\n",
    "record('greedy_right', greedy_score)\n",
    "record('greedy_gini', round(greedy_gini, 3))\n",
    "record('greedy_tree', as_tree(greedy_root, greedy_l, greedy_r))\n",
    "print(f'greedy: {QUESTIONS[greedy_root]} -> {greedy_score}/{len(ALL)}, total gini {greedy_gini:.4f}')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c3e6e4f2",
   "metadata": {},
   "source": [
    "## 2. Every tree it could have built instead\n",
    "\n",
    "A two-question tree is a root question, and then each side either stops or asks\n",
    "one more. Five roots, and five options on each side — stop, or one of the four\n",
    "remaining questions.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "41ce5aa8",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-20T13:49:06.676239Z",
     "iopub.status.busy": "2026-08-20T13:49:06.676045Z",
     "iopub.status.idle": "2026-08-20T13:49:06.683788Z",
     "shell.execute_reply": "2026-08-20T13:49:06.683566Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "n_trees = 125\n",
      "count_columns = ['', 'Choices']\n",
      "count_rows = [['The first question', '5'], ['On the yes side: stop, or one of the rest', '5'], ['On the no side: stop, or one of the rest', '5'], ['Trees in total', '5 x 5 x 5 = 125']]\n",
      "125 trees\n"
     ]
    }
   ],
   "source": [
    "#| caption: All 125 two-question trees, built and scored twice\n",
    "trees = []\n",
    "for root in KEYS:\n",
    "    others = [q for q in KEYS if q != root]\n",
    "    for ql in [None] + others:\n",
    "        for qr in [None] + others:\n",
    "            trees.append({'root': root, 'yes': ql, 'no': qr,\n",
    "                          'right': score(root, ql, qr), 'gini': total_gini(root, ql, qr)})\n",
    "\n",
    "record('n_trees', len(trees))\n",
    "record('count_columns', ['', 'Choices'])\n",
    "record('count_rows', [\n",
    "    ['The first question', f'{len(KEYS)}'],\n",
    "    ['On the yes side: stop, or one of the rest', f'{len(KEYS)}'],\n",
    "    ['On the no side: stop, or one of the rest', f'{len(KEYS)}'],\n",
    "    ['Trees in total', f'{len(KEYS)} x {len(KEYS)} x {len(KEYS)} = {len(trees)}'],\n",
    "])\n",
    "print(f'{len(trees)} trees')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "290c87ff",
   "metadata": {},
   "source": [
    "## 3. Ranking one: total impurity, the measure greedy used at every step\n",
    "\n",
    "Gini was computed at every split and never for the finished tree. So compute it\n",
    "now — the impurity left in all the leaves, weighted by size — and see where the\n",
    "greedy tree lands.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "6360f914",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-20T13:49:06.684938Z",
     "iopub.status.busy": "2026-08-20T13:49:06.684848Z",
     "iopub.status.idle": "2026-08-20T13:49:06.782489Z",
     "shell.execute_reply": "2026-08-20T13:49:06.782242Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "n_lower_gini = 16\n",
      "greedy_gini_rank = 17\n",
      "best_gini = 0.264\n",
      "best_gini_question = Did it open in summer?\n",
      "figure no-global-cost -> a-search-that-cannot-go-back.no-global-cost.{light,dark}.svg\n",
      "16 of 125 trees have a lower total gini than greedy's 0.3189\n"
     ]
    }
   ],
   "source": [
    "#| caption: Greedy's rank on the very measure it used\n",
    "by_gini = sorted(trees, key=lambda t: t['gini'])\n",
    "lower = [t for t in by_gini if t['gini'] < greedy_gini - 1e-9]\n",
    "best_g = by_gini[0]\n",
    "\n",
    "record('n_lower_gini', len(lower))\n",
    "record('greedy_gini_rank', len(lower) + 1)\n",
    "record('best_gini', round(best_g['gini'], 3))\n",
    "record('best_gini_question', QUESTIONS[best_g['root']])\n",
    "\n",
    "def plot_gini(ax):\n",
    "    vals = [t['gini'] for t in trees]\n",
    "    ax.hist(vals, bins=28, color='#c9c9d1')\n",
    "    ax.axvline(greedy_gini, color='#e2574c', lw=2.2)\n",
    "    ax.axvline(best_g['gini'], color='#2f9e6e', lw=2.2, ls='--')\n",
    "    ax.annotate(f\"greedy  {greedy_gini:.3f}\", (greedy_gini, ax.get_ylim()[1] * 0.92),\n",
    "                textcoords='offset points', xytext=(7, 0), fontsize=9, color='#e2574c')\n",
    "    ax.annotate(f\"best  {best_g['gini']:.3f}\", (best_g['gini'], ax.get_ylim()[1] * 0.72),\n",
    "                textcoords='offset points', xytext=(-8, 0), ha='right', fontsize=9, color='#2f9e6e')\n",
    "    ax.set_xlabel('Total impurity left in the finished tree (lower is better)')\n",
    "    ax.set_ylabel('Trees')\n",
    "    ax.grid(axis='x', visible=False)\n",
    "\n",
    "save_fig('no-global-cost', plot_gini, figsize=(7, 3.6))\n",
    "print(f\"{len(lower)} of {len(trees)} trees have a lower total gini than greedy's {greedy_gini:.4f}\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6cf6e554",
   "metadata": {},
   "source": [
    "## 4. Ranking two: films it gets right\n",
    "\n",
    "The other thing anybody would ask of a tree. Same 125 trees, scored on how many\n",
    "of the 24 films they classify correctly.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "12521dbc",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-20T13:49:06.783608Z",
     "iopub.status.busy": "2026-08-20T13:49:06.783517Z",
     "iopub.status.idle": "2026-08-20T13:49:06.847017Z",
     "shell.execute_reply": "2026-08-20T13:49:06.846795Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "n_better = 1\n",
      "best_right = 20\n",
      "best_question = Did it open in summer?\n",
      "best_gain_of_root = 0.000\n",
      "best_tree = {'q': 'Opened in summer?', 'note': '24 films - 12 hit', 'yes': {'q': '3,000+ screens?', 'note': '12 films - 6 hit', 'yes': {'leaf': 'hit', 'note': '6 films - 5 hit'}, 'no': {'leaf': 'flop', 'note': '6 films - 1 hit'}}, 'no': {'q': 'A sequel?', 'note': '12 films - 6 hit', 'yes': {'leaf': 'hit', 'note': '8 films - 6 hit'}, 'no': {'leaf': 'flop', 'note': '4 films - 0 hit'}}}\n",
      "compare_columns = ['', 'First question', 'Films right', 'Total impurity']\n",
      "compare_rows = [['The tree greedy builds', 'Is there a star the audience turns up for?', '19 of 24', '0.319'], ['The best two-question tree', 'Did it open in summer?', '20 of 24', '0.264']]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "figure greedy-against-every-tree -> a-search-that-cannot-go-back.greedy-against-every-tree.{light,dark}.svg\n",
      "greedy 19/24; best 20/24; 1 tree(s) beat greedy\n",
      "best tree's first question: Did it open in summer? — gain 0.000\n"
     ]
    }
   ],
   "source": [
    "#| caption: Greedy against every tree, on films it gets right\n",
    "best_r = max(trees, key=lambda t: t['right'])\n",
    "better = [t for t in trees if t['right'] > greedy_score]\n",
    "\n",
    "record('n_better', len(better))\n",
    "record('best_right', best_r['right'])\n",
    "record('best_question', QUESTIONS[best_r['root']])\n",
    "record('best_gain_of_root', f\"{gain(ALL, best_r['root']):.3f}\")\n",
    "record('best_tree', as_tree(best_r['root'], best_r['yes'], best_r['no']))\n",
    "\n",
    "record('compare_columns', ['', 'First question', 'Films right', 'Total impurity'])\n",
    "record('compare_rows', [\n",
    "    ['The tree greedy builds', QUESTIONS[greedy_root], f'{greedy_score} of {len(ALL)}', f'{greedy_gini:.3f}'],\n",
    "    ['The best two-question tree', QUESTIONS[best_r['root']], f\"{best_r['right']} of {len(ALL)}\", f\"{best_r['gini']:.3f}\"],\n",
    "])\n",
    "\n",
    "def plot_right(ax):\n",
    "    vals = sorted({t['right'] for t in trees}, reverse=True)\n",
    "    counts = [sum(1 for t in trees if t['right'] == v) for v in vals]\n",
    "    colors = ['#2f9e6e' if v == best_r['right'] else '#e2574c' if v == greedy_score else '#c9c9d1'\n",
    "              for v in vals]\n",
    "    ax.bar([str(v) for v in vals], counts, color=colors)\n",
    "    for i, (v, c) in enumerate(zip(vals, counts)):\n",
    "        if v in (best_r['right'], greedy_score):\n",
    "            ax.text(i, c + 1.2, 'best' if v == best_r['right'] else 'greedy', ha='center',\n",
    "                    fontsize=9, color='#2f9e6e' if v == best_r['right'] else '#e2574c')\n",
    "    ax.set_xlabel(f'Films right, out of {len(ALL)}')\n",
    "    ax.set_ylabel('Trees')\n",
    "    ax.grid(axis='x', visible=False)\n",
    "\n",
    "save_fig('greedy-against-every-tree', plot_right, figsize=(7, 3.6))\n",
    "print(f\"greedy {greedy_score}/{len(ALL)}; best {best_r['right']}/{len(ALL)}; \"\n",
    "      f\"{len(better)} tree(s) beat greedy\")\n",
    "print(f\"best tree's first question: {QUESTIONS[best_r['root']]} — gain {gain(ALL, best_r['root']):.3f}\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "616f90e3",
   "metadata": {},
   "source": [
    "## What this notebook establishes\n",
    "\n",
    "- Greedy's finished tree is **not** the lowest-impurity tree available, on the\n",
    "  very measure it consulted at every split. Nothing ever scored the whole tree.\n",
    "- Exactly one of the 125 gets more films right, and its first question is the\n",
    "  one with a gain of **0.000** — the split `decision-trees` held up as the worst\n",
    "  question in the table.\n",
    "- Taking the best step is not the same as taking the best path.\n",
    "\n",
    "**Worth changing:** allow three questions instead of two and the count goes past\n",
    "what this loop can enumerate quickly, which is the reason greedy exists at all.\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.13.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}