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

Nk:MDLBICbesterr:MDLBICbest
1501.49.52.20.22180.25120.1951
3002.48.62.50.19210.23300.1890
6002.66.92.40.18490.19290.1830
12002.86.32.80.18430.18880.1821
24003.87.72.20.18700.19080.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