「随机」有两种,而它们恰好互相拆台:Shannon 熵测不出结构,Kolmogorov 复杂度又算不出来
【锚点】只钉一个判断:一个序列「有多随机」不是一个数。Shannon 熵度量的是「给定模型下的不可预测性」,Kolmogorov 复杂度度量的是「最短描述长度」。前者可算但看不见结构,后者看得见结构但不可算。夹在中间,就是为什么「复杂度」「理解」「结构」这些词永远没法被一个标量收编。
【显式】先摆一个反例。取两个长度 n=10^6 的二进制串:A = 0101010101…(周期 2);B = 真随机(反复抛公平硬币)。把它们都当成 i.i.d. Bernoulli(0.5) 建模,二者 Shannon 熵都是 1 bit/符号,一模一样。Shannon 熵是分布的属性,不是序列的属性——你喂给它的是「模型」,不是「数据」。这一步很多人搞反。
【隐式】换一把尺子,A 和 B 立刻分家。Kolmogorov 复杂度 K(x) = 能打印 x 并停机的最短程序长度。K(A) ≈ log n + O(1)(程序就是「打印 01 循环 n/2 次」);K(B) ≈ n + O(1)(没有比「把 B 原样抄一遍」更短的描述)。所以 A 简单、B 复杂,尽管 Shannon 熵一样。这就是「两种随机」:Shannon 随机 = 不可预测;Kolmogorov 随机 = 不可压缩。周期串对前者是随机的(边际分布 0.5/0.5),对后者是高度可压缩的。
【细微】必须比对多处才看得见的细节:K 依赖「用什么语言/通用图灵机」。换一台机器,K 只差一个常数(不变性定理),但当 n 不大时,这个常数可能比 K 本身还大。所以「结构」不是绝对量,是「相对某个描述语言」的量——而描述语言恰恰是你(或你的模型)选的那把尺子。
【极难发现】致命的一刀:K(x) 不可计算(Chaitin 的不可判定性)。你不可能写一个程序,输入任意 x,输出它的最短描述长度。这意味着:(1)「压缩即理解」(MDL、Solomonoff 归纳)原则上对,实践上只能逼近不能判定;(2) 任何复杂度指标(Lempel-Ziv、Gell-Mann–Lloyd 有效复杂度、语义熵)都是对 K 的可计算代理,代理必有失真;(3) 于是 Occam 剃刀不是一条能自动执行的规则,而是一个关于模型类的选择。
【流程节点链路】「我想给一个序列的随机性打分」→ 我选 Shannon 熵 → 它只告诉我模型下的平均意外,看不见周期结构(A、B 同分)→ 我改用 Kolmogorov 复杂度 → 它能区分 A、B,但不可计算 → 我只能用可计算代理(LZ/MDL)→ 代理在有限 n 下被描述语言常数支配 → 终点:没有一把无失真的尺子,「随机性」永远是多指标的向量,不是标量。
【观点】这对认知科学不是脚注,是地基。当我们说「这个解释更简洁」「这个理论更深刻」,我们其实在做压缩,而压缩的好坏依赖我们默认的描述语言——而那个语言本身,没法被同一个语言判定。科学哲学里「简洁性无法形式化」的争论(从 Popper 到 Sober 的奥卡姆之争),根子就在这里。
【值得辩论的问题】如果「结构」和「理解」在原则上不可计算,那「衡量一个模型是否真的理解了数据」是不是一个范畴错误?还是说,我们本就该放弃「理解」的绝对度量,只保留「相对某个模型类的压缩率」?——你怎么划线?







0 Comments