关于「整数也要付费:通用整数码、克拉夫特不等式与例外名单的比特数」,《规则库的奥卡姆剃刀》给出的定量结论是什么?

结论:程序 p13 把四种写法放在 600 条记录与 6,000 条记录两个规模上比较。在 600 条记录、30 条例外时,逐条打标要 600 个比特,列编号要 309 个,枚举码只要 177.1 个,离香农下限 171.8 只差 5.25 个比特。平均到每一条例外,枚举码花 5.90 个比特,列编号花 10.30 个。到了 6,000 条记录、600 条例外,列编号要 7,819 个比特,枚举码只要 2,827.1 个,下限是 2,814.0。

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

English version

对照数据表

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

bits to name the exceptions among N records
Neflagsindexenumbound
60066006550.848.5
60030600309177.1171.8
60060600611288.2281.4
6001206001213441.5433.2
6001806001815539.0528.8
6003006003017612.1600.0
6000606000791491.5484.8
6000300600039171730.01718.4
6000600600078192827.12814.0
600012006000156214346.34331.6
600018006000234215302.35287.7
600030006000390236016.46000.0
N 600, e 30: enum per exception 5.90 bits, index 10.30
enum minus bound at N 600, e 30: 5.25 bits
查看完整验算程序
# Chapter 1. p13: bits to say WHICH of N decision records break the
# rules (the exceptions), four ways:
#   flags   one bit per record                         N
#   index   gamma(e+1) + e * ceil(log2 N)  (list the positions)
#   enum    gamma(e+1) + log2 C(N, e)      (count, then which subset)
#   bound   N h(e/N), the Shannon entropy limit (not a real code)
# N = 600 and 6000 records; e = number of exceptions. Exact arithmetic.
import math


def gamma(n):
    return 2 * (n.bit_length() - 1) + 1


def h2(p):
    if p <= 0 or p >= 1:
        return 0.0
    return -p * math.log2(p) - (1 - p) * math.log2(1 - p)


def costs(n, e):
    index = gamma(e + 1) + e * math.ceil(math.log2(n))
    enum = gamma(e + 1) + math.log2(math.comb(n, e))
    return n, index, enum, n * h2(e / n)


if __name__ == "__main__":
    print("bits to name the exceptions among N records")
    print("     N     e   flags    index     enum    bound")
    for n in (600, 6000):
        for share in (0.01, 0.05, 0.10, 0.20, 0.30, 0.50):
            e = round(n * share)
            f, i, en, b = costs(n, e)
            print("  {:>4}  {:>4}  {:>6}  {:>7}  {:>7.1f}  {:>7.1f}"
                  .format(n, e, f, i, en, b))
    n, e = 600, 30
    f, i, en, b = costs(n, e)
    print("N 600, e 30: enum per exception {:.2f} bits,"
          " index {:.2f}".format(en / e, i / e))
    print("enum minus bound at N 600, e 30: {:.2f} bits".format(en - b))

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《最小描述长度原则与规则库奥卡姆剃刀、两部编码判定新规则值不值得入库母典》第 1 章「整数也要付费:通用整数码、克拉夫特不等式与例外名单的比特数」(版本 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}
}

本书其他章节结论