直感的な説明と性質

ウィキペディア小見出し辞書

直感的な説明と性質

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2014/11/16 18:48 UTC 版)

「アルゴリズム的確率」の記事における「直感的な説明と性質」の解説

次のような問題を扱う。 ある理解したいと思う現象のデータが与えられたとする。 そのデータがどのようにして起こったのかについてのすべての可能な仮定の中で、どのようにして最もありそうな仮定を選んだら良いだろうか？ どのように異なる仮定を評価したら良いだろうか？ どのようにして未来を予測したら良いだろうか？ アルゴリズム的確率はオッカムの剃刀、エピクロスの複数説明の原理、現代の計算理論による符号手法など、いくつかのアイディアを組み合わせて、 事前確率は予測に関するベイズの定理を使用した式から得られる。 オッカムの剃刀とは、「観察された現象に合致する理論の中で、最も単純なものを選ぶべき」というものである。 一方、エピクロスは複数説明の原理を唱えている。つまり、「複数の理論が観察に合致するなら、すべての理論を保持せよ。」 そこで、特別な数学的道具である普遍機械を使って、すべての興味ある理論に量を割り当てる。 アルゴリズム的確率はオッカムの剃刀と複数説明の原理を組み合わせ、与えられた観察を説明するそれぞれの仮定（アルゴリズムやプログラム）に次のようにして確率値を割り当てる。 単純な仮定（短いプログラム）には高い確率を、複雑な仮定（長いプログラム）には小さな確率を割り当てる。 すると、これらの確率は観察に対して事前確率になっており、ソロモノフはそれが定数倍を除いて機械に依存しないことを示した。（不変定理と呼ばれている。） さらに、ベイズの定理を用いて最もありそうな未来の予測に使える。 ソロモノフが不変定理の発見と共にアルゴリズム的確率の概念を発明したのは、1960年頃であり、 それに関しての論文も出版している。 これらの考えをハッキリと明らかにしたのは、1964年の2本の論文であろう。 アルゴリズム的確率はソロモノフの帰納推論の理論（観察に基づく予測の理論）における鍵であり、 機械学習への応用を目指して開発された。 文字列が与えられたら、次に来る文字は何であろうか？ ソロモノフの理論はこの問題に対しある意味で最善の解答を与えている。 ただし、計算可能ではない。 ただ、例えばポッパーの帰納推論の理論とは違い、ソロモノフの理論は数学的には厳格である。 アルゴリズム的確率はコルモゴロフ複雑性の概念と深い関係がある。 コルモゴロフはこの概念を情報理論やランダムネスの問題から着想を得て導入したが、 ソロモノフはそれより早く帰納推論という別の理由で導入していた。 実際、普遍的な事前確率はコルモゴロフ複雑性を用いて書くことができる。 ソロモノフのc.e.測度は普遍性を持つ代わりに、計算時間が有限ではない。 この問題に対して、Leonid Levinによるサーチアルゴリズムの変種を考え、 計算時間を制限して、短い時間で出力するプログラムに高い確率を与える方法がある。