极客教育30u30 中文导读
30u30 中文导读 / 30 天目录 / 第 5 天

第 5 天 · 谁能把数据压得最短，谁就是更好的模型

第 1 单元A Tutorial Introduction to the Minimum Description Length PrinciplePeter GrünwaldarXiv（后作为 MIT Press 2005 年文集 Advances in Minimum Description Length 的前 2 章出版） · 2004
这是导读，不是翻译。先用 10 分钟拿到这篇论文的思想地图，再去读 原论文 →，去原仓库的 05_MDL_Principle/ 目录 → 动手写代码。
给孩子讲：这一天有 10 岁孩子能听懂的讲义，带猜字游戏和动手活动，可打印。打开儿童讲义 → · PDF 简体 · PDF 繁體

一句话

Grünwald 用 80 页、2 章的篇幅系统讲解最小描述长度原则：数据中的任何规律都能用来压缩数据，所以学习就是寻找最短编码。教程从直观的两部分编码讲到精炼 MDL 的通用编码与参数复杂度，并说明 MDL 怎样在拟合度与复杂度之间自动取舍。

论文讲了什么

核心思想：学习 = 压缩。任何规律都能用来缩短数据的描述。9000 个字符的“abcabc……abc”可以写成“abc 重复 3000 次”，非常短。9000 次掷骰子的结果没有规律，最短描述几乎就是它本身。MDL 主张：在候选模型中，选能把数据描述得最短的那个。

为什么不直接用 Kolmogorov 复杂度？理想的最短描述是 Kolmogorov 复杂度（Kolmogorov complexity），即输出数据的最短程序长度。它不可计算，而且依赖编程语言带来的常数差。实用 MDL 改用受限的编码类：只在给定的模型族里找最短编码，结果可以计算。

编码与概率是一回事。根据 Kraft 不等式（Kraft inequality），每个前缀码对应一个概率分布，反过来也成立。编码长度 L(x) = -log2 P(x)。概率高的数据，编码短。这一条把“压缩”和“统计建模”变成同一个问题。

粗糙 MDL：两部分编码。对每个假设 H，计算 L(H) + L(D|H)：

教程用多项式拟合做贯穿全文的例子。1 阶多项式便宜但拟合差。阶数等于样本数减 1 的多项式能穿过每个点，但它把噪声也记了下来。总长度最短的模型落在中间。

精炼 MDL：通用编码。两部分编码中 L(H) 的写法有任意性。精炼 MDL（refined MDL）把整个模型族当成一个编码，要求它对族里每个分布都“差不多一样好”。这叫通用编码（universal code）。教程介绍了 4 种构造：

用 NML 时，数据的编码长度叫随机复杂度（stochastic complexity）：-log2 P(D|θ̂) + COMP。COMP 是参数复杂度（parametric complexity），衡量模型族能把多少种数据集都拟合好。对 k 个参数、n 个样本的常见模型族，COMP ≈ (k/2) log2 n + 常数，主项和 BIC 的惩罚项相同。

哲学立场。MDL 不假设存在“真实模型”。它只问哪个模型压缩数据最好。所以候选模型全都是错的时候，MDL 仍然有清楚的含义。

关键概念

两部分编码（two-part code）
先发送模型，再发送借助模型编码的数据，总长度为 L(H) + L(D|H)。模型越复杂，第一部分越长、第二部分越短，MDL 选总和最小的点。
Kraft 不等式（Kraft inequality）
前缀码的码长必须满足 Σ 2^(-L(x)) ≤ 1。它保证码长和概率可以互相换算：L(x) = -log2 P(x)。“压缩”和“建模”因此是同一件事。
通用编码（universal code）
针对一整个模型族设计的编码。对族里任何一个分布，它的码长都只比该分布的最优码长多一点。精炼 MDL 用它代替两部分编码。
归一化最大似然（Normalized Maximum Likelihood, NML）
把每个数据集的最大似然值除以所有可能数据集最大似然值之和，得到一个分布。在最坏情况下，它的额外码长最小。
参数复杂度（parametric complexity）
NML 的归一化项取对数，记作 COMP。它衡量模型族的灵活程度：能拟合好的数据集越多，COMP 越大。它取决于参数个数，也取决于参数怎样进入模型。
前序 MDL（prequential MDL）
按顺序逐个预测数据点，每次只用之前的数据训练，累加每一步的 -log2 P。它不需要单独计算模型长度，和自回归语言模型的训练方式完全一致。

历史位置：为什么值得读

MDL 由 Jorma Rissanen 1978 年提出。它的源头是 Solomonoff、Kolmogorov 和 Chaitin 在 1960 年代建立的算法信息论。Wallace 和 Boulton 1968 年独立提出了思路相近的最小消息长度（Minimum Message Length, MML）。1980–90 年代，Rissanen 把 MDL 从两部分编码发展到随机复杂度和 NML。

问题是原始文献分散，数学门槛高。Grünwald 这篇教程 2004 年发布在 arXiv 上，2005 年作为文集的前 2 章出版。它把直觉层面的两部分编码和精炼理论放在一份材料里串起来，成为 MDL 最常被推荐的入门读物。2007 年，Grünwald 又出版了专著 The Minimum Description Length Principle。

它为什么在 Ilya 的清单里：

读懂这篇，就能说清“压缩即智能”这句话的具体含义。

学前准备

在原仓库怎么学

原仓库第 5 天用多项式阶数选择演示 MDL，并对比 AIC 和 BIC。本天的练习目录名是大写的 Exercises/。建议按下面的顺序学：

  1. 先读教程第 1 章，再打开 README.md 看本天的结构。
  2. 读 implementation.py。按教程的顺序看 3 组函数：two_part_mdl_polynomial、prequential_mdl_polynomial、nml_complexity_polynomial。
  3. 运行 train_minimal.py：在带噪声的多项式数据上，看 MDL 能否选回真实阶数。
  4. 打开 notebook.ipynb，用 visualization.py 画 3 类图：复杂度与拟合度的取舍、MDL 总分拆解、MDL 与 AIC/BIC 对比。
  5. 做 Exercises/ 里的 5 个练习：两部分编码、前序 MDL、模型选择、NML 复杂度、MDL 与 AIC/BIC 对比。
  6. 对照 solutions.py 检查答案，最后用 CHEATSHEET.md 复习。

建议：先做练习 1 和 2，体会两部分编码和前序编码的差别。练习 4 的 NML 复杂度计算量大，先用小样本验证。做练习 5 时，改变样本数和噪声大小，观察 MDL、AIC、BIC 选出的阶数何时一致、何时分歧。

今天再看

压缩即学习成了主流叙事。大语言模型的训练损失是每个词元的平均交叉熵，也就是用模型做算术编码时每个词元的平均比特数。训练一个模型，就是在找一个更短的编码。

前序编码最贴近大模型。前序 MDL 逐个预测数据、累加编码长度，这正是自回归语言模型的训练方式。Ilya Sutskever 2023 年的演讲 An Observation on Generalization 用压缩视角解释无监督学习为什么有效。Voita 和 Titov 2020 年把前序编码长度用于探针（probing）分析，称为 MDL 探针。

没解决的部分：NML 在神经网络上无法计算。两部分编码要求把模型本身的长度算进去。大模型有上千亿参数，按朴素的两部分编码看非常贵，泛化却很好。怎样正确计算神经网络的“模型长度”，仍是开放问题。第 4 天的噪声权重和今天的量化研究，都在尝试回答它。

容易卡住的地方

延伸阅读

← 返回 30 天目录