What does Ockham's Razor for Rule Bases conclude, in numbers, about “The Pruner's Admission Threshold: a Gate that Only Catches Repeats and a Gate that Counts Bits”?

Answer: Chapter 6 brings the gate to the cross-volume axiom pruner: a gate that only catches repeats admits 46 rules with a hold-out error of 0.4155, while the description-length gate admits only the 2 true rules.

Scope of the numbers: All decision records are synthetic, all parameters illustrative, and all calculations generated by the book's programs; it is general business analysis, not personalised business advice. Marked boxes separate published evidence, runnable Python calculations (18 programs), classical sources and the author's hypotheses.

中文版

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: 0.4155, 46

proposals: true 2, dup 4, spec 8, pocket 12, noise 24
gatetrue dup spec pocket noiserulesL(total) holdout
G0 text2081224461194.30.4155
G1 MDL200002432.00.1973
G2 MDL+16200002432.00.1973
Show the full program
# Chapter 6. p61: three admission gates facing one stream of proposals.
# Ledger: the 600 seeded training records of p23; 4000 hold-out records.
# 50 proposals arrive in a seeded order (illustrative mix):
#   true   the 2 rules of the generating process
#   dup    4 verbatim repeats of a true rule (the first copy to
#          arrive is counted as true)
#   spec   8 true rules with one extra condition (narrower copies)
#   pocket 12 three-condition rules inside rg=4 (act rate 0.45) that
#          happen to show a net gain on the training ledger
#   noise  24 random two- or three-condition rules
# Gates, applied one proposal at a time against the admitted base:
#   G0 text gate: reject only an exact repeat of an admitted rule
#   G1 MDL gate: admit if two-part length falls (margin > 0)
#   G2 MDL gate with slack: margin > 16 bits (p52)
import itertools
import math
import random

V = (4, 4, 3, 4, 3, 5)
A = len(V)
NAMES = ("ch", "bd", "sg", "ss", "sz", "rg")


def truth(x):
    if x[0] == 0 and x[1] == 3:
        return 0.85
    if x[2] == 2 and x[3] == 1:
        return 0.80
    return 0.45 if x[5] == 4 else 0.12


def records(rng, n):
    out = []
    for _ in range(n):
        x = tuple(rng.randrange(v) for v in V)
        out.append((x, 1 if rng.random() < truth(x) else 0))
    return out


def gamma(n):
    return 2 * (n.bit_length() - 1) + 1


def rule_bits(r):
    m = len(r)
    t = [float(gamma(m)), math.log2(math.comb(A, m))]
    t += [math.log2(V[a]) for a, _ in r]
    return math.fsum(t)


def exc_bits(n, e):
    return gamma(e + 1) + math.log2(math.comb(n, e))


def candidates():
    out = []
    for m in (1, 2, 3):
        for at in itertools.combinations(range(A), m):
            for vs in itertools.product(*[range(V[a]) for a in at]):
                out.append(tuple(zip(at, vs)))
    return out


def cover_masks(data, cands):
    am, pos = {}, 0
    for i, (x, y) in enumerate(data):
        for a in range(A):
            am[(a, x[a])] = am.get((a, x[a]), 0) | (1 << i)
        pos |= y << i
    full = (1 << len(data)) - 1
    cov = []
    for r in cands:
        c = full
        for cond in r:
            c &= am.get(cond, 0)
        cov.append(c)
    return cov, pos, full


def show(r):
    return "&".join("{}={}".format(NAMES[a], v) for a, v in r)


def greedy_path(cov, pos, full, kmax=40):
    unc, path = full, []
    while len(path) < kmax:
        best, bi = 0, -1
        for i, c in enumerate(cov):
            nw = c & unc
            g = (nw & pos).bit_count() - (nw & ~pos).bit_count()
            if g > best:
                best, bi = g, i
        if bi < 0:
            break
        path.append((bi, best))
        unc &= ~cov[bi]
    return path


def errors(rules, cov, pos, full):
    act = 0
    for i in rules:
        act |= cov[i]
    return (pos & ~act & full).bit_count() + (act & ~pos).bit_count()


def length(rules, cands, cov, pos, full, n):
    e = errors(rules, cov, pos, full)
    return math.fsum([float(gamma(len(rules) + 1)), exc_bits(n, e)]
                     + [rule_bits(cands[i]) for i in rules])


def stream(rng, cands, cov, pos, full):
    tb = [cands.index(((0, 0), (1, 3))), cands.index(((2, 2), (3, 1)))]
    out = [("true", i) for i in tb] + [("dup", tb[j % 2])
                                       for j in range(4)]
    spec = [i for i, r in enumerate(cands) if len(r) == 3 and any(
        set(cands[t]) < set(r) for t in tb)]
    out += [("spec", i) for i in rng.sample(spec, 8)]
    pocket = []
    for i, r in enumerate(cands):
        if len(r) == 3 and (5, 4) in r and not any(
                set(cands[t]) < set(r) for t in tb):
            c = cov[i] & ~(cov[tb[0]] | cov[tb[1]])
            if (c & pos).bit_count() > (c & ~pos).bit_count():
                pocket.append(i)
    out += [("pocket", i) for i in rng.sample(pocket, 12)]
    noise = [i for i, r in enumerate(cands) if len(r) > 1]
    out += [("noise", i) for i in rng.sample(noise, 24)]
    rng.shuffle(out)
    seen = set()
    for j, (kind, i) in enumerate(out):
        if kind in ("true", "dup"):
            out[j] = ("dup" if i in seen else "true", i)
            seen.add(i)
    return out


if __name__ == "__main__":
    rng = random.Random(20261113)
    tr, te = records(rng, 600), records(rng, 4000)
    cands = candidates()
    cov, pos, full = cover_masks(tr, cands)
    tcov, tpos, tfull = cover_masks(te, cands)
    props = stream(random.Random(20261114), cands, cov, pos, full)
    kinds = ("true", "dup", "spec", "pocket", "noise")
    print("proposals: " + ", ".join("{} {}".format(
        k, len([1 for t, _ in props if t == k])) for k in kinds))
    print("gate      true dup spec pocket noise  rules  L(total) holdout")
    for gate, d in (("G0 text", None), ("G1 MDL", 0.0),
                    ("G2 MDL+16", 16.0)):
        base, got = [], []
        for kind, i in props:
            if d is None:
                ok = i not in base
            else:
                now = length(base, cands, cov, pos, full, 600)
                new = length(base + [i], cands, cov, pos, full, 600)
                ok = now - new > d
            if ok:
                base.append(i)
                got.append(kind)
        cnt = [len([1 for g in got if g == k]) for k in kinds]
        print("{:<9} {:>4} {:>3} {:>4} {:>6} {:>5}  {:>5}  {:>8.1f}"
              "  {:.4f}".format(gate, *cnt, len(base),
                                length(base, cands, cov, pos, full, 600),
                                errors(base, tcov, tpos, tfull) / 4000))

Single source and citation

Fan, Y. (2026). The Minimum Description Length Principle and Ockham's Razor for Rule Bases: Two-Part Codes that Decide Whether a New Rule Earns Its Place (Version 1.0.0), Chapter 6: The Pruner's Admission Threshold: a Gate that Only Catches Repeats and a Gate that Counts Bits. 5D Library. DOI pending

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

BibTeX
@book{fan2026311,
  author    = {Fan, Yafu},
  title     = {The Minimum Description Length Principle and Ockham's Razor for Rule Bases: Two-Part Codes that Decide Whether a New Rule Earns Its Place},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

Other chapter answers in this book