在开源学习仓库 30u30 中，Day 5 带你精读 Grünwald (2004) 的 MDL（Minimum Description Length，最小描述长度）原则教程。核心思想一句话就能说清：模型选择就是编码选择，最好的模型是那个能把数据压缩得最狠的模型。读完本章，你会掌握 Two-Part Codes、Prequential 编码、NML 三种等价表述，以及 MDL 与 AIC、BIC 的对比方法——这是理解机器学习"防过拟合"数学语言的完整指南。

📌 一分钟理解 MDL 原则

想象你要把一份数据D传给对方，你有两种选择：

1. 裸发数据：把每个数字原封不动地发过去；
2. 发"模型 + 残差"：先描述一个模式，再描述数据偏离模式的小修正。

如果模型抓住了真实结构，第二种方式的总消息长度更短。MDL 原则正是把这个直觉形式化：

最佳模型 = argmin [ L(H) + L(D|H) ]

• L(H)：描述模型本身需要多少比特
• L(D|H)：给定模型后，描述残差还需要多少比特

这张表解释了 MDL 为什么能自动防过拟合：

不需要任何调参——求和运算会自动找到平衡点。这正是它比"手动加正则项"更优雅的地方。

🧩 Two-Part Codes：最朴素也最核心的表述

Two-Part Code（两段式编码）是 MDL 的入门形态（论文 Section 3）：

• 模型描述：k 个参数、每个参数 b 比特 →L(H) = k · b
• 数据描述：高斯残差的编码长度 →L(D|H) = (n/2) · log₂(2πe·σ̂²)

残差方差越小，说明拟合越好，编码残差所需比特就越少。

论文用多项式阶数选择作为贯穿全文的例子：数据由真实的 3 阶多项式加噪声生成，那么该选几阶？MDL 的账本是这样的：

4 阶以上的模型虽然能进一步压低残差，但多出来的参数"买"不回来它们花掉的比特——MDL 精准地选中了真实的 3 阶。完整推演过程见 paper_notes.md。

⏱️ Prequential MDL：用顺序预测代替模型描述

Two-Part Code 需要人为决定"每个参数算多少比特"，多少都有点主观。Prequential（预测性）编码换了一条路（论文 Section 5）：

不描述模型，直接逐点预测：用前 i−1 个数据预测第 i 个，把所有"惊讶值"累加起来。

L_preq = Σᵢ −log₂ P(xᵢ | x₁, ..., x_{i−1})

这个累加预测误差本身就是合法的编码长度（满足 Kraft 不等式）。它的好处很实际：

• 没有任意选择模型编码方式的烦恼
• 天然适合在线 / 顺序到达的数据
• 模型类的复杂性会通过预测表现被自动"计入账单"

🏆 NML：理论上的黄金标准

Normalized Maximum Likelihood（NML）是 Grünwald 教程给出的理论制高点（论文 Section 6）：

P_NML(x) = P(x | θ̂(x)) / Cₙ

分子是"模型类在这份数据上能做到的最好成绩"，分母是对所有可能的数据集求和——它衡量的是模型类的灵活度。模型越灵活、能拟合的花样越多，分母越大，每个具体数据被分到的比特就越多（代价越高）。

分母取对数后得到随机复杂性（Stochastic Complexity）：

COMP(M, n) ≈ (k/2) · log(n / 2π)

它长得像 BIC 的惩罚项，但来源完全不同：BIC 来自贝叶斯边缘似然的拉普拉斯近似，而 NML 惩罚是从信息论第一性原理推导出来的。

⚖️ MDL vs AIC vs BIC：模型选择标准怎么选

论文 Section 8 的对比结论，也是新手最常问的问题：

三个最有意思的差异：

1. AIC 惩罚不随样本量增长，大样本下会系统性选到过复杂的模型；
2. MDL 的惩罚是"自适应"的——接近 0 的参数几乎不花钱，AIC/BIC 对每个参数一视同仁；
3. MDL 不假设"真模型"存在，它只从压缩出发，这一点哲学上更干净。

公式速查可以收藏 CHEATSHEET.md，一页看完三种表述 + 三大标准对照。

📐 MDL 与 Kolmogorov 复杂度：压缩的终极意义

MDL 的思想源头是Kolmogorov 复杂度 K(x)——能产生 x 的最短程序的长度，这是压缩的绝对极限。但 K(x) 不可计算（停机问题）。MDL 的做法是：把搜索限制在一个可计算的模型类里，随着模型类越来越 expressive，MDL 编码长度会逼近 K(x)。

"学习 = 压缩"正是这条思想链给出的结论。下面这两张图来自仓库中 Day 26（Kolmogorov 复杂度章节）的可视化，直观展示了这条谱系：

左边的常数列几乎可以零成本压缩，而随机序列压缩到极限也还是很长——MDL 就是在两类极端之间找到那个"真实规律"。

🚀 动手：运行 MDL 多项式选阶 Demo

本章节的代码实现完全可运行，核心演示就是让 MDL 在带噪声的数据中找出真实的 3 阶多项式：

# 进入 Day 5 目录后 python train_minimal.py python train_minimal.py --monte-carlo # 蒙特卡洛多次试验对比

• 基础库：implementation.py —— 提供two_part_mdl_polynomial()、prequential_mdl_polynomial()、nml_complexity_polynomial()等完整 MDL 计算函数
• 演示脚本：train_minimal.py —— 生成噪声多项式数据，用 MDL / AIC / BIC 三方选阶
• 可视化：visualization.py —— MDL 得分曲线与准则对比图
• 交互式走读：notebook.ipynb

依赖只有 NumPy + SciPy，安装说明见 requirements.txt。

📝 练习路线：5 道题目覆盖全部三种表述

Exercises/目录下 5 道练习逐一对应论文章节，附参考实现，先做再对答案：

参考答案在 solutions.py，练习说明见 Exercises/README.md。

📂 文件导航

🎯 本章要点速记

1. MDL = 基于压缩的模型选择：总描述长度 = 模型比特 + 残差比特，最小者胜；
2. 三种表述，一个原则：Two-Part Codes（直观）、Prequential（顺序）、NML（理论最优）；
3. MDL 的惩罚是自适应的，不像 AIC 的固定 2k 或 BIC 的固定 k·log n；
4. MDL 是 Kolmogorov 复杂度的可计算近似——"学习即压缩"有了数学落脚点；
5. 不依赖"真模型存在"假设，纯从压缩出发工作。

💡 衔接提示：Day 4（Hinton & van Camp 的 MDL 神经网络正则化）用的是"结论"，Day 5 讲的正是那个结论下面的"地基"。学完本章再看 Day 6 复杂动力学，你会发现信息论的语言再次出场。