{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "fa72a7ba",
   "metadata": {},
   "source": [
    "# Decision Trees · How many questions is the answer worth?\n",
    "\n",
    "The animals lesson ended on a number that was never explained. Sixteen animals,\n",
    "and the best possible strategy needs **four** questions — so the tree that\n",
    "averaged 4.1 was within a tenth of perfect.\n",
    "\n",
    "Where did the four come from?\n",
    "\n",
    "It came from **entropy**, which is the second measure of how mixed a pile is,\n",
    "and which answers a question with a very concrete meaning: *how many yes-or-no\n",
    "questions is this answer worth?* This notebook computes it by hand, then proves\n",
    "it by building the best possible questioning strategy and counting."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "efc40496",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-19T12:20:54.587228Z",
     "iopub.status.busy": "2026-08-19T12:20:54.586931Z",
     "iopub.status.idle": "2026-08-19T12:20:54.964911Z",
     "shell.execute_reply": "2026-08-19T12:20:54.964495Z"
    }
   },
   "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": "a0b1a8cd",
   "metadata": {},
   "source": [
    "## 1. The same ten deals\n",
    "\n",
    "Six won, four lost. Gini said this pile scores 0.48. Entropy asks a different\n",
    "question about the same pile and answers in a different unit.\n",
    "\n",
    "> **If I knew the outcome and you did not, how many yes-or-no questions would\n",
    "> you need to get it out of me?**\n",
    "\n",
    "One deal, two possible answers, so: one question. But not quite — because if\n",
    "won is more likely than lost, a clever question is worth more than a stupid\n",
    "one, and over many deals the average comes out below one."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "a45e0af0",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-19T12:20:54.967127Z",
     "iopub.status.busy": "2026-08-19T12:20:54.966987Z",
     "iopub.status.idle": "2026-08-19T12:20:54.970436Z",
     "shell.execute_reply": "2026-08-19T12:20:54.970184Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  0.6 x log2(1/0.6) = 0.442\n",
      "  0.4 x log2(1/0.4) = 0.529\n",
      "                      -----\n",
      "                      0.971 bits\n",
      "deals_entropy = 0.971\n",
      "even_entropy = 1.0\n",
      "pure_entropy = 0.0\n",
      "\n",
      "five and five  1.000   (a whole question — you know nothing)\n",
      "all won        -0.000   (no question needed — you already know)\n"
     ]
    }
   ],
   "source": [
    "#| caption: Entropy of the ten deals, by hand and by function\n",
    "from math import log2\n",
    "\n",
    "DEALS = [\"won\"] * 6 + [\"lost\"] * 4\n",
    "\n",
    "def entropy(pile):\n",
    "    \"\"\"The average number of yes/no questions the answer is worth, in bits.\"\"\"\n",
    "    if not pile:\n",
    "        return 0.0\n",
    "    shares = [pile.count(k) / len(pile) for k in set(pile)]\n",
    "    return -sum(s * log2(s) for s in shares if s > 0)\n",
    "\n",
    "by_hand = -0.6 * log2(0.6) - 0.4 * log2(0.4)\n",
    "print(f\"  0.6 x log2(1/0.6) = {-0.6 * log2(0.6):.3f}\")\n",
    "print(f\"  0.4 x log2(1/0.4) = {-0.4 * log2(0.4):.3f}\")\n",
    "print(f\"                      -----\")\n",
    "print(f\"                      {by_hand:.3f} bits\")\n",
    "\n",
    "record(\"deals_entropy\", round(by_hand, 3))\n",
    "record(\"even_entropy\", round(entropy([\"won\", \"lost\"]), 3))\n",
    "# abs(): -0.0 is a true statement and an ugly one to print in a lesson.\n",
    "record(\"pure_entropy\", abs(round(entropy([\"won\"] * 10), 3)))\n",
    "print(f\"\\nfive and five  {entropy(['won'] * 5 + ['lost'] * 5):.3f}   (a whole question — you know nothing)\")\n",
    "print(f\"all won        {entropy(['won'] * 10):.3f}   (no question needed — you already know)\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b2869976",
   "metadata": {},
   "source": [
    "## 2. What a bit actually is\n",
    "\n",
    "A **bit** is one yes-or-no question's worth of answer. Two equally likely\n",
    "outcomes cost one bit. Four cost two. Sixteen cost four — which is the number\n",
    "the animals lesson used and never justified.\n",
    "\n",
    "The formula is the same shape as gini, with a logarithm where gini has a\n",
    "square:\n",
    "\n",
    "> entropy = − Σ (share × log₂ share)\n",
    "\n",
    "and log₂ of a share is just *how many halvings it takes to get down to that\n",
    "share*. A one-in-sixteen animal is four halvings away, so naming it is worth\n",
    "four questions. That is the entire idea."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "80fabfd1",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-19T12:20:54.971567Z",
     "iopub.status.busy": "2026-08-19T12:20:54.971495Z",
     "iopub.status.idle": "2026-08-19T12:20:54.974784Z",
     "shell.execute_reply": "2026-08-19T12:20:54.974589Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "entropy of 16 equally likely animals = 4.000 bits\n",
      "log2(16)                             = 4.000\n",
      "animals_entropy = 4.0\n",
      "animals_measured = 4.1\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "4.1"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#| caption: Sixteen equally likely animals — where the four came from\n",
    "uniform = [f\"animal {i}\" for i in range(16)]\n",
    "print(f\"entropy of 16 equally likely animals = {entropy(uniform):.3f} bits\")\n",
    "print(f\"log2(16)                             = {log2(16):.3f}\")\n",
    "\n",
    "record(\"animals_entropy\", round(entropy(uniform), 3))\n",
    "record(\"animals_measured\", 4.1)   # what the greedy tree in lesson 1 actually averaged"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a1792dd4",
   "metadata": {},
   "source": [
    "## 3. Proving it, rather than asserting it\n",
    "\n",
    "Entropy claims to be a **floor**: no questioning strategy can beat it on\n",
    "average. That is a strong claim, so build the best possible strategy and count.\n",
    "\n",
    "The best strategy is a known one — repeatedly join the two least likely\n",
    "possibilities and ask about the group — and it produces the shortest average\n",
    "number of questions there is. Run it on the sixteen animals and it should land\n",
    "on four."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "fd6de409",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-19T12:20:54.975760Z",
     "iopub.status.busy": "2026-08-19T12:20:54.975692Z",
     "iopub.status.idle": "2026-08-19T12:20:54.978609Z",
     "shell.execute_reply": "2026-08-19T12:20:54.978421Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "entropy of the sixteen        4.000 questions\n",
      "best possible strategy        4.000 questions\n",
      "animals_best_strategy = 4.0\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "4.0"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#| caption: The best possible questioning strategy, built and measured\n",
    "import heapq\n",
    "\n",
    "def best_tree_cost(weights):\n",
    "    \"\"\"Average questions under the shortest possible strategy (Huffman).\"\"\"\n",
    "    if len(weights) == 1:\n",
    "        return 0.0\n",
    "    heap = [(w, i, 0) for i, w in enumerate(weights)]   # (weight, tiebreak, depth-so-far)\n",
    "    heapq.heapify(heap)\n",
    "    total = 0.0\n",
    "    nxt = len(weights)\n",
    "    while len(heap) > 1:\n",
    "        a = heapq.heappop(heap)\n",
    "        bq = heapq.heappop(heap)\n",
    "        merged = a[0] + bq[0]\n",
    "        total += merged          # every merge adds one question to everything below it\n",
    "        heapq.heappush(heap, (merged, nxt, 0))\n",
    "        nxt += 1\n",
    "    return total\n",
    "\n",
    "equal = [1 / 16] * 16\n",
    "print(f\"entropy of the sixteen        {entropy(uniform):.3f} questions\")\n",
    "print(f\"best possible strategy        {best_tree_cost(equal):.3f} questions\")\n",
    "\n",
    "record(\"animals_best_strategy\", round(best_tree_cost(equal), 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "87f94215",
   "metadata": {},
   "source": [
    "## 4. When some answers are more likely than others\n",
    "\n",
    "Everything above assumed the sixteen animals were equally likely. They are not.\n",
    "If half the people who play think of the dolphin, then *is it the dolphin?* —\n",
    "the question lesson 1 dismissed as the stupid opening — becomes the best\n",
    "question on the board.\n",
    "\n",
    "**Entropy is the number that knows this.** Skew the likelihoods and it falls\n",
    "below four, and the best strategy falls with it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "60a80d8a",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-19T12:20:54.979812Z",
     "iopub.status.busy": "2026-08-19T12:20:54.979714Z",
     "iopub.status.idle": "2026-08-19T12:20:55.047283Z",
     "shell.execute_reply": "2026-08-19T12:20:55.046945Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "                         entropy   best strategy\n",
      "all equally likely         4.000           4.000\n",
      "one picked half the time     2.953           2.967\n",
      "skewed_entropy = 2.953\n",
      "skewed_best = 2.967\n",
      "questions_saved = 1.0\n",
      "figure entropy-is-the-floor -> how-many-questions-is-it-worth.entropy-is-the-floor.{light,dark}.svg\n"
     ]
    }
   ],
   "source": [
    "#| caption: A skewed game — entropy falls, and so does the number of questions\n",
    "def entropy_of(weights):\n",
    "    return -sum(w * log2(w) for w in weights if w > 0)\n",
    "\n",
    "skewed = [0.5] + [0.5 / 15] * 15   # one animal picked half the time\n",
    "print(f\"{'':22} {'entropy':>9} {'best strategy':>15}\")\n",
    "print(f\"{'all equally likely':22} {entropy_of(equal):>9.3f} {best_tree_cost(equal):>15.3f}\")\n",
    "print(f\"{'one picked half the time':22} {entropy_of(skewed):>9.3f} {best_tree_cost(skewed):>15.3f}\")\n",
    "\n",
    "record(\"skewed_entropy\", round(entropy_of(skewed), 3))\n",
    "record(\"skewed_best\", round(best_tree_cost(skewed), 3))\n",
    "record(\"questions_saved\", round(best_tree_cost(equal) - best_tree_cost(skewed), 1))\n",
    "\n",
    "def plot(ax):\n",
    "    labels = [\"all sixteen\\nequally likely\", \"one animal picked\\nhalf the time\"]\n",
    "    ent = [entropy_of(equal), entropy_of(skewed)]\n",
    "    best = [best_tree_cost(equal), best_tree_cost(skewed)]\n",
    "    xs = range(len(labels))\n",
    "    ax.bar([x - 0.19 for x in xs], ent, width=0.36, color=\"#e2574c\", label=\"entropy — the floor\")\n",
    "    ax.bar([x + 0.19 for x in xs], best, width=0.36, color=\"#9aa0aa\", label=\"best strategy — measured\")\n",
    "    for x, (e, bb) in enumerate(zip(ent, best)):\n",
    "        ax.text(x - 0.19, e + 0.07, f\"{e:.2f}\", ha=\"center\", fontsize=9.5)\n",
    "        ax.text(x + 0.19, bb + 0.07, f\"{bb:.2f}\", ha=\"center\", fontsize=9.5)\n",
    "    ax.set_xticks(list(xs))\n",
    "    ax.set_xticklabels(labels)\n",
    "    ax.set_ylabel(\"Questions to name the animal\")\n",
    "    ax.set_ylim(0, 5.0)\n",
    "    ax.legend(frameon=False, fontsize=9)\n",
    "    ax.grid(axis=\"x\", visible=False)\n",
    "\n",
    "save_fig(\"entropy-is-the-floor\", plot, figsize=(7, 3.9))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6b938f5b",
   "metadata": {},
   "source": [
    "## 5. Gini and entropy, side by side\n",
    "\n",
    "Two measures, same job, different units. Gini is a probability — the chance two\n",
    "draws disagree. Entropy is a count of questions. Drawn on the same axis they are\n",
    "almost the same curve, entropy simply rising more steeply away from purity.\n",
    "\n",
    "Where they differ in practice is: barely. On the same splits they usually pick\n",
    "the same winner, and when they disagree it is between two questions that were\n",
    "close anyway."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "30b94b4a",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-19T12:20:55.048708Z",
     "iopub.status.busy": "2026-08-19T12:20:55.048599Z",
     "iopub.status.idle": "2026-08-19T12:20:55.112342Z",
     "shell.execute_reply": "2026-08-19T12:20:55.111967Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "n_splits_compared = 33\n",
      "same_best_split = True\n",
      "same_top_three = True\n",
      "33 possible splits of the ten deals\n",
      "same best split      True\n",
      "same top three       True\n",
      "identical ranking    False\n",
      "figure gini-and-entropy -> how-many-questions-is-it-worth.gini-and-entropy.{light,dark}.svg\n"
     ]
    }
   ],
   "source": [
    "#| caption: The two curves, and whether they ever disagree about a split\n",
    "def gini(pile):\n",
    "    if not pile:\n",
    "        return 0.0\n",
    "    shares = [pile.count(k) / len(pile) for k in set(pile)]\n",
    "    return 1 - sum(s * s for s in shares)\n",
    "\n",
    "# Every way of splitting ten deals into two sides, scored both ways: does the\n",
    "# ranking ever change? This is the honest version of \"they mostly agree\".\n",
    "from itertools import combinations\n",
    "rows = []\n",
    "for size in range(1, 10):\n",
    "    for left_won in range(0, min(size, 6) + 1):\n",
    "        left_lost = size - left_won\n",
    "        if left_lost > 4:\n",
    "            continue\n",
    "        left = [\"won\"] * left_won + [\"lost\"] * left_lost\n",
    "        right = [\"won\"] * (6 - left_won) + [\"lost\"] * (4 - left_lost)\n",
    "        w = len(left) / 10\n",
    "        rows.append((\n",
    "            gini(DEALS) - (w * gini(left) + (1 - w) * gini(right)),\n",
    "            entropy(DEALS) - (w * entropy(left) + (1 - w) * entropy(right)),\n",
    "        ))\n",
    "\n",
    "by_gini = sorted(range(len(rows)), key=lambda i: -rows[i][0])\n",
    "by_entropy = sorted(range(len(rows)), key=lambda i: -rows[i][1])\n",
    "record(\"n_splits_compared\", len(rows))\n",
    "record(\"same_best_split\", by_gini[0] == by_entropy[0])\n",
    "record(\"same_top_three\", by_gini[:3] == by_entropy[:3])\n",
    "print(f\"{len(rows)} possible splits of the ten deals\")\n",
    "print(f\"same best split      {by_gini[0] == by_entropy[0]}\")\n",
    "print(f\"same top three       {by_gini[:3] == by_entropy[:3]}\")\n",
    "print(f\"identical ranking    {by_gini == by_entropy}\")\n",
    "\n",
    "def plot2(ax):\n",
    "    ps = [i / 200 for i in range(201)]\n",
    "    ax.plot(ps, [1 - p * p - (1 - p) ** 2 for p in ps], color=\"#e2574c\", label=\"gini — chance two draws disagree\")\n",
    "    ax.plot(ps, [0 if p in (0, 1) else -p * log2(p) - (1 - p) * log2(1 - p) for p in ps],\n",
    "            color=\"#3b6fd4\", ls=\"--\", label=\"entropy — questions the answer is worth\")\n",
    "    ax.set_xlabel(\"Share of the pile that were won\")\n",
    "    ax.set_ylabel(\"Impurity\")\n",
    "    ax.legend(frameon=False, fontsize=9)\n",
    "\n",
    "save_fig(\"gini-and-entropy\", plot2, figsize=(7, 3.6))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0706fedc",
   "metadata": {},
   "source": [
    "## Try this\n",
    "\n",
    "1. **Make the skew extreme.** Give one animal 0.9 of the probability. Entropy\n",
    "   falls under one question — and the best strategy is almost always just\n",
    "   *is it the dolphin?* Then think about what that means for a dataset where\n",
    "   99% of rows have the same outcome.\n",
    "2. **Check the floor is real.** Try to build a strategy for the equally-likely\n",
    "   sixteen that averages under four questions. You cannot, and the reason is\n",
    "   the only thing entropy is claiming.\n",
    "3. **Find a disagreement.** Section 5 compares every split of the ten deals.\n",
    "   Widen the pile to twenty and look for a split where gini and entropy rank\n",
    "   differently. They are rarer than the amount of argument about them suggests."
   ]
  }
 ],
 "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
}