What does Ockham's Razor for Rule Bases conclude, in numbers, about “The Overfitting Curve: Rule Count, Total Description Length and Hold-out Error”?

Answer: Chapter 3 draws the overfitting curve: training exceptions keep falling while hold-out error climbs back from 0.1973 to 0.2333; over twenty repetitions, the base that stops at the shortest total length has a hold-out error of 0.1916 against 0.2223 with no gate.

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.1916, 0.1973, 0.2223, 0.2333

seed kMDL kbest kend errMDL errbest errend ertrue
03 2 12 0.2047 0.1973 0.2333 0.1973
14 5 10 0.1895 0.1890 0.2100 0.1903
22 2 10 0.1785 0.1785 0.2072 0.1785
32 2 11 0.1790 0.1790 0.2295 0.1790
42 2 18 0.1852 0.1852 0.2507 0.1852
53 3 5 0.2170 0.2170 0.2343 0.2005
62 2 16 0.1810 0.1810 0.2248 0.1810
73 2 14 0.1918 0.1885 0.2152 0.1885
(12 more seeds computed, not listed)
mean2.9 2.2 11.2 0.1916 0.1872 0.2223 0.1865
MDL beats the proposer's end point in 20 of 20 seeds
kMDL within one rule of kbest in 17 of 20 seeds
mean excess error of MDL over oracle 0.0043, of end 0.0350
Show the full program
# Chapter 3. p32: does the shortest total length land near the best
# hold-out error? Twenty seeded replications of p31 (600 training and
# 4000 hold-out records each, illustrative process of p23).
# Per seed: k at minimum total length (MDL), k at minimum hold-out error
# (an oracle nobody has in practice), k where the greedy proposer stops,
# and the hold-out error of each. Means use 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__":
    print(" seed  kMDL kbest kend   errMDL  errbest   errend  ertrue")
    res = []
    cands = candidates()
    tb = [cands.index(((0, 0), (1, 3))), cands.index(((2, 2), (3, 1)))]
    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)
        tot, 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]]))
            tot.append(math.fsum([float(gamma(k + 1)), exc_bits(600, e)]
                                 + rb))
            err.append(errors([i for i, _ in path[:k]], tcov, tpos,
                              tfull) / 4000)
        km = min(range(len(tot)), key=lambda k: (tot[k], k))
        kb = min(range(len(err)), key=lambda k: (err[k], k))
        et = errors(tb, tcov, tpos, tfull) / 4000
        res.append((km, kb, len(path), err[km], err[kb], err[-1], et))
        if s < 8:
            print(" {:>4}  {:>4} {:>5} {:>4}   {:.4f}   {:.4f}   {:.4f}"
                  "  {:.4f}".format(s, *res[-1]))
    print("  (12 more seeds computed, not listed)")
    m = [math.fsum(r[i] for r in res) / len(res) for i in range(7)]
    print("mean  {:>4.1f} {:>5.1f} {:>4.1f}   {:.4f}   {:.4f}   {:.4f}"
          "  {:.4f}".format(*m))
    win = len([r for r in res if r[3] < r[5]])
    near = len([r for r in res if abs(r[0] - r[1]) <= 1])
    print("MDL beats the proposer's end point in {} of 20 seeds".format(win))
    print("kMDL within one rule of kbest in {} of 20 seeds".format(near))
    print("mean excess error of MDL over oracle {:.4f}, of end {:.4f}"
          .format(m[3] - m[4], m[5] - m[4]))

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 3: The Overfitting Curve: Rule Count, Total Description Length and Hold-out Error. 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