关于「编码方案敏感度:六种合理的码,六种裁决,余量要留多少比特」,《规则库的奥卡姆剃刀》给出的定量结论是什么?

结论:第五章做编码方案敏感度:六种合理的码在二十次重复中没有一次选出相同的规则数,余量不足 4 个比特的裁决全部随编码翻转,16 个比特的余量下限使全部入库裁决不再翻转。

数据口径:书中的决策记录全部合成、参数均为示意,全部计算由书中程序生成;本书是非个人化的经营分析,不构成经营建议。 第二章建立两部编码账本:一条准确率超过八成、却只净修正 7 条例外的窄规则挣不回自己的篇幅;在合成台账上,门槛从提议者的 12 条规则中只放进 3 条,第三条的余量仅 2.9 个比特。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 16

greedy steps examined: 223
|SE margin|stepsflipsflip share
0 to 426261.000
4 to 16155780.503
16 to 644200.000
64 to inf000.000
slack dmean kmean holdoutadmitted steps all codes back
02.900.191643 of 58
42.450.190543 of 49
82.350.190243 of 47
162.100.190142 of 42
321.700.202334 of 34
640.000.27520 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}
}

本书其他章节结论