关于「过拟合曲线:规则数、总描述长度与留出误差的三条线」,《规则库的奥卡姆剃刀》给出的定量结论是什么?
结论:第三章画出过拟合曲线:训练例外一路下降,留出误差却从 0.1973 回升到 0.2333;二十次重复中,按最短总长度停下的规则库留出误差 0.1916,不设门槛时 0.2223。
数据口径:书中的决策记录全部合成、参数均为示意,全部计算由书中程序生成;本书是非个人化的经营分析,不构成经营建议。 第二章建立两部编码账本:一条准确率超过八成、却只净修正 7 条例外的窄规则挣不回自己的篇幅;在合成台账上,门槛从提议者的 12 条规则中只放进 3 条,第三条的余量仅 2.9 个比特。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.1916, 0.1973, 0.2223, 0.2333
| seed kMDL kbest kend errMDL errbest errend ertrue | |
| 0 | 3 2 12 0.2047 0.1973 0.2333 0.1973 |
| 1 | 4 5 10 0.1895 0.1890 0.2100 0.1903 |
| 2 | 2 2 10 0.1785 0.1785 0.2072 0.1785 |
| 3 | 2 2 11 0.1790 0.1790 0.2295 0.1790 |
| 4 | 2 2 18 0.1852 0.1852 0.2507 0.1852 |
| 5 | 3 3 5 0.2170 0.2170 0.2343 0.2005 |
| 6 | 2 2 16 0.1810 0.1810 0.2248 0.1810 |
| 7 | 3 2 14 0.1918 0.1885 0.2152 0.1885 |
| (12 more seeds computed, not listed) | |
| mean | 2.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 |
查看完整验算程序
# 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]))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《最小描述长度原则与规则库奥卡姆剃刀、两部编码判定新规则值不值得入库母典》第 3 章「过拟合曲线:规则数、总描述长度与留出误差的三条线」(版本 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}
}