コルモゴロフ複雑性
出典: フリー百科事典『ウィキペディア（Wikipedia）』
コルモゴロフ複雑性（コルモゴロフふくざつせい, Kolmogorov complexity）とは、計算機科学において有限長のデータ列の複雑さを表す指標のひとつで、出力結果がそのデータに一致するプログラムの長さの最小値として定義される。 コルモゴロフ複雑度、コルモゴロフ＝チェイティン複雑性 (Kolmogorov-Chaitin complexity) とも呼ばれる。
コルモゴロフ複雑性の概念は一見すると単純なものであるが、テューリングの停止問題やゲーデルの不完全性定理と関連する深遠な内容をもつ。 コルモゴロフ複雑性やその他の文字列やデータ構造の複雑性の計量を研究する計算機科学の分野はアルゴリズム情報理論 (en:algorithmic information theory) と呼ばれており、 1960 年代末にアンドレイ・コルモゴロフ、レイ・ソロモノフ、グレゴリー・チェイティン によって創始された。
目次 |
[編集] 定義
厳密には、ある有限長の文字列 x として表されるデータ列のある万能計算機 u におけるコルモゴロフ複雑性は以下の式で定義される:
ここで、p は計算機 u のためのプログラムであり、u(p) はそれを実行したときに出力される文字列である。l(p) はプログラムの長さを表す。ただし、プログラムは入力をもたず、つねに決まった出力を返すようなものとする。 ここで万能計算機とは万能チューリングマシンと同等の能力をもつ計算機を意味し、例えば C など通常のプログラム言語を解釈し実行するような処理系だと考えてよい。
[編集] 直観的な例
ある文字列が別の文字列よりも複雑であると言うためにはどうすればよいかという問題を考えよう。 例えば、同じ 60 文字の長さの 0, 1 からなる以下の 2 種類の文字列が与えられたとする。
010101010101010101010101010101010101010101010101010101010101
110010000110000111011110111011001111101001000010010101111001
これらを見比べると、直観的に前者の文字列はより簡単であって、後者の方はより複雑であると感じる。 この直観を明確にするひとつの方法として、文字列を言語で説明することを考えよう。 このとき前者は「01 の 30 回の繰り返し」と 11 文字で説明できる。 それに対して、後者はそのような簡単な説明が与えられそうもなく、説明するには文字列そのものを含めて 60 文字以上で記す他はないように思える。
この例のように言語による記述によって短くできる文字列がある一方で、圧縮できないような文字列も存在しており、文字列の説明の長さは文字列そのものの複雑さと関係していると考えられる。 このことをより形式的に取り扱うためにアルゴリズムという概念を用いて定式化されたものがコルモゴロフ複雑性である。
コルモゴロフ複雑性を定めるためには、文字列に対する形式的な記述言語をまず指定しなければならない。 このような記述言語としては何かの具体的なプログラミング言語を選べばよい。 あるプログラム言語 L を固定したとき、 L のプログラム p が有限長の文字列 x を出力するなら、p は x の「記述」であるということにする。
このとき特に p として x 自身を明示的に含むような自明な記述がある。 例えば、上記の前者の文字列を標準出力に出力する Perl プログラムは、
print "010101010101010101010101010101010101010101010101010101010101"
のようになるだろう。 このようなプログラムの長さは明らかに x の長さよりもある定数分だけ長くなる。 しかし文字列に何かの構造が発見できれば、適切なアルゴリズムを用いることによってより短いプログラムを作れるかもしれない。 例えば次のPerlプログラムは上と同じ文字列を出力する。
print "01" x 30
このように記述言語 L における文字列 x のあらゆる記述のうちで最小の長さをもつ記述が見出せたとするなら、その長さが L における x のコルモゴロフ複雑性となる。
[編集] 基本的な性質
[編集] 自明な上限
前述の例で示されたように明示的に文字列 x をプログラムに含めることができるので、すべての x に対してそのコルモゴロフ複雑性 Ku(x) は x 自体の長さ |x| を定数分以上越えることはない。 すなわち、
定理 任意の u に対して、ある定数 c が存在して、任意の x に対して、
が成り立つ。
[編集] 記述言語による相対性
定義から明らかなように、コルモゴロフ複雑性は記述言語あるいは万能計算機に依存する。 しかし、ある万能計算機 u1 から別の万能計算機 u2 にプログラムを移植しても、コルモゴロフ複雑性はたかだか（u1 と u2 によって決まる） 定数分しか増えない。なぜなら2つの万能計算機は、必ずもう一方の計算機をエミュレートできるからである。 u2 上で u1を模倣するエミュレーションプログラム ε1,2 を作り、その上で u1 のためのプログラム p を動かせば、結果として u2 の上でプログラム p を動かせたことになる。 そしてこのエミュレーションプログラムはエミュレートするプログラムの大きさにかかわらずつねに一定である。 従って、 u2 上でのコルモゴロフ複雑性はたかだか l(p) + l(ε1,2) である。 逆の場合も同様にエミュレートができるので、すなわち、
定理 任意の万能計算機 u1, u2 に対し、ある定数 c1,2 が存在して、任意の x に対し、
が成り立つ。
なおコルモゴロフ複雑性の議論では、記述言語の違いによりこのようなある定数分を除いて成立するという関係が頻出する。
[編集] 圧縮不能な文字列
文字列 x が Ku(x) ≧ |x| となるなら x は「圧縮不能」であるという。 このような圧縮不能な文字列が存在するならどの程度存在するかを考えたい。 まず、簡単な基数 (濃度) についての考察から、ある長さの文字列 x すべての中には「圧縮不能」な文字列が少なくとも 1 つは存在していることがわかる。 なぜなら、長さ n のバイナリ列 (2 種類のアルファベットからなる文字列) は 2n 個存在するが、 それより短いバイナリ列は長さ 0 も含めて 2n - 1 しか存在しないからである。
さらに同じ理由で、長さ n 以下の 2n+1 - 1 個の文字列のうち、その半数より多い 2n が長さ n をもつのであるから、ある長さ以下の文字列のうち圧縮不能な文字列は半数より多い。 一般に、圧縮不能の定義に自然数 c だけの余裕を入れ、Ku(x) ≧ |x| - c を満たすとした x を「c 圧縮不能」 という。 長さ n - c より短いバイナリ列の個数は、長さ n のバイナリ列と比べ、 (2n-c - 1) / 2n しかないので、 c 圧縮不能な文字列は全体の 1 - 1/2c より多い。 例えば、 c = 100 ビットだけ圧縮できるような文字列は、たかだか全体の 2-100 ∼ 10-30 しかない。
よって、ほとんどの文字列は文字列の長さと大きく違わないコルモゴロフ複雑性しかもたないだろうと結論できる。
[編集] コルモゴロフ複雑性の計算不能性
コルモゴロフ複雑性に関する計算論上の興味深い帰結のひとつは、コルモゴロフ複雑性が効率的に計算できないということである。
定理 K は計算可能関数 (computable function) ではない。
K が計算可能ではないということは、個別の文字列 x のコルモゴロフ複雑性 K(x) が常に求められないことを意味するのではなく、任意の x を入力として取り、そのコルモゴロフ複雑性 K(x) を出力するような計算可能な関数もしくはプログラムは存在しないということである。
この証明は背理法で示され、ベリーのパラドックスとして知られる自己言及パラドクスに類似している。 まず、関数 K を実現するサブルーチン K が存在すると仮定する。 このとき、定数 n 以上のコルモゴロフ複雑性をもつ文字列を捜し出して出力するプログラム Pn を作ることができる。
function Pn : string
l = 1 から 1 ずつ増加させて繰り返し。
長さ l をもつすべての文字列 x 各々に対して繰り返し。
もし K(x) ≧ n ならば、 x を返して終了。
Pn は短い文字列から始めてすべての文字列 x に対しコルモゴロフ複雑性を計算しようと試み、それが長さ n 以上となったときにその文字列 x を出力して中断する。 このプログラム Pn とサブルーチン K とを合わせてプログラム長 Un をもつとする。 Un は n に依存するが、n の記述長は対数オーダーでしか大きくならないので、 Un < n となる n を取ることができる。 しかしこのとき、このプログラム自身が K(x) よりも短い x を生成するプログラムとなってしまっており、これは最小の記述長を計算するという K の仮定と矛盾する。
なお、任意のプログラムは文字列であるということに注意すると、以下のプログラム Q は一見して K を実現しているように思える。
function Q (x : string) : integer
l = 1 から 1 ずつ増加させて繰り返し。
長さ l をもつすべての文字列 q 各々に対して繰り返し。
もし文字列 q がプログラム Gq と見なせるならば、
Gq を実行し、 Gq = x ならば、 l を出力して終了。
このプログラムは、小さな文字列から初め、すべての文字列をプログラムとして実行してみて結果が x になっているかどうかを確かめる。 ある文字列が文法的に正しいかどうかをプログラムによって判別することは可能である。 しかしそれを実際に実行したときにそれが停止するとは限らない。 すなわち、文字列のコルモゴロフ複雑性を見出す前にこのプログラムは無限ループに陥るかもしれない。 チューリングマシンの停止問題の帰結により任意のプログラムが停止するかどうかを判別するプログラムは存在しないので、このプログラムを期待通りに働かせる方法は存在しない。
[編集] 関連する問題
[編集] データ圧縮の限界
(可逆な) 圧縮プログラムは与えられた文字列 x に関して、文字列 y を返す関数とみることができる。 ただし y は対応する展開プログラムで x に復元できなければならない。 よって、コルモゴロフ複雑性の定義から、展開プログラムの長さと y の長さの和は x のコルモゴロフ複雑性以上でなければならない。 この意味でコルモゴロフ複雑性はその文字列データに対する究極的な圧縮を限界づけている。
通常、圧縮プログラムでは y の長さは x よりも小さくなることが期待されるが、上述の圧縮不能な文字列の議論は圧縮プログラムに関しても成立するので、実際には圧縮できない x が少なくとも半数存在し、ほとんどは大きな圧縮ができない。 圧縮プログラムが我々が扱う多くの文字列を圧縮できるようにみえるのは、我々が実際に扱う文字列が、可能なすべての文字列と比べて極めて偏ったものにすぎないからである。
また、コルモゴロフ複雑性が計算不能であるという事実は、すべての文字列 x に対してコルモゴロフ複雑性がしめす究極の圧縮を実現するプログラムを作ることが原理的に不可能であるということを意味している。
[編集] ランダム性
十分長い文字列において「圧縮不能」な文字列は、アルゴリズム化できるような何の規則性ももたないと考えられるので「ランダム」な文字列だとみなせるだろう。 コルモゴロフ複雑性を無限長の文字列に拡張したとき、圧縮できないような文字列は「アルゴリズム的にランダムな列」 (en:algorithmically random sequence) と呼ばれている。 正確には、与えられた無限列 x のすべての接頭部分列が c 圧縮不能であるような c が存在するとき、x はアルゴリズム的にランダムである。
有限列の場合と同様に濃度の議論から、プログラムは可算個しかないのに対して、無限長のバイナリ列は非可算個であるので、この意味で「ほとんどすべて」の無限列はアルゴリズム的にランダムである。 しかしこのようなランダム列をプログラムによって生成することは決してできない。 統計的にランダム性をもつように見える列、例えば疑似乱数列や、円周率のような計算可能な超越数、あるいは有限長で記述される初期状態をもつ記号力学系が示すカオスなどは、すべてそれらを生成するプログラムが存在するので、この意味でのランダムではない。 ランダムな文字列はその特定の文字列の説明の複雑さという直観を元にしたコルモゴロフの意味ではもっとも複雑となるが、ランダムな列のアンサンブルは逆に統計的に特徴づけることがもっとも簡単な文字列でもある。
[編集] 関連項目
[編集] 参考文献
- Ming Li, P.M.B. Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, Springer-Verlag, 1993:1997, ISBN 0387948686
