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

この理論は哲学的基盤に基づいており、1960 年頃にレイ・ソロモノフによって提唱されました。 ^{[ 9 ]}これは、オッカムの剃刀^{[ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ]}と多重説明の原理^{[ 10 ]}を数学的に形式化したものです。過去の観測を完全に説明するすべての計算可能な理論が次の観測の確率を計算するために使用され、より短い計算可能な理論に重みが置かれます。マーカス・ハッターの汎用人工知能は、これを基にして行動の期待値を計算します。

ソロモノフの帰納法は、純粋なベイズ主義の計算論的定式化であると主張されてきた。^{[ 3 ]}理解するために、ベイズ主義は事後確率を導出することを思い出そう。${\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より大きくなります。より正確には、すべての${\displaystyle \epsilon }$> 0の場合、lより長いすべてのプログラムの確率が最大で${\displaystyle \epsilon }$しかし、これは非常に長いプログラムが非常に高い確率を持つ可能性を排除するものではない。

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

ソロモノフの帰納法の特筆すべき特性は、その完全性である。本質的に、完全性定理は、ソロモノフの帰納法に基づく予測によって生じる累積誤差の期待値が、 （確率的）データ生成過程のコルモゴロフ複雑度によって上限が定められることを保証する。誤差は、カルバック・ライブラー情報量、あるいは帰納法の予測値と（確率的）データ生成過程によって割り当てられた確率との差の二乗を用いて測定できる。

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

ソロモノフの帰納的推論は計算不可能ですが、AIXIから派生したいくつかのアルゴリズムは、現代のコンピュータで実行できるようにそれを近似しています。これらのアルゴリズムに与えられる計算能力が高ければ高いほど、予測は帰納的推論の予測に近づきます (数学的な限界はソロモノフの帰納的推論です)。^{[ 11 ] [ 12 ] [ 13 ]}

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