基于反思预言机的Solomonoff归纳
Solomonoff Induction with Reflective Oracles
作者证明带反射预言机的 Solomonoff 预测器能学习只约束部分比特的可计算规则,并给出可表示其整个假设类的最优预测器。
- 普通 Solomonoff 归纳的假设类不含有效枚举,且作者引述称其在选定比特上可能学不会简单规律;反射预言机版本的最优预测器能否与只指定部分数据生成过程的有效预测策略竞争,论文称此前未被回答。
- 在反射预言机假设类上,把部分模型改写为借用预测器条件概率的比较假设,用乘法支配界定其累积对数损失优势,进而推出对可计算区间约束的几乎必然收敛;另构造在指定历史记录各假设条件概率的预测器。
- 纯理论结果:预测器到可计算区间 [l(σ), u(σ)] 的距离在每一相容测度下几乎必然趋于 0,期望平方误差和被 2(K(l,u)+C)ln2 界定;选定比特与加权校准作为推论成立;并存在呈现整个反射假设类的最优预测器。
- 作者称:固定预测器是否呈现该类、是否存在不呈现该类的支配成员仍未解决(Section 3);随机选定比特结果不回答普通 Solomonoff 预测器的对应问题(Section 2.4);允许模型约束依赖预言机被作者认为不自然(Section 2.3)。
基于反思预言机的Solomonoff归纳变体,其最优预测器能胜过只指定部分数据生成过程的可计算预测策略。论证依赖由预测器自身条件概率可计算的假设仍在反思假设类内,预测器因此能学到下一比特概率的可计算区间限制给出的不完整模型。论文还建立无偏性与校准性的加权形式,并讨论最优预测器的条件概率是否足以计算反思类中每个假设。
相关热点
1 个事件 · 1 条新闻提到
提到这篇论文的新闻
论文提出反射预言机版Solomonoff归纳
- AI Alignment Forum引用了论文编号或链接基于反射预言机的Solomonoff归纳
深度解读
这篇论文试图解决什么问题?
反射版 Solomonoff 最优预测器能否与只指定部分数据生成过程的有效预测策略竞争。
核心问题:带反射预言机(reflective oracle)的 Solomonoff 最优预测器 ξᴼ,能否与只指定部分数据生成过程的有效预测策略竞争——例如某策略只知道"每个偶数位重复前一位",对奇数位无可计算描述。
- 背景:Solomonoff 归纳把通用预测看作与有效预测策略的竞争,但可计算测度类没有有效枚举,标准做法是把假设类扩大到下半可计算半测度,其最优成员的条件概率一般只是极限可计算,且相对任何确定性预言机 A 这一障碍依旧存在(Introduction)。
- 反射预言机的作用:反射预言机允许概率图灵机查询使用同一预言机的机器之输出概率,在边界情形随机化以避免对角矛盾;补全后的假设类 M^O_refl 可有效索引、条件概率关于 O 一致可计算,并含有乘法支配全类的成员 ξᴼ(Introduction,引 [2, 9, 15])。
- 现有结果的缺口:作者引述 Lattimore、Hutter 和 Gavane [8] 的结果称,普通 Solomonoff 半测度可能连"偶数位重复前一位"这样的简单规律都学不会,而其归一化版本被证明能学会所有这类可计算子模式;反射版本在部分指定策略下的表现此前未被处理。
- 论文的贡献:作者构造借用 ξᴼ 条件概率的比较假设,用支配性界定其累积对数损失优势,证明 ξᴼ 对可计算上下界约束的预测几乎必然收敛到允许区间,并推出选定比特预测、加权无偏性和校准等推论(Section 2);另构造一个最优预测器 b ξᴼ,使反射类恰好等于由其预测可计算的假设集合(Section 3)。
有哪些相关研究?
所引工作分四组:Solomonoff 归纳、反射预言机、选定比特与不完全模型、校准与逻辑归纳。
Solomonoff 归纳与算法信息论
- Solomonoff [11, 12]——提出归纳推理的形式理论,按最短描述长度给假设赋先验权重,混合得到最优预测器。
- Hutter [5]、Li 与 Vitányi [10]——通用人工智能与 Kolmogorov 复杂度的标准文献,论文用其记号和背景。
反射预言机与反射版 Solomonoff 归纳
- Fallenstein、Taylor 和 Christiano [3]——提出反射预言机,作为经典博弈论的基础;论文采用其对角矛盾处随机化的思想。
- Fallenstein、Soares 和 Taylor [2]——研究 Solomonoff 归纳与 AIXI 的反射变体。
- Leike、Taylor 和 Fallenstein [9]——给出"grain of truth"问题的形式解,证明反射预言机可取为极限可计算。
- Wyeth、Hutter、Leike 和 Taylor [15]——论文采用其 step reflective oracle 约定和采样性质,并用其 Theorem 20 的构造得到最优预测器 ξᴼ。
选定比特预测与不完全模型
- Lattimore、Hutter 和 Gavane [8]——证明普通 Solomonoff 半测度在选定比特上可能失败,而归一化版本能学习所有可计算子模式;其第 5 节提出确定性结果能否推广到可计算随机模式的问题。论文把他们的分析扩展到反射设定,并称 Corollary 2.8 回答了反射版的对应问题,但不解决普通预测器的问题。
- Kosoy [7]——把不完全模型形式化为概率测度的闭凸集,其主定理构造一个在适当归一化的 Kantorovich–Rubinstein 度量下几乎必然收敛到相容不完全模型的预测器。论文指出自己的模型是可计算区间约束这一更特殊的形式,但结论是关于反射 Solomonoff 预测器 ξᴼ 本身的收敛,并给出期望累积平方误差的描述长度界。
校准与相关概念
- Dawid [1]——证明贝叶斯预测器在自身概率律下几乎必然校准。
- Kakade 和 Foster [6]、Vovk 等 [13]——通过连续检验的确定性弱校准与 defensive forecasting。
- Garrabrant 等 [4]——逻辑归纳的加权无偏与校准性质;论文沿用其 Definition 4.3.2 的指示函数,并指出其 recurring-unbiasedness 只给出极限点、unbiasedness-from-feedback 需要反馈条件,而本文在序贯设定下对 ξᴼ 证明收敛。
论文没有实验基线和基准数据集。作者把本文定位为:在反射设定下建立选定比特、不完全模型与校准的对应保证,并补充一个"预测器呈现其假设类"的表示定理。
论文如何解决这个问题?
用"从预测器预测可计算的假设仍在反射类中"加支配性界,统一推出不完全模型、选定比特与校准结果。
整体思路:固定反射预言机 O 和最优预测器 ξᴼ,凡是由 ξᴼ 的预测经可计算修改得到的假设仍属于反射假设类 M^O_refl,因而被 ξᴼ 乘法支配;把部分模型、投注策略等都写成这种比较假设,即可用支配性界定其累积对数损失优势。
反射假设类与最优预测器
- 假设类:M^O_refl = {λ̄ᵀᴼ : T 是带 O 访问的概率图灵机},即各机器输出概率经反射补全后得到的概率测度类,由带预言机的机器有效枚举(Section 2.1)。
- 最优预测器:按 Solomonoff 方式给每个补全测度 ν 赋权重 w_ν = 2^(−K(ν)),用 Wyeth 等 [15, Theorem 20] 的构造得到 ξᴼ ∈ M^O_refl,满足 ξᴼ(σ) ≥ Σ_ν w_ν ν(σ),即乘法支配全类;因类中含均匀测度,ξᴼ 有全支撑(Section 2.1)。
闭包与预测器相对描述长度
- 可计算于预测器:定义 μ ⪯pred ρ 表示存在一台机器,从 ρ 的任意条件表示的名字计算出 μ 的名字;H(ρ) 为所有这样的 μ(Definition 2.1、2.2)。
- 闭包(Proposition 2.3):若 ρ ∈ M^O_refl 且 μ ⪯pred ρ,则 μ ∈ M^O_refl;特别地 H(ξᴼ) ⊆ M^O_refl。证明思路是用 O 模拟对 ρ 条件概率的有理逼近请求,再用采样性质把所得条件概率实现为几乎必然停机的预言机机器。
- 相对复杂度界(Proposition 2.5):定义 K^ρ(ν) 为从 ρ 的名字计算 ν 的名字的最短前缀程序长度,则存在常数 C_ρ 使 ξO(σ) ≥ 2−Kρ(ν)−Cρ ν(σ);含义是:凡能从预测器预测计算出的假设,其累积对数损失相对 ξᴼ 的优势被其相对描述长度界定。
不完全模型与选定比特
- 不完全模型(Theorem 2.6):给定可计算的逐历史上下界 l(σ) ≤ u(σ),相容测度族 I 为所有满足 l(σ)μ(σ) ≤ μ(σ1) ≤ u(σ)μ(σ) 的测度。构造比较假设 ν_I,其条件概率是把 ξᴼ(1|σ) 投影到区间 [l(σ), u(σ)];由闭包 ν_I ∈ M^O_refl,再用支配性、KL 恒等式与 Pinsker 不等式推出:对每一 μ ∈ I,ξᴼ 的预测到区间的距离 d_t 满足期望平方和 2E_μ[Σ d_t²] ≤ (K(l,u)+C)ln2,从而 d_t → 0 μ-几乎必然。
- 选定比特(Corollaries 2.7、2.8):确定性规则 f(在部分位置预测比特)取 l = u = f,对满足 f 的序列 α 用点质量测度 δ_α ∈ I,得 ξᴼ(α_{p_i}|α_{<p_i}) → 1;随机规则 g 类似地得到 ξᴼ 的预测与 g 给出的概率之差趋于 0。
无偏性与校准
- 加权无偏(Proposition 2.10):对可计算权重函数 w : [0,1] → [0,1],构造比较测度 μ_y(x|σ) = ξᴼ(x|σ)(1 + y·w(p_σ)(x − p_σ)),把乘法投注策略表示为比较假设;由支配界推出当累积权重 W_n → ∞ 时,加权平均误差 (1/W_n)Σ w_t(α_t − p_t) → 0,对每一序列成立。
- 校准(Proposition 2.12):取权重为集中在可计算区间 [a, b] 上的连续指示函数(沿用 [4] 的 Ind_δ),得加权经验频率与加权平均预测之差趋于 0,极限点落在 [a, b] 内。
呈现假设类的预测器
- 反例(Proposition 3.1):对任意全支撑测度 ρ,存在全支撑测度 μ 与 ρ 相互 2 倍支配但 μ ⋠pred ρ;作者指出该构造不保证 μ 属于反射类,因此不解决反射类内部的分离问题。
- 表示定理(Theorem 3.2):构造 b ξᴼ,在前缀自由的历史集合 R = {1^(n−1)0} 中的历史 r_⟨e,σ⟩ 处令 b ξᴼ(1|r_⟨e,σ⟩) = 1/3 + (1/3)p_e(σ),把第 e 个假设在 σ 处的条件概率编码进去;每条序列至多经过一个编码历史,故 b ξᴼ(σ) ≥ (1/3)ξᴼ(σ),二者相互乘法支配,且 H(b ξᴼ) = M^O_refl。
- 复杂度不变量:对该预测器 K^{b ξᴼ}(ν) = K(ν) + O(1)(Section 3);Proposition 3.3 进一步称,凡呈现并支配同一类的全支撑预测器,其相对描述长度相差不超过加性常数。
- 附录扩展(Theorem 4.1):把 Theorem 2.6 推广到关于未来 m 比特的可判定事件,界为 m(K(m,A,l,u) + ⌈log₂m⌉ + C)ln2。
论文做了哪些实验?
论文为纯理论工作,无实验;主要结果是关于 ξᴼ 的收敛定理、推论与表示定理。
实验设置
论文不包含实验、被测模型、数据集或数值评测;全部结果都是数学定理及其证明。以下按"主要理论结果"组织。
主要理论结果
- 不完全模型收敛(Theorem 2.6):对任意可计算界 l, u 和每一相容测度 μ ∈ I,2E_μ[Σ_{t=1}^∞ d_t(α)²] ≤ (K(l,u)+C)ln2,其中 d_t 是 ξᴼ(1|α_{<t}) 到区间 [l(α_{<t}), u(α_{<t})] 的距离;特别地 d_t → 0 μ-几乎必然。证明还给出期望的 ε-违例次数上界 B_I/(2ε²)。
- 确定性选定比特(Corollary 2.7):对满足可计算规则 f 的序列 α,在 f 做出预测的无穷多个位置 p_i 上,lim_{i→∞} ξᴼ(α_{p_i}|α_{<p_i}) = 1。
- 随机选定比特(Corollary 2.8):对可计算随机规则 g 及与其相容的测度 μ,μ-几乎处处有 ξᴼ(α_{p_i}|α_{<p_i}) − g(α_{<p_i})(α_{p_i}) → 0。作者称这回答了 Lattimore 等 [8, Section 5] 问题在反射设定下的对应版本,但不解决普通 Solomonoff 预测器的问题。
无偏性、校准与表示
- 加权无偏(Proposition 2.10):对每一序列 α 和每一可计算权重方案 w,当累积权重 W_n → ∞ 时,(1/W_n)Σ_{t≤n} w_t(α_t − p_t) → 0,其中 p_t = ξᴼ(1|α_{<t})。
- 校准(Proposition 2.12):取权重集中于可计算区间 [a, b],加权经验频率与加权平均预测之差趋于 0;加权经验频率的每一极限点属于 [a, b],且若任一平均收敛则两者收敛到同一值。
- 表示定理(Theorem 3.2):存在全支撑测度 b ξᴼ ∈ M^O_refl,使 H(b ξᴼ) = M^O_refl 且 b ξᴼ(σ) ≥ (1/3)ξᴼ(σ) 对所有 σ 成立,即 b ξᴼ 与 ξᴼ 相互乘法支配;构造沿任一序列至多改变一次下一位预测。
- 复杂度一致性(Section 3 正文与 Proposition 3.3):对 b ξᴼ 有 K^{b ξᴼ}(ν) = K(ν) + O(1);任意两个呈现并支配同一类的全支撑预测器,其相对描述长度之差有界。
其他结果
- 有限视界扩展(附录 Theorem 4.1):把 Theorem 2.6 推广到关于未来 m 比特的可判定事件 A_σ,界为 2E_μ[Σ (d_t^(m))²] ≤ m(K(m,A,l,u) + ⌈log₂m⌉ + C)ln2,d_t^(m) → 0 μ-几乎必然。
- 支配不蕴含可恢复(Proposition 3.1):对任意全支撑 ρ 存在全支撑 μ,满足 (1/2)ρ(σ) ≤ μ(σ) ≤ 2ρ(σ) 但 μ 不可从 ρ 的预测计算;作者注明该 μ 不一定在反射类中。
- 预言机依赖的界(Section 2.3 末尾):作者称当 l 和 u 是借助 O 可计算时收敛结论仍成立,但认为让模型约束依赖预言机"似乎相当不自然"。
有什么可以进一步探索的点?
作者列出两个未决问题并指出一处不自然的推广;论文为纯理论,无实验覆盖可言。
作者指出的局限与后续方向
- 固定预测器是否呈现该类未解决:作者称"固定预测器 ξᴼ 是否呈现该类,以及是否存在某个支配成员不能呈现该类,在此仍未解决"(Section 3,Proposition 3.1 后的讨论)。
- 反例不进反射类:Proposition 3.1 的构造不保证所得的 μ 属于 M^O_refl,因此作者称它不在反射类内部建立支配与可恢复性的分离(Section 3)。
- 普通预测器的问题未解决:作者称 Corollary 2.8 回答了反射版随机选定比特问题,但"不解决普通预测器的对应问题"(Section 2.4,Corollary 2.8 前的说明)。
- 预言机依赖的约束不自然:作者称允许不完全模型的约束 l, u 依赖预言机 O 时收敛仍成立,但"让模型的限制依赖预言机似乎相当不自然"(Section 2.3 末尾)。
- 编码依赖:作者指出 b ξᴼ 的构造依赖于所选编码,并用 Proposition 3.3 给出呈现同一类的支配预测器之间相对描述长度的不变性(Section 3)。
实验覆盖范围
- 论文为纯理论工作,未运行任何模型、数据集或数值实验,无样本量、重复次数或评审方式可言。
- 结果陈述限于无限二元序列(Cantor 空间);脚注 1 称结果可扩展到有限字母表生成的数据(Section 1 脚注)。
- 收敛与校准结论的适用范围:Theorem 2.6 要求界 l, u 可计算(或借助 O 可计算);Proposition 2.10 与 2.12 要求权重方案可计算且累积权重发散。
- 论文未提供任何构造的有效算法或可计算性以外的复杂度分析;Kolmogorov 复杂度相关界都含未具体化的加性常数 C。
总结一下论文的主要内容
反射版 Solomonoff 预测器被证明能学习部分指定的可计算规律,且存在呈现整个反射假设类的最优预测器。
这是一篇关于通用归纳的理论论文,研究带反射预言机的 Solomonoff 最优预测器 ξᴼ 在部分指定的数据生成过程下的表现。
- 问题:有效预测策略可能只指定部分规律(如"偶数位重复前一位"),对其余比特无可计算描述;作者引述称普通 Solomonoff 半测度在这类选定比特上可能失败,反射版本的表现此前未被处理。
- 方法要点:凡从 ξᴼ 的预测可计算修改得到的假设仍在反射类 M^O_refl 中(Proposition 2.3),因而被 ξᴼ 乘法支配,其累积对数损失优势由相对描述长度 K^ρ(ν) 界定(Proposition 2.5);不完全模型、投注策略等都表示为这种比较假设。
- 不完全模型:对可计算上下界 l, u,ξᴼ 的预测到区间 [l(σ), u(σ)] 的距离在每一相容测度下几乎必然趋于 0,期望平方误差和被 (K(l,u)+C)ln2 界定(Theorem 2.6);附录推广到未来 m 比特的事件(Theorem 4.1)。
- 选定比特与校准:确定性规则下 ξᴼ 在预测位置的条件概率趋于 1(Corollary 2.7),随机规则下预测与规则概率之差趋于 0(Corollary 2.8);对每一序列成立加权无偏性(Proposition 2.10)和区间校准(Proposition 2.12)。
- 表示定理:存在最优预测器 b ξᴼ 使反射类恰好等于由其预测可计算的假设集合,b ξᴼ 与 ξᴼ 相互乘法支配,且 K^{b ξᴼ}(ν) = K(ν) + O(1)(Theorem 3.2 及 Section 3)。
- 作者的结论与未决问题:作者认为这些结果把 Lattimore 等的选定比特分析扩展到了反射设定并给出校准保证;固定预测器 ξᴼ 是否自身呈现该类、以及普通 Solomonoff 预测器的随机选定比特问题,作者称仍未解决。