香农信息论和柯尔莫哥洛夫复杂度假设无限计算能力——这正是它们无法解释现代机器学习的根本原因。CMU/NYU 团队提出 epiplexity（认知信息量），为计算受限智能体重新定义信息的度量。
Marc Finzi · Shikai Qiu · Yiding Jiang · Pavel Izmailov · J. Zico Kolter · Andrew Gordon Wilson
卡内基梅隆大学 · 纽约大学
arXiv:2601.03220v1, 2026年1月
---
摘要
我们能从数据中学到比生成过程本身更多的信息吗？仅对已有数据施加确定性变换，能否构造出新的、有用的信息？能否在不考虑下游任务的情况下评估数据的可学习内容？
对这些问题，香农信息论和柯尔莫哥洛夫复杂度几乎交了一张白卷——部分原因在于它们假设观察者拥有无限计算能力，且未能瞄准有用的信息内容。
本文识别并例证了信息论中的三个看似悖论的命题：（1）信息不能通过确定性变换增加；（2）信息与数据的顺序无关；（3）似然建模仅仅是分布匹配。
为了阐明这些理论结果与现代实践之间的张力，并量化数据的价值，我们引入了 epiplexity（认知信息量）——一种刻画计算受限观察者能从数据中学到什么的信息形式化定义。认知信息量捕捉数据中的结构化内容，同时排除时间受限熵——即伪随机数生成器和混沌动力系统所代表的不可预测的随机内容。
借助这些概念，我们展示了信息如何通过计算被创造、如何依赖于数据排列顺序，以及似然建模如何能产生比数据生成过程本身更复杂的程序。我们还提出了估计认知信息量的实用方法，这些方法能捕捉不同数据源的差异、跟踪下游性能，并凸显能改善分布外泛化的数据集干预。
与模型选择的原则相对，认知信息量为数据选择提供了理论基础——指导如何为学习系统选择、生成或变换数据。
---
1. 引言
随着 AI 研究向更通用的智能系统迈进，数学直觉的基础机制开始出现裂痕。
大多数学习理论围绕控制给定分布下的泛化误差构建——将训练分布视为固定的，将优化精力集中在模型选择上。然而，现代系统被期望能在训练时未指定的任务、领域和目标之间迁移，通常是在大规模、多样化、异构数据上进行预训练之后。在这种范式下，成败往往不取决于架构选择，而取决于模型最初暴露于什么数据。
追求向分布外任务的广泛泛化，迫使我们转变视角：与其将数据视为给定、为分布内性能优化——我们需要选择和管理数据，以促进向未见过任务的泛化。这种转变使数据本身的价值成为一个核心问题：模型能从训练中获取多少可用的、可迁移的信息？
换句话说，不是模型选择，我们如何做数据选择？
在数据选择的问题上，现有理论几乎无法提供指导，甚至常常天真地与实践观察相矛盾。
三个悖论
悖论 1：信息不能通过确定性过程增加。 对于香农熵和柯尔莫哥洛夫复杂度，确定性变换无法有意义地增加对象的信息内容。然而，我们使用伪随机数生成器产生随机性、合成数据提升模型能力、数学家从公理中推导出新知识、动力系统产生涌现现象、AlphaZero 等自我博弈循环从游戏中学习精妙策略。
悖论 2：信息与分解顺序无关。 香农熵和柯尔莫哥洛夫复杂度的一个性质是，总信息量对分解方式不变：先观察 X 再观察 Y 的信息量，与先观察 Y 再观察 X 相同。然而，LLM 在从左到右排列的英文文本上比反向排列的文本上学得更好，这揭示出一种"时间之箭"；而我们整个密码学体系正是建立在"一个方向计算困难、另一个方向计算简单"的函数之上。
悖论 3：似然建模仅仅是分布匹配。 最大化似然通常等同于匹配训练数据的生成过程：真实的数据生成过程是自身的完美模型，没有模型能获得更高的期望似然。因此，人们常假设在一个数据集上训练的模型无法提取出比数据生成过程更多的结构或有用特征。然而，我们证明，一个计算受限的观察者事实上可以揭示远超数据生成过程的丰富结构。
Epiplexity：计算受限的信息量
这三个看似悖论的命题与实际现象之间的张力，可以通过对观察者施加计算约束、并将随机内容与结构化内容分离来解决。
借鉴密码学、算法信息论和这些未解经验现象的思想，我们定义了一个新的信息度量——epiplexity（认知信息量，epistemic complexity 的缩写），它形式化地定义了计算受限观察者能从数据中提取的结构化信息量（第 3 节，定义 8）。
简言之，认知信息量是在计算约束下最小化数据描述长度的模型所包含的信息量。一个简单的启发式测量方法是损失曲线下、最终损失之上的面积；而更严格的方法则使用教师模型和学生模型之间的累积 KL 散度（第 4 节，图 2）。
观察者依赖性
我们的形式化定义具有一个本质属性：信息依赖于观察者——同一对象可能因观察者的计算资源不同而呈现出随机或结构化的面貌。
例如，一个强伪随机数生成器的输出，对于任何缺乏密钥（种子）的多项式时间观察者来说，与真正的随机序列不可区分。而混沌动力系统则同时产生看似随机的行为和结构化信息：系统状态在长时间尺度上无法精确预测，但观察者仍可学习到有意义的预测分布。
本文贡献
我们识别出现有信息论概念与现代实践之间的差距（体现为三个悖论），并引入认知信息量作为计算受限观察者获取的结构化信息的度量。
我们展示了信息如何纯粹通过计算被创造（对合成数据的洞察），研究了某些数据分解方式如何增加结构化信息和下游分布外性能，揭示了似然建模为何比分布匹配做得更多——识别出归纳（induction）和涌现（emergence）两种观察者能学到比数据生成过程更多信息的机制。我们还展示了认知信息量与分布外泛化相关，从而解释为何某些数据能促进更广泛的泛化。
---
2. 背景：什么是"随机"？
马丁-洛夫随机性
20 世纪中叶，数学家试图形式化"一个给定样本是从某个分布中随机抽取的"这一命题的精确含义。马丁-洛夫（Martin-Löf）的解决方案是：不要求序列通过所有随机性检验，而是要求通过所有可计算的随机性检验。这一定义等价于：不存在可以预测该序列的算法。
这引出了前缀柯尔莫哥洛夫复杂度 K(x)：输出 x 的最短自定界程序的长度。
定义（马丁-洛夫随机序列）：无限序列 x 是马丁-洛夫随机的，当且仅当存在常数 c，使得对所有 n，K(x₁:ₙ) ≥ n − c。
一个关键结论是：每个随机序列都是不可计算的。冯·诺依曼的名言——"任何考虑用算术方法生成随机数字的人，当然都处于原罪之中"——预见了这一形式化结论。
密码学随机性：多项式时间不可区分
密码学社区通过再次限制观察者的计算模型，取得了重要进展：密码学安全的伪随机数生成器（CSPRNG）被定义为产生通过所有多项式时间随机性检验的序列的函数。
定义（CSPRNG）：函数 G 将 k 比特种子拉伸为 n 比特输出，当且仅当没有任何具有多项式大小建议字符串的多项式时间算法能以超过可忽略的优势区分 G 的输出和均匀随机序列。
---
3. 认知信息量（Epiplexity）
核心直觉
数据中既包含随机、本质上不可预测的信息（熵），也包含可预测的结构化信息（认知信息量），后者使观察者能通过识别模式来实现泛化：
- 高冗余内容（重复的代码、简单渐变）几乎没有信息量，无论结构化还是随机；
- 结构化内容（算法内部逻辑、动物图片）包含复杂的长程依赖关系，模型可从中学习到对跨任务有用的特征和子回路；
- 随机数据（随机生成的 API 密钥、文件路径、hash 值、均匀打乱的像素）几乎没有可学习内容，无长程依赖，训练后不产生复杂特征。
正式定义
定义 8（认知信息量与时间受限熵）：
对随机变量 X，令 P* 为在时间 T 内最小化"程序长度 + 期望损失"的程序：
P* = arg min { |P| + 𝔼[log 1/P(X)] }
定义：
- 认知信息量 Sₜ(X) = |P*| ——最优程序的比特长度
- 时间受限熵 Hₜ(X) = 𝔼[log 1/P*(X)] ——给定模型下编码数据所需比特数
时间受限熵捕捉随机变量中随机且不可预测的信息量，而认知信息量捕捉在给定计算水平下对象中可见的结构和规律性。
- 均匀随机变量：认知信息量几乎为零（最简单的均匀分布程序即可），但时间受限熵极大
- 简单模式（如交替 0101...）：认知信息量和熵都很小
- CSPRNG 输出：对多项式时间观察者，时间受限熵接近极大，认知信息量接近常数——认知信息量恰当地刻画了伪随机数携带大量时间受限随机性但几乎没有可学习结构这一直觉
关键定理
定理 9：对于任何多项式时间的 CSPRNG，其时间受限熵近乎极大，而认知信息量近乎常数。
定理 10：在单向函数存在的假设下，存在一系列随机变量，其多项式时间认知信息量至少以对数增长。这意味着具有任意大认知信息量的随机变量确实存在。
---
5. 解决三个悖论
悖论 1：信息可以通过计算被创造
传统信息论认为确定性变换不能增加信息。但在我们的框架中，密码学安全的伪随机数生成器展示了信息如何被创造：输入简短的种子，输出对多项式时间观察者而言与最大熵不可区分的序列。从计算受限观察者的视角来看，信息量增加了 n − k 比特。
确定性系统（如细胞自动机或混沌动力系统）可以通过计算产生对模仿行为、形态发生等任务有用的结构化信息。
悖论 2：信息依赖于顺序
认知信息量对数据的分解方式高度敏感。在密码学中，给定 CSPRNG 的密钥，你可以高效地生成输出并最小化描述长度。但给定输出而缺乏密钥，在多项式时间内无法在时间受限信息度量中找到同等简洁的描述。
这意味着对计算受限观察者而言，压缩某些序列是容易的，而逆转序列（从输出回到种子）是困难的——认知信息量捕捉到了这种不对称性。
悖论 3：似然建模不止于分布匹配
传统观点认为，在数据集上训练的模型只能学到数据生成过程中已有的结构。但计算受限的观察者可以选择不同于数据生成程序的方式来解释数据，从而提取出更多可复用的结构：
- 归纳（Induction）：观察者可以发现生成过程中显式编码的简洁规律，如物理定律
- 涌现（Emergence）：观察者可以学习到并非由数据生成程序直接产生的、在更高抽象层次上出现的结构——如在 Conway 生命游戏中，即使简单的局部规则也能产生可预测运动的滑翔机等涌现物体
这两者都使观察者能学到比生成过程本身更多的信息。
---
6. 认知信息量与分布外泛化
在大型语言模型的预训练中，某些数据能促进更广泛的迁移学习——即使在看似不相关的任务上。认知信息量为这种直觉提供了理论基础和实验验证。
我们的实验表明：
1. 文本数据比图像数据具有更高的认知信息量，这解释了为何文本预训练能更广泛地泛化 2. 数据集排列顺序影响认知信息量，进而影响分布外性能——即使训练损失更差 3. 认知信息量能追踪数据集的干预效果：去除冗余、增加结构性内容能提升认知信息量及相关下游性能
---
8. 结论
我们识别出信息论中三个看似悖论的命题——这些命题在数学上可被香农和算法信息论所辩护，却与现代机器学习的实践相矛盾。这些张力指向一个根本性的盲点：经典信息论假设无限计算能力的观察者。
通过施加计算约束并将随机内容与结构化内容分离，我们提出并形式化了epiplexity（认知信息量）——一种刻画计算受限智能体从数据中可提取的结构化信息的度量。
认知信息量为数据选择提供了理论基础——指导选择、生成和变换数据以构建更强的学习系统。它解释了为何信息可以被计算创造、为何依赖于数据的排列顺序、以及为何似然建模能做到比分布匹配更多。
在通用人工智能的竞赛中，数据不再是给定的——它是被选择和塑造的。认知信息量提供了理解这一过程的理论语言。
---