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

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

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

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

起源

哲学的な

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

原理

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

P[T|D]＝P[D|T]P[T]P[D|T]P[T]+∑あ≠TP[D|あ]P[あ]{\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]}}}

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

興味深いことに、計算可能な確率分布の集合は、すべてのプログラムの集合の部分集合であり、これは可算である。同様に、ソロモンオフが考察した観測可能なデータの集合は有限であった。したがって、一般性を失うことなく、任意の観測可能なデータは有限のビット列であるとみなすことができる。結果として、ソロモンオフの帰納法は、離散確率分布のみを用いることで定義できる。

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

数学

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

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

数学的な保証

ソロモンオフの完全性

The remarkable property of Solomonoff's induction is its completeness. In essence, the completeness theorem guarantees that the expected cumulative errors made by the predictions based on Solomonoff's induction are upper-bounded by the Kolmogorov complexity of the (stochastic) data generating process. The errors can be measured using the Kullback–Leibler divergence or the square of the difference between the induction's prediction and the probability assigned by the (stochastic) data generating process.

Solomonoff's uncomputability

Unfortunately, Solomonoff also proved that Solomonoff's induction is uncomputable. In fact, he showed that computability and completeness are mutually exclusive: any complete theory must be uncomputable. The proof of this is derived from a game between the induction and the environment. Essentially, any computable induction can be tricked by a computable environment, by choosing the computable environment that negates the computable induction's prediction. This fact can be regarded as an instance of the no free lunch theorem.

Modern applications

Artificial intelligence

Though Solomonoff's inductive inference is not computable, several AIXI-derived algorithms approximate it in order to make it run on a modern computer. The more computing power they are given, the closer their predictions are to the predictions of inductive inference (their mathematical limit is Solomonoff's inductive inference).[11][12][13]

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

参照

参考文献

  1. ^ラスマナー、サミュエル（2011年6月3日）. 「普遍帰納法の哲学的論文」 .エントロピー. 13 (6): 1076–1136 . arXiv : 1105.5721 . doi : 10.3390/e13061076 .
  2. ^ a b Solomonoff, Ray J. (2009), Emmert-Streib, Frank; Dehmer, Matthias (eds.), "Algorithmic Probability: Theory and Applications" , Information Theory and Statistical Learning , Boston, MA: Springer US, pp.  1– 23, doi : 10.1007/978-0-387-84816-7_1 , ISBN 978-0-387-84816-7、 2020年7月21日取得{{citation}}: CS1 maint: work parameter with ISBN (link)
  3. ^ a b Lê, Nguyên Hoang (2020).知識の方程式：ベイズの定理から統一科学哲学へ. フロリダ州ボカラトン：CRCプレス. ISBN 978-0-367-42815-0。
  4. ^ a b JJ McCall. 帰納法：コルモゴロフとソロモンオフからデ・フィネッティへ、そして再びコルモゴロフへ – Metroeconomica, 2004 – Wiley Online Library.
  5. ^ a b D Stork. オッカムの剃刀と倹約の基礎、ricoh.com からの学習 – NIPS 2001 ワークショップ、2001
  6. ^ a b A.N. Soklakov. 物理理論の形式的基礎としてのオッカムの剃刀（arxiv.orgより） – Foundations of Physics Letters, 2002 – Springer
  7. ^ a b Jose Hernandez-Orallo (1999). 「チューリングテストを超えて」(PDF) . Journal of Logic, Language and Information . 9 .
  8. ^ a b M Hutter. 計算可能な普遍的事前分布の存在と収束についてarxiv.org – アルゴリズム学習理論, 2003 – Springer
  9. ^サミュエル・ラスマナーとマーカス・フッター著『普遍帰納法の哲学的論文』エントロピー、13(6):1076–1136、2011
  10. ^ Ming Li、Paul Vitanyi、「コルモゴロフ複雑性とその応用入門」、 Springer-Verlag、NY、2008年、339ページ以降。
  11. ^ J. Veness, KS Ng, M. Hutter, W. Uther, D. Silver. 「モンテカルロAIXI近似」 – Arxivプレプリント, 2009 arxiv.org
  12. ^ J. Veness、KS Ng、M. Hutter、D. Silver。「AIXI近似による強化学習」 Arxivプレプリント、2010年 – aaai.org
  13. ^ S. Pankov. AIXIモデルの計算近似、agiri.orgより – 人工知能、2008年：…の議事録、2008年 – books.google.com
  14. ^ゴールド、E.マーク (1967). 「限界における言語識別」(PDF) .情報と制御. 10 (5): 447– 474. doi : 10.1016/S0019-9958(67)91165-5 .
  15. ^ J. Schmidhuber (2002). 「一般化コルモゴロフ複雑度の階層と極限で計算可能な非列挙普遍測度」(PDF) . International Journal of Foundations of Computer Science . 13 (4): 587– 612. doi : 10.1142/S0129054102001291 . 2017年7月6日時点のオリジナル(PDF)からアーカイブ。

出典

  • アングルイン, ダナ; スミス, カール 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 年、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。
  • ヘイ、ニック。「ユニバーサル・セミメジャー：入門」、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 年。
  • ソロモノフ, レイ・J. (1999). 「2種類の確率的帰納法」(PDF) .コンピュータジャーナル. 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 .
「 https://en.wikipedia.org/w/index.php?title=ソロモンオフの理論と推論&oldid=1311829183」より取得