計算科学とエントロピー

2021年9月6日 2022年1月19日 OkudaSotaro

2021/09/30 マルゼミ「計算科学とエントロピー -- コロモゴロフ複雑性とアルゴリズム論的情報理論」概要

これまで、丸山のセミナーでは、エントロピーについて、主要に、ボルツマン・ギブスらの統計力学的アプローチと、シャノンの情報理論的アプローチの二つを見てきました。

今回のマルゼミ「計算科学とエントロピー -- コロモゴロフ複雑性とアルゴリズム論的情報理論」では、それら二つとは異なるエントロピーへのアプローチを取り上げます。「アルゴリズム論的情報理論 ("Algorithmic information theory")」といわれるものです。

「アルゴリズム論的情報理論」は、計算科学でのチューリング＝チャーチらの計算可能性の理論と、シャノンの情報理論とを結びつけようという試みです。

熱力学的エントロピーは、分子の運動の「乱雑さ」の尺度と考えられます。同じ「水」でも、水の分子が結晶上に規則的に並ぶ「氷」のエントロピーは低く、水の分子が自由に空中を飛び回る「水蒸気」のエントロピーは高くなります。

ビットの列で与えられる情報でも同じです。100個の"0"が連なるビット列は、規則的なのでエントロピーは低く、「ランダム」に、"0"と"1"が並ぶビット列は、エントロピーが高いと考えることができます。

ただ、この例え話は、実は、我々が何が「規則的」で何が「ランダム」かを判断できることを、暗黙のうちに仮定しています。「ランダムさ」でエントロピーを説明するのなら、「ランダムさ」とは何かを、きちんと説明できなければいけません。

あるビット列Xとビット列Yが与えられた時、次のように考えることにしましょう。 Xを出力するコンピュータ・プログラムの集まりをPX、Yを出力するコンピュータ・プログラムの集まりをPYとしましょう。（X,Yを出力するプログラムは一つとは限りません）

ここで、「プログラムの長さ」を考えます。Xを出力するコンピュータ・プログラムの集まりPXに属する全てのプログラムについて、その「長さ」を考え、その中で一番短いものの長さをx とします。同様に、Yを出力するプログラムで一番短いものの長さをy とします。

この時、プログラムの長さ x, y を比較して、x < y なら、ビット列Yはビット列Xより「複雑」だと考えます。要するに、あるビット列を出力する最小のプログラムの長さが大きければ大きいほど、そのビット列は、より複雑でよりランダムだと考えるのです。

先の例で言えば、100個の"0"が連なるビット列を出力するプログラムは（例えば、ループを使って）短く書けるが、「ランダム」に"0"と"1"が並ぶビット列を出力するプログラムは、短くは書けないということです。

ある出力Xを与えるプログラムの長さの最小値を、Xの「コロモロゴフの複雑性」と言います。「アルゴリズム論的情報理論」の出発点は、この「コロモロゴフの複雑性」です。

項目をクリックするとその箇所から、ビデオの再生を始めることができまあす。