关于「与贝叶斯信息准则对账:参数复杂度、归一化最大似然与规则库上的分歧」,《规则库的奥卡姆剃刀》给出的定量结论是什么?
结论:在 150 条记录上,贝叶斯信息准则平均收了 9.5 条规则,留出误差是 0.2512;最小描述长度只收了 1.4 条,误差 0.2218;最优是 2.2 条,误差 0.1951。在 600 条记录上,三者分别是 6.9 条、2.6 条与 2.4 条,误差是 0.1929、0.1849 与 0.1830。贝叶斯信息准则在每一个规模上都比最优多收好几条规则,而且误差也都更高。原因正是上面说的:它只为每条规则付了「一个参数」的钱,却没有为「从 1347 条候选里挑中了这一条」付钱。规则的结构越丰富,这个漏掉的结构代价就越大。
数据口径:书中的决策记录全部合成、参数均为示意,全部计算由书中程序生成;本书是非个人化的经营分析,不构成经营建议。 第二章建立两部编码账本:一条准确率超过八成、却只净修正 7 条例外的窄规则挣不回自己的篇幅;在合成台账上,门槛从提议者的 12 条规则中只放进 3 条,第三条的余量仅 2.9 个比特。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 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 |
查看完整验算程序
# 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))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《最小描述长度原则与规则库奥卡姆剃刀、两部编码判定新规则值不值得入库母典》第 4 章「与贝叶斯信息准则对账:参数复杂度、归一化最大似然与规则库上的分歧」(版本 1.0.0). 5D Library. DOI 待发布
DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 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}
}