关于「过拟合曲线:规则数、总描述长度与留出误差的三条线」,《规则库的奥卡姆剃刀》给出的定量结论是什么?

结论:第三章画出过拟合曲线:训练例外一路下降,留出误差却从 0.1973 回升到 0.2333;二十次重复中,按最短总长度停下的规则库留出误差 0.1916,不设门槛时 0.2223。

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

English version

对照数据表

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

seed kMDL kbest kend errMDL errbest errend ertrue
03 2 12 0.2047 0.1973 0.2333 0.1973
14 5 10 0.1895 0.1890 0.2100 0.1903
22 2 10 0.1785 0.1785 0.2072 0.1785
32 2 11 0.1790 0.1790 0.2295 0.1790
42 2 18 0.1852 0.1852 0.2507 0.1852
53 3 5 0.2170 0.2170 0.2343 0.2005
62 2 16 0.1810 0.1810 0.2248 0.1810
73 2 14 0.1918 0.1885 0.2152 0.1885
(12 more seeds computed, not listed)
mean2.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}
}

本书其他章节结论