Skip to content

Instantly share code, notes, and snippets.

@coalg

coalg/kolmogolov.md Secret

Last active March 31, 2024 13:35
Show Gist options
  • Save coalg/8609bfb03fdea2529d2d217e0ed37545 to your computer and use it in GitHub Desktop.
Save coalg/8609bfb03fdea2529d2d217e0ed37545 to your computer and use it in GitHub Desktop.
Download ZIP
Kolmogorov複雑性と（正規化）圧縮距離
Raw
kolmogolov.md

Kolmogorov Complexity And Compression Distance

（LaTeX記法使えないのですごく雑です…）

Kolmogorov複雑性

お話

アリスとボブの2人でコントスゲームをする。表（Head）と裏（Tail）で裏が多く出た方の勝ちというゲームである。コインは全部で20回トスする。

1回ゲームをした結果、以下のようになった。

  • アリスが得た系列
    • HHHTHTHTTHTHHTHTTTTH
  • ボブが得た系列
    • TTTTTTTTTTTTTTTTTTTT

アリスはイカサマだと抗議するが、ボブは以下のように反論する。

ボブ「コインを20回投げて現れる系列のパターンは $2^{20}$ 通り、その中から特定の ランダムな 系列を得る確率は $2^{-20}$。 アリスが HHHTHTHTTHTHHTHTTTTH を得る確率も私が TTTTTTTTTTTTTTTTTTTT を得る確率も全く同じなのだからこれは公平な勝負だよね」

ボブは彼とアリスが得る系列の確率が同じだからこの勝負は公平だと主張したわけである。賢いアリスは納得しない。 アリスは特定の系列を得る確率は、そのランダム性に関する情報を含んでいるわけではないのでこの文脈ではその主張は使えないと反論する。

アリスが自分の系列がボブの系列よりランダムであることを示すのは簡単に思える。 確率を使う代わりに、アリスは特定の系列（文字列、配列）がいかに記述しにくいかという観点で指摘をしようと思った。 しかしこれはあまり厳密ではないので、以下の議論ではKolmogorov複雑性として知られる数学的道具を用いてアリスの反論を助けていこう。 まず、ボブの系列をPythonで記述してみよう。

In [0]: 'T'*20
Out[0]: TTTTTTTTTTTTTTTTTTTT

このコードの長さ自体は6文字であり、元の20文字より短い。

In [1]: len("'T'*20")
Out[1]: 6

アリスの系列をPythonで記述しようとした場合、かなり複雑な記述になることは想像に難くない。おそらく20文字に等しいかそれ以上の長さになるだろう。

また、こうした記述を行う際は、記述言語も重要である。Pythonでは6文字だったが、JavaScriptでは以下のようになる。

>> "T".repeat(20)
"TTTTTTTTTTTTTTTTTTTT"

>> "\"T\".repeat(20)".length
14

記述言語が変わっただけで文字数が6文字から14文字に増えた点に注目してもらいたい。 文字列の複雑さは記述しようとしている文字だけでなく、それを記述する言語にも依存するのである。

ここまでの考察をまとめて数学的記述に落とし込むと、Kolmogorov複雑性 (KC) を以下のように定義できる。

$KC(x) = \min \lbrace|d|: L(d) = x \rbrace $

ここで $L$ は文字列 $x$ と同じ出力を与えるプログラム $d$ を受け入れる言語である。この数学的定義を先程までのPythonやJavaScriptの例に当てはめると以下のようになる。

Python

$KC('TTTTTTTTTTTTTTTTTTTT') = \min \lbrace |d|:Python(d)='TTTTTTTTTTTTTTTTTTTT' \rbrace = 6$

$where,d \in \lbrace'T'*20,'TTTTTTTTTTTTTTTTTTTT',... \rbrace$

JavaScript

$KC('TTTTTTTTTTTTTTTTTTTT') = \min \lbrace |d|:JavaScript(d)='TTTTTTTTTTTTTTTTTTTT' \rbrace =14$

$where,d \in \lbrace 'T'.repeat(20), 'TTTTTTTTTTTTTTTTTTTT',... \rbrace$

ここでは文字列のKolmogorov複雑性を、その文字列を出力する最短プログラムの長さと定義している。 そしてこうして定義したKolmogorov複雑性が文字列のランダム性を示してくれるという考え方をする。 Kolmogorov複雑性が文字列の長さに等しい文字列は、Kolmogorov複雑性が文字列より短いものよりもランダムである、ということである。

さらに、Kolomogorov複雑性が以下のように文字列の長さ以上の場合は圧縮できない。

$KC(x) \geq |x|$

さらに注意点として、文字列のKolmogorov複雑性は計算不能であることも気をつけたい。すべての文字列のKolmogorov複雑性を保証するコンピュータは存在しない。 これは数学的事実である。このことを感覚的に理解するために以下のパラドックスを考えよう。

興味深い数のパラドックス

興味深い数のパラドックスは、「すべての自然数は興味深い」という主張を中心に展開する。 1は最初の数だから興味深い。2は最初の偶数であるから興味深い。3は最初の奇素数であるから興味深い。4=2x2、4=2+2だから4も興味深い。 このようにして多くの数について興味深い性質を見つけることができる。さて、ある時点で興味深い性質を持たない数にぶち当たったとしよう。 その数を「最初の興味深くない数」と名付けることにしよう。しかし「興味深くない」という事実そのものが興味深いのである。 ゆえに興味深くない数は実際は興味深い数なのである。

Kolmogorov Complexity and Our Search for Meaning - Nautilus

この考え方から類推して、我々は自分たちが考えた最短のプログラムを最短であることを証明することができないのである（なぜなのか考えてみよう）。

特定の言語への依存を外せるか？

現状Pythonを使うかJavaScriptを使うかで複雑さが変わってしまう。これだと困るので言語 $L$ に依存しない複雑さが定義できないかと思うだろう。 すべての文字列に対して常に最短の記述長を与える普遍言語 $U$ が存在すると仮定してみよう。

つまり以下のような言語が存在すると考える。

$KC_{U}(x) \leq KC_{L}(x)+C$

この式の言わんとするところは、文字列 $x$ を言語 $U$ で記述する場合と、任意の言語 $L$ で記述する場合では、その複雑さが最大でも定数倍 $C$ 違うことを意味する。

ところで、先程述べたパラドックス（最短のプログラムは最短と証明できない）に立ち戻ってみよう。 このパラドックスによると $U$ は存在できないか、 $U$ は任意の $L$ よりも短い記述を提供できない。

この問題に対処するために、有効な記述言語の集合に制約を設けて、単一の普遍的な記述方法 $U$ を出現させることを可能にしてみる。ここで考えたいのがチューリング・マシンである。 チューリング・マシンはアルゴリズムの特性を分析しどの計算問題が実現可能か不可能かを決定するために使われる基本的な概念的コンピュータモデルである。

  • チューリングマシンモデルにおける停止性問題とは、任意のコンピュータプログラムの記述と入力から、 そのプログラムが実行を終了するか、永遠に実行され続けるかを判定するというよく知られた問題である。（Halting problem - Wikipedia）
  • 数学的には、停止性問題は $w$ が $H(TM)$ の要素であるようなすべての組 $(TM, w)$ 、ここで $H(TM)$ はチューリング・マシン $TM$ が停止ないし $\lbrace (TM, w): w \in H(TM) \rbrace $である入力の集合を表す
  • 上記の表現は、チューリング・マシンには停止するかしないか分からない入力が存在することを含意している

したがって、我々の普遍言語 $U$ をある入力で停止することが分かっているチューリング・マシンとしてモデル化すれば、上記で説明したパラドックを回避できる。

上記の観察から再出発して、Kolmogorov複雑性が言語にとらわれないものであるためには、 普遍言語 $U$ があらゆる入力 $w$ に対して $U(w) = x$ を出力として停止するチューリング・マシン $TM$ をシミュレーションする必要がある。

Kolmogorov複雑性の言語にとらわれない真の定義は以下のようになる。

$KC_{U}(x)=\min \lbrace |(TM,w)|: \text{TM halts on input w and outputs x} \rbrace $

正規化距離

Kolmogorov複雑性を定義すると、それを使って2つの文字列/オブジェクトがどれくらい似ているかを推定することができる。

2つの文字列間の 正規化情報距離（Normalized Information Distance） は以下のように定義できる：

$$ \begin{eqnarray} NID(x, y) = \frac{KC(x,y)−min(KC(x),KC(y))}{max(KC(x),KC(y))} \end{eqnarray} $$

ここで $KC(x,y)$ は $x$ と $y$ を連結した後のコルモゴロフ複雑性である。

正規化圧縮距離（Normalized Compression Distance） は以下のように定義できる。

$$ \begin{eqnarray} NCD(x, y) = \frac{C(x,y)−min(C(x),C(y))}{max(C(x),C(y))} \end{eqnarray} $$

ここで $C(x, y)$ は $x$ と $y$ を連結した後の圧縮長である。 $KC(x)$ は（gzipのような）圧縮機 $C$ を用いて $x$ をエンコードするのに必要なビット数により、合理的に推定できることが知られている。

アリスはこれらの知識を用いてボブをやり込めることができるだろう ✌

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment