随机不是『看起来乱』,而是『压不动』:Kolmogorov 复杂性为什么让所有模型选择都是近似
【锚点】这一讲钉一个判断:【真正的随机性】不是视觉上的混乱,而是无法被更短程序【压缩】;而【Kolmogorov 复杂性】不可计算,所以所有【复杂度惩罚】都只是可计算阴影。
【显式】Kolmogorov 与 Chaitin 把 K(x) 定义为:固定通用机器上,输出 x 并停止的最短程序长度。对 100 位字符串,任何 x 都有 K(x) ≤ 100 + O(1),因为可写“直接打印 x”。但 100 个 0 的字符串可写成“打印 100 个 0”,长度约 O(log2 100)≈7 位的数量级,再加机器常数;绝大多数 100 位随机字符串的 K(x) 接近 100 位,只差常数。
【隐式】关键不是“乱”,而是“没有更短描述”。若数据集能被压缩,压缩码就是模型;若压不动,就不存在更短规律。Rissanen 的【MDL】把这个思想工程化:选模型 = 选“模型描述 + 数据残差描述”总长度最短的编码。认知上,这也是 Tversky 与 Kahneman 的【代表性启发式】陷阱:低维直觉把“看起来像随机”当成不可压缩,真正该问的是它能否被更短规则生成。
【细微】Kolmogorov 复杂性不可计算。若 K 可计算,就能枚举长度 n 的字符串,找到第一个 K(x)>n 的字符串;这样的字符串必然存在,因为 Kn 矛盾。因此,任何声称精确给出“最短程序长度”的算法,要么撒谎,要么偷偷换了定义。
【极难发现】盲点在于:【AIC】、【BIC】、【MDL】、【交叉验证】常被当成“真相复杂度”的读数,但它们只是可计算代理。它们依赖模型族、编码约定、参数计数和样本量;小样本下,O(1) 常数、先验、程序语言选择可能比模型本身更影响结论。简单不是美德,简单是压缩;压缩不是真理,只是当前机器下更短的赌注。
【流程节点链路】:【原始数据】 → 【候选模型/程序】 → 【描述长度(模型+残差)】 → 【真实最短描述不可计算】 → 【用可计算压缩率/后验近似】 → 【模型选择与预测】。
可辩论问题:如果没有任何算法能告诉你“最短程序”是什么,你凭什么相信自动模型选择比领域判断更接近自然规律——是更短,还是更省?







0 評論