Information gainについてメモ2

前回のあらすじ

離散確率変数Xの値xを観測したときに得る「情報量」を、 $-\log(p(x))$ で定義する。ただし、 $p(x)$ は確率質量関数。情報量は驚きの度合いを表していて、

その得られる確率が大きい $x$ に対しては情報量は小さく、確率の小さい $x$ に対しては情報量は大きい
$x, y$ が独立であるとき、その両方を観測したときの情報量はそれぞれの情報量の和である

などの性質がある。

エントロピー

離散確率変数 $X$ に対して、その値の情報量の期待値をエントロピーと呼ぶ。つまり、

${\displaystyle -\sum p(x)\log(p(x)) }$

を $X$ のエントロピーと呼ぶ。
ただし、 $p(x)=0$ のときは、この和では $p(x)\log(p(x))=0$ として扱う。

noiseless coding theorem

エントロピーは、確率変数の値を「伝える」のに最低限必要な平均ビット数を表す。*1 今回は、このことの証明はしないが、このことを調べる文脈でエントロピーが現れることを観察する。

素朴なコーディング

確率変数はa, b, c, d, e, f, g, hの8種類の値を取るとする。このうちどの値が観測されたかを伝えるには、3ビットあればよい。
つまり、

a = 000, b = 001, c = 010, d = 011, e = 100, f = 101, g = 110, h = 111

などと符号化（コーディング）すれば、すべての値を表現できる。

工夫したコーディング

同じ状況で、それぞれの値をとる確率は偏っているものとする。例えば $p(a) = \frac{1}{2}, p(b) = \frac{1}{4}, p(c) = \frac{1}{8}, p(d) = \frac{1}{16},$
$p(e) = \frac{1}{32}, p(f) = \frac{1}{64}, p(g) = \frac{1}{128}, p(h) = \frac{1}{128}$
であることが分かっているとする。この場合、それぞれの情報量（その値だった場合の驚き度）に応じた長さの符号化をしたほうが効率が良い。例えば

a = 0, b = 10, c = 110, d = 1110, e = 11110, f = 111110, g = 1111110, h = 1111111

と符号化すれば、平均して $\frac{1}{2}\times 1 + \frac{1}{4}\times 2 + \frac{1}{8}\times 3 + \frac{1}{16}\times 4 + \frac{1}{32}\times 5 + \frac{1}{64}\times 6 + \frac{1}{128}\times 7 + \frac{1}{128}\times 7$

ビットでそれぞれの値を表現できる。この値 $1.984375$ がエントロピーである。

ほとんどの値は素朴なコーディングよりも長いコードで表現されるが、出現頻度の高いものを短くコーディングすることでビット数を節約できていることになる。

具体例

aaaaabadaaaaaeaaccaabbcbbadbdabbabaabcacaaaabbaacacbabdbabcabccafabaaabababacbeaabbddcafbabcdbaaeaaaaaagaaaaaaahccabcaabeabababd

aが64個、bが32個、cが16個、dが8個、eが4個、fが2個、gとhが1個含まれている、全部で128字の文字列をコード化することを考える。

素朴なコーディングでは、単純に1文字を3ビットでコーディングするので

000000000000000001000011000000000000000100000000010010000000001001010001001000011001011000001001000001000000001010000010000000000000001001000000010000010001000001011001000001010000001010010000101000001000000000001000001000001000010001100000000001001011011010000101001000001010011001000000100000000000000000000110000000000000000000000111010010000001010000000001100000001000001000001011

このように $384$ ビットとなる。この $384$ というのは、 $128\times 3$ のことである。このコードから元の文字列を復元するには、3桁ずつに区切ればよい。

工夫したコーディングでは、よく現れるものほど短いコードになっているので

00000100111000000111100011011000101011010100111010111001010010001011001100000101000110011010010111010010110010110110011111001000010010010011010111100010101110111011001111101001011011101000111100000001111110000000011111111101100101100010111100100100101110

このように $254$ ビットとなる。この $254$ というのは、 $128\times 1.984375$ のことであるから、たしかにエントロピーが現れている。このコードから元の文字列を復元するには、先頭から順に、そのコードに当てはまる文字があるかどうかを見ればよい。

注意

今回、エントロピーを情報量の期待値としたが、エントロピー自体を情報量と呼ぶこともある。区別する場合は、確率変数の値の情報量を「選択情報量」、エントロピーを「平均情報量」と呼んで区別するらしい。

熱力学のエントロピーとは無関係だと思ってよい。少なくとも、熱力学のエントロピーに対してあいまいなイメージしか持っていない場合、無関係だと思ったほうがたぶん良い。

参考

■PRML 1章 http://www.amazon.co.jp/dp/4621061224

■wikipedia Shannon's source coding theorem https://en.wikipedia.org/wiki/Shannon%27s_source_coding_theorem

*1:対数の底は2であることにする。