关于「剪枝器的入库门槛:只查重复的门与描述长度的门」,《规则库的奥卡姆剃刀》给出的定量结论是什么?

结论:第六章把门槛搬到跨卷公理剪枝器上:只查重复的门收进 46 条规则,留出误差 0.4155,描述长度门只收 2 条真规则。

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

English version

对照数据表

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

proposals: true 2, dup 4, spec 8, pocket 12, noise 24
gatetrue dup spec pocket noiserulesL(total) holdout
G0 text2081224461194.30.4155
G1 MDL200002432.00.1973
G2 MDL+16200002432.00.1973
查看完整验算程序
# Chapter 6. p61: three admission gates facing one stream of proposals.
# Ledger: the 600 seeded training records of p23; 4000 hold-out records.
# 50 proposals arrive in a seeded order (illustrative mix):
#   true   the 2 rules of the generating process
#   dup    4 verbatim repeats of a true rule (the first copy to
#          arrive is counted as true)
#   spec   8 true rules with one extra condition (narrower copies)
#   pocket 12 three-condition rules inside rg=4 (act rate 0.45) that
#          happen to show a net gain on the training ledger
#   noise  24 random two- or three-condition rules
# Gates, applied one proposal at a time against the admitted base:
#   G0 text gate: reject only an exact repeat of an admitted rule
#   G1 MDL gate: admit if two-part length falls (margin > 0)
#   G2 MDL gate with slack: margin > 16 bits (p52)
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 length(rules, cands, cov, pos, full, n):
    e = errors(rules, cov, pos, full)
    return math.fsum([float(gamma(len(rules) + 1)), exc_bits(n, e)]
                     + [rule_bits(cands[i]) for i in rules])


def stream(rng, cands, cov, pos, full):
    tb = [cands.index(((0, 0), (1, 3))), cands.index(((2, 2), (3, 1)))]
    out = [("true", i) for i in tb] + [("dup", tb[j % 2])
                                       for j in range(4)]
    spec = [i for i, r in enumerate(cands) if len(r) == 3 and any(
        set(cands[t]) < set(r) for t in tb)]
    out += [("spec", i) for i in rng.sample(spec, 8)]
    pocket = []
    for i, r in enumerate(cands):
        if len(r) == 3 and (5, 4) in r and not any(
                set(cands[t]) < set(r) for t in tb):
            c = cov[i] & ~(cov[tb[0]] | cov[tb[1]])
            if (c & pos).bit_count() > (c & ~pos).bit_count():
                pocket.append(i)
    out += [("pocket", i) for i in rng.sample(pocket, 12)]
    noise = [i for i, r in enumerate(cands) if len(r) > 1]
    out += [("noise", i) for i in rng.sample(noise, 24)]
    rng.shuffle(out)
    seen = set()
    for j, (kind, i) in enumerate(out):
        if kind in ("true", "dup"):
            out[j] = ("dup" if i in seen else "true", i)
            seen.add(i)
    return out


if __name__ == "__main__":
    rng = random.Random(20261113)
    tr, te = records(rng, 600), records(rng, 4000)
    cands = candidates()
    cov, pos, full = cover_masks(tr, cands)
    tcov, tpos, tfull = cover_masks(te, cands)
    props = stream(random.Random(20261114), cands, cov, pos, full)
    kinds = ("true", "dup", "spec", "pocket", "noise")
    print("proposals: " + ", ".join("{} {}".format(
        k, len([1 for t, _ in props if t == k])) for k in kinds))
    print("gate      true dup spec pocket noise  rules  L(total) holdout")
    for gate, d in (("G0 text", None), ("G1 MDL", 0.0),
                    ("G2 MDL+16", 16.0)):
        base, got = [], []
        for kind, i in props:
            if d is None:
                ok = i not in base
            else:
                now = length(base, cands, cov, pos, full, 600)
                new = length(base + [i], cands, cov, pos, full, 600)
                ok = now - new > d
            if ok:
                base.append(i)
                got.append(kind)
        cnt = [len([1 for g in got if g == k]) for k in kinds]
        print("{:<9} {:>4} {:>3} {:>4} {:>6} {:>5}  {:>5}  {:>8.1f}"
              "  {:.4f}".format(gate, *cnt, len(base),
                                length(base, cands, cov, pos, full, 600),
                                errors(base, tcov, tpos, tfull) / 4000))

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《最小描述长度原则与规则库奥卡姆剃刀、两部编码判定新规则值不值得入库母典》第 6 章「剪枝器的入库门槛:只查重复的门与描述长度的门」(版本 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}
}

本书其他章节结论