{ "cells": [ { "cell_type": "markdown", "id": "0a46b824", "metadata": {}, "source": [ "# Decision Trees · Twenty questions\n", "\n", "Somebody is thinking of an animal. You get yes-or-no questions, and you want to\n", "name it in as few as possible.\n", "\n", "Everybody already knows the strategy. You do not open with *is it a dolphin?*\n", "You open with something that splits the room — *does it live in water?* — and\n", "you do it again on whatever is left.\n", "\n", "**That is a decision tree.** This notebook measures how much the strategy is\n", "actually worth, on sixteen animals and eight allowed questions." ] }, { "cell_type": "code", "execution_count": 1, "id": "487ab1fb", "metadata": { "execution": { "iopub.execute_input": "2026-08-19T11:51:59.342969Z", "iopub.status.busy": "2026-08-19T11:51:59.342720Z", "iopub.status.idle": "2026-08-19T11:51:59.604020Z", "shell.execute_reply": "2026-08-19T11:51:59.603317Z" } }, "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": "2dbd02ce", "metadata": {}, "source": [ "## 1. Sixteen animals, eight questions\n", "\n", "Small on purpose. You can hold sixteen animals in your head, check any answer\n", "below against your own knowledge, and count the rows yourself — which is the\n", "only reason the numbers later in this notebook are believable.\n", "\n", "The one thing that has to be true: **no two animals answer all eight questions\n", "the same way.** If two did, no sequence of these questions could ever separate\n", "them, and the assert below would stop the notebook." ] }, { "cell_type": "code", "execution_count": 2, "id": "d94db6e5", "metadata": { "execution": { "iopub.execute_input": "2026-08-19T11:51:59.607796Z", "iopub.status.busy": "2026-08-19T11:51:59.607346Z", "iopub.status.idle": "2026-08-19T11:51:59.640893Z", "shell.execute_reply": "2026-08-19T11:51:59.640627Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "n_animals = 16\n", "n_questions = 8\n" ] }, { "data": { "text/plain": [ "8" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "#| caption: Sixteen animals, and the eight yes/no questions we are allowed to ask\n", "QUESTIONS = {\n", " \"water\": \"Does it live in water?\",\n", " \"flies\": \"Can it fly?\",\n", " \"feathers\": \"Does it have feathers?\",\n", " \"fur\": \"Does it have fur or hair?\",\n", " \"eggs\": \"Does it lay eggs?\",\n", " \"hunts\": \"Does it hunt other animals?\",\n", " \"big\": \"Is it bigger than a person?\",\n", " \"legs\": \"Does it have legs?\",\n", "}\n", "KEYS = list(QUESTIONS)\n", "\n", "# water flies feath fur eggs hunts big legs\n", "ANIMALS = {\n", " \"Dolphin\": (1, 0, 0, 0, 0, 1, 1, 0),\n", " \"Shark\": (1, 0, 0, 0, 1, 1, 1, 0),\n", " \"Crocodile\": (1, 0, 0, 0, 1, 1, 1, 1),\n", " \"Goldfish\": (1, 0, 0, 0, 1, 0, 0, 0),\n", " \"Octopus\": (1, 0, 0, 0, 1, 1, 0, 0),\n", " \"Penguin\": (1, 0, 1, 0, 1, 1, 0, 1),\n", " \"Duck\": (1, 1, 1, 0, 1, 0, 0, 1),\n", " \"Eagle\": (0, 1, 1, 0, 1, 1, 0, 1),\n", " \"Ostrich\": (0, 0, 1, 0, 1, 0, 1, 1),\n", " \"Chicken\": (0, 0, 1, 0, 1, 0, 0, 1),\n", " \"Bat\": (0, 1, 0, 1, 0, 1, 0, 1),\n", " \"Elephant\": (0, 0, 0, 1, 0, 0, 1, 1),\n", " \"Lion\": (0, 0, 0, 1, 0, 1, 1, 1),\n", " \"Cat\": (0, 0, 0, 1, 0, 1, 0, 1),\n", " \"Mouse\": (0, 0, 0, 1, 0, 0, 0, 1),\n", " \"Snake\": (0, 0, 0, 0, 1, 1, 0, 0),\n", "}\n", "\n", "assert len(set(ANIMALS.values())) == len(ANIMALS), \"two animals answer identically\"\n", "record(\"n_animals\", len(ANIMALS))\n", "record(\"n_questions\", len(QUESTIONS))" ] }, { "cell_type": "markdown", "id": "216a480b", "metadata": {}, "source": [ "## 2. What makes a first question good\n", "\n", "A question you ask of sixteen animals sends some to the *yes* side and the rest\n", "to the *no* side. The best one to ask first is the one that leaves the smallest\n", "pile behind whichever way the answer goes — and that is the question that splits\n", "closest to eight and eight.\n", "\n", "*Does it have feathers?* sends five one way and eleven the other. If the answer\n", "is no, you have barely made progress. **Even splits buy more than lopsided\n", "ones**, and that single sentence is most of what a decision tree does." ] }, { "cell_type": "code", "execution_count": 3, "id": "ecf25fca", "metadata": { "execution": { "iopub.execute_input": "2026-08-19T11:51:59.642154Z", "iopub.status.busy": "2026-08-19T11:51:59.642047Z", "iopub.status.idle": "2026-08-19T11:51:59.719968Z", "shell.execute_reply": "2026-08-19T11:51:59.719752Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Does it live in water? yes 7 no 9 worst case 9 left\n", "Is it bigger than a person? yes 6 no 10 worst case 10 left\n", "Does it lay eggs? yes 10 no 6 worst case 10 left\n", "Does it hunt other animals? yes 10 no 6 worst case 10 left\n", "Does it have feathers? yes 5 no 11 worst case 11 left\n", "Does it have fur or hair? yes 5 no 11 worst case 11 left\n", "Does it have legs? yes 11 no 5 worst case 11 left\n", "Can it fly? yes 3 no 13 worst case 13 left\n", "first_question = Does it live in water?\n", "first_yes = 7\n", "first_no = 9\n", "worst_question = Can it fly?\n", "worst_left = 13\n", "figure first-question-choice -> twenty-questions.first-question-choice.{light,dark}.svg\n" ] } ], "source": [ "#| caption: Every allowed question, scored by how evenly it splits the sixteen\n", "def split(animals, feature):\n", " \"\"\"(yes-side, no-side) — the animals that answer yes, and those that answer no.\"\"\"\n", " i = KEYS.index(feature)\n", " yes = {n: v for n, v in animals.items() if v[i]}\n", " no = {n: v for n, v in animals.items() if not v[i]}\n", " return yes, no\n", "\n", "scored = []\n", "for f in KEYS:\n", " yes, no = split(ANIMALS, f)\n", " scored.append((f, len(yes), len(no), abs(len(yes) - len(no))))\n", "scored.sort(key=lambda r: (r[3], r[0]))\n", "\n", "for f, ny, nn, gap in scored:\n", " print(f\"{QUESTIONS[f]:<32} yes {ny:>2} no {nn:>2} worst case {max(ny, nn):>2} left\")\n", "\n", "first = scored[0]\n", "record(\"first_question\", QUESTIONS[first[0]])\n", "record(\"first_yes\", first[1])\n", "record(\"first_no\", first[2])\n", "record(\"worst_question\", QUESTIONS[scored[-1][0]])\n", "record(\"worst_left\", max(scored[-1][1], scored[-1][2]))\n", "\n", "def plot(ax):\n", " labels = [QUESTIONS[f].rstrip(\"?\") for f, *_ in scored][::-1]\n", " worst = [max(ny, nn) for _, ny, nn, _ in scored][::-1]\n", " colors = [\"#e2574c\" if w == min(worst) else \"#9aa0aa\" for w in worst]\n", " ax.barh(labels, worst, color=colors)\n", " ax.axvline(len(ANIMALS) / 2, ls=\"--\", lw=1.2, color=\"#3b6fd4\")\n", " ax.set_xlabel(\"Animals still possible, if the answer goes the wrong way\")\n", " ax.set_xlim(0, len(ANIMALS))\n", " ax.grid(axis=\"y\", visible=False)\n", "\n", "save_fig(\"first-question-choice\", plot, figsize=(7, 4.0))" ] }, { "cell_type": "markdown", "id": "a95a58b5", "metadata": {}, "source": [ "## 3. Ask it again on whatever is left\n", "\n", "The tree is one line of thinking repeated: pick the most even question, ask it,\n", "and then start over on each side as if it were a fresh, smaller game. Stop when\n", "one animal is left.\n", "\n", "That is the whole algorithm. Six lines of it below, and it is a real decision\n", "tree — the same shape the library version builds, without the library." ] }, { "cell_type": "code", "execution_count": 4, "id": "110020bf", "metadata": { "execution": { "iopub.execute_input": "2026-08-19T11:51:59.721288Z", "iopub.status.busy": "2026-08-19T11:51:59.721187Z", "iopub.status.idle": "2026-08-19T11:51:59.725519Z", "shell.execute_reply": "2026-08-19T11:51:59.725311Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "tree = {'q': 'Does it live in water?', 'yes': {'q': 'Is it bigger than a person?', 'yes': {'q': 'Does it lay eggs?', 'yes': {'q': 'Does it have legs?', 'yes': {'leaf': 'Crocodile'}, 'no': {'leaf': 'Shark'}}, 'no': {'leaf': 'Dolphin'}}, 'no': {'q': 'Does it have feathers?', 'yes': {'q': 'Can it fly?', 'yes': {'leaf': 'Duck'}, 'no': {'leaf': 'Penguin'}}, 'no': {'q': 'Does it hunt other animals?', 'yes': {'leaf': 'Octopus'}, 'no': {'leaf': 'Goldfish'}}}}, 'no': {'q': 'Does it lay eggs?', 'yes': {'q': 'Does it hunt other animals?', 'yes': {'q': 'Does it have feathers?', 'yes': {'leaf': 'Eagle'}, 'no': {'leaf': 'Snake'}}, 'no': {'q': 'Is it bigger than a person?', 'yes': {'leaf': 'Ostrich'}, 'no': {'leaf': 'Chicken'}}}, 'no': {'q': 'Is it bigger than a person?', 'yes': {'q': 'Does it hunt other animals?', 'yes': {'leaf': 'Lion'}, 'no': {'leaf': 'Elephant'}}, 'no': {'q': 'Can it fly?', 'yes': {'leaf': 'Bat'}, 'no': {'q': 'Does it hunt other animals?', 'yes': {'leaf': 'Cat'}, 'no': {'leaf': 'Mouse'}}}}}}\n", "Dolphin 3 questions\n", "Crocodile 4 questions\n", "Shark 4 questions\n", "Duck 4 questions\n", "Penguin 4 questions\n", "Octopus 4 questions\n", "Goldfish 4 questions\n", "Eagle 4 questions\n", "Snake 4 questions\n", "Ostrich 4 questions\n", "Chicken 4 questions\n", "Lion 4 questions\n", "Elephant 4 questions\n", "Bat 4 questions\n", "Cat 5 questions\n", "Mouse 5 questions\n", "best_avg = 4.1\n", "best_worst = 5\n", "perfect = 4\n" ] }, { "data": { "text/plain": [ "4" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "#| caption: The tree, built by always asking the most even question left\n", "def build_tree(animals):\n", " if len(animals) == 1:\n", " return {\"leaf\": next(iter(animals))}\n", " usable = [f for f in KEYS if all(split(animals, f))]\n", " if not usable:\n", " return {\"leaf\": \" or \".join(sorted(animals))}\n", " best = min(usable, key=lambda f: (abs(len(split(animals, f)[0]) - len(split(animals, f)[1])), f))\n", " yes, no = split(animals, best)\n", " return {\"q\": QUESTIONS[best], \"yes\": build_tree(yes), \"no\": build_tree(no)}\n", "\n", "TREE = build_tree(ANIMALS)\n", "record(\"tree\", TREE)\n", "\n", "def depths(node, d=0):\n", " if \"leaf\" in node:\n", " return {node[\"leaf\"]: d}\n", " return {**depths(node[\"yes\"], d + 1), **depths(node[\"no\"], d + 1)}\n", "\n", "tree_depth = depths(TREE)\n", "for name in sorted(tree_depth, key=tree_depth.get):\n", " print(f\"{name:<12} {tree_depth[name]} questions\")\n", "\n", "best_avg = record(\"best_avg\", round(sum(tree_depth.values()) / len(tree_depth), 1))\n", "best_worst = record(\"best_worst\", max(tree_depth.values()))\n", "record(\"perfect\", 4) # log2(16): four perfect halvings would do it" ] }, { "cell_type": "markdown", "id": "8816f88a", "metadata": {}, "source": [ "## 4. Against asking one at a time\n", "\n", "The other strategy is the one nobody uses on purpose but every untrained model\n", "uses by default: *is it a dolphin? is it a shark? is it a crocodile?*\n", "\n", "It gets there too. It is not wrong. It is just expensive, and the gap between\n", "the two is the entire value of choosing questions well." ] }, { "cell_type": "code", "execution_count": 5, "id": "4c1a13e0", "metadata": { "execution": { "iopub.execute_input": "2026-08-19T11:51:59.726623Z", "iopub.status.busy": "2026-08-19T11:51:59.726534Z", "iopub.status.idle": "2026-08-19T11:51:59.850798Z", "shell.execute_reply": "2026-08-19T11:51:59.850566Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "naive_avg = 8.4\n", "naive_worst = 15\n", "times_more = 2.0\n", "figure questions-per-animal -> twenty-questions.questions-per-animal.{light,dark}.svg\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "figure what-is-left -> twenty-questions.what-is-left.{light,dark}.svg\n" ] } ], "source": [ "#| caption: Questions needed per animal — choosing the split, against one at a time\n", "# Fifteen guesses is enough for sixteen animals: fifteen no's identify the last.\n", "naive_depth = {name: min(i + 1, len(ANIMALS) - 1) for i, name in enumerate(ANIMALS)}\n", "\n", "naive_avg = record(\"naive_avg\", round(sum(naive_depth.values()) / len(naive_depth), 1))\n", "record(\"naive_worst\", max(naive_depth.values()))\n", "record(\"times_more\", round(naive_avg / best_avg, 1))\n", "\n", "def plot(ax):\n", " order = sorted(ANIMALS, key=lambda n: (tree_depth[n], n))\n", " ax.bar(range(len(order)), [tree_depth[n] for n in order], color=\"#e2574c\", width=0.68)\n", " ax.axhline(best_avg, ls=\"--\", lw=1.2, color=\"#e2574c\")\n", " ax.axhline(naive_avg, ls=\"--\", lw=1.2, color=\"#9aa0aa\")\n", " ax.text(0.2, best_avg + 0.25, f\"asking the splitting question: {best_avg} on average\",\n", " fontsize=9.5, color=\"#e2574c\")\n", " ax.text(0.2, naive_avg + 0.25, f\"one animal at a time: {naive_avg} on average\",\n", " fontsize=9.5, color=\"#77777f\")\n", " ax.set_xticks(range(len(order)))\n", " ax.set_xticklabels(order, rotation=55, ha=\"right\", fontsize=9)\n", " ax.set_ylabel(\"Questions to name it\")\n", " ax.set_ylim(0, max(naive_avg, max(tree_depth.values())) + 1.6)\n", " ax.grid(axis=\"x\", visible=False)\n", "\n", "save_fig(\"questions-per-animal\", plot, figsize=(7, 4.4))\n", "\n", "def plot2(ax):\n", " steps = range(0, len(ANIMALS))\n", " halving = [max(1, len(ANIMALS) / 2 ** k) for k in steps]\n", " one_at_a_time = [max(1, len(ANIMALS) - k) for k in steps]\n", " ax.plot(list(steps), halving, marker=\"o\", ms=4, color=\"#e2574c\",\n", " label=\"split the field\")\n", " ax.plot(list(steps), one_at_a_time, marker=\"o\", ms=4, color=\"#9aa0aa\",\n", " label=\"one animal at a time\")\n", " ax.set_xlabel(\"Questions asked\")\n", " ax.set_ylabel(\"Animals still possible\")\n", " ax.legend(frameon=False)\n", "\n", "save_fig(\"what-is-left\", plot2, figsize=(7, 3.8))" ] }, { "cell_type": "markdown", "id": "dec7d974", "metadata": {}, "source": [ "## 4. What the tree does to the field\n", "\n", "The tree is easier to believe as a picture of the sixteen being carved up than\n", "as a list of questions. Each row below is one more question asked; each block is\n", "a group of animals that have answered everything above it the same way.\n", "\n", "**Every block splits into two, and neither half is ever much bigger than the\n", "other.** That is the halving, and it is why the bottom row — one animal per\n", "block — arrives after four rows and not fifteen." ] }, { "cell_type": "code", "execution_count": 6, "id": "0c69851b", "metadata": { "execution": { "iopub.execute_input": "2026-08-19T11:51:59.851956Z", "iopub.status.busy": "2026-08-19T11:51:59.851865Z", "iopub.status.idle": "2026-08-19T11:51:59.902806Z", "shell.execute_reply": "2026-08-19T11:51:59.902609Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "figure carving-up-the-field -> twenty-questions.carving-up-the-field.{light,dark}.svg\n" ] } ], "source": [ "#| caption: The sixteen carved up, one row per question asked\n", "def leaves(node):\n", " return [node[\"leaf\"]] if \"leaf\" in node else leaves(node[\"yes\"]) + leaves(node[\"no\"])\n", "\n", "def spans(node, x0, x1, d, out):\n", " out.append((d, x0, x1, len(leaves(node))))\n", " if \"leaf\" in node:\n", " return\n", " share = len(leaves(node[\"yes\"])) / len(leaves(node))\n", " xm = x0 + (x1 - x0) * share\n", " spans(node[\"yes\"], x0, xm, d + 1, out)\n", " spans(node[\"no\"], xm, x1, d + 1, out)\n", "\n", "blocks = []\n", "spans(TREE, 0.0, 1.0, 0, blocks)\n", "\n", "def plot3(ax):\n", " rows = max(d for d, *_ in blocks)\n", " for d, x0, x1, n in blocks:\n", " ax.add_patch(plt.Rectangle((x0, -d - 0.86), x1 - x0, 0.72,\n", " facecolor=\"#e2574c\", alpha=0.16 + 0.1 * min(d, 4),\n", " edgecolor=\"#e2574c\", lw=1.0))\n", " if (x1 - x0) > 0.055:\n", " ax.text((x0 + x1) / 2, -d - 0.5, str(n), ha=\"center\", va=\"center\", fontsize=10)\n", " for d in range(rows + 1):\n", " ax.text(-0.012, -d - 0.5, f\"{d}\", ha=\"right\", va=\"center\", fontsize=9, color=\"#77777f\")\n", " ax.set_xlim(-0.06, 1.01)\n", " ax.set_ylim(-rows - 1.05, 0.02)\n", " ax.set_ylabel(\"Questions asked\")\n", " ax.set_yticks([])\n", " ax.set_xticks([])\n", " ax.grid(visible=False)\n", " for side in (\"left\", \"bottom\"):\n", " ax.spines[side].set_visible(False)\n", "\n", "import matplotlib.pyplot as plt\n", "save_fig(\"carving-up-the-field\", plot3, figsize=(7, 3.6))" ] }, { "cell_type": "markdown", "id": "16e31068", "metadata": {}, "source": [ "## Try this\n", "\n", "1. **Add an animal.** A frog, a bee, a whale. Does the tree get deeper, or does\n", " it absorb it for free?\n", "2. **Take a question away** — delete `legs` from `QUESTIONS`. The assert in\n", " cell 1 still passes, but watch what happens to `best_worst`.\n", "3. **Break the tie-break.** `min(...)` currently prefers the alphabetically\n", " first question when two split equally well. Prefer the last instead. The\n", " tree changes shape; check whether `best_avg` changes at all." ] } ], "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 }