Understanding Generalization Requires Universal Induction
Aram Ebtekar, Marcus Hutter, Danica J. Sutherland
NeurIPS 2026 Position Paper Tra
stat.ML, cs.AI, cs.IT, cs.LG, math.ST
2026-09-28
经典统计学习解释不了通用模型的泛化。Hutter 等把 Solomonoff 归纳相对化到信息视角，证明任何预测器的超额后悔不超过它与数据的算法互信息。
经典统计学习理论能证明一件事：假设类够小，训练误差和测试误差就不会差太远。VC 维、均匀收敛、结构风险最小化，做的都是防过拟合。选哪个小类才盖得住真实函数，理论把选择外包给人类。专用模型还能靠经验拍脑袋；通用模型要在越来越任意的新任务上工作，这个外包就是缺口。
No Free Lunch 把缺口钉死。有限输入输出集合上，训练点之外每种标签出现的次数完全一样。任何只吃训练数据的算法，在大多数目标函数上都会输给瞎猜。把问题抬一层，变成「该学哪种归纳偏置」，计数结构不变，这就是 meta-NFL。经验、元学习、甚至把演化当成从无知起步的学习，都推不出第一份非均匀先验。能证明不欠拟合或不过拟合，不能同时证明两件。
一个具体计数：要学 f : Z19 → Z19，已见 f(4)=4、f(8)=8、f(11)=11。直觉猜 f1(x)=x，预测 f1(0)=0。三次式 f2 同样拟合这三点，却预测 f2(0)=9。f1 和 f2 各自待在大小同为 361 的小类里；更大的三次类有 130321 个元素。学习理论说选小类，不说选哪一个。低多项式次数碰到 f3(x)=⌊x/10⌋ 会直接崩。
有意义的预测必须从数据之外的归纳偏置起步。把偏置选成「短程序」，就得到 Solomonoff 归纳：对全体可计算预测器做带权混合，权重按程序长度指数衰减。样本效率上它对所有可计算专家竞争最优，后悔不超过 log(1/wi)，与序列无关。跟已经写进背景知识的专用方法比，这个加性常数会大到失去比较意义。描述语言一换，短的定义也换。任何先验都能包装成某种「简单」。
把 SI 相对化到信息视角。固定一台通用单调图灵机 U，再给它一条预言带 q。q 装着观察者已经有的全部信息：本地盘、网络快照、库、可下载的预训练模型。相对化先验 M^q(x) 等于随机程序在能查 q 时，输出以 x 为前缀的比例。偏置从绝对短，改成相对这个视角容易够到。巴别图书馆那种什么都有但什么都不好找的数据，不会提升可及性：指向其中一本书的指令，可以和书本身一样长。
Theorem 3 给出后悔形状。M^q 对任意预测器 μp 的对数损失后悔，上界是 p 与数据 x 相对 q 的算法互信息 MI^q(p:x)，再减去反向的 MI^p(q:x)。Theorem 5 接着证明：短元程序 r 即使用随机源生成 p，期望互信息仍被 r 的长度卡住。信息不能无中生有。设计者能把已有信息写进 q，不能造出额外有用信息。
立场论文，没有新的 benchmark。能钉死的是定理关系。
| 设置 | 结论 |
| 均匀先验或均匀抽一致假设 | 未观测点后验为 1/k，无泛化 |
| 经典 SI（q 为空） | 对可计算预测器竞争最优，对专用专家常数可很大 |
| 预言 SI M^q | 后悔不超过 MI^q(p:x) 减 MI^p(q:x)，进而不超过 MI^q(p:x) |
| 短元算法 r 生成的 p | 期望互信息不超过 r 的长度，几乎打不过 M^q |
对深度学习只串已有证据，不当新实验。宽前馈网参数空间里，对应更窄网的区域不成比例地大，随机搜到的插值解更像窄教师。窄网接近短电路；加循环和外部记忆就靠近通用图灵机；带思维链的 Transformer 在往那边走。大模型的上下文学习被论证成像贝叶斯，甚至像 SI。Grau-Moya 等人用限时随机程序当合成数据、完全不用真实数据，也能训出近似 SI 的上下文预测器。按 NFL，合成数据拟合本身解释不了未见输入上的强泛化，真正该查的是算法和架构在见数据之前有没有伪通用偏置。
读完带不走可跑代码。SI 不可计算，停机问题挡着。它给的是无限算力极限下的形式最优，以及一个该追的后悔形状：通用系统在算力远超专家时，目标是逼近 Theorem 3 的界。真实系统相对这个理想型的缺口，计算限制算在内，成了分析基线。
Goldblum 等人 2024 年的立场是：真实数据和模型共享低复杂度结构，所以一个模型类能跨域泛化。方向成立，但低复杂度相对哪种语言、为什么，经验成功会绕回 Corollary 2 的元归纳。可及性把话收成：不能保证 M^q 准，但能保证现实里够得到的替代方案好不了多少。AIXI 这类基于 M^q 的主体模型，被点名为预估未来主体能力和安全风险的工具。
SI 不可计算。时间与样本效率的联合优化被明确划出范围，时间受限的可及性也写成未决。隐藏乘性和加性常数只依赖 U，理论上可选 U 让常数变小；跟已经写进领域知识的专家比，这个「小」没有定量校准。论证设计者无法创造信息，还要接受物理 Church-Turing 论题。
「前沿系统大致近似 SI」停留在拼图阶段，没有直接测量。参数空间简单性偏置、ICL 的贝叶斯解读、合成程序数据训练，全部来自引用。没有测过大模型相对某个具体 q 的互信息或后悔。把 q 取成「当前网页加本地盘」，当代工程几乎整包进先验，解释力强，打假困难。对「简单」本身的哲学批评，论文引用了 McGregor、Herrmann、Neth、Sterkenburg；相对化是回应，实验没有裁决。