めもめも

このブログに記載の内容は個人の見解であり、必ずしも所属組織の立場、戦略、意見を代表するものではありません。

Asymptotic equipartition property を説明するコードサンプル

大雑把な解説

「確率 p で表の出るコインを n 回投げる」という実験には 2^n 通りの結果がありますが、それぞれの結果 x^n の発生確率 p(x^n) を計算すると、n が大きい場合、その確率はある特定の値 p_0 のまわりに集中します。一方、この実験を多数回繰り返して、実際に得られたそれぞれの結果に対して発生確率 p(x^n) を計算すると、これもまた、ある特定の値 p_1 のまわりに集中します。

ただし、p_0p_1 は一致しません。一般に p_0 < p_1 という関係が成り立ちます。

なぜなら、確率 p_0 付近の事象は、その数は非常に多い代わりに、それらが発生する確率 p_0 はあまり大きくないため、実際のサンプルとして得られる数は少なくなるからです。サンプルとして得られる結果が多数集まる確率 p_1 は、p_0 よりも大きい値にずれるのです。

このズレを実際に乱数でサンプリングして示すと次の結果が得られます。

横軸は確率の対数 \log_2 p(x^n) で、縦軸は(正規化した)累積度数です。n=1000 の場合、\log_2 p(x^n)=-900 のあたりで赤色のグラフが急速に立ち上がっており、ほとんどのサンプルがこのあたりに集中していることを示します。一方、青色のグラフは、2^n 通りの結果が均等に発生したと仮定した場合のグラフです。こちらは、\log_2 p(x^n)=-1100 あたりで急速に立ち上がっており、潜在的に発生し得る事象の大部分は、このあたりに集中しています。

特に注目すべき点は、n=1000 の場合、赤色のグラフが立ち上がる \log_2 p(x^n)=-900 の部分において、青色のグラフはほぼ完全に立ち上がりきっており、その値はほとんど変化しなくなっていることです。これは、「潜在的に発生し得る事象の大部分は、現実には観測されることがない」という事を示しています。言い換えると、現実に観測される事象は、潜在的に発生し得る事象のごく一部にすぎないのです。

この事実は、データの圧縮処理に活用できます。個々の事象は、全部で 2^n 通りあり、生のデータとしては n bit の値として表現されていますが、「現実に観測されるごく一部のデータ」だけを集めて通し番号を振れば、ずっと小さな bit 数でラベリングできてしまいます。可逆性が求められない場合であれば、「現実に観測されるごく一部のデータ」以外の大部分のデータには、同じラベルを振ってしまえば高い圧縮率が実現されます。この圧縮方法は、厳密には可逆性が無いとは言え、同じラベルで潰れてしまうデータは、「現実に観測されるデータ」にはほとんど含まれないので、実用的には可逆性を保つものと考えることができます。

もうちょっと厳密な記述

「現実に観測されるデータ」が集中する部分の確率 p(x^n) は、2^{-nH(X)} に一致します。ここに、H(X) は、1回の試行 x に対する確率が持つエントロピーで、今の場合は 0\le H(X)\le 1 を満たします。先のグラフの破線は、-n\left\{H(X)\pm 0.1\right\} の範囲を示しています。

観測データの確率が 2^{-nH(X)} 付近に集中するという事実は、次の定理で表現されます。

まず、Typical set と呼ばれる集合を次で定義します。

 A^{(n)}_\epsilon = \left\{ x^n \mid 2^{-n(H(X)+\epsilon)} \le p(x^n) \le 2^{-n(H(X)-\epsilon)}\right\}

この時、任意の \epsilon > 0 に対して、

 \displaystyle \lim_{n\to\infty} {\rm Pr}\left[A^{(n)}_\epsilon\right] = 1

が成り立ちます。

次に、「確率が 2^{-nH(X)} 付近のデータは、潜在的に発生し得る事象のごく一部にすぎない」という事実は、次の関係式で示されます。

 |A^{(n)}_\epsilon| \le 2^{n(H(X)+\epsilon)}

これは、任意の n>0 について成り立ちます。今の場合、全データ数は 2^n ですので、全データに対する Typical set の割合は、

 \displaystyle \frac{|A^{(n)}_\epsilon|}{2^n} \le 2^{-n\left\{1-(H(X)+\epsilon)\right\}}

となり、H(X) = 1(つまり、p=\frac{1}{2} の一様分布)の場合を除いて、 十分に小さな \epsilon に対して、

 \displaystyle \lim_{n\to\infty} \frac{|A^{(n)}_\epsilon|}{2^n} = 0

が成り立ちます。

一般に、1回の試行に伴う結果(Alphabet)が d 種類ある場合、全データ数は d^n であり、Typeical set の割合は、

 \displaystyle \frac{|A^{(n)}_\epsilon|}{d^n} \le 2^{-n\left\{\log_2 d-(H(X)+\epsilon)\right\}}

となります。一様分布の場合を除いて H(X) < \log_2 d が成り立つので、この場合もやはり、

 \displaystyle \lim_{n\to\infty} \frac{|A^{(n)}_\epsilon|}{d^n} = 0

が得られます。

冒頭のサンプリングを実施するコードは、下記になります。


Example: Asymptotic equipartition property