アルゴリズム的確率
アルゴリズム的情報理論において、ソロモノフのアルゴリズム的確率とはある観察にたいし事前確率を割り当てる数学的方法である。理論的には、その事前確率は普遍的である。帰納的推論の理論やアルゴリズムの解析などに使われている。計算可能ではなく、近似できるのみである[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