最小描述长度原理
概述
最小描述长度（MDL）原理是 Rissanen (1978) 提出的模型选择准则：最佳模型是使"模型描述长度 + 数据在模型下的编码长度"最小的那个，是 Kolmogorov 复杂性的可计算近似。
关键内容
公式
$$\text{最佳模型} = \arg\min_M { |M| + |D \,|\, M| }$$
其中 |M| 是模型复杂度（描述模型所需的比特数），|D|M| 是数据在模型下的编码长度。
直觉
好的理论（模型）就是对数据的好的压缩。MDL 原理将 Occam 剃刀精确化为一个可计算的优化目标： - 模型太简单 → |M| 小但 |D|M| 大（数据无法被有效压缩） - 模型太复杂 → |M| 大但 |D|M| 小（过拟合） - 最佳模型在两者之间取得平衡
与 Kolmogorov 复杂性的关系
MDL 是 Kolmogorov 复杂性的可计算近似： - Kolmogorov 复杂性 K(D) 是不可计算的"终极压缩下界" - MDL 在受限的模型族中搜索最短描述，是可计算的
与 Huffman 编码的关系
Huffman 编码是可计算的最优无损编码（在给定概率分布下）；Kolmogorov-Chaitin 复杂性是不可计算的"终极压缩下界"；MDL 介于两者之间——在有限模型族中寻找最优压缩。
应用
- 统计学中的模型选择
- 机器学习中的正则化
- 数据挖掘中的模式发现
- 神经网络架构搜索
来源
- raw/books/信息论/10_chaitin_1966_length_of_programs.md — Chaitin (1966) 深度解析
- Rissanen, J. (1978). "Modeling by Shortest Data Description." Automatica, 14(5), 465–471