This is the Japanese translation of this site.
2024/2/28 6:56
私の著書『Design Inference』の初版とその続編『No Free Lunch』では、特定された複雑性の正確な情報理論的測度を定義するための舞台を整えました。これがこの連載の主題です。しかし、この概念を明確にするためには、まだ行うべきことがありました。これらの2冊の本では両方とも、特定された複雑性は、一方の側に起こりにくさあるいは複雑性があり、他方の側には特定性があって、それらを組み合わせたものとして扱われていました。
当時提示されたところでは、複雑性と特定性は、明確な共通性を示さない2つの異なるタイプとして扱われ、油と酢のような組み合わせでした。そのため、どちらの本でも特定された複雑性を統一的な情報測度として定式化していませんでした。それでも、そのような測度の鍵となる考え方は、それらより前の本にありました。ここでは、それらの鍵となる情報理論的考え方を概観します。次のセクションでは、それらを統合して統一的なものとします。
複雑性から始めよう
以前述べたように、確率と複雑性の間には深いつながりがあります。このつながりは、シャノンの情報理論で明確にされています。この理論では、確率はビットに変換されます。これがどのように働くかを見るために、コイントスを100回することを考えてみましょう。この場合、確率2^100分の1の事象が発生します (ここでキャレット記号はべき乗を表します)。しかし、この数字は100ビットの情報にも相当します。なぜなら、コイントスを100回した結果を特徴づけるのに、100ビットを要するからです (1が表で0が裏だと考えてください)。
一般に、確率 p は －log(p) ビットの情報に相当します。ここでもこの記事の他の場所でも、対数の底は (確率をビットに変換するのに必要なので) 2です。対数を指数として考えてみましょう。対数関数が適用された数値を得るには、底 (ここでは常に2) にその指数を累乗する必要があるということです。したがって、例えば p=1/10 の確率は、－log(1/10) ≈ 3.322 ビット (あるいは 2^(－3.322) ≈ 1/10 ) の情報測度に相当します。このような少数のビットにより、確率と情報測度の間の正確な対応が可能になります。
したがって、特定された複雑性における複雑性とはシャノン情報のことです。クロード・シャノン (1916‐2001、上の写真) は1940年代、通信チャネルを介した信号伝送 (主にビットの信号ですが、他の文字列も) を理解するために、この情報の考え方を導入しました。伝送されるビット列が長ければ長いほど、情報は大きくなり、したがってその複雑性も大きくなります。
どんな通信チャネルにおいてもノイズが存在するため、信号の複雑性が大きければ大きいほど、その信号が歪む可能性は高くなり、したがって信号を伝送する際の適切な符号化と誤り訂正の必要性は高くなります。そのため、シャノン理論の中では、伝送されるビット列の複雑性が重要な考え方となりました。
シャノンの情報測度は、確率 P(E) を持つあらゆる事象 E に容易に拡張できます。ということで、E のシャノン情報を－log(P(E)) = I(E) と定義します。マイナス記号があるのは、E の確率が下がるにつれて、E に関連する情報が増大することを保証するためです。これがあるべき姿です。情報は常に、可能性を狭めることと関連しています。可能性が狭まれば狭まるほど、その確率に関連する確率は低下しますが、それに対応して、狭まる可能性に関連する情報は増加します。
例えば、公正なコインを10回トスした結果を考慮しましょう。EとFの2つの事象を考慮します。E は、10回のトスのうちの最初の5回が全て表で、残りのトスについては分からない事象を表すとしましょう。F は、10回のトスで全て表が出た場合を表すとしましょう。明らかに、F は E よりもこれら10回のトスの可能性の範囲を狭めています。Eは最初の5回のトスにしか基づいていないので、その確率は P(E) = 2^(－5) = 1/(2^5) = 1/32 となります。一方、F は10回全てのトスに基づくので、その確率は P(F) = 2^(－10) = 1/(2^10) = 1/1,024 です。この場合、E と F に関連するシャノン情報はそれぞれ I(E)=5 ビット、I(F)=10 ビットとなります。
コルモゴロフ複雑性も必要
しかし、シャノン情報だけでは特定された複雑性を理解するには不十分です。コルモゴロフ情報、あるいはコルモゴロフ複雑性と呼ばれるものも必要です。アンドレイ・コルモゴロフ (1903‐1987) は20世紀最大の確率論者です。1960年代、彼は数字の列がランダムであるとは何を意味するのかについて、筋道を立てようとしました。物事を単純にしつつ一般性を損なわないために、ここではビット列に焦点を当てることにします (どんな数字や文字もビットの組み合わせで表現できるからです)。シャノン情報についても同じ単純化の仮定をしたことに注意してください。
コルモゴロフが直面した問題は、公正なコインをトスした結果として扱われるどのようなビット列も等しく起こりうることなのかということでした。例えば、100回の連続したコイントスは確率1/(2^100)、あるいは100ビットのシャノン情報を持つことになります。とはいえコルモゴロフには、以下の2つの100回の連続したコイントス (0を裏、1を表と記しています) には甚大な差があるように思われました。
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
および、
1001101111101100100010011
0001010001010010101110001
0101100000101011000100110
1100110100011000000110001
前者は同じコイントスを100回繰り返すだけです。決してランダムではないように見えます。一方、2番目は顕著なパターンを呈していないので、ランダムに見えます (私はこれをちょうど今、オンラインのランダムビットジェネレーターから得ました)。しかし、ここで言うランダムとはどういう意味でしょうか？一方の数列はコイントスから予想されるようなものですが、もう一方はそうではないということでしょうか？しかしその場合、確率は2つの数列を区別する方法について何も語っていません。なぜなら、両方とも同じ小さな確率で発生するからです。
流布していたアイディア
コルモゴロフの見事な一撃は、これらの数列のランダム性を確率論的にではなく、計算的に理解することでした。興味深いことに、コルモゴロフを活気づけたアイディアは、1960年代半ばの当時には流布していました。レイ・ソロモノフとグレゴリー・チャイティン (当時まだ10代) も同じアイディアを思いついていたのです。恐らく不公正なことですが、ランダム性を計算的に特徴づけた最大の功労者はコルモゴロフとされています。したがってほとんどの情報理論の本 (例えば、カバーとトーマスの『情報理論の基礎』をご覧ください) では、このランダム性へのアプローチを議論する際にコルモゴロフに焦点を当て、アルゴリズム情報理論 (AIT) と呼ばれるものの下に置いています。
簡潔に言えば、コルモゴロフのランダム性へのアプローチは、あるビット列はそれを生成する短いコンピュータプログラムを持たないのならランダムである、ということです。したがって、上記の最初の数列では、それを生成する非常に短いプログラム、たとえば単に「『0』を100回繰り返す」というプログラムがあるので、非ランダムです。一方、2番目の数列を生成する短いプログラムは (分かる範囲では) 存在しません。
大部分のビット列が、その数列自体よりも短いプログラムでは特徴付けられないというのは、組み合せ論的な事実 (すなわち、可能性を数えたり列挙したりする数学についての事実) です。明らかに、どのような数列も、数列全体を単純に取り込み、それを単純に吐き出すプログラムによって特徴付けることができます。しかし、そのようなプログラムは数列を圧縮することには失敗します。非ランダム数列は、数列そのものよりも短いプログラムを持つことによって、それゆえに圧縮可能な数列となります。上記の最初の数列は圧縮可能です。2番目は、私たちの知っている範囲では、そうではありません。
コルモゴロフ情報 (コルモゴロフ複雑性としても知られています) は、与えられたビット列を生成する最短のプログラムを識別することに焦点を当てているので、計算理論です。とはいえ、ここに皮肉があります。与えられたビット列が、圧縮可能なプログラムを持たないという意味で、本当にランダムであると確実に言えることはめったにありません。組合わせ論では、その数学的な計数原理から、ビット列の大部分はコルモゴロフの意味でランダムでなければならないことが分かっています。なぜなら、短いプログラムの数は非常に限られており、長い数列はごくわずかしか生成できないからです。長い数列のほとんどは、長いプログラムを必要とします。
私たちに共通する経験
しかし、任意のビット列 D について、D を生成する最も短いプログラムの長さを K(D) と定義すると、K(D) を計算するコンピュータプログラムは存在しないことが判明します。簡単に言えば、関数Kは計算不可能です。理論計算機科学から得られたこの事実は、何かが一時的にランダムに見えても、実際にはランダムではないことを明らかに示すパターンを発見するかもしれないので、それがランダムであると確信できないという、私たちに共通する経験と一致しています (「ランダムな」インクのしみのように見えても、よく見ると人間の顔であることが分かる錯視を思い浮かべてください)。
しかし、K は計算不可能であっても、実践的には、特に非ランダム性を理解するのに有用な測度です。その計算不可能性ゆえに、K は特定の非圧縮性数列、これらはランダム数列ですが、それらを識別する助けにはなりません。K がよく定義された数学的関数であっても、ほとんどの場合、その精密な値を決定することはできません。それにもかかわらず、圧縮可能な数列に対して K は、それを正確に計算することはできなくても、推定はできるかもしれない場合に、確かに有用です。
そのような場合に典型的に起こることとして、数列に顕著なパターンが見つかります。すると、それが圧縮可能であることを示せます。その目的のために、ビット列の長さを表す測度が必要です。したがって、任意のビット列 D について、|D| をその長さ (ビットの総数) と定義します。任意の数列はそれ自体で定義されるので、|D| はコルモゴロフ複雑性の上限を形成します。ここで、洞察力や創意工夫によって、D を十分に圧縮するプログラムを見つけたとしましょう。そのプログラムの長さを n とすると、これは |D| よりかなり小さくなります ― 言い換えると、n < |D| となります。
このプログラムの長さ n は D よりもずっと短くなるものの、典型的には、この長さ n のプログラムが D を生成する最も短いプログラムであることを示すのは不可能です。しかし、それでいいのです。そのような長さ n のプログラムが与えられたとき、K(D) はそのようなプログラムの中で最も短いものを測るので、K(D) は n より大きくなり得ないことが分かります。したがって、長さ n の短いプログラムをいくつか見つければ、K(D) ≦ n < |D| であることが分かります。実践的には、|D| より相当小さい長さ n の短いプログラムを見つければ十分です。そうすれば、その数 n が K(D) の上限を形成することになります。実践的には、n を K(D) の推定値として使用します。そのような推定値は、これから見ていくように、応用においては結局のところコルモゴロフ複雑性の控えめな推定値になります。
次回: 「統一された情報測度としての特定された複雑性」
編集部注: この記事は当初BillDembski.comに掲載されたものです。
