Solomonoff帰納推論

1. 概要

1.1 帰納推論の問題

過去の観測x₁x₂...xₙから次の観測xₙ₊₁を予測する。

例: 101010... → 次は1？0？

ヒューム問題: どの規則性を外挿すべきか？
Solomonoffの解: すべての計算可能な仮説を重み付け

1.2 万能事前分布

M(x) = Σ_p 2^{-|p|}  [U(p) = x* となるpについて和]

U: 万能チューリングマシン
p: プログラム
x*: xで始まる無限列

「xを出力するプログラムの確率の総和」

2. 予測

2.1 Solomonoff予測

P(xₙ₊₁ = 1 | x₁...xₙ) = M(x₁...xₙ1) / M(x₁...xₙ)

条件付き確率としての予測

2.2 最適性

定理（Solomonoff）:
任意の計算可能な確率分布μに対して、
Solomonoff予測との累積KLダイバージェンスは有界:

Σₙ D_KL(μ(xₙ₊₁|x₁...xₙ) || M(xₙ₊₁|x₁...xₙ)) ≤ K(μ) log 2

→ 真の分布がどれであっても、有限の損失で収束

3. 性質

3.1 オッカムの剃刀

  • 短いプログラム（単純な仮説）に高い重み
  • 2^{-|p|}: プログラム長に指数的に減少
  • 単純さへのバイアスが組み込まれている

3.2 普遍性

  • すべての計算可能な仮説を考慮
  • 特定のモデルクラスに限定されない
  • 「理想的な」ベイズ学習

3.3 計算不可能性

M(x)は計算不可能
- K(x)の計算が必要
- 停止問題に帰着

→ 理論的な理想であり、直接実装は不可能
→ 近似が必要（圧縮ベースの方法など）

4. LLMとの関係

4.1 類似点

  • 次トークン予測 ≈ Solomonoff予測
  • 大規模データからパターンを学習
  • 多様な仮説を暗黙的に考慮

4.2 相違点

  • LLMは計算可能（近似）
  • 訓練データに依存
  • アーキテクチャによる帰納バイアス

5. 参考文献

  • Solomonoff (1964). "A Formal Theory of Inductive Inference" Parts I & II
  • Hutter (2005). "Universal Artificial Intelligence"
  • Rathmanner & Hutter (2011). "A Philosophical Treatise of Universal Induction"