Understanding Generalization Requires Universal Induction¶

会议: NeurIPS 2026
arXiv: 2609.34458
领域: 其他
关键词: 泛化理论, 算法信息论, 所罗门诺夫归纳, 归纳偏置, 认知可达性

一句话总结¶

证明经典统计学习理论及其元学习均受制于无免费午餐定理，唯有以物理计算可达性为基准的相对化所罗门诺夫归纳（Oracle Solomonoff Induction）能从算法互信息守恒上为通用 AI 的泛化提供非平凡理论解释。

研究背景与动机¶

现代深度学习模型展现出惊人的跨任务通用泛化能力，但经典统计学习理论（如一致收敛、Rademacher 复杂度、VC 维、稳定性等）始终无法解释为什么模型在未见过的新任务上不会欠拟合。根据无免费午餐定理（No Free Lunch, NFL），在所有数学上可能的函数空间中，任何在部分任务上优于随机猜测的算法，必在其他任务上劣于随机猜测；统计学习理论所证明的收敛界仅保证了“小假说空间上测试误差贴近训练误差”，本质上只回答了“为什么不严重过拟合”，却无法回答“为什么真实目标函数偏偏落在该小空间内”。试图通过多任务经验、终身学习或达尔文进化来元学习（Meta-Learning）先验归纳偏置的尝试同样在数学上破产，因为元学习本身是一个高阶学习问题，同样被元无免费午餐定理（Meta-NFL）所约束，若初始种群没有非均匀偏置，经验积累绝不可能产生归纳优势。

核心矛盾在于：学习理论长期依赖人为手工设定的“平滑性”、“低范数”或“简单性”假定，而面对越来越通用的前沿大模型，这些手工假设不仅先验上无法辩护，而且奥卡姆剃刀中的“简单性”本身高度依赖描述语言的选择——只要更换编码系统，任何复杂函数都可以被编码为单比特程序。

本文的切入视角是摒弃对某种“绝对简单性”的哲学执念，转而从观察者所处的信息视角（Information Vantage Point）出发，以物理与计算可达性（Accessibility）重构通用归纳理论。我们不必寄希望于战胜那些在人类物理世界中根本无法实现的特异预测器，而是追求与所有从现有先验知识和计算接口可达的算法相抗衡。核心 idea：将所罗门诺夫归纳相对化至配备背景信息神谕机的通用图灵机 $U^q$，证明其对任意可计算预测器的对数损失悔流（Regret）严格受限于该预测器与未见数据间的相对算法互信息；由于任何有限元算法均无法凭空生成信息，该机制构成了破解元无免费午餐定理的唯一理论出口。

方法详解¶

整体框架¶

本文构建了面向通用序列预测的最优在线学习形式化理论体系。预测器针对任意未假定独立同分布（甚至由对抗者生成）的二进制序列 $x \in \mathbb{B}^*$ 做出逐比特概率预测，优化目标为对数损失（交叉熵）。为了打破传统学习理论对特定模型族分布假设的依赖，本文以单调图灵机为参考计算架构，将学习者的物理与数据环境形式化为“信息视角” $U^q$（通用计算机 $U$ 配合包含外部已有信息、网页快照和先验代码库的神谕带 $q$）。由此定义相对化所罗门诺夫-列文半测度 $M^q(x)$，将预测过程视作对所有可从该视角由短程序检索、扩展并在无限算力极限下运行的模型进行贝叶斯混合。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["信息视角定义<br/>参考通用机 U + 知识神谕带 q"] --> B["相对化所罗门诺夫半测度<br/>M^q(x) = P(x ⊑ U^q(α))"]
    B --> C["算法互信息相对化刻画<br/>MI^q(p:x) = KM^q(x) - KM^(p⊕q)(x)"]
    C --> D["单调在线预测与悔流界<br/>L(M^q,x) - L(μ_p,x) ≤+ MI^q(p:x)"]
    D --> E["信息守恒不变量约束<br/>E[MI^q(p:x)] ≤+ |r|，禁绝凭空生成信息"]

关键设计¶

1. 信息视角与相对化通用半测度构建：消除参考机与描述语言的人为偏置

传统所罗门诺夫归纳 $M^{\mathbf{0}}(x)$ 依赖于空神谕图灵机，面对具有专业背景知识的领域专家时会产生巨大的常数后悔值，且极易因参考图灵机的选择而引发描述长度的任意扭曲。本文通过引入信息视角 $U^q$，将计算机系统、Bash 命令接口、已存库、自然语言语料及互联网快照编码于神谕带 $q \in \mathbb{B}^\infty$ 中。对任意程序 $p \in \mathbb{B}^\infty$，定义其在均匀随机输入 $\alpha \sim \lambda$ 下生成的下半可计算测度为 $\mu_p(x) := \mathbb{P}_{\alpha\sim\lambda}(x \sqsubseteq U^\alpha(p))$。相对化通用先验半测度定义为： $$M^q(x) := \mathbb{P}_{\alpha\sim\lambda}\left(x \sqsubseteq U^q(\alpha)\right)$$ 由于所有已知计算模型与自然语言解释器均可作为子程序置于神谕 $q$ 内，选择特定参考机 $U$ 仅引入与 $p, q, x$ 无关的极小通用常数项（记为 $\le^+$ 或 $\ge^\times$），从而彻底消解了奥卡姆剃刀在经典理论中对表征语言的病态依赖。

2. 算法互信息度量与相对化先验复杂度：精细区分有效知识与伪随机扰动

经典算法信息论使用柯尔莫哥洛夫复杂度或先验复杂度 $KM(x)$，但无法直接刻画预测算法 $p$ 中到底包含多少关于目标数据 $x$ 的特异信息。本文基于相对化先验复杂度 $KM^q(x) := \log \frac{1}{M^q(x)}$，提出了预测器 $p$ 与数据 $x$ 在神谕 $q$ 下的非对称算法互信息定义： $$MI^q(p:x) := KM^q(x) - KM^{p \oplus q}(x) = \log \frac{M^{p \oplus q}(x)}{M^q(x)}$$ 其中 $p \oplus q$ 表示将程序 $p$ 与神谕 $q$ 逐比特交错输入。这一度量的核心洞察在于：若某个随机化算法 $p = r\alpha$ 包含大量未针对 $x$ 调整的随机比特串 $\alpha$，其单体复杂度 $KM^q(p)$ 趋近无穷，但其有效算法互信息 $MI^q(p:x)$ 依然保持极小。该设计使得对通用归纳能力的数学刻画只对“真正泄露数据规律的有用先验”敏感，而免疫于冗余实现和随机噪声。

3. 相对化所罗门诺夫归纳的非渐近悔流界：样本效率的最优性保证

针对任意可计算（或半可计算）的竞争预测器 $\mu_p$ 以及任意未假设真实分布的序列 $x \in \mathbb{B}^*$，评估对数累积损失 $L(\nu, x) := -\sum_{t=1}^{|x|} \log \nu(x_t \mid x_{<t})$。本文证明了通用学习器 $M^q$ 对任意预测器 $\mu_p$ 的悔流界上界： $$L(M^q, x) - L(\mu_p, x) \le^+ MI^q(p:x) - MI^p(q:x) \le^+ MI^q(p:x)$$ 该不等式表明，任何算法 $\mu_p$ 能够超越通用归纳 $M^q$ 的唯一途径，是其程序编码 $p$ 中天然包含了关于测试数据 $x$ 的额外互信息 $MI^q(p:x)$。如果不借助关于数据的额外信息，任何算法都无法显著战胜 $M^q$。

4. 物理信息无中生有禁令：奠定元归纳的最优性根基

为了封闭上述理论闭环，必须论证“人类或算法设计者不可能随意合成具有高 $MI^q(p:x)$ 的程序”。基于物理丘奇-图灵论题，设计者的设计过程本身亦由受控于其视角的元算法 $r \in \mathbb{B}^*$ 所决定。本文证明了信息守恒定理（No Information Ex Nihilo）：对于任意通过随机化元程序生成目标模型 $p := U^q(r\beta)$ 的过程，其互信息的数学期望满足： $$\mathbb{E}_p [MI^q(p:x)] \le \log_2 \mathbb{E}_p [2^{MI^q(p:x)}] \le^+ |r|$$ 由于人类设计者所编写的新代码元指令长度 $|r|$ 极小，设计者在统计上无法凭空产生与未知测试数据相关联的新信息。因此，不仅现实世界中不存在超越 $M^q$ 的神谕模型，而且任何现实学习系统所能逼近的最优理论极限就是 $M^q$。

损失函数 / 训练策略¶

在连续在线预测过程中，预测器给出第 $t$ 步的条件转移概率 $M^q(x_t \mid x_{<t}) = \frac{M^q(x_{\le t})}{M^q(x_{<t})}$。由于停机问题的限制，$M^q$ 本身是不可计算的（仅为下半可计算限值）。在有限算力与物理近似视角下，本文论证了前沿深度架构（如 Transformer 加思维链 CoT、自回归预训练大模型）在参数空间上的天然归纳偏置（窄网络/低电路复杂度占优、最小描述长度近似）构成了对 $M^q$ 的一种逐步逼近的可计算投影，这解释了为何上下文学习（ICL）在实证中展现出近似贝叶斯推断甚至所罗门诺夫预测的特质。

实验关键数据¶

主实验：统计学习理论与算法信息论在无免费午餐下的判决对比¶

本文通过构建规范的函数分类与有限域学习反例（输入输出阶数 $n=k=19$），对经典统计学习理论的核心复杂度指标与相对化算法信息论进行了严格的理论不变性对照分析。

理论框架	核心复杂度/收敛度量	目标函数对称变换下的不变性	能否区分同容量下的目标函数	能否防御元无免费午餐 (Meta-NFL)	悔流上界性质
经典经验风险最小化 (ERM)	假说空间基数 $\log	\mathcal{H}	$	双射保积置换不变	否（$\mathcal{H}_1$ 与 $\mathcal{H}_2$ 容量同为 361）
Rademacher 复杂度	$\text{Rad}_{\mathcal{D}^m}(\mathcal{H})$	函数平移不变 $\text{Rad}(\mathcal{H}+\{f\}) = \text{Rad}(\mathcal{H})$	否（无法指导选择 $w_0$ 偏置方向）	否（仅约束泛化差距，不约束泛化误差）	仅界定训练与测试差距
VC 维 / 组合维数	$\text{VCdim}(\mathcal{H})$	异或不变 $\text{VCdim}(\mathcal{H} \mathbin{\mathtt{xor}} f) = \text{VCdim}(\mathcal{H})$	否（对任意函数对称变形打散容量完全相同）	否（无法解释为何真实世界偏好低次项）	仅提供一致收敛性极值条件
均匀稳定性 (Uniform Stability)	$\beta(m) \to 0$	训练集微扰误差不变	否（不惩罚处处欠拟合的常数盲猜）	否（算法行为稳定不等于预测正确）	依附于损失函数Lipschitz连续性
相对化所罗门诺夫归纳 (本文)	相对先验复杂度 $KM^q(x)$	打破抽象对称，受物理可达性单调偏置	是（由神谕与代码检索距离严格偏置）	是（基于信息守恒定理定理5证明不可超越）	严格受控于算法互信息 $\le^+ MI^q(p:x)$

消融实验：不同归纳机制与信息假定下的理论性能边界¶

针对学习系统在不同信息注入、算力形式及任务序列下的表征能力，论文在附录及正文中对各变体进行了细致的边界条件推导消融分析。

机制 / 假设配置	悔流上界主导项	算力与可计算性开销	对抗序列防御能力	适用场景与关键理论推论
经典全局所罗门诺夫 $M^{\mathbf{0}}(x)$	$\le^+ KM^{\mathbf{0}}(p)$	不可计算（需模拟所有空输入图灵机）	存在普特南反例（对向逆向死锁）	缺乏背景知识神谕，对现代大模型与专业专家常数界过松
神谕所罗门诺夫 $M^q(x)$ (本文全配置)	$\le^+ MI^q(p:x)$	极限下可由随时算法（Anytime）多路逼近	对任意自然序列紧致成立	核心推荐：以物理计算可达性对齐现代 AI 的预训练与工具接口
终身学习机制 $M^{\mathbf{0}}(hx)$	$\sum \text{Regret} \le O(KM(p))$	需全局持续维持单一前向状态	历史足够长时强制收敛于主假说	跨多 Episode 累积损失最优，但在单 Episode 重启时会过度下注
瞬时重启机制 $M^{h\mathbf{0}}(x)$	逐 Episode 独立计界，常数累加	每次推理重置神谕上下文状态	每轮保留多样性对冲备选分布	更加贴近当前大模型上下文学习（In-Context Learning）工作机制
随时逼近截断 $\nu_{p,t}$ (运行 $t$ 步)	$\le^+	r(t)	+ MI^q(p:x)$	计算复杂度 $O(t)$，实际可执行

关键发现¶

经典学习理论的复杂度度量（Rademacher、VC 维、Natarajan 维、DS 维）具备完全的“平移或打散不变性”：无论目标函数是平滑低次多项式还是极其混乱的伪随机映射，只要类空间容量相同，其界定完全等价。这在数学上证明了纯统计理论永远无法推导“真实物理世界为何偏好某种函数”。
所谓“从进化中获得无偏先验”是认知幻觉：元无免费午餐定理（Proposition 2）证明，若达尔文初始种群均匀覆盖所有可能函数，第四天自然选择后的存活率依然恒等于随机乱猜。进化之所以有效，是因为物理分子在原始汤中的随机碰撞天然偏向短电路计算机器。
在对数损失下，通用预测器的泛化劣势并非由模型结构容量决定，而是精确等于竞争对手“暗中携带的目标数据信息量”（$MI^q(p:x)$）。

亮点与洞察¶

提出“认知可达性（Accessibility）”取代传统的“绝对简单性（Simplicity）”：彻底终结了关于奥卡姆剃刀编码语言依赖性的百年争论，明确指出泛化的本质不是追求宇宙绝对意义下的短代码，而是追求相对于人类或机器当前所处“信息视点”易于构建和检索的表征。
为大模型预训练与上下文学习（ICL）提供了最高层次的理论依据：大模型的 Scaling Law、隐式低秩偏置以及思维链（CoT）推理，本质上是在可计算资源受限的条件下对所罗门诺夫归纳的逐步工程逼近；无免费午餐定理不能用来否定通用大模型，因为大模型是“有偏”的，且其偏置恰好与人类可达信息高度一致。
提出了“信息无中生有禁令”作为学习理论公理：利用算法热力学思想，证明任何计算程序或随机化过程均无法从真空中生成与未知数据相关的算法信息，从而确立了相对化所罗门诺夫归纳在所有现实预测机制中的不可逾越性。

局限与展望¶

理论仅对对数损失严格成立：由于证明高度依赖对数损失的强凸性以允许预测器进行概率对冲（Hedging），在离散 0-1 损失或强化学习离散决策下，普特南对抗序列（Putnam's Adversary）会导致确定性策略全盘皆输；如何将其推广至 0-1 损失甚至通用非凸损失仍需结合图灵跳跃（Turing Jump $q'$）深入探索。
不可计算性与有限算力落差：$M^q$ 是极限不可计算的理想形式化对象，现实 AI 均为极端算力受限（Resource-bounded）系统；当前工作尚未给出多项式时间约束下的定量逼近速率与泛化界。
神谕选择的主观性边界：虽然引入神谕 $q$ 吸收了环境与常数项，但神谕内容的截断范围（例如究竟哪些互联网数据应被视为“已有视角”）缺乏精确的操作化物理边界。

评分¶

新颖性: ⭐⭐⭐⭐⭐ [立足算法信息论与元无免费午餐定理，首创从信息视点与相对化神谕重构深度学习泛化哲学]
理论充分度: ⭐⭐⭐⭐⭐ [严格证明了相对化悔流界与信息守恒不变量定理，对统计学习核心指标做出了完备的反例审视]
写作质量: ⭐⭐⭐⭐⭐ [逻辑严密精悍，哲学思辨与数学推导融会贯通，对经典学派争鸣剖析鞭辟入里]
价值: ⭐⭐⭐⭐⭐ [为后大模型时代理解通用泛化、上下文学习机制及 AI 安全边界指明了根本性理论方向]

机制 / 假设配置	悔流上界主导项	算力与可计算性开销	对抗序列防御能力	适用场景与关键理论推论
经典全局所罗门诺夫 \(M^{\mathbf{0}}(x)\)	\(\le^+ KM^{\mathbf{0}}(p)\)	不可计算（需模拟所有空输入图灵机）	存在普特南反例（对向逆向死锁）	缺乏背景知识神谕，对现代大模型与专业专家常数界过松
神谕所罗门诺夫 \(M^q(x)\) (本文全配置)	\(\le^+ MI^q(p:x)\)	极限下可由随时算法（Anytime）多路逼近	对任意自然序列紧致成立	核心推荐：以物理计算可达性对齐现代 AI 的预训练与工具接口
终身学习机制 \(M^{\mathbf{0}}(hx)\)	\(\sum \text{Regret} \le O(KM(p))\)	需全局持续维持单一前向状态	历史足够长时强制收敛于主假说	跨多 Episode 累积损失最优，但在单 Episode 重启时会过度下注
瞬时重启机制 \(M^{h\mathbf{0}}(x)\)	逐 Episode 独立计界，常数累加	每次推理重置神谕上下文状态	每轮保留多样性对冲备选分布	更加贴近当前大模型上下文学习（In-Context Learning）工作机制
随时逼近截断 \(\nu_{p,t}\) (运行 \(t\) 步)	$\le^+	r(t)	+ MI^q(p:x)$	计算复杂度 \(O(t)\)，实际可执行