What does Ockham's Razor for Rule Bases conclude, in numbers, about “Reconciling with the Bayesian Information Criterion: Parametric Complexity, Normalised Maximum Likelihood and Where Rule Bases Part Ways”?
Answer: On 150 records the Bayesian information criterion admits 9.5 rules on average, with a hold-out error of 0.2512; minimum description length admits only 1.4, with an error of 0.2218; the optimum is 2.2 rules with an error of 0.1951. On 600 records the three are 6.9, 2.6 and 2.4 rules, with errors of 0.1929, 0.1849 and 0.1830. At every size the Bayesian information criterion admits several rules more than the optimum, and its error is higher every time. The reason is the one just given: it pays for each rule as though it were one parameter, and nothing for having picked this particular rule out of 1347 candidates. The richer the structure of the rules, the larger this unpaid structural cost.
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.1830, 0.1849, 0.1929, 0.1951, 0.2218, 0.2512
| N | k:MDL | BIC | best | err:MDL | BIC | best |
|---|---|---|---|---|---|---|
| 150 | 1.4 | 9.5 | 2.2 | 0.2218 | 0.2512 | 0.1951 |
| 300 | 2.4 | 8.6 | 2.5 | 0.1921 | 0.2330 | 0.1890 |
| 600 | 2.6 | 6.9 | 2.4 | 0.1849 | 0.1929 | 0.1830 |
| 1200 | 2.8 | 6.3 | 2.8 | 0.1843 | 0.1888 | 0.1821 |
| 2400 | 3.8 | 7.7 | 2.2 | 0.1870 | 0.1908 | 0.1837 |
Show the full program
# Chapter 4. p42: MDL and BIC choosing the size of the same rule base.
# Process, candidates and greedy proposer as in p23 and p31; training
# size N varies, 4000 hold-out records, 10 seeds per N (illustrative).
# MDL two-part length of p21: rule syntax + exception subset
# BIC N h(e/N) + ((k + 1) / 2) log2 N: one parameter per rule and one
# for the exception rate, whatever a rule's syntax
# best the k with least hold-out error (an oracle)
# Reported: mean k chosen and mean hold-out error (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()
if __name__ == "__main__":
cands = candidates()
print(" N k:MDL BIC best err:MDL BIC best")
for n in (150, 300, 600, 1200, 2400):
out = []
for s in range(10):
rng = random.Random(20261113 + 100 * s + n)
tr, te = records(rng, n), records(rng, 4000)
cov, pos, full = cover_masks(tr, cands)
tcov, tpos, tfull = cover_masks(te, cands)
path = greedy_path(cov, pos, full)
mdl, bic, err, rb = [], [], [], []
e = (pos & full).bit_count()
for k in range(len(path) + 1):
if k:
e -= path[k - 1][1]
rb.append(rule_bits(cands[path[k - 1][0]]))
mdl.append(math.fsum([float(gamma(k + 1)),
exc_bits(n, e)] + rb))
p = e / n
h = 0.0 if p in (0, 1) else -p * math.log2(p) - (
1 - p) * math.log2(1 - p)
bic.append(n * h + (k + 1) / 2 * math.log2(n))
err.append(errors([i for i, _ in path[:k]], tcov, tpos,
tfull) / 4000)
km = min(range(len(mdl)), key=lambda k: (mdl[k], k))
kb = min(range(len(bic)), key=lambda k: (bic[k], k))
ko = min(range(len(err)), key=lambda k: (err[k], k))
out.append((km, kb, ko, err[km], err[kb], err[ko]))
m = [math.fsum(r[i] for r in out) / len(out) for i in range(6)]
print(" {:>4} {:>6.1f} {:>4.1f} {:>5.1f} {:.4f} {:.4f} {:.4f}"
.format(n, *m))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 4: Reconciling with the Bayesian Information Criterion: Parametric Complexity, Normalised Maximum Likelihood and Where Rule Bases Part Ways. 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
- Chapter 1 · Even Integers Cost Something: Universal Codes, the Kraft Inequality and the Bits of an Exception List
- Chapter 2 · The Two-Part Ledger: How Many Exceptions a Rule Must Fix to Earn Its Own Length
- Chapter 3 · The Overfitting Curve: Rule Count, Total Description Length and Hold-out Error
- Chapter 5 · Sensitivity to the Code: Six Reasonable Codes, Six Verdicts, and How Many Bits of Slack to Reserve
- Chapter 6 · The Pruner's Admission Threshold: a Gate that Only Catches Repeats and a Gate that Counts Bits
- Chapter 7 · Sources East and West: the Extra Finger of the Zhuangzi and Ockham's "In Vain through More"
- Chapter 8 · Closing the Loop: the Admission Check-up, the Rule Admission Description-Length Referee and a Pre-registered Plan of Refutation