アルゴリズム的確率
(Algorithmic Probability から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2014/11/16 18:48 UTC 版)
アルゴリズム的情報理論において、ソロモノフのアルゴリズム的確率とはある観察にたいし事前確率を割り当てる数学的方法である。 理論的には、その事前確率は普遍的である。 帰納的推論の理論やアルゴリズムの解析などに使われている。 計算可能ではなく、近似できるのみである。[1]
直感的な説明と性質
次のような問題を扱う。 ある理解したいと思う現象のデータが与えられたとする。 そのデータがどのようにして起こったのかについてのすべての可能な仮定の中で、どのようにして最もありそうな仮定を選んだら良いだろうか？ どのように異なる仮定を評価したら良いだろうか？ どのようにして未来を予測したら良いだろうか？
アルゴリズム的確率はオッカムの剃刀、エピクロスの複数説明の原理、現代の計算理論による符号手法など、いくつかのアイディアを組み合わせて、 事前確率は予測に関するベイズの定理を使用した式から得られる。[2] オッカムの剃刀とは、「観察された現象に合致する理論の中で、最も単純なものを選ぶべき」というものである。[3] 一方、エピクロスは複数説明の原理を唱えている。つまり、「複数の理論が観察に合致するなら、すべての理論を保持せよ。」[4] そこで、特別な数学的道具である普遍機械を使って、すべての興味ある理論に量を割り当てる。[5]
アルゴリズム的確率はオッカムの剃刀と複数説明の原理を組み合わせ、与えられた観察を説明するそれぞれの仮定（アルゴリズムやプログラム）に次のようにして確率値を割り当てる。 単純な仮定（短いプログラム）には高い確率を、複雑な仮定（長いプログラム）には小さな確率を割り当てる。 すると、これらの確率は観察に対して事前確率になっており、ソロモノフはそれが定数倍を除いて機械に依存しないことを示した。（不変定理と呼ばれている。） さらに、ベイズの定理を用いて最もありそうな未来の予測に使える。
ソロモノフが不変定理の発見と共にアルゴリズム的確率の概念を発明したのは、1960年頃であり、[6] それに関しての論文も出版している。[7] これらの考えをハッキリと明らかにしたのは、1964年の2本の論文であろう。 [8] [9]
アルゴリズム的確率はソロモノフの帰納推論の理論（観察に基づく予測の理論）における鍵であり、 機械学習への応用を目指して開発された。 文字列が与えられたら、次に来る文字は何であろうか？ ソロモノフの理論はこの問題に対しある意味で最善の解答を与えている。 ただし、計算可能ではない。 ただ、例えばポッパーの帰納推論の理論とは違い、ソロモノフの理論は数学的には厳格である。
アルゴリズム的確率はコルモゴロフ複雑性の概念と深い関係がある。 コルモゴロフはこの概念を情報理論やランダムネスの問題から着想を得て導入したが、 ソロモノフはそれより早く帰納推論という別の理由で導入していた。 実際、普遍的な事前確率はコルモゴロフ複雑性を用いて書くことができる。[10]
ソロモノフのc.e.測度は普遍性を持つ代わりに、計算時間が有限ではない。 この問題に対して、Leonid Levinによるサーチアルゴリズムの変種[11]を考え、 計算時間を制限して、短い時間で出力するプログラムに高い確率を与える方法がある。
参考文献リスト
Rathmanner, S and Hutter, M., "A Philosophical Treatise of Universal Induction" in Entropy 2011, 13, 1076-1136: A very clear philosophical and mathematical analysis of Solomonoff's Theory of Inductive Inference
参考文献
- ^ Hutter, M., Legg, S., and Vitanyi, P., "Algorithmic Probability", Scholarpedia, 2(8):2572, 2007.
- ^ Li, M. and Vitanyi, P., An Introduction to Kolmogorov Complexity and Its Applications, 3rd Edition, Springer Science and Business Media, N.Y., 2008, p 347
- ^ ibid, p. 341
- ^ ibid, p. 339.
- ^ Hutter, M., "Algorithmic Information Theory", Scholarpedia, 2(3):2519.
- ^ Solomonoff, R., "The Discovery of Algorithmic Probability", Journal of Computer and System Sciences, Vol. 55, No. 1, pp. 73-88, August 1997.
- ^ Solomonoff, R., "A Preliminary Report on a General Theory of Inductive Inference", Report V-131, Zator Co., Cambridge, Ma. (Nov. 1960 revision of the Feb. 4, 1960 report).
- ^ Solomonoff, R., "A Formal Theory of Inductive Inference, Part I". Information and Control, Vol 7, No. 1 pp 1-22, March 1964.
- ^ Solomonoff, R., "A Formal Theory of Inductive Inference, Part II" Information and Control, Vol 7, No. 2 pp 224–254, June 1964.
- ^ Gács, P. and Vitányi, P., "In Memoriam Raymond J. Solomonoff", IEEE Information Theory Society Newsletter, Vol. 61, No. 1, March 2011, p 11.
- ^ Levin, L.A., "Universal Search Problems", in Problemy Peredaci Informacii 9, pp. 115–116, 1973
関連項目
外部リンク
Algorithmic Probability
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/03/20 15:36 UTC 版)
「レイ・ソロモノフ」の記事における「Algorithmic Probability」の解説
1960年代より以前、確率を計算するには頻度に基づくのが普通だった。試行回数に対して、希望の結果が得られた回数の比率を求めるのである。1960年のソロモノフの論文では、この確率の定義が大きく改訂されており、1964年の論文でさらに完全なものとなっている。 後にコルモゴロフ複雑性と呼ばれることになる基本定理は、ソロモノフの理論にも含まれていた。1960年の論文の導入部に次のような一節がある。 非常に長い記号列を考えてみよう。…その記号列についての非常に簡単な説明があり、もちろん所定の記述方法を使っているなら、我々はその記号列が「単純」であるとみなすことができ、アプリオリな高い確率で予測することができる。より正確に言えば、0と1だけで何かを表現する場合、それが N 桁の二進数が可能な限り最短の表現であれば、その確率として 2-N を割り当てることになる。 この確率は、特定の万能チューリング機械（英語版）への参照と結びついている。ソロモノフは機械の選択を示し、1964年には証明したが、定数因子を加えても確率の比率はあまり変化しないということも示した。それらの確率は機械独立である。 1965年、ロシア人数学者コルモゴロフが独自に同様の考え方を発表した。コルモゴロフは後にソロモノフの業績を知り、ソロモノフの業績を認めた。その後数年間は、西欧よりもソ連でソロモノフの業績がよく知られるようになった。しかし学会全体としては、記号列の無作為性をより強調したコルモゴロフの名が結び付けられる結果となった。ソロモノフの Algorithmic Probability は記号列の外挿による予測に重きを置いていた。 後に1960年の後の時点で、ソロモノフは単一最短符号理論の拡張版を発表している。それが Algorithmic Probability である。彼は「記号列を説明するいくつかの異なる方法があるとき、それぞれの方法が記号列の確率を決定する際に何らかの重みを与えられるべきと思われる」と記している。そして、この考え方を使って汎用的でアプリオリな確率分布を生成する方法と、ベイズの定理を帰納推論に使えるようにする方法を示している。帰納推論は、特定の記号列を説明する全モデルの予測を加算することにより、それらのモデルの長さに基づいた適切な重み付けを使うことで、その記号列の拡張の確率分布を得る。この推論方法は後に「ソロモノフ推論」とも呼ばれるようになった。 その後もいくつかの論文を発表しつつ理論を発展させていき、1964年の発表へとつなげた。1964年の論文では Algorithmic Probability とソロモノフ推論についてより詳細に述べており、Universal Distribution と呼ばれるモデルを含む5つのモデルを提示している。
※この「Algorithmic Probability」の解説は、「レイ・ソロモノフ」の解説の一部です。
「Algorithmic Probability」を含む「レイ・ソロモノフ」の記事については、「レイ・ソロモノフ」の概要を参照ください。
- Algorithmic Probabilityのページへのリンク
