What does A Zero-Leak Socratic Examiner conclude, in numbers, about “The Probing Tree: Information-Gain Item Selection, Greedy Trees and Stopping Rules”?

Answer: Chapter 5 builds probing trees from information gain, whose benefit comes mainly from the stopping rule: 7.71 items on average against 9.59 for a fixed order, with better accuracy.

Scope of the numbers: Parameters are illustrative; all calculations are generated by the book's programs, which call no model interface, contain no keys or server addresses and include no concrete extraction prompts. This is not individual business advice.

中文版

Data table

The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 7.71, 9.59

policymean questionsstopped by ruleall three right
greedy7.710.93500.9285
cycle9.590.64500.8810
random10.820.36600.7815
Show the full program
# Chapter 5. p53: the tree pays off through its stopping rule.
# Monte Carlo with a fixed seed: 2000 simulated students drawn from the
# p51 prior, answering by the same DINA rule (s = 0.10, g = 0.20).
# Items may be repeated as parallel forms (same skills, new numbers).
# Every policy stops when each skill's posterior is below 0.05 or
# above 0.95, or after 12 questions. Policies:
#   greedy  ask the item with the largest expected information gain
#   cycle   ask F, R, E, F, R, E in turn
#   random  ask a uniformly random item
# Reported: mean questions, share stopped by the rule (not the cap),
# and share whose three skills are all classified correctly.
import itertools
import math
import random

SKILLS = ("F", "R", "E")
MARG = (0.50, 0.70, 0.30)
S, G = 0.10, 0.20
ITEMS = ("F", "R", "E", "FR", "FE", "RE", "FRE")
PROFILES = list(itertools.product((0, 1), repeat=3))
LO, HI, CAP, N = 0.05, 0.95, 12, 2000


def p_corr(item, prof):
    ok = all(prof[SKILLS.index(c)] for c in item)
    return 1 - S if ok else G


def h(ps):
    return -math.fsum(p * math.log2(p) for p in ps if p > 0)


def gain(item, w):
    pc = math.fsum(x * p_corr(item, pr) for x, pr in zip(w, PROFILES))
    cond = math.fsum(x * h((p_corr(item, pr), 1 - p_corr(item, pr)))
                     for x, pr in zip(w, PROFILES))
    return h((pc, 1 - pc)) - cond


def margs(w):
    return [math.fsum(x for x, pr in zip(w, PROFILES) if pr[k])
            for k in range(3)]


def settled(w):
    return all(m <= LO or m >= HI for m in margs(w))


def examine(policy, truth, rng, pick):
    w = [math.prod(m if b else 1 - m for m, b in zip(MARG, pr))
         for pr in PROFILES]
    n = 0
    while n < CAP and not settled(w):
        if policy == "greedy":
            item = max(ITEMS, key=lambda it: (gain(it, w), it))
        elif policy == "cycle":
            item = SKILLS[n % 3]
        else:
            item = pick.choice(ITEMS)
        right = rng.random() < p_corr(item, truth)
        lik = [p_corr(item, pr) if right else 1 - p_corr(item, pr)
               for pr in PROFILES]
        w = [x * y for x, y in zip(w, lik)]
        z = math.fsum(w)
        w = [x / z for x in w]
        n += 1
    guess = tuple(1 if m > 0.5 else 0 for m in margs(w))
    return n, settled(w), guess == truth


top = random.Random(20261113)
truths = [tuple(1 if top.random() < m else 0 for m in MARG)
          for _ in range(N)]
print("policy  mean questions  stopped by rule  all three right")
for policy in ("greedy", "cycle", "random"):
    qs, stops, oks = [], 0, 0
    pick = random.Random(7)
    for i, truth in enumerate(truths):
        rng = random.Random(1000 + i)
        n, st, ok = examine(policy, truth, rng, pick)
        qs.append(n)
        stops += st
        oks += ok
    print("%-7s %-15.2f %-16.4f %.4f"
          % (policy, math.fsum(qs) / N, stops / N, oks / N))

Single source and citation

Fan, Y. (2026). A Zero-Leak Socratic Examiner: Server-Side Isolation of Answers and Bayesian Mastery Probing Trees (Version 1.0.0), Chapter 5: The Probing Tree: Information-Gain Item Selection, Greedy Trees and Stopping Rules. 5D Library. DOI pending

DOI pending · monograph page goes live after publication · 5DL-B-262 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026262,
  author    = {Fan, Yafu},
  title     = {A Zero-Leak Socratic Examiner: Server-Side Isolation of Answers and Bayesian Mastery Probing Trees},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

Other chapter answers in this book