关于「编码方案敏感度:六种合理的码,六种裁决,余量要留多少比特」,《规则库的奥卡姆剃刀》给出的定量结论是什么?
结论:第五章做编码方案敏感度:六种合理的码在二十次重复中没有一次选出相同的规则数,余量不足 4 个比特的裁决全部随编码翻转,16 个比特的余量下限使全部入库裁决不再翻转。
数据口径:书中的决策记录全部合成、参数均为示意,全部计算由书中程序生成;本书是非个人化的经营分析,不构成经营建议。 第二章建立两部编码账本:一条准确率超过八成、却只净修正 7 条例外的窄规则挣不回自己的篇幅;在合成台账上,门槛从提议者的 12 条规则中只放进 3 条,第三条的余量仅 2.9 个比特。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 16
| greedy steps examined: 223 | |||
| |SE margin| | steps | flips | flip share |
| 0 to 4 | 26 | 26 | 1.000 |
| 4 to 16 | 155 | 78 | 0.503 |
| 16 to 64 | 42 | 0 | 0.000 |
| 64 to inf | 0 | 0 | 0.000 |
| slack d | mean k | mean holdout | admitted steps all codes back |
| 0 | 2.90 | 0.1916 | 43 of 58 |
| 4 | 2.45 | 0.1905 | 43 of 49 |
| 8 | 2.35 | 0.1902 | 43 of 47 |
| 16 | 2.10 | 0.1901 | 42 of 42 |
| 32 | 1.70 | 0.2023 | 34 of 34 |
| 64 | 0.00 | 0.2752 | 0 of 0 |
查看完整验算程序
# Chapter 5. p52: how much slack makes an admission verdict code-proof?
# For every step of the greedy path in 20 seeds of p31, the margin
# (bits saved minus bits spent) is computed under the six codes of p51.
# A verdict "flips" when some codes say admit and others say reject.
# Then the gate "admit while the SE margin exceeds d bits" is run for
# several slacks d; Cohen's RIPPER (1995) used 64 bits in a related
# stopping rule. Illustrative records; means by 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()
def total(code, k, rules, n, e, ncand):
rc = {"S": [rule_bits(r) for r in rules],
"U": [math.log2(ncand)] * k,
"F": [8.0 + 8 * len(r) for r in rules]}[code[0]]
if code[1] == "E":
ex = exc_bits(n, e)
else:
ex = gamma(e + 1) + e * math.ceil(math.log2(n))
return math.fsum([float(gamma(k + 1)), ex] + rc)
if __name__ == "__main__":
cands = candidates()
codes = [a + b for a in "SUF" for b in "EI"]
steps, runs = [], []
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)
es, e = [(pos & full).bit_count()], (pos & full).bit_count()
for _, g in path:
e -= g
es.append(e)
tl = {c: [total(c, k, [cands[i] for i, _ in path[:k]], 600,
es[k], len(cands)) for k in range(len(es))]
for c in codes}
for k in range(1, len(es)):
steps.append([tl[c][k - 1] - tl[c][k] for c in codes])
runs.append((path, tl["SE"], tcov, tpos, tfull))
print("greedy steps examined: {}".format(len(steps)))
print(" |SE margin| steps flips flip share")
for lo, hi in ((0, 4), (4, 16), (16, 64), (64, 10 ** 9)):
b = [m for m in steps if lo <= abs(m[0]) < hi]
f = len([m for m in b if min(m) <= 0 < max(m)])
print(" {:>4} to {:<5} {:>6} {:>6} {:>10.3f}".format(
lo, "inf" if hi > 10 ** 6 else hi, len(b), f,
f / len(b) if b else 0.0))
print(" slack d mean k mean holdout admitted steps all codes back")
for d in (0, 4, 8, 16, 32, 64):
ks, er, ok, tot = [], [], 0, 0
for path, tl, tcov, tpos, tfull in runs:
k = 0
while k < len(path) and tl[k] - tl[k + 1] > d:
k += 1
ks.append(k)
er.append(errors([i for i, _ in path[:k]], tcov, tpos,
tfull) / 4000)
idx = 0
for (path, tl, _, _, _), k in zip(runs, ks):
for j in range(len(path)):
if j < k:
tot += 1
ok += 1 if min(steps[idx + j]) > 0 else 0
idx += len(path)
print(" {:>7} {:>6.2f} {:>12.4f} {:>9} of {}".format(
d, math.fsum(ks) / 20, math.fsum(er) / 20, ok, tot))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《最小描述长度原则与规则库奥卡姆剃刀、两部编码判定新规则值不值得入库母典》第 5 章「编码方案敏感度:六种合理的码,六种裁决,余量要留多少比特」(版本 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}
}