13 最短的那个程序：奥卡姆剃刀的数学形式

▷ 先猜一下

用不同阶数的字符模型去「从零开始把 2053 个字符传给对方」（模型也从零开始学，边编边学，所以模型不用单独传）。哪个阶数总共花的比特最少？

A 0 阶B 2 阶C 5 阶D 阶数越高越少

先看两个字符串

A: 01010101010101010101010101010101010101010101010101010101010101010101

B: 01101100110100010111010011000101110100101100011101001011010001110100

两串都是 68 位。按第 2 章的熵来算，两串的零阶熵几乎一样（0 和 1 各占一半）。

但你一眼就知道它们不是一回事。

A 可以这么描述：「01 重复 34 遍」。B 呢？好像只能把它整个念一遍。

熵抓不到这个差别，因为熵是关于分布的量——它需要「有一个信息源在按某个概率吐符号」这个设定。而这里我们面对的是两个具体的字符串，没有信息源，没有分布。

1960 年代，Solomonoff、Kolmogorov 和 Chaitin 三个人各自独立地给出了同一个答案：

◆ 柯尔莫哥洛夫复杂度

一个字符串 s 的复杂度 K(s)，是「能输出 s 然后停机的最短程序」的长度。

K(A) ≈ len("print('01' * 34)")        ≈ 几十个比特
K(B) ≈ len("print('0110110011...')")  ≈ 68 + 常数个比特

# A 可以被【压缩成一个规律】。
# B 只能被【原样背下来】。

注意它不需要概率，不需要信息源，不需要「这个字符串是从哪来的」。它是单个对象的性质。

「随机」的终极定义

这个定义顺手解决了一个哲学上很麻烦的问题：什么叫「这个序列是随机的」？

日常语言里我们会说「随机 = 没有规律」，但「没有规律」是什么意思？柯尔莫哥洛夫给的答案干脆利落：

一个字符串是【随机的】，当且仅当
    K(s) ≈ len(s)

# 也就是：描述它的最短办法，就是把它整个写出来。
# 「没有规律」= 「没有比它本身更短的描述」。

而且可以证明：绝大多数长度为 n 的字符串都是随机的。理由又是鸽笼——长度小于 n 的程序只有 2ⁿ − 1 个，而字符串有 2ⁿ 个，所以至少有一个压不动；稍微算细一点，能压缩超过 k 比特的字符串占比不到 2⁻ᵏ。

换句话说：「有规律」是极其罕见的性质。你之所以觉得世界上到处是规律，是因为你只接触到了那个极其特殊的角落。

坏消息：它不可计算

K(s) 是一个定义得很好的数——对每个字符串它都有确定的值。但没有任何程序能算出它。

∑ 为什么不可计算（贝里悖论的程序版）

假设存在一个函数 K(s) 能算出任意字符串的复杂度。那么我可以写这个程序：

def berry(n):
    for s in 按长度和字典序枚举所有字符串:
        if K(s) > n:
            return s        # 第一个复杂度超过 n 的字符串

这个程序本身有多长？大约是 len(berry 的源码) + log₂(n) 比特——因为要把 n 写进去。设它总共 C + log₂ n 比特。

现在取 n 足够大，让 n > C + log₂ n。那么：

berry(n) 输出的那个字符串，按定义它的复杂度 > n；
但它能被一个长度只有 C + log₂ n < n 比特的程序输出，所以它的复杂度 ≤ C + log₂ n < n。

矛盾。所以 K 不可计算。

这个论证的日常版本是贝里悖论：「不能用二十个以内的汉字描述的最小的自然数」——这句话本身只有二十个字，却描述了那个数。

（顺带一提：K 虽然不可计算，但它是上半可计算的——你可以不断尝试越来越短的程序，找到一个就更新上界。你永远不知道自己到没到，但你可以一直往下逼。这正是所有压缩比赛在做的事。）

好消息：它的可算近似很有用

不可计算的东西不能直接用，但可以退一步：不要求「所有可能的程序」，只在一个你能枚举的模型族里找最短的。

这就是最小描述长度原则（MDL），由 Rissanen 在 1978 年提出：

◆ 最小描述长度（MDL）

总描述长度 = L(模型) + L(用这个模型编码数据)

# 选让【总长度】最小的那个模型。

两项在拉锯：

模型越复杂 → L(模型) 越大，但 L(数据|模型) 越小。
模型越简单 → 反过来。

这就是奥卡姆剃刀，只不过「简单」这个模糊的词被换成了「比特数」这个可以算的数。而且它不需要留出集，不需要交叉验证——光看总账就能选模型。

怎么算「模型有多少比特」

这一步是 MDL 最容易做错的地方。直接去数模型有多少个参数、每个参数多少位，会得到一个非常粗糙（而且往往过高）的估计。

有一个更漂亮的做法，叫前置式编码（prequential coding）：

◆ 边编码边学：让模型费用自动进账

模型从零开始。每个字符编码时，它只见过这个字符之前的历史；编完这个字符，再把它学进去。

解码方做完全相同的更新，所以两边永远同步。于是模型根本不需要单独传输——它的成本已经体现在「前面那些字符编得比较贵」里了。

# 开头几个字符很贵（模型什么都不知道，只能均匀猜）
# 越往后越便宜（模型学到东西了）
# 总比特数 = 一个诚实的「模型 + 数据」总账

这个思路叫 prequential principle（Dawid, 1984）。它优雅的地方在于：「学习的代价」和「编码的代价」被合并成了一笔账，不需要人为地把它们分开算。

下面这台就在算这三笔账——训练集、留出集、前置式总账：

三条曲线，三个答案

阶	训练集 bpc	留出集 bpc	前置式总账
0	4.037	4.048	1113 字节
1	2.913	3.013	968 字节
2	1.804	2.087	949 字节 ←最小
3	1.055	1.587	977 字节
4	0.654	1.425	1009 字节
5	0.452	1.412 ←最小	1036 字节
6	0.311	1.431	1058 字节

第一列：永远往下，永远没用

阶数越高，训练集上的表现越好，一路掉到 0.311。这条曲线不会回头，所以它选不出任何东西。用训练集选模型，你永远会选最大的那个。

它掉得这么低的原因很直白：6 阶模型在训练文本里遇到的每个 6 字符上下文，几乎都只出现过一次，而它把那一次的答案记住了。这不叫学会，这叫背下来。

第二列：在阶 5 触底反弹

这是标准的过拟合曲线。阶 5 之后，模型开始学习训练数据里那些不会重现的偶然细节。

第三列：在阶 2 触底，而且不需要留出集

前置式总账在阶 2 最小（949 字节）。它给出的答案和留出集不一样。

◆ 为什么两个答案不同，而且都对

它们回答的是两个不同的问题：

前置式（阶 2）：「我要从零开始把这 2053 个字符传给你，用几阶最省？」
高阶模型学得慢，前面那段学习期的代价很贵，2053 个字符不够摊平它。
留出集（阶 5）：「我已经有这 2053 个字符的训练数据了，对新文本哪一阶最准？」
训练成本已经付过了，不用再算。

关键在于：数据越多，两个答案都会往更高的阶移动。MDL 不是说「简单的模型总是更好」，它说的是「你的数据量决定了你养得起多复杂的模型」。

这也是 scaling law 的一个古老回声：模型规模和数据规模必须匹配。数据不够时把模型堆大，多出来的容量全部拿去背答案了。

✗ 这个直觉是错的

奥卡姆剃刀说「简单的解释更好」，所以应该总是选小模型。 MDL 说的是「模型 + 数据加起来最短的最好」。当数据量增加时，最优模型会变大，不会变小。

这个区别很关键。奥卡姆剃刀不是一条偏爱简单的美学原则，它是一条关于「总描述成本」的记账原则。一个复杂但能把数据压得极小的模型，总账可以比一个简单但压不动的模型更短。

另一个常见误读：「参数多 = 复杂 = 违反奥卡姆」。不对。MDL 关心的是「把模型写下来要多少比特」，不是「有几个数」。一个有一亿个参数但高度规整（可以用一个短程序生成）的模型，描述长度可以很短。这也是为什么深度网络能在参数量远超样本量的情况下不崩溃——这个现象至今仍是活跃的研究话题。

回到第 4 章那个没解决的问题

第 4 章留了一个悬念：「白噪声熵最大，所以白噪声信息量最大」——这句话在信息论里完全正确，而它让人很不舒服。

现在可以正面回答了。柯尔莫哥洛夫复杂度也说白噪声复杂度最高（K(s) ≈ len(s)）。所以这两把尺子都告诉你白噪声「最复杂」，而你的直觉说它「最无聊」。

你的直觉没错，只是它测的是第三样东西。

✎ 术语正名：复杂 ≠ 有意思

有人为「有意思」这件事也造了一个量，叫逻辑深度（logical depth，Bennett 1988）：

不是「最短程序有多长」，而是「那个最短程序要跑多久」。

白噪声：程序很长（就是数据本身），但跑得飞快（print 一下）。→ 深度低。
全零串：程序极短，跑得也快。→ 深度低。
圆周率的前一百万位：程序很短，但要跑很久。→ 深度高。
一个生物的基因组、一本好书、一份运行中的操作系统：程序不算特别长，但「跑出来」需要极长的计算（或者演化）。→ 深度高。

逻辑深度捕捉的是「这个东西凝结了多少计算」。它比熵和复杂度都更接近日常说的「有内容」。

它也不可计算，而且远不如熵好用。但知道它存在很重要——因为它标出了信息论的边界在哪：信息论量的是「有多难描述」，它从来没打算量「有多值得」。把这两件事搞混，是所有信息论误用的源头。

▸ 在现实里：MDL 在你已经用过的地方

AIC / BIC。统计学里选模型用的那两个准则，本质上都是「拟合优度 + 参数个数的惩罚」，而那个惩罚项正是 MDL 里的 L(模型) 的一个近似。BIC 的推导可以直接从 MDL 走出来。
正则化。L2 正则等价于「参数服从高斯先验」，而按第 10 章那个换算，先验的负对数就是编码长度。所以 loss + λ‖w‖² 字面上就是 L(数据|模型) + L(模型)。你每天写的那个 weight decay，是 MDL 的一个特例。
决策树剪枝。用 MDL 判断一个分支值不值得留：这个分支让数据编码省下的比特，够不够付「描述这个分支」的比特。
贝叶斯模型选择。贝叶斯证据（evidence）的负对数，和 MDL 的总描述长度在很多设定下是同一个东西。「贝叶斯」和「MDL」这两派看起来在吵架，其实经常在算同一个积分。

◇ 结账

B：2 阶，949 字节

选 D 的人抓的是「模型越强越好」——那在训练集上永远对，在总账上从阶 3 就开始亏。

选 C 的人抓的是「留出集上最好的那个阶」——那是另一个问题的正确答案（阶 5），但不是这个问题的。

这一题真正的价值在于：同一份数据、同一族模型，问法不同答案就不同，而两个答案都是对的。「哪个模型最好」从来不是一个完整的问题——必须先说清楚，你要付的是哪一笔账。

这一章的一句话

柯尔莫哥洛夫复杂度是「最短程序有多长」，它定义了随机，也不可计算。它的可算近似 MDL 说：最好的模型是让「模型 + 数据」总共最短的那个——这就是奥卡姆剃刀，换成了比特。

卷 III 结束。前十三章有一个共同的前提，而它是假的：我们假设比特能被完好无损地送到对面。

卷 IV 把这个前提拿掉。现实里的线路会翻位、会丢包、会被宇宙射线打中。下一章我们把十分之一的比特翻掉，看会发生什么——然后你会遇到 1948 年那句最反直觉的话。