{ "cells": [ { "cell_type": "markdown", "id": "aef1baec", "metadata": {}, "source": [ "# Decision Trees · Growing it, and knowing when to stop\n", "\n", "One question has been chosen. That leaves two smaller piles, and the honest\n", "next move is the one lesson 1 already described: **start over on each side.**\n", "\n", "Two things happen when you actually do that, and neither is obvious from the\n", "first split.\n", "\n", "The first is that **a different question wins on the smaller pile.** The second\n", "is that, left alone, the tree does not stop until it has filed every film in a\n", "box of its own — which looks like a perfect model and is nothing of the kind." ] }, { "cell_type": "code", "execution_count": 1, "id": "d2da27d3", "metadata": { "execution": { "iopub.execute_input": "2026-08-19T12:42:29.622633Z", "iopub.status.busy": "2026-08-19T12:42:29.622530Z", "iopub.status.idle": "2026-08-19T12:42:29.943496Z", "shell.execute_reply": "2026-08-19T12:42:29.942705Z" } }, "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" ] }, { "cell_type": "markdown", "id": "0c59fa70", "metadata": {}, "source": [ "## 1. The same table, the same five questions\n", "\n", "Nothing new here. The films from *Which question to ask first*, and the gini and\n", "gain from the two lessons before it, so this notebook stands on its own." ] }, { "cell_type": "code", "execution_count": 2, "id": "ec18ffcb", "metadata": { "execution": { "iopub.execute_input": "2026-08-19T12:42:29.946368Z", "iopub.status.busy": "2026-08-19T12:42:29.946102Z", "iopub.status.idle": "2026-08-19T12:42:29.950913Z", "shell.execute_reply": "2026-08-19T12:42:29.950525Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "24 films, 12 hits, impurity 0.50\n" ] } ], "source": [ "#| caption: The same twenty-four films, and the two measures from the last three lessons\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", "SHORT = {\"star\": \"A star?\", \"summer\": \"Summer?\", \"sequel\": \"A sequel?\",\n", " \"wide\": \"3,000+ screens?\", \"budget\": \"Over $100m?\"}\n", "KEYS = list(QUESTIONS)\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", "\n", "def answers(f): return FILMS[f][:len(KEYS)]\n", "def hit(f): return FILMS[f][-1]\n", "\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) * (1 - p)\n", "\n", "def gain(films, q):\n", " yes, no = split(films, q)\n", " if not yes or not no:\n", " return 0.0\n", " return gini(films) - (len(yes) * gini(yes) + len(no) * gini(no)) / len(films)\n", "\n", "print(f\"{len(ALL)} films, {sum(hit(f) for f in ALL)} hits, impurity {gini(ALL):.2f}\")" ] }, { "cell_type": "markdown", "id": "8237892b", "metadata": {}, "source": [ "## 2. The two sides disagree about what to ask next\n", "\n", "*Is there a star?* was the best opening question. It leaves ten films on one\n", "side and fourteen on the other, and the obvious thing to do is score all five\n", "questions again — separately — on each.\n", "\n", "Do that and the ranking **flips**. On the fourteen without a star, *is it a\n", "sequel?* is the better question. On the ten with a star, it is *did it open on\n", "3,000 screens?* Same five questions, same table, opposite answers.\n", "\n", "**That is why a tree is not a ranked list of features.** A question's worth\n", "depends entirely on which films are still standing in front of it, and a tree\n", "re-asks that at every single node. A ranked list can only answer it once.\n" ] }, { "cell_type": "code", "execution_count": 3, "id": "d862fea3", "metadata": { "execution": { "iopub.execute_input": "2026-08-19T12:42:29.953095Z", "iopub.status.busy": "2026-08-19T12:42:29.952799Z", "iopub.status.idle": "2026-08-19T12:42:30.063269Z", "shell.execute_reply": "2026-08-19T12:42:30.062963Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "question all 24 the 10 with a star the 14 without\n", "A star? 0.129 0.000 0.000\n", "Summer? 0.000 0.000 0.000\n", "A sequel? 0.093 0.003 0.079\n", "3,000+ screens? 0.087 0.015 0.069\n", "Over $100m? 0.003 0.000 0.003\n", "n_star_films = 10\n", "star_hits = 8\n", "n_no_star = 14\n", "no_star_hits = 4\n", "best_on_star = Did it open on 3,000 screens or more?\n", "best_on_no_star = Is it a sequel?\n", "sequel_on_star = 0.003\n", "wide_on_star = 0.015\n", "sequel_on_no_star = 0.079\n", "wide_on_no_star = 0.069\n", "star_gain_below_itself = 0.0\n", "figure a-different-question-wins -> growing-the-tree.a-different-question-wins.{light,dark}.svg\n" ] } ], "source": [ "#| caption: All five questions, scored separately on each side of the first split\n", "star_films, no_star = split(ALL, \"star\")\n", "\n", "print(f\"{'question':<18} {'all 24':>8} {'the 10 with a star':>20} {'the 14 without':>16}\")\n", "for q in KEYS:\n", " print(f\"{SHORT[q]:<18} {gain(ALL, q):>8.3f} {gain(star_films, q):>20.3f} {gain(no_star, q):>16.3f}\")\n", "\n", "best_star = max(KEYS, key=lambda q: (gain(star_films, q), q))\n", "best_no_star = max(KEYS, key=lambda q: (gain(no_star, q), q))\n", "record(\"n_star_films\", len(star_films))\n", "record(\"star_hits\", sum(hit(f) for f in star_films))\n", "record(\"n_no_star\", len(no_star))\n", "record(\"no_star_hits\", sum(hit(f) for f in no_star))\n", "record(\"best_on_star\", QUESTIONS[best_star])\n", "record(\"best_on_no_star\", QUESTIONS[best_no_star])\n", "record(\"sequel_on_star\", round(gain(star_films, \"sequel\"), 3))\n", "record(\"wide_on_star\", round(gain(star_films, \"wide\"), 3))\n", "record(\"sequel_on_no_star\", round(gain(no_star, \"sequel\"), 3))\n", "record(\"wide_on_no_star\", round(gain(no_star, \"wide\"), 3))\n", "# A question already asked is worth exactly nothing below itself. The tree is\n", "# never told this; it falls out of the arithmetic, because one side is empty.\n", "record(\"star_gain_below_itself\", round(gain(star_films, \"star\"), 3))\n", "\n", "def plot(ax):\n", " xs = range(len(KEYS))\n", " ax.bar([x - 0.25 for x in xs], [gain(ALL, q) for q in KEYS], width=0.24,\n", " color=\"#9aa0aa\", label=\"all 24 films\")\n", " ax.bar([x for x in xs], [gain(star_films, q) for q in KEYS], width=0.24,\n", " color=\"#e2574c\", label=\"the 10 with a star\")\n", " ax.bar([x + 0.25 for x in xs], [gain(no_star, q) for q in KEYS], width=0.24,\n", " color=\"#3b6fd4\", label=\"the 14 without\")\n", " ax.set_xticks(list(xs))\n", " ax.set_xticklabels([SHORT[q] for q in KEYS], fontsize=9)\n", " ax.set_ylabel(\"Impurity removed\")\n", " ax.legend(frameon=False, fontsize=9)\n", " ax.grid(axis=\"x\", visible=False)\n", "\n", "save_fig(\"a-different-question-wins\", plot, figsize=(7, 3.8))" ] }, { "cell_type": "markdown", "id": "cb16d2ef", "metadata": {}, "source": [ "## 3. Growing the whole thing\n", "\n", "The algorithm is lesson 1's, with lesson 4's scoring dropped in: pick the\n", "question with the most gain, split, repeat on each side.\n", "\n", "Left alone it stops only when it has to — when a pile agrees with itself, or\n", "when no question separates it any further." ] }, { "cell_type": "code", "execution_count": 4, "id": "d55b3da6", "metadata": { "execution": { "iopub.execute_input": "2026-08-19T12:42:30.064904Z", "iopub.status.busy": "2026-08-19T12:42:30.064802Z", "iopub.status.idle": "2026-08-19T12:42:30.072280Z", "shell.execute_reply": "2026-08-19T12:42:30.071608Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "full_depth = 5\n", "full_leaves = 12\n", "full_singletons = 7\n", "full_right = 23\n", "full_total = 24\n", "depth 5, 12 leaves, 7 of them holding a single film\n", "gets 23 of 24 right — on the very films it was built from\n" ] } ], "source": [ "#| caption: The tree, grown until it cannot grow any more\n", "def build(films, min_leaf=1, max_depth=None, depth=0):\n", " call = \"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", " stop = (gini(films) == 0\n", " or (max_depth is not None and depth >= max_depth)\n", " or len(films) < 2 * min_leaf)\n", " if not stop:\n", " usable = [q for q in KEYS\n", " if all(len(side) >= min_leaf for side in split(films, q)) and gain(films, q) > 0]\n", " if usable:\n", " best = max(usable, key=lambda q: (gain(films, q), q))\n", " yes, no = split(films, best)\n", " return {\"q\": SHORT[best], \"note\": note,\n", " \"yes\": build(yes, min_leaf, max_depth, depth + 1),\n", " \"no\": build(no, min_leaf, max_depth, depth + 1)}\n", " return {\"leaf\": call, \"note\": note}\n", "\n", "def leaves(node):\n", " return [node] if \"leaf\" in node else leaves(node[\"yes\"]) + leaves(node[\"no\"])\n", "\n", "def depth_of(node):\n", " return 0 if \"leaf\" in node else 1 + max(depth_of(node[\"yes\"]), depth_of(node[\"no\"]))\n", "\n", "def predict(node, f):\n", " while \"leaf\" not in node:\n", " i = KEYS.index(next(k for k in KEYS if SHORT[k] == node[\"q\"]))\n", " node = node[\"yes\"] if answers(f)[i] else node[\"no\"]\n", " return node[\"leaf\"]\n", "\n", "def score(node):\n", " right = sum(1 for f in ALL if (predict(node, f) == \"hit\") == bool(hit(f)))\n", " return right, len(ALL)\n", "\n", "FULL = build(ALL)\n", "right, total = score(FULL)\n", "record(\"full_depth\", depth_of(FULL))\n", "record(\"full_leaves\", len(leaves(FULL)))\n", "record(\"full_singletons\", sum(1 for l in leaves(FULL) if l[\"note\"].startswith(\"1 films\")))\n", "record(\"full_right\", right)\n", "record(\"full_total\", total)\n", "print(f\"depth {depth_of(FULL)}, {len(leaves(FULL))} leaves, \"\n", " f\"{sum(1 for l in leaves(FULL) if l['note'].startswith('1 films'))} of them holding a single film\")\n", "print(f\"gets {right} of {total} right — on the very films it was built from\")" ] }, { "cell_type": "markdown", "id": "a49edd70", "metadata": {}, "source": [ "## 4. The one it cannot get right\n", "\n", "Twenty-three of twenty-four, on the films it was built from. The one it misses\n", "is the pair from *Which question to ask first* — identical on all five\n", "questions, opposite outcomes. They land in the same leaf and the leaf has to\n", "call one way.\n", "\n", "**A tree cannot be more certain than its questions allow.** No amount of growing\n", "fixes that leaf, and a tree that kept trying would be inventing a distinction\n", "the table does not contain.\n" ] }, { "cell_type": "code", "execution_count": 5, "id": "c1ee45d1", "metadata": { "execution": { "iopub.execute_input": "2026-08-19T12:42:30.074352Z", "iopub.status.busy": "2026-08-19T12:42:30.074197Z", "iopub.status.idle": "2026-08-19T12:42:30.079124Z", "shell.execute_reply": "2026-08-19T12:42:30.078872Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "leaf calls 'hit' holding Saltwater Sunday, Copper Harbour\n", "n_mixed_leaves = 1\n", "full_wrong = 1\n", "stuck_films = ['Copper Harbour', 'Saltwater Sunday']\n" ] }, { "data": { "text/plain": [ "['Copper Harbour', 'Saltwater Sunday']" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "#| caption: Which leaves still hold a mixture, and what they had to call\n", "def leaf_counts(node, films=None):\n", " \"\"\"Walk the tree with the films, so a leaf's contents are read not parsed.\"\"\"\n", " if films is None:\n", " films = ALL\n", " if \"leaf\" in node:\n", " return [(node, films)]\n", " q = next(k for k in KEYS if SHORT[k] == node[\"q\"])\n", " yes, no = split(films, q)\n", " return leaf_counts(node[\"yes\"], yes) + leaf_counts(node[\"no\"], no)\n", "\n", "mixed = [(l, fs) for l, fs in leaf_counts(FULL) if 0 < sum(hit(f) for f in fs) < len(fs)]\n", "for l, fs in mixed:\n", " print(f\"leaf calls '{l['leaf']}' holding {', '.join(fs)}\")\n", "\n", "record(\"n_mixed_leaves\", len(mixed))\n", "record(\"full_wrong\", total - right)\n", "record(\"stuck_films\", sorted(f for _, fs in mixed for f in fs))" ] }, { "cell_type": "markdown", "id": "69ce9dae", "metadata": {}, "source": [ "## 5. Making it stop\n", "\n", "The fix is not cleverness, it is a floor: **refuse to make a leaf smaller than\n", "n films.** Sweep that floor from 1 upwards and watch two things move in opposite\n", "directions — the tree gets smaller and more readable, and it gets more of the\n", "twenty-four wrong.\n", "\n", "That trade is the whole of the next lesson. Here it is only worth seeing that\n", "the trade exists, and that the score on the films it was built from goes **down**\n", "every time the tree is made more sensible." ] }, { "cell_type": "code", "execution_count": 6, "id": "550cb4f5", "metadata": { "execution": { "iopub.execute_input": "2026-08-19T12:42:30.080313Z", "iopub.status.busy": "2026-08-19T12:42:30.080233Z", "iopub.status.idle": "2026-08-19T12:42:30.149749Z", "shell.execute_reply": "2026-08-19T12:42:30.149533Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " min films in a leaf depth leaves right of 24\n", " 1 5 12 23\n", " 2 3 6 19\n", " 3 3 6 19\n", " 4 3 5 18\n", " 5 2 3 18\n", " 6 2 3 18\n", "sweep = [{'min_leaf': 1, 'depth': 5, 'leaves': 12, 'right': 23}, {'min_leaf': 2, 'depth': 3, 'leaves': 6, 'right': 19}, {'min_leaf': 3, 'depth': 3, 'leaves': 6, 'right': 19}, {'min_leaf': 4, 'depth': 3, 'leaves': 5, 'right': 18}, {'min_leaf': 5, 'depth': 2, 'leaves': 3, 'right': 18}, {'min_leaf': 6, 'depth': 2, 'leaves': 3, 'right': 18}]\n", "readable_min_leaf = 3\n", "readable_leaves = 6\n", "readable_depth = 3\n", "readable_right = 19\n", "readable_tree = {'q': 'A star?', 'note': '24 films - 12 hit', 'yes': {'q': '3,000+ screens?', 'note': '10 films - 8 hit', 'yes': {'q': 'Over $100m?', 'note': '7 films - 6 hit', 'yes': {'leaf': 'hit', 'note': '4 films - 4 hit'}, 'no': {'leaf': 'hit', 'note': '3 films - 2 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': {'q': '3,000+ screens?', 'note': '11 films - 2 hit', 'yes': {'leaf': 'hit', 'note': '4 films - 2 hit'}, 'no': {'leaf': 'flop', 'note': '7 films - 0 hit'}}}}\n", "figure shrinking-the-tree -> growing-the-tree.shrinking-the-tree.{light,dark}.svg\n" ] } ], "source": [ "#| caption: A floor under leaf size — the tree shrinks, and the score falls\n", "print(f\"{'min films in a leaf':>20} {'depth':>6} {'leaves':>7} {'right of 24':>12}\")\n", "sweep = []\n", "for m in range(1, 7):\n", " t = build(ALL, min_leaf=m)\n", " r, _ = score(t)\n", " sweep.append((m, depth_of(t), len(leaves(t)), r))\n", " print(f\"{m:>20} {depth_of(t):>6} {len(leaves(t)):>7} {r:>12}\")\n", "\n", "record(\"sweep\", [{\"min_leaf\": m, \"depth\": d, \"leaves\": lv, \"right\": r} for m, d, lv, r in sweep])\n", "record(\"readable_min_leaf\", 3)\n", "READABLE = build(ALL, min_leaf=3)\n", "record(\"readable_leaves\", len(leaves(READABLE)))\n", "record(\"readable_depth\", depth_of(READABLE))\n", "record(\"readable_right\", score(READABLE)[0])\n", "record(\"readable_tree\", READABLE)\n", "\n", "def plot2(ax):\n", " ms = [m for m, *_ in sweep]\n", " ax.plot(ms, [lv for *_, lv, _ in sweep], marker=\"o\", ms=5, color=\"#9aa0aa\", label=\"leaves in the tree\")\n", " ax.plot(ms, [r for *_, r in sweep], marker=\"o\", ms=5, color=\"#e2574c\", label=\"films called right, of 24\")\n", " ax.set_xlabel(\"Fewest films allowed in a leaf\")\n", " ax.set_ylim(0, 26)\n", " ax.legend(frameon=False, fontsize=9)\n", "\n", "save_fig(\"shrinking-the-tree\", plot2, figsize=(7, 3.6))" ] }, { "cell_type": "markdown", "id": "d0f8923f", "metadata": {}, "source": [ "## Try this\n", "\n", "1. **Cap the depth instead.** `build(ALL, max_depth=2)` limits how many questions\n", " deep the tree can go rather than how small a leaf can be. Compare the two\n", " kinds of floor at the same number of leaves — do they choose the same tree?\n", "2. **Grow it on nineteen films** picked at random, then score it on the five you\n", " held back. Do it a few times. The spread in that second number is the whole\n", " subject of the next lesson.\n", "3. **Remove the star question entirely** and grow it again. The tree is worse,\n", " but by how much — and which question steps up to replace it?" ] } ], "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 }