アルゴリズム論的情報量

【アルゴリズム論的情報量】

ここでは、「アルゴリズム論的情報量」の定義を２つ与えます。

プログラム言語を固定します。ここで、プログラムは、有限のビット列で、プログラムが停止するなら、その出力も、有限のビット列です。

この時、ある有限なビット列の「アルゴリズム論的情報量」を、そのビット列を出力するプログラムの最小の長さで定義します。

この、ある自然数nの「アルゴリズム論的情報量」の第一の定義では、それが、nの「コロモゴロフ複雑性」に等しいと考えます。

「アルゴリズム論的情報量」＝「コロモゴロフ複雑性」を、通常の、シャノン情報理論での「情報量」＝「シャノン・エントロピー」とを比較してみましょう。

あるイベントxが確率pで起きたとしましょう。シャノンの情理論では、あるイベントxが起きたことを知った時に、「獲得した情報量」を、
$$−log ⁡𝑝$$

で表します。

“information gain” とか “information content”、“surprise” あるいは「自己情報量」といわれる情報量です。

ただ、シャノンの情報理論で、通常、「情報量」と言われるのは、X上の確率分布Pが与えられ、$𝑥∈𝑋が確率𝑝_𝑥$で起きる時、次の式で与えられる量です。

$$𝑆(𝑃 ) = −\sum_{𝑥∈𝑋} 𝑝_𝑥 log ⁡𝑝_𝑥 $$

これをシャノン・エントロピーと呼びます。

ただ、この「情報量」＝「エントロピー」は、先に見た「アルゴリズム論的情報量」と似ているようには見えませんね。

通常のシャノンの「情報量」との関係を、もっと分かりやすくするために、「アルゴリズム論的情報量」の二番目の定義を導入することにしましょう。

引き続き、プログラムは、有限のビット列だと考えます。もちろん、すべての有限のビット列が停止するプログラムを与えるわけではありません。

Xをプログラムのビット列の集合とする時、 𝑥∈𝑋なら任意のビット列yについて、𝑥𝑦∉𝑋とします。プログラム 𝑥で始まり、その後ろに𝑦をつなげた𝑥𝑦は、プログラムのビット列にはならないということです。

この条件を満たす時、Xをprefix free と言います。

Xが prefix freeなプログラムの集合で、𝑥∈𝑋である xの長さを𝑉(𝑥)で表すと、次の式が成り立ちます。

$$\sum_{𝑥∈𝑋} 2^{−𝑉(𝑥)} ≤ 1$$

この時、次の式で、「アルゴリズム論的情報量」 S(n)を定義します。

$$𝑆(𝑛) = − log⁡ \sum_{𝑥∈𝑋, 𝑁(𝑥)=𝑛} 2^{−𝑉(𝑥)}$$

要するに、S(n)は、nを出力するすべてのプログラムxを考え、そのプログラムの長さV(x)について、2^(−𝑉(𝑥))を足しあわせたものの対数をとったものです。

この和は、prefix free なXについては、次の式が成り立っていますので、収束します。

$$\sum_{𝑥∈𝑋} 2^{−𝑉(𝑥)} ≤ 1$$

------------

ショートムービーのpdfファイルは、次から利用できます。

セミナー「コロモゴロフ複雑性とアルゴリズム論的情報理」のまとめページは、こちらです。

セミナーのAgendaはこちらです。

セミナーへのお申し込みは、次のサイトからお願いします。

過去・現在・未来