ソロモノフの帰納的推論理論

ソロモノフの帰納的推論の理論は、常識的な仮定（公理）の下では、検討中の経験的データを生成する最短のアルゴリズムが最善の科学的モデルであることを証明している。データの選択に加えて、事後誤謬を避けるために、プログラミング言語はデータより前に選択されなければならないこと^{[1] 、および観察される環境は未知のアルゴリズムによって生成されることが他の仮定である。これは}帰納理論とも呼ばれる。アルゴリズム情報理論の動的（状態空間モデル）特性に基づいているため、モデル選択のための統計的および動的情報基準を包含している。これは、確率論と理論計算機科学に基づいてレイ・ソロモノフによって導入された。^{[2] [3] [4]}本質的に、ソロモノフの帰納法は、観測されたデータのシーケンスが与えられた場合に、計算可能な理論の事後確率を導出する。この事後確率は、ベイズの定理と何らかの普遍的な事前確率、つまり計算可能な理論に正の確率を割り当てる事前確率 から導き出されます。

ソロモノフは、この帰納法が計算不可能（正確には下半計算可能）であることを証明したが、「この計算不可能性は非常に無害な種類のものである」こと、そして「実際の予測に使用することを決して妨げない」（より多くの計算リソースを使用して下からより正確に近似できるため）ことを指摘した。^[3] 科学的コンセンサスが、現在の最良の科学理論がすべての可能な理論の中で最良であることを証明できないという点でのみ、「計算不可能」である。しかし、ソロモノフの理論は、与えられた一連の観察を説明する現在の科学理論の中から決定するための客観的な基準を提供している。

ソロモノフの帰納法は、より短いアルゴリズム記述を必要とする理論に、より大きな事前の信念を割り当てることによって、オッカムの剃刀^{[5] [6] [7] [8] [9]}を自然に形式化します。

この理論は哲学的な基礎に基づいており、1960年頃にレイ・ソロモノフによって創始されました。 ^[10]これは、オッカムの剃刀^{[5] [6] [7] [8] [9]}と多重説明の原理^[11]を数学的に形式化した組み合わせです。以前の観察を完全に説明するすべての計算可能な理論は、次の観察の確率を計算するために使用され、より短い計算可能な理論に重点が置かれます。マーカス・ハッターの汎用人工知能は、これに基づいてアクションの 期待値を計算します。

ソロモノフの帰納法は、純粋ベイズ主義の計算形式化であると主張されてきた。^[4]理解するには、ベイズ主義がベイズの定理を適用して データを与えられた理論の事後確率を導き出すことを思い出すと、次のようになる。${\displaystyle \mathbb {P} [T|D]}$${\displaystyle T}$${\displaystyle D}$

${\displaystyle \mathbb {P} [T|D]={\frac {\mathbb {P} [D|T]\mathbb {P} [T]}{\mathbb {P} [D|T]\mathbb {P} [T]+\sum _{A\neq T}\mathbb {P} [D|A]\mathbb {P} [A]}}}$

ここで、理論 は理論 の代替です。この方程式が意味を成すためには、量および がすべての理論およびに対して明確に定義されていなければなりません。言い換えれば、どの理論も観測可能なデータ 上の確率分布を定義しなければなりません。ソロモンフの帰納法は、本質的には、そのような確率分布がすべて計算可能であることを要求することになります。 ${\displaystyle A}$${\displaystyle T}$${\displaystyle \mathbb {P} [D|T]}$${\displaystyle \mathbb {P} [D|A]}$${\displaystyle T}$${\displaystyle A}$${\displaystyle D}$

興味深いことに、計算可能な確率分布の集合は、すべてのプログラムの集合のサブセットであり、これは可算です。同様に、ソロモノフが考えた観測可能なデータの集合は有限でした。したがって、一般性を失うことなく、観測可能なデータは有限のビット文字列であると考えることができます。その結果、ソロモノフの帰納法は、離散確率分布を呼び出すだけで定義できます。

ソロモノフの帰納法では、確率の法則に従うだけで、将来のデータの確率的予測を行うことができます。つまり、 となります。この量は、過去のデータが与えられた場合のすべての理論の平均予測値として解釈でき、その事後確信度によって重み付けされます。 ${\displaystyle F}$${\displaystyle \mathbb {P} [F|D]=\mathbb {E} _{T}[\mathbb {P} [F|T,D]]=\sum _{T}\mathbb {P} [F|T,D]\mathbb {P} [T|D]}$${\displaystyle \mathbb {P} [F|T,D]}$${\displaystyle T}$${\displaystyle D}$${\displaystyle \mathbb {P} [T|D]}$

「かみそり」の証明は、可算集合上の確率分布の既知の数学的特性に基づいています。これらの特性が関係するのは、すべてのプログラムの無限集合が可算集合であるためです。すべてのプログラムの確率の合計 S は、(確率の定義に従って) 1 に等しくなければなりません。したがって、すべてのプログラムの無限集合を列挙するにつれて確率はほぼ減少するはずです。そうでない場合、S は 1 より大きくなります。より正確には、すべての > 0 に対して、長さlが存在し、 lより長いすべてのプログラムの確率は最大 になります。ただし、これは非常に長いプログラムが非常に高い確率を持つことを妨げるものではありません。 ${\displaystyle \epsilon }$${\displaystyle \epsilon }$

理論の基本的な構成要素は、アルゴリズム確率 とコルモゴロフ複雑性の概念です。計算可能なシーケンスxの任意のプレフィックスpの普遍事前確率は、 pで始まる何かを計算するすべてのプログラム (普遍的なコンピュータの場合) の確率の合計です。あるpと、 xがサンプリングされる計算可能だが未知の確率分布が与えられれば、普遍事前確率とベイズの定理を使用して、xのまだ見えない部分を最適な方法で予測できます。

ソロモノフの帰納法の注目すべき特性は、その完全性です。本質的に、完全性定理は、ソロモノフの帰納法に基づく予測によって生じる予想される累積誤差が、 （確率的）データ生成プロセスのコルモゴロフ複雑度によって上限が定められることを保証します。誤差は、カルバック・ライブラー・ダイバージェンス、つまり帰納法の予測と（確率的）データ生成プロセスによって割り当てられた確率との差の二乗を使用して測定できます。

残念ながら、ソロモノフはソロモノフの帰納法が計算不可能であることも証明しました。実際、彼は計算可能性と完全性は相互に排他的であることを示しました。つまり、完全な理論はどれも計算不可能でなければなりません。この証明は帰納法と環境の間のゲームから導き出されます。本質的に、計算可能な帰納法はどれも、計算可能な帰納法の予測を否定する計算可能な環境を選択することで、計算可能な環境によって騙される可能性があります。この事実は、ノー・フリー・ランチ定理の例と見なすことができます。

ソロモノフの帰納的推論は計算不可能であるが、いくつかのAIXI由来のアルゴリズムはそれを近似し、現代のコンピュータで実行できるようにしている。計算能力が高ければ高いほど、その予測は帰納的推論の予測に近づく（その数学的限界はソロモノフの帰納的推論である）。^{[12] [13] [14]}

帰納的推論のもう一つの方向性は、1967年のE. Mark Goldの極限学習モデルに基づいており、それ以来、ますます多くの学習モデルが開発されてきました。^[15]一般的なシナリオは次のとおりです。計算可能関数のクラスSが与えられた場合、形式 ( f (0), f (1),..., f ( n ))の任意の入力に対して仮説 (すべての計算可能関数の事前に合意された許容可能な番号付けに関するインデックスe 。インデックス付き関数は、 fの指定された値と一貫性が求められる場合があります) を出力する学習器 (つまり、再帰関数) があります。学習器M は、その仮説のほとんどすべてが関数f を生成する同じインデックスeである場合に関数f を学習します。M がS内のすべてのf を学習する場合、 MはS を学習します。基本的な結果は、すべての再帰的に列挙可能な関数のクラスは学習可能であるが、すべての計算可能関数のクラス REC は学習可能ではないということです。^[要出典] 多くの関連モデルが検討されており、正値データからの再帰的可算集合のクラスの学習も、1967年のゴールドの先駆的な論文以降研究されているトピックです。ゴールドのアプローチの広範囲にわたる拡張は、シュミットフーバーの一般化コルモゴロフ複雑性の理論によって開発されており、^{[16]一種の}超再帰アルゴリズムです。

• アルゴリズム情報理論
• ベイズ推論
• 帰納的推論
• 帰納的確率
• ミルの方法
• 最小説明長
• 最小メッセージ長
• 哲学的な観点からは、「帰納法の問題」と「帰納法の新たな謎」を参照。

• Angluin , Dana; Smith, Carl H. (1983 年9月)。「帰納的推論: 理論と方法」。コンピューティング調査。15 (3): 237–269。doi :10.1145/356914.356918。S2CID 3209224  。
• Burgin, M. (2005)、「スーパー再帰アルゴリズム」、コンピュータサイエンスのモノグラフ、Springer。ISBN 0-387-95569-0 
• Burgin, M.、「テクノロジーで何ができるかを知る方法」、Communications of the ACM、v. 44、No. 11、2001、pp. 82–88。
• Burgin, M.; Eberbach, E.、「チューリングマシン、帰納的チューリングマシン、進化的アルゴリズムの普遍性」、Fundamenta Informaticae、v. 91、No. 1、2009、53–77。
• Burgin, M.; Eberbach, E.、「進化的計算の基礎について: 進化的オートマトンアプローチ」、人工免疫システムと自然コンピューティングの研究ハンドブック: 複雑適応型テクノロジーの適用(Hongwei Mo 編)、IGI Global、ペンシルベニア州ハーシー、2009 年、342-360 ページ。
• Burgin, M.; Eberbach, E.、「進化オートマトン：進化的計算の表現力と収束」、Computer Journal、v. 55、No. 9、2012、pp. 1023–1029。
• Burgin, M.; Klinger, A. 機械学習における経験、世代、限界、理論計算機科学、v. 317、No. 1/3、2004、pp. 71–91
• デイビス、マーティン(2006)「チャーチ＝チューリングのテーゼ：合意と反対」。議事録、ヨーロッパにおける計算可能性 2006。コンピュータサイエンスの講義ノート、3988、pp. 125–132。
• Gasarch, W. ; Smith, CH (1997)「クエリに重点を置いた帰納的推論の調査」複雑性、論理、および再帰理論、純粋数学と応用数学の講義ノート、187、デッカー、ニューヨーク、pp. 225–260。
• Hay, Nick. 「ユニバーサル半測度: 入門」、CDMTCS 研究レポート シリーズ、オークランド大学、2007 年 2 月。
• Jain, Sanjay; Osherson, Daniel; Royer, James; Sharma, Arun, 『学習するシステム：学習理論入門（第2版）』、MIT Press、1999年。
• クリーネ、スティーブン C. (1952)、メタ数学入門(初版)、アムステルダム: 北ホラント。
• Li Ming、Vitanyi、Paul、「コルモゴロフ複雑性とその応用入門」、第 2 版、Springer Verlag、1997 年。
• オシェルソン、ダニエル、ストブ、マイケル、ワインスタイン、スコット、『学習するシステム：認知科学者およびコンピュータ科学者のための学習理論入門』、MIT 出版、1986 年。
• Solomonoff, Ray J. (1999). 「2種類の確率的帰納法」(PDF) . The Computer Journal . 42 (4): 256. CiteSeerX  10.1.1.68.8941 . doi :10.1093/comjnl/42.4.256.
• ソロモノフ、レイ（1964年3月）。「帰納的推論の形式理論パートI」（PDF）。情報と制御。7 （1）：1–22。doi ：10.1016 / S0019-9958（64）90223-2。
• ソロモノフ、レイ（1964年6月）。「帰納的推論の形式理論パートII」（PDF）。情報と制御。7 （2）：224–254。doi ：10.1016 / S0019-9958（64）90131-7。

• アルゴリズムの確率 – Scholarpedia