欢迎大家提Issue反馈问题或建议，建设推理王国！
推理王国

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

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

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

这章要打开这个黑盒。

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

答案的关键词是压缩。

21.0 压缩侦探游戏：从样本反推出规律 ​

学习不是把数据背下来。背下来太容易，也太没用。真正的学习像侦探破案：桌上有一堆线索，你要找出一条比线索本身更短的解释。

游戏开始时，自然给你一串样本：

S={(x1,y1),(x2,y2),…,(xn,yn)}

你可以提交一个假设 h。这个假设必须做两件事：第一，它要解释已经看到的数据；第二，它本身不能太长。因为最愚蠢的“规律”永远存在：把所有样本逐条背下来。这样的规律训练误差为零，但没有任何泛化能力。

压缩侦探的评分规则是：

L(h)+L(S∣h)

前一项是描述假设本身要多少比特，后一项是在假设给定后还需要多少比特描述数据。最好的假设，不是最复杂的，也不是最贴合训练集的，而是让总描述长度最短的那个。

这个游戏的形式化骨架
  • 状态空间：样本集 S、假设类 H、编码方案 L。
  • 合法动作：选择一个假设 h∈H，并用它压缩数据。
  • 转移规则：从观测样本反推候选规律，比较 L(h)+L(S∣h)。
  • 胜利条件：找到能压缩训练数据、并对未见样本保持低误差的假设。
  • 失败模式：死记硬背样本；或选择过强归纳偏置，把世界压缩成错误形状。

这个游戏把泛化的秘密说得很直白：能泛化，是因为你发现了可压缩结构。如果数据完全随机，就没有短规律可找；如果你找到了一条短规律解释大量样本，那么它很可能抓住了某种真实结构。

但这里也有危险。压缩需要编码方案，编码方案就是归纳偏置。你以为自己在“从数据中学习”，其实你一直带着一把剃刀进场：什么算简单，什么算复杂，早就由你的表示系统决定了。

压缩侦探游戏的冷酷之处在于：没有偏置，就没有学习。完全中立的学习者只能背诵样本；想泛化，就必须偏爱某些规律。机器学习课喜欢把这叫“模型选择”。说得太轻了。这其实是在选择你愿意相信世界长什么样。

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 复杂度：用"压缩程序的长度"衡量复杂度（前人工作：Kolmogorov, 1965）

Kolmogorov 复杂度 K(x) 是对"这个对象有多复杂"的数学化定义——复杂度等于描述它所需的最短程序的长度。

直觉例子：

  • "前一百万个自然数" → 一段很短的程序就够了（for i in range(1000000): print(i)），K 很小
  • 随机生成的一百万位数字 → 没有比"把数字本身列出来"更短的描述，K≈ 字符串长度

重要的不可计算性：K(x) 是不可计算的——不存在算法能对任意 x 计算出 K(x) 的精确值（这是停机问题的推论）。你只能计算它的上界（找到一个能生成 x 的程序，其长度就是上界）。

为什么仍然有用？ 即使不可计算，Kolmogorov 复杂度提供了一个理论标准——衡量"简单性"的绝对基准。实践中用 MDL 近似（用实际的压缩算法代替最短程序）。

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

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

最优假设=arg⁡minh[L(h)+L(数据∣h)]

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

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

arg⁡maxhP(h∣数据)=arg⁡maxh[P(数据∣h)⋅P(h)]=arg⁡minh[L(数据∣h)+L(h)]

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

21.3 泛化就是压缩 ​

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

为什么？

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

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

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

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

这个问题在理论界一度是个谜：深度神经网络的参数数量往往超过训练数据量，按照传统学习理论，这样的模型应该严重过拟合。但实践中它们往往泛化良好。MDL 的视角给出了一个方向：衡量泛化能力的不是参数数量，而是模型实际使用的"有效描述长度"——一个有一百亿参数但参数之间高度结构化的模型，其有效描述长度可能远小于参数数量。压缩才是关键，不是规模。但是随着深度学习学术社区的发现，但值得一提的是，前面的描述更多的是经典深度表示学习的方法，在大语言模型以及现代神经网络的训练中不一定是Gold标准。在2023年以后，我们的深度学习的数据与参数配比更多的是强调过度训练，也就是说，参数量一定的情况下，我们会倾注于百倍甚至千倍的数据量来训练相同规模的神经网络。最新研究发现，过度训练是深度学习以及大语言模型有效泛化的有效形式。

21.4 归纳偏置的选择 ​

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

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

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

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

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

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

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

21.5 逆推断的两个困难 ​

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

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

第二个困难：分布偏移。PAC 学习假设训练数据和测试数据来自同一分布 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 在实践中被使用，用的是可计算的近似版本。试着列出至少两种可计算的"描述长度"近似方案，并分析：每种近似相当于隐含了什么样的归纳偏置？不同的近似方案，什么时候会给出不同的"最优假设"？

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