{ "cells": [ { "cell_type": "markdown", "id": "c41837d0", "metadata": {}, "source": [ "# Decision Trees · Which question to ask first\n", "\n", "Sixteen animals could be told apart perfectly, so the only thing that mattered\n", "was speed: ask the question that halves the field.\n", "\n", "Twenty-four films cannot. Two of them answer every question we are allowed to\n", "ask in exactly the same way, and one was a hit and one was a flop. No question\n", "separates them, because there is nothing left to ask.\n", "\n", "**So \"which split is most even\" stops being the right question, and something\n", "has to replace it.** This notebook is that replacement, computed on numbers\n", "small enough to add up by hand." ] }, { "cell_type": "code", "execution_count": 1, "id": "f194164c", "metadata": { "execution": { "iopub.execute_input": "2026-08-19T12:22:30.700036Z", "iopub.status.busy": "2026-08-19T12:22:30.699942Z", "iopub.status.idle": "2026-08-19T12:22:31.036942Z", "shell.execute_reply": "2026-08-19T12:22:31.036571Z" } }, "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": "dacaed70", "metadata": {}, "source": [ "## 1. Twenty-four films\n", "\n", "**This table is constructed, not sourced.** Twenty-four rows and five questions\n", "is a size a reader can total in their head — and being able to check the counts\n", "yourself is the entire reason for the next three cells. No real box-office\n", "dataset is small enough to do that with, and a number you cannot check is a\n", "number you are trusting rather than reading.\n", "\n", "Twelve hits, twelve flops. Everything below starts from that even split." ] }, { "cell_type": "code", "execution_count": 2, "id": "704a129c", "metadata": { "execution": { "iopub.execute_input": "2026-08-19T12:22:31.038416Z", "iopub.status.busy": "2026-08-19T12:22:31.038279Z", "iopub.status.idle": "2026-08-19T12:22:31.045171Z", "shell.execute_reply": "2026-08-19T12:22:31.044931Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "n_films = 24\n", "n_hits = 12\n", "twin_hit = Saltwater Sunday\n", "twin_flop = Copper Harbour\n", "twin_columns = ['', 'Saltwater Sunday', 'Copper Harbour']\n", "twin_rows = [['Is there a star the audience turns up for?', 'no', 'no'], ['Did it open in summer?', 'yes', 'yes'], ['Is it a sequel?', 'no', 'no'], ['Did it open on 3,000 screens or more?', 'yes', 'yes'], ['Did it cost over $100 million?', 'yes', 'yes'], ['Result', 'hit', 'flop']]\n", "['Saltwater Sunday', 'Copper Harbour'] answer identically: {'star': 0, 'summer': 1, 'sequel': 0, 'wide': 1, 'budget': 1}\n" ] } ], "source": [ "#| caption: Twenty-four films, five questions, and whether each one was a hit\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", "\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", "\n", "def answers(name):\n", " return FILMS[name][:len(KEYS)]\n", "\n", "def hit(name):\n", " return FILMS[name][-1]\n", "\n", "ALL = list(FILMS)\n", "record(\"n_films\", len(ALL))\n", "record(\"n_hits\", sum(hit(f) for f in ALL))\n", "\n", "# The pair the whole lesson turns on: same answers, opposite outcomes.\n", "same = {}\n", "for f in ALL:\n", " same.setdefault(answers(f), []).append(f)\n", "twins = [g for g in same.values() if len(g) > 1 and len({hit(f) for f in g}) > 1][0]\n", "def row(name):\n", " return [name] + [\"yes\" if a else \"no\" for a in answers(name)] + [\"hit\" if hit(name) else \"flop\"]\n", "\n", "record(\"twin_hit\", next(f for f in twins if hit(f)))\n", "record(\"twin_flop\", next(f for f in twins if not hit(f)))\n", "# Transposed — questions down the side, the two films across. Seven columns of\n", "# yes/no is unreadable projected (tests/present-fits.test.ts caps a slide at\n", "# six), and this way the two answer columns sit next to each other, which is\n", "# the entire thing the table is there to show.\n", "pair = sorted(twins, key=lambda f: -hit(f))\n", "record(\"twin_columns\", [\"\"] + pair)\n", "record(\"twin_rows\",\n", " [[QUESTIONS[q]] + [\"yes\" if answers(f)[i] else \"no\" for f in pair]\n", " for i, q in enumerate(KEYS)]\n", " + [[\"Result\"] + [\"hit\" if hit(f) else \"flop\" for f in pair]])\n", "print(twins, \"answer identically:\", dict(zip(KEYS, answers(twins[0]))))" ] }, { "cell_type": "markdown", "id": "226877d2", "metadata": {}, "source": [ "## 2. The rule from lesson 1, and where it breaks\n", "\n", "*Ask the question that splits the field most evenly.* Applied here, the winner\n", "is **did it open in summer** — twelve films one way, twelve the other, a\n", "perfect halving.\n", "\n", "And it is worthless. Six of the summer films were hits and six flopped; six of\n", "the rest were hits and six flopped. You have cut the pile exactly in two and\n", "learned nothing whatsoever about which ones made money." ] }, { "cell_type": "code", "execution_count": 3, "id": "a68f4708", "metadata": { "execution": { "iopub.execute_input": "2026-08-19T12:22:31.046249Z", "iopub.status.busy": "2026-08-19T12:22:31.046171Z", "iopub.status.idle": "2026-08-19T12:22:31.050355Z", "shell.execute_reply": "2026-08-19T12:22:31.050093Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "question yes no hits on the yes side hits on the no side\n", "star 10 14 8 of 10 4 of 14 \n", "summer 12 12 6 of 12 6 of 12 \n", "sequel 9 15 7 of 9 5 of 15 \n", "wide 13 11 9 of 13 3 of 11 \n", "budget 11 13 6 of 11 6 of 13 \n", "even_question = Did it open in summer?\n", "even_yes_hits = 6\n", "even_yes_n = 12\n" ] }, { "data": { "text/plain": [ "12" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "#| caption: Every question, by how evenly it splits — and by what each side then agrees on\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", "print(f\"{'question':<9} {'yes':>3} {'no':>3} {'hits on the yes side':>22} {'hits on the no side':>21}\")\n", "for q in KEYS:\n", " yes, no = split(ALL, q)\n", " print(f\"{q:<9} {len(yes):>3} {len(no):>3} \"\n", " f\"{sum(hit(f) for f in yes):>10} of {len(yes):<9} {sum(hit(f) for f in no):>9} of {len(no):<9}\")\n", "\n", "evenest = min(KEYS, key=lambda q: abs(len(split(ALL, q)[0]) - len(split(ALL, q)[1])))\n", "ey, en = split(ALL, evenest)\n", "record(\"even_question\", QUESTIONS[evenest])\n", "record(\"even_yes_hits\", sum(hit(f) for f in ey))\n", "record(\"even_yes_n\", len(ey))" ] }, { "cell_type": "markdown", "id": "68548743", "metadata": {}, "source": [ "## 3. The number for how mixed a pile is\n", "\n", "The previous two lessons built this from scratch on ten deals. The short\n", "version: **Gini impurity is the chance that two films pulled out of a pile at\n", "random disagree about the outcome** — 0 when they never do, 0.5 when it is a\n", "coin flip.\n", "\n", "Twenty-four films at twelve and twelve is the worst it can be.\n" ] }, { "cell_type": "code", "execution_count": 4, "id": "f3cf236d", "metadata": { "execution": { "iopub.execute_input": "2026-08-19T12:22:31.051717Z", "iopub.status.busy": "2026-08-19T12:22:31.051635Z", "iopub.status.idle": "2026-08-19T12:22:31.055382Z", "shell.execute_reply": "2026-08-19T12:22:31.054855Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "root_gini = 0.5\n", "all 24 films 0.500 (12 hits, 12 flops — as bad as it gets)\n", "the 10 with a star 0.320 (8 hits, 2 flops)\n", "the 14 without 0.408 (4 hits, 10 flops)\n" ] } ], "source": [ "#| caption: The pile before any question is asked, and the two piles one question makes\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", "root = record(\"root_gini\", round(gini(ALL), 3))\n", "print(f\"all 24 films {gini(ALL):.3f} (12 hits, 12 flops — as bad as it gets)\")\n", "yes, no = split(ALL, \"star\")\n", "print(f\"the 10 with a star {gini(yes):.3f} ({sum(hit(f) for f in yes)} hits, {len(yes) - sum(hit(f) for f in yes)} flops)\")\n", "print(f\"the 14 without {gini(no):.3f} ({sum(hit(f) for f in no)} hits, {len(no) - sum(hit(f) for f in no)} flops)\")" ] }, { "cell_type": "markdown", "id": "b88d6499", "metadata": {}, "source": [ "## 4. Gain: what a question is worth\n", "\n", "A question takes one pile and makes two. So score it by subtraction:\n", "\n", "> **gain = the impurity you started with − the impurity you are left with**\n", "\n", "with the two sides weighted by how many films landed on each, because a very\n", "pure side holding two films is worth less than a fairly pure side holding\n", "fourteen.\n", "\n", "That is information gain. It is the whole of how a decision tree chooses, and\n", "there is nothing else in it." ] }, { "cell_type": "code", "execution_count": 5, "id": "329ffa4e", "metadata": { "execution": { "iopub.execute_input": "2026-08-19T12:22:31.056669Z", "iopub.status.busy": "2026-08-19T12:22:31.056563Z", "iopub.status.idle": "2026-08-19T12:22:31.130104Z", "shell.execute_reply": "2026-08-19T12:22:31.129811Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Is there a star the audience turns up for? 0.500 -> 0.371 gain 0.129\n", "Is it a sequel? 0.500 -> 0.407 gain 0.093\n", "Did it open on 3,000 screens or more? 0.500 -> 0.413 gain 0.087\n", "Did it cost over $100 million? 0.500 -> 0.497 gain 0.003\n", "Did it open in summer? 0.500 -> 0.500 gain 0.000\n", "best_question = Is there a star the audience turns up for?\n", "best_gain = 0.129\n", "best_yes_hits = 8\n", "best_yes_n = 10\n", "best_no_hits = 4\n", "best_no_n = 14\n", "even_gain = 0.0\n", "budget_gain = 0.003\n", "question_columns = ['Question', 'Splits into', 'Hits on the yes side', 'Hits on the no side']\n", "question_rows = [['Is there a star the audience turns up for?', '10 / 14', '8 of 10', '4 of 14'], ['Is it a sequel?', '9 / 15', '7 of 9', '5 of 15'], ['Did it open on 3,000 screens or more?', '13 / 11', '9 of 13', '3 of 11'], ['Did it cost over $100 million?', '11 / 13', '6 of 11', '6 of 13'], ['Did it open in summer?', '12 / 12', '6 of 12', '6 of 12']]\n", "figure gain-by-question -> which-question-first.gain-by-question.{light,dark}.svg\n" ] } ], "source": [ "#| caption: Every question scored by what it actually buys\n", "def gain(films, q):\n", " yes, no = split(films, q)\n", " after = (len(yes) * gini(yes) + len(no) * gini(no)) / len(films)\n", " return gini(films) - after\n", "\n", "scores = sorted(((gain(ALL, q), q) for q in KEYS), reverse=True)\n", "for g, q in scores:\n", " yes, no = split(ALL, q)\n", " print(f\"{QUESTIONS[q]:<42} {gini(ALL):.3f} -> \"\n", " f\"{(len(yes) * gini(yes) + len(no) * gini(no)) / len(ALL):.3f} gain {g:.3f}\")\n", "\n", "best_gain, best_q = scores[0]\n", "record(\"best_question\", QUESTIONS[best_q])\n", "record(\"best_gain\", round(best_gain, 3))\n", "record(\"best_yes_hits\", sum(hit(f) for f in split(ALL, best_q)[0]))\n", "record(\"best_yes_n\", len(split(ALL, best_q)[0]))\n", "record(\"best_no_hits\", sum(hit(f) for f in split(ALL, best_q)[1]))\n", "record(\"best_no_n\", len(split(ALL, best_q)[1]))\n", "record(\"even_gain\", round(gain(ALL, evenest), 3))\n", "record(\"budget_gain\", round(gain(ALL, \"budget\"), 3))\n", "\n", "# The table the lesson prints, in the order it prints it. Recorded rather than\n", "# retyped into the lesson: five rows of counts is exactly the sort of thing\n", "# that goes stale silently when a film is edited.\n", "record(\"question_columns\", [\"Question\", \"Splits into\", \"Hits on the yes side\", \"Hits on the no side\"])\n", "record(\"question_rows\", [\n", " [QUESTIONS[q],\n", " f\"{len(split(ALL, q)[0])} / {len(split(ALL, q)[1])}\",\n", " f\"{sum(hit(f) for f in split(ALL, q)[0])} of {len(split(ALL, q)[0])}\",\n", " f\"{sum(hit(f) for f in split(ALL, q)[1])} of {len(split(ALL, q)[1])}\"]\n", " for _, q in scores\n", "])\n", "\n", "\n", "def plot2(ax):\n", " labels = [QUESTIONS[q].rstrip(\"?\") for _, q in scores][::-1]\n", " vals = [g for g, _ in scores][::-1]\n", " colors = [\"#e2574c\" if v == max(vals) else \"#9aa0aa\" for v in vals]\n", " ax.barh(labels, vals, color=colors)\n", " for y, (v, q) in enumerate(zip(vals, [q for _, q in scores][::-1])):\n", " yes, no = split(ALL, q)\n", " ax.text(v + 0.003, y, f\"{len(yes)} / {len(no)} films\", va=\"center\", fontsize=9, color=\"#77777f\")\n", " ax.set_xlabel(\"Impurity removed (gain)\")\n", " ax.set_xlim(0, max(vals) * 1.55)\n", " ax.grid(axis=\"y\", visible=False)\n", "\n", "save_fig(\"gain-by-question\", plot2, figsize=(7, 3.9))" ] }, { "cell_type": "markdown", "id": "7051274a", "metadata": {}, "source": [ "## 5. The even split, scored properly\n", "\n", "The question that halved the field perfectly removes no impurity at all. Not a\n", "little — none. Both sides come out of it at exactly the same 0.5 they went in\n", "at.\n", "\n", "**Evenness was never the point. Agreement is.**" ] }, { "cell_type": "code", "execution_count": 6, "id": "5ef68522", "metadata": { "execution": { "iopub.execute_input": "2026-08-19T12:22:31.131657Z", "iopub.status.busy": "2026-08-19T12:22:31.131552Z", "iopub.status.idle": "2026-08-19T12:22:31.178731Z", "shell.execute_reply": "2026-08-19T12:22:31.178485Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "figure even-against-useful -> which-question-first.even-against-useful.{light,dark}.svg\n" ] } ], "source": [ "#| caption: The evenest question against the most useful one\n", "def plot3(ax):\n", " pairs = [(evenest, \"the evenest split\"), (best_q, \"the most useful split\")]\n", " x = 0\n", " for q, label in pairs:\n", " yes, no = split(ALL, q)\n", " for side, name in ((yes, \"yes\"), (no, \"no\")):\n", " h = sum(hit(f) for f in side)\n", " ax.bar([x], [h], color=\"#e2574c\", width=0.7)\n", " ax.bar([x], [len(side) - h], bottom=[h], color=\"#9aa0aa\", width=0.7)\n", " ax.text(x, len(side) + 0.4, f\"{h}/{len(side)}\", ha=\"center\", fontsize=9)\n", " ax.text(x, -1.4, name, ha=\"center\", fontsize=9, color=\"#77777f\")\n", " x += 1\n", " ax.text(x - 1.5, -2.9, f\"{label}\\ngain {gain(ALL, q):.3f}\", ha=\"center\", fontsize=9.5)\n", " x += 0.8\n", " ax.set_ylabel(\"Films\")\n", " ax.set_ylim(-3.6, 17)\n", " ax.set_xticks([])\n", " ax.grid(axis=\"x\", visible=False)\n", " ax.spines[\"bottom\"].set_visible(False)\n", "\n", "save_fig(\"even-against-useful\", plot3, figsize=(7, 4.0))" ] }, { "cell_type": "markdown", "id": "19d8125d", "metadata": {}, "source": [ "## Try this\n", "\n", "1. **Move one film.** Flip `Copper Harbour` from flop to hit and re-run. Does\n", " the winning question change, or only its gain?\n", "2. **Add a useless column** — a coin flip for each film — and score it. It will\n", " not be exactly zero. Think about why, and about what that means for a\n", " question with hundreds of possible answers rather than two.\n", "3. **Score the second level.** Take the ten films with a star and run the same\n", " five questions on just those. The winner is a different question, which is\n", " the next lesson." ] } ], "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 }