关于「与贝叶斯信息准则对账:参数复杂度、归一化最大似然与规则库上的分歧」,《规则库的奥卡姆剃刀》给出的定量结论是什么?

结论:在 150 条记录上,贝叶斯信息准则平均收了 9.5 条规则,留出误差是 0.2512;最小描述长度只收了 1.4 条,误差 0.2218;最优是 2.2 条,误差 0.1951。在 600 条记录上,三者分别是 6.9 条、2.6 条与 2.4 条,误差是 0.1929、0.1849 与 0.1830。贝叶斯信息准则在每一个规模上都比最优多收好几条规则,而且误差也都更高。原因正是上面说的:它只为每条规则付了「一个参数」的钱,却没有为「从 1347 条候选里挑中了这一条」付钱。规则的结构越丰富,这个漏掉的结构代价就越大。

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

English version

对照数据表

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

Nk:MDLBICbesterr:MDLBICbest
1501.49.52.20.22180.25120.1951
3002.48.62.50.19210.23300.1890
6002.66.92.40.18490.19290.1830
12002.86.32.80.18430.18880.1821
24003.87.72.20.18700.19080.1837
查看完整验算程序
# Chapter 4. p42: MDL and BIC choosing the size of the same rule base.
# Process, candidates and greedy proposer as in p23 and p31; training
# size N varies, 4000 hold-out records, 10 seeds per N (illustrative).
#   MDL  two-part length of p21: rule syntax + exception subset
#   BIC  N h(e/N) + ((k + 1) / 2) log2 N: one parameter per rule and one
#        for the exception rate, whatever a rule's syntax
#   best the k with least hold-out error (an oracle)
# Reported: mean k chosen and mean hold-out error (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__":
    cands = candidates()
    print("     N   k:MDL  BIC  best   err:MDL     BIC    best")
    for n in (150, 300, 600, 1200, 2400):
        out = []
        for s in range(10):
            rng = random.Random(20261113 + 100 * s + n)
            tr, te = records(rng, n), records(rng, 4000)
            cov, pos, full = cover_masks(tr, cands)
            tcov, tpos, tfull = cover_masks(te, cands)
            path = greedy_path(cov, pos, full)
            mdl, bic, 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]]))
                mdl.append(math.fsum([float(gamma(k + 1)),
                                      exc_bits(n, e)] + rb))
                p = e / n
                h = 0.0 if p in (0, 1) else -p * math.log2(p) - (
                    1 - p) * math.log2(1 - p)
                bic.append(n * h + (k + 1) / 2 * math.log2(n))
                err.append(errors([i for i, _ in path[:k]], tcov, tpos,
                                  tfull) / 4000)
            km = min(range(len(mdl)), key=lambda k: (mdl[k], k))
            kb = min(range(len(bic)), key=lambda k: (bic[k], k))
            ko = min(range(len(err)), key=lambda k: (err[k], k))
            out.append((km, kb, ko, err[km], err[kb], err[ko]))
        m = [math.fsum(r[i] for r in out) / len(out) for i in range(6)]
        print("  {:>4}  {:>6.1f} {:>4.1f} {:>5.1f}   {:.4f}  {:.4f}  {:.4f}"
              .format(n, *m))

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《最小描述长度原则与规则库奥卡姆剃刀、两部编码判定新规则值不值得入库母典》第 4 章「与贝叶斯信息准则对账:参数复杂度、归一化最大似然与规则库上的分歧」(版本 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}
}

本书其他章节结论