Entropy — how many questions is the answer worth?

from math import log2

DEALS = ["won"] * 6 + ["lost"] * 4

def entropy(pile):
    """The average number of yes/no questions the answer is worth, in bits."""
    if not pile:
        return 0.0
    shares = [pile.count(k) / len(pile) for k in set(pile)]
    return -sum(s * log2(s) for s in shares if s > 0)

by_hand = -0.6 * log2(0.6) - 0.4 * log2(0.4)
print(f"  0.6 x log2(1/0.6) = {-0.6 * log2(0.6):.3f}")
print(f"  0.4 x log2(1/0.4) = {-0.4 * log2(0.4):.3f}")
print(f"                      -----")
print(f"                      {by_hand:.3f} bits")

record("deals_entropy", round(by_hand, 3))
record("even_entropy", round(entropy(["won", "lost"]), 3))
# abs(): -0.0 is a true statement and an ugly one to print in a lesson.
record("pure_entropy", abs(round(entropy(["won"] * 10), 3)))
print(f"\nfive and five  {entropy(['won'] * 5 + ['lost'] * 5):.3f}   (a whole question — you know nothing)")
print(f"all won        {entropy(['won'] * 10):.3f}   (no question needed — you already know)")

uniform = [f"animal {i}" for i in range(16)]
print(f"entropy of 16 equally likely animals = {entropy(uniform):.3f} bits")
print(f"log2(16)                             = {log2(16):.3f}")

record("animals_entropy", round(entropy(uniform), 3))
record("animals_measured", 4.1)   # what the greedy tree in lesson 1 actually averaged

import heapq

def best_tree_cost(weights):
    """Average questions under the shortest possible strategy (Huffman)."""
    if len(weights) == 1:
        return 0.0
    heap = [(w, i, 0) for i, w in enumerate(weights)]   # (weight, tiebreak, depth-so-far)
    heapq.heapify(heap)
    total = 0.0
    nxt = len(weights)
    while len(heap) > 1:
        a = heapq.heappop(heap)
        bq = heapq.heappop(heap)
        merged = a[0] + bq[0]
        total += merged          # every merge adds one question to everything below it
        heapq.heappush(heap, (merged, nxt, 0))
        nxt += 1
    return total

equal = [1 / 16] * 16
print(f"entropy of the sixteen        {entropy(uniform):.3f} questions")
print(f"best possible strategy        {best_tree_cost(equal):.3f} questions")

record("animals_best_strategy", round(best_tree_cost(equal), 3))

def entropy_of(weights):
    return -sum(w * log2(w) for w in weights if w > 0)

skewed = [0.5] + [0.5 / 15] * 15   # one animal picked half the time
print(f"{'':22} {'entropy':>9} {'best strategy':>15}")
print(f"{'all equally likely':22} {entropy_of(equal):>9.3f} {best_tree_cost(equal):>15.3f}")
print(f"{'one picked half the time':22} {entropy_of(skewed):>9.3f} {best_tree_cost(skewed):>15.3f}")

record("skewed_entropy", round(entropy_of(skewed), 3))
record("skewed_best", round(best_tree_cost(skewed), 3))
record("questions_saved", round(best_tree_cost(equal) - best_tree_cost(skewed), 1))

def plot(ax):
    labels = ["all sixteen\nequally likely", "one animal picked\nhalf the time"]
    ent = [entropy_of(equal), entropy_of(skewed)]
    best = [best_tree_cost(equal), best_tree_cost(skewed)]
    xs = range(len(labels))
    ax.bar([x - 0.19 for x in xs], ent, width=0.36, color="#e2574c", label="entropy — the floor")
    ax.bar([x + 0.19 for x in xs], best, width=0.36, color="#9aa0aa", label="best strategy — measured")
    for x, (e, bb) in enumerate(zip(ent, best)):
        ax.text(x - 0.19, e + 0.07, f"{e:.2f}", ha="center", fontsize=9.5)
        ax.text(x + 0.19, bb + 0.07, f"{bb:.2f}", ha="center", fontsize=9.5)
    ax.set_xticks(list(xs))
    ax.set_xticklabels(labels)
    ax.set_ylabel("Questions to name the animal")
    ax.set_ylim(0, 5.0)
    ax.legend(frameon=False, fontsize=9)
    ax.grid(axis="x", visible=False)

save_fig("entropy-is-the-floor", plot, figsize=(7, 3.9))

def gini(pile):
    if not pile:
        return 0.0
    shares = [pile.count(k) / len(pile) for k in set(pile)]
    return 1 - sum(s * s for s in shares)

# Every way of splitting ten deals into two sides, scored both ways: does the
# ranking ever change? This is the honest version of "they mostly agree".
from itertools import combinations
rows = []
for size in range(1, 10):
    for left_won in range(0, min(size, 6) + 1):
        left_lost = size - left_won
        if left_lost > 4:
            continue
        left = ["won"] * left_won + ["lost"] * left_lost
        right = ["won"] * (6 - left_won) + ["lost"] * (4 - left_lost)
        w = len(left) / 10
        rows.append((
            gini(DEALS) - (w * gini(left) + (1 - w) * gini(right)),
            entropy(DEALS) - (w * entropy(left) + (1 - w) * entropy(right)),
        ))

by_gini = sorted(range(len(rows)), key=lambda i: -rows[i][0])
by_entropy = sorted(range(len(rows)), key=lambda i: -rows[i][1])
record("n_splits_compared", len(rows))
record("same_best_split", by_gini[0] == by_entropy[0])
record("same_top_three", by_gini[:3] == by_entropy[:3])
print(f"{len(rows)} possible splits of the ten deals")
print(f"same best split      {by_gini[0] == by_entropy[0]}")
print(f"same top three       {by_gini[:3] == by_entropy[:3]}")
print(f"identical ranking    {by_gini == by_entropy}")

def plot2(ax):
    ps = [i / 200 for i in range(201)]
    ax.plot(ps, [1 - p * p - (1 - p) ** 2 for p in ps], color="#e2574c", label="gini — chance two draws disagree")
    ax.plot(ps, [0 if p in (0, 1) else -p * log2(p) - (1 - p) * log2(1 - p) for p in ps],
            color="#3b6fd4", ls="--", label="entropy — questions the answer is worth")
    ax.set_xlabel("Share of the pile that were won")
    ax.set_ylabel("Impurity")
    ax.legend(frameon=False, fontsize=9)

save_fig("gini-and-entropy", plot2, figsize=(7, 3.6))