BOOK 12 · ALGORITHMIC INFORMATION THEORY · 1964 –

理解,
就是压缩

香农信息论度量的是"平均"信息量——一个信源长期的不确定性。算法信息论把镜头对准单个对象:一个字符串的信息量,等于能生成它的最短程序的长度。这个定义看似朴素,却把压缩、学习、归纳、奥卡姆剃刀焊成一体——"理解就是压缩"在这里第一次有了严格证明。它也是贝叶斯先验的终极形态,和自由能那句"预测即压缩"的数学底座。

一个理论的价值,在于它比它所解释的数据更短。若你的模型和数据一样长,你没有理解,只是记住了。 MDL 原则的一句话概括 · 本站导言
SAME LENGTH · DIFFERENT COMPLEXITY 01010101010101010101010101010101 32 bit · 高度规律 print "01" × 16 K ≈ 小 · 可压缩 · 有结构 01101000110010100110111101110010 32 bit · 无规律 print "01101000110010100110111101110010" K ≈ 串长本身 · 不可压缩 · 即"随机"的定义 K(x) := 最短程序长度 = x 的固有信息量 随机 = 不可压缩 = 没有比"照抄"更短的描述
FIG. I 柯尔莫哥洛夫复杂度 K(x) —— 两个 32 位串等长,信息量却天差地别:规律串能被一句短程序生成(K 小),随机串的最短程序几乎就是"照抄它自己"(K ≈ 串长)。随机性 = 不可压缩性——这是它最深的定义。
CUR LEGERE · 为什么读算法信息论

一个定义,接通四件大事

统一

压缩 = 学习 = 预测

能压缩一段数据,就意味着你找到了它的规律;找到规律,就能预测它的续写。无损压缩率与预测能力在数学上是一回事——这解释了为什么大语言模型的训练目标(预测下一个词)本质上是一台压缩机。

证明

奥卡姆剃刀不再是审美

"如无必要,勿增实体"两千年来是一条哲学格言。Solomonoff 归纳把它变成定理:给每个假设按其最短程序长度赋先验概率,最简单的解释在数学上就是最可能对的——剃刀有了刀刃。

极限

智能的理论天花板

把 Solomonoff 归纳装进一个决策智能体,就得到 Hutter 的 AIXI——在数学上最优的通用人工智能。它不可计算,却像光速一样标定了"学习"这件事的绝对上界,是一切 AI 的北极星。

MAPPA · 本站地图

六页怎么走

历史与人物先讲三个人几乎同时发现同一件事:Solomonoff 为了归纳、Kolmogorov 为了随机性、Chaitin 为了极限,殊途同归于"最短程序"。核心概念是主菜:柯氏复杂度、不变性定理、不可计算性、Solomonoff 归纳、MDL、Chaitin 的 Ω,配签名互动「MDL 实验台」——亲手拖动模型复杂度,看总描述长度画出那条 U 形曲线,在过简与过繁之间找到理解的最优点。MDL 入口教材与 AIXI逐本拆骨架、给读法、亮保留意见。压缩与决策收束全站:五个推论、五个检查动作,并与书架诸站的暗线合拢。

COMPRESSION IS COMPREHENSION