What does Ockham's Razor for Rule Bases conclude, in numbers, about “Sensitivity to the Code: Six Reasonable Codes, Six Verdicts, and How Many Bits of Slack to Reserve”?

Answer: Chapter 5 measures sensitivity to the code: in twenty repetitions six reasonable codes never once choose the same rule count, every verdict with a margin below 4 bits flips with the code, and a minimum margin of 16 bits makes every admission verdict code-proof.

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: 16

greedy steps examined: 223
|SE margin|stepsflipsflip share
0 to 426261.000
4 to 16155780.503
16 to 644200.000
64 to inf000.000
slack dmean kmean holdoutadmitted steps all codes back
02.900.191643 of 58
42.450.190543 of 49
82.350.190243 of 47
162.100.190142 of 42
321.700.202334 of 34
640.000.27520 of 0
Show the full program
# Chapter 5. p52: how much slack makes an admission verdict code-proof?
# For every step of the greedy path in 20 seeds of p31, the margin
# (bits saved minus bits spent) is computed under the six codes of p51.
# A verdict "flips" when some codes say admit and others say reject.
# Then the gate "admit while the SE margin exceeds d bits" is run for
# several slacks d; Cohen's RIPPER (1995) used 64 bits in a related
# stopping rule. Illustrative records; means by math.fsum.
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 total(code, k, rules, n, e, ncand):
    rc = {"S": [rule_bits(r) for r in rules],
          "U": [math.log2(ncand)] * k,
          "F": [8.0 + 8 * len(r) for r in rules]}[code[0]]
    if code[1] == "E":
        ex = exc_bits(n, e)
    else:
        ex = gamma(e + 1) + e * math.ceil(math.log2(n))
    return math.fsum([float(gamma(k + 1)), ex] + rc)


if __name__ == "__main__":
    cands = candidates()
    codes = [a + b for a in "SUF" for b in "EI"]
    steps, runs = [], []
    for s in range(20):
        rng = random.Random(20261113 + s)
        tr, te = records(rng, 600), records(rng, 4000)
        cov, pos, full = cover_masks(tr, cands)
        tcov, tpos, tfull = cover_masks(te, cands)
        path = greedy_path(cov, pos, full)
        es, e = [(pos & full).bit_count()], (pos & full).bit_count()
        for _, g in path:
            e -= g
            es.append(e)
        tl = {c: [total(c, k, [cands[i] for i, _ in path[:k]], 600,
                        es[k], len(cands)) for k in range(len(es))]
              for c in codes}
        for k in range(1, len(es)):
            steps.append([tl[c][k - 1] - tl[c][k] for c in codes])
        runs.append((path, tl["SE"], tcov, tpos, tfull))
    print("greedy steps examined: {}".format(len(steps)))
    print("  |SE margin|   steps  flips  flip share")
    for lo, hi in ((0, 4), (4, 16), (16, 64), (64, 10 ** 9)):
        b = [m for m in steps if lo <= abs(m[0]) < hi]
        f = len([m for m in b if min(m) <= 0 < max(m)])
        print("  {:>4} to {:<5} {:>6} {:>6}  {:>10.3f}".format(
            lo, "inf" if hi > 10 ** 6 else hi, len(b), f,
            f / len(b) if b else 0.0))
    print("  slack d  mean k  mean holdout  admitted steps all codes back")
    for d in (0, 4, 8, 16, 32, 64):
        ks, er, ok, tot = [], [], 0, 0
        for path, tl, tcov, tpos, tfull in runs:
            k = 0
            while k < len(path) and tl[k] - tl[k + 1] > d:
                k += 1
            ks.append(k)
            er.append(errors([i for i, _ in path[:k]], tcov, tpos,
                             tfull) / 4000)
        idx = 0
        for (path, tl, _, _, _), k in zip(runs, ks):
            for j in range(len(path)):
                if j < k:
                    tot += 1
                    ok += 1 if min(steps[idx + j]) > 0 else 0
            idx += len(path)
        print("  {:>7}  {:>6.2f}  {:>12.4f}  {:>9} of {}".format(
            d, math.fsum(ks) / 20, math.fsum(er) / 20, ok, tot))

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 5: Sensitivity to the Code: Six Reasonable Codes, Six Verdicts, and How Many Bits of Slack to Reserve. 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