第21章：学习作为逆推断——泛化是压缩的另一种说法

模型"学到了东西"的形式含义是：它找到了更短的描述。

---

第20章结尾留下了一个问题：启发函数能否自动从数据里发现？PAC 学习保证了学习的可能性，但没有说学习是什么——它只是描述了一个黑盒，告诉你黑盒的输出有什么性质。

这章要打开这个黑盒。

学习，在最抽象的意义上，是从一批观测——例子、数据、经验——中推断出一个可以泛化的规律。这个推断过程，如果要有形式的含义，就必须回答：推断出的规律，相比观测本身，多了什么？少了什么？它为什么能从见过的例子，说出没见过的例子的事情？

答案的关键词是压缩。

---

21.1 学习的逆问题结构

形式逻辑里，推断的方向是从公理到定理：给定前提，推出结论。这是正向推断。

学习的方向正好相反：给定一批定理（观测到的事实），反推最可能的公理集合（规律）。这是逆推断——从结果往回推原因。

这个逆向结构有一个根本性的困难：它是欠定的（underdetermined）。一批有限的观测，通常与无数个不同的规律兼容。你看到太阳每天升起，这与"太阳每天升起"这条规律兼容，也与"太阳每天升起，除了2035年3月17日"兼容，还与无数个其他规律兼容。

这个困难没有纯粹逻辑的解决方案。你无法从观测中演绎出唯一正确的规律。你需要某种归纳偏置（inductive bias）——一种对规律的先验偏好，在所有兼容观测的规律中，偏向某一类。

归纳偏置是什么，决定了学习是什么。

兔狲教授评

归纳偏置不是技术选项，是形而上学承诺。你选了线性模型，你就在承认"规律是线性的"；你选了深度网络，你就在承认某种关于特征层级的结构假设。大多数机器学习课把这件事叫做"调超参数"，把形而上学承诺藏进了工程操作里。这是在逃避一个真实的问题，不是在解决它。

---

21.2 奥卡姆剃刀的形式化

最古老、最直觉的归纳偏置，是奥卡姆剃刀：更简单的解释优先。

但"简单"是什么意思？

Kolmogorov 复杂度给出了一个回答。

定义（Kolmogorov 复杂度）：字符串 $x$ 的 Kolmogorov 复杂度 $K(x)$ 是能生成 $x$ 的最短程序的长度（以某个固定通用图灵机为参考）。

$K(x)$ 衡量的是 $x$ 的内在复杂度——不是 $x$ 有多长，而是 $x$ 有多难描述。一个全是零的字符串"000...0"（一百万个零）的 $K$ 值很小——有一个很短的程序可以生成它（"输出一百万个零"）。一个随机字符串的 $K$ 值大约等于它的长度——没有比"把字符串本身列出来"更短的描述。

在这个语言里，"简单"就是"Kolmogorov 复杂度小"，"更简单的解释优先"就是"选择 $K$ 值更小的规律"。

这就是最小描述长度（Minimum Description Length，MDL）原理的核心：

$$\text{最优假设}=\arg \underset{h}{min}[L(h)+L(\text{数据}\mid h)]$$

$L(h)$ 是描述假设 $h$ 本身所需的比特数，$L(\text{数据}\mid h)$ 是在假设 $h$ 下描述数据所需的额外比特数。最优假设是让"假设 + 数据在假设下的编码"总长度最短的那个。

MDL 和贝叶斯的等价性

MDL 原理和贝叶斯推断是同一件事的两种语言。若假设 $h$ 的先验概率 $P(h)\propto 2^{-L(h)}$（即较短的假设有更高先验，Shannon 编码的标准形式），则最大后验估计（MAP）恰好等价于 MDL：

$$\arg \underset{h}{max}P(h\mid \text{数据})=\arg \underset{h}{max}[P(\text{数据}\mid h)\cdot P(h)]=\arg \underset{h}{min}[L(\text{数据}\mid h)+L(h)]$$

奥卡姆剃刀，在贝叶斯语言里是先验对简单性的偏好；在 MDL 语言里是最短描述长度的选择。两者是等价的数学结构，穿着不同的衣服。

---

21.3 泛化就是压缩

MDL 原理揭示了一个深刻的等价：泛化能力等价于压缩能力。

为什么？

一个假设 $h$ 能泛化，意味着它捕捉到了数据里的规律，而不是记住了噪声。规律是可以被简洁描述的结构，噪声是不能被压缩的随机成分。如果 $h$ 能用少于数据本身长度的描述来"解释"数据，说明 $h$ 真正压缩了数据——发现了数据中可以被简洁捕捉的部分。

反过来，一个完全记忆训练数据的模型，没有压缩——它只是把数据原封不动地存了下来。这样的模型在训练数据上表现完美，但对新数据没有预测能力，因为它没有发现任何规律，只是储存了例子。

这正是第5章（上卷）"过拟合"的形式化：过拟合是没有压缩的记忆，泛化是有效的压缩。

用 Kolmogorov 复杂度的语言，泛化的量可以被度量：假设把训练数据从 $n$ 比特压缩到了 $k$ 比特（$k<n$），那么压缩率 $n/k$ 在某种意义上衡量了假设的"泛化潜力"——发现了多少可以泛化的规律，而不是记住了多少特例。

为什么深度神经网络能泛化

这个问题在理论界一度是个谜：深度神经网络的参数数量往往超过训练数据量，按照传统学习理论，这样的模型应该严重过拟合。但实践中它们往往泛化良好。MDL 的视角给出了一个方向：衡量泛化能力的不是参数数量，而是模型实际使用的"有效描述长度"——一个有一百亿参数但参数之间高度结构化的模型，其有效描述长度可能远小于参数数量。压缩才是关键，不是规模。

---

21.4 归纳偏置的选择

MDL 和 Kolmogorov 复杂度给出了一个优雅的框架，但有一个实际问题：Kolmogorov 复杂度是不可计算的。

兔狲教授评

所以奥卡姆剃刀，在最严格的形式下，本身是不可判定的。你无法写一个算法，对任意两个假设，总是在有限时间内找出哪个更简单。"简单"这个词背后，藏着一个停机问题。这不妨碍你用 MDL 的近似——但你得知道你用的是近似，不是真正的剃刀。

给定一个字符串 $x$，计算 $K(x)$ 需要找到最短的能生成 $x$ 的程序——这等价于解决停机问题，第19章已经证明这是不可判定的。你无法写一个算法，对任意输入在有限时间内计算出它的 Kolmogorov 复杂度。

这意味着 MDL 在最纯粹的形式下，本身就是不可计算的。实践中的 MDL 是它的近似版本：用某个固定的编码方案替代通用图灵机，用可计算的描述长度替代不可计算的 Kolmogorov 复杂度。

不同的近似方案，对应不同的归纳偏置：

• 决策树学习：假设空间是决策树，描述长度是树的深度或节点数。偏向小树，即简单的决策规则。
• 线性模型：假设空间是线性函数，描述长度是系数的范数。L1正则化偏向稀疏系数（大多数系数为零），L2正则化偏向小系数。
• 神经网络：假设空间是特定架构的网络，"描述长度"由参数值和网络结构共同决定。这个描述长度很难精确定义，理论和实践之间有巨大的空白。

每一种学习算法，都在隐含地选择一种归纳偏置，一种对"什么是简单"的理解。这个选择，在绝大多数机器学习课程里，以"超参数调节"的名义被处理——但它实际上是关于"什么样的规律是优先的"的形而上学承诺。

---

21.5 逆推断的两个困难

学习作为逆推断，面临两个根本困难，都无法被数据本身解决。

第一个困难：欠定性。如上所述，有限数据与无限多个假设兼容，必须有归纳偏置才能从中选择。归纳偏置是输入的，不是从数据里推断出来的。学习问题的解，依赖于假设空间的选择——而假设空间的选择，不在学习算法的管辖范围之内。

第二个困难：分布偏移。PAC 学习假设训练数据和测试数据来自同一分布 $\mathcal{D}$。但在实际应用里，这个假设经常被违反——训练时的数据分布和部署时的数据分布可能不同。当分布偏移发生，任何基于训练数据的泛化保证都可能失效。

这两个困难，是学习理论的根本限制，不是算法的缺陷。它们说明：任何学习系统，都在某些假设下工作，假设之外，保证消失。

这个结构，和第14章的形式系统高度相似：形式系统在公理之内是可靠的，公理之外没有保证；学习系统在假设之内是可靠的，假设之外没有保证。两者的可靠性，都依赖于一个不可从内部验证的外部承诺。

---

21.6 学习与推断的统一图景

把这一章的内容放在下卷的框架里看。

第14章建立了推断的句法机器。第15章发现这台机器有内在的限制——某些真命题无法从内部证明。第16章修改了一条结构规则，得到一种新的推断。第17章把真值扩张到 $[0,1]$，得到概率推断。第18章引入干预算子，得到因果推断。第19章发现这些推断的计算代价有根本的下界。第20章在代价约束下，精确地定义了"足够好"。

第21章做的事情是：把"学习"嵌入这个框架。学习是逆推断——从观测出发，反推规律。MDL 原理给出了逆推断的基本原则：最短的解释。PAC 框架给出了逆推断的质量保证：以高概率近似正确。

但这个统一图景还差最后一块：当推断系统足够大、足够复杂，它的"推断"开始包含关于自身的命题——关于自身能学什么、不能学什么、自身的归纳偏置是什么。这时，第15章的哥德尔结构重新出现：一个足够强的推断系统，无法完全推断自身。

这是第22章的入口。

---

悬而未决

Kolmogorov 复杂度不可计算，那 MDL 有意义吗？ Kolmogorov 复杂度的不可计算性意味着它是一个理想，不是一个算法。但数学里充满了这样的理想：最优决策、完美信息、无穷精度。理想不需要可计算，它需要的是作为标杆——告诉我们实际算法离最优有多远。MDL 的可计算近似，是对这个理想的有限逼近，理想本身的存在，使"逼近"这个词有意义。

泛化真的等价于压缩吗？ MDL 框架暗示：一个不能压缩训练数据的模型不会泛化，能压缩的模型会泛化。但这个等价在深度学习的实践里并不总是成立——有些大规模模型在"记忆"数据的同时也能泛化良好。这个张力指向一个未解的理论问题：深度学习的泛化机制，究竟是什么？

归纳偏置能被学习吗？ 如果学习是逆推断，那么"什么样的假设空间是好的"这件事，能不能也被学习？元学习（meta-learning）尝试在任务分布上学习一个好的归纳偏置，让模型在新任务上更快适应。但元学习本身也有归纳偏置——这是一个无穷退回，还是在某个层次上可以停止？

---

思考题

★ 热身

以下两个字符串，哪个的 Kolmogorov 复杂度更低？只需给出直觉判断和一句话理由，不需要计算具体数值。

1. 0101010101010101010101010101010101010101（40个字符，01交替）
2. 1101001000011010110101010001010001000010（40个随机字符）

再想一个问题：一个"完全随机"的字符串，它的 Kolmogorov 复杂度大约是多少？和字符串本身的长度相比如何？

---

★★ 推导

1. 压缩与泛化：一个模型在训练集上零误差，但测试集误差很大（过拟合）；另一个在训练集上误差5%，测试集也是5%（良好泛化）。用 MDL 的语言描述差异：哪个压缩了数据？哪个在记忆数据？"过拟合模型的描述长度"和"泛化模型的描述长度"各自包含什么？

2. 归纳偏置的显化：线性回归、决策树、神经网络（带L2正则化）三种学习算法，分别隐含了什么归纳偏置？用"什么样的规律被优先选择"来描述。每种偏置在什么类型的数据上会系统性地失败？

---

★★★ 挑战

Kolmogorov 复杂度不可计算（因为它等价于停机问题）。这意味着：没有算法能对任意两个假设，在有限时间内判断哪个更简单。

但 MDL 在实践中被使用，用的是可计算的近似版本。试着列出至少两种可计算的"描述长度"近似方案，并分析：每种近似相当于隐含了什么样的归纳偏置？不同的近似方案，什么时候会给出不同的"最优假设"？

这个问题的目的是：把"超参数选择"翻译成"归纳偏置选择"，再翻译成"对什么叫简单的隐含承诺"——三层翻译做完，说说你对机器学习"客观性"的看法有没有变化。