情報理論の定義の話

この資料を参考につらつらと書いてみます。
Lecture 6; Using Entropy for Evaluating and Comparing Probability Distributions

今までに「エントロピーは未知の値を定式化」とか他にも色々言われたけど結局よくわかりませんでした。式を見ても、よくわかならいので、例が欲しい、と行き着いた先が上の資料です。

上の資料を翻訳しただけですが、これはわかりやすかったです。
まず、僕は今NLP（自然言語処理）の領域にいるので、NLPの例に考えます。あと最近トピックモデルも勉強しているので、各文が「圧縮」、「言語モデル」、「その他」のいずれかのトピック（話題）について話しているとします。

例：
ハフマン符号すげー！　（圧縮）
ニューラル言語モデル、時間かかりすぎワロタ　（言語モデル）
コミケ初日と東京湾花火大会は被っている！！！　（その他）

僕がそれぞれの話題を話す確率を仮に
圧縮：0.8
言語モデル：0.15
その他：0.05
とします。

どういう話題が出てきたかを、符号化する（1と0で表す）時、一つの話題に関して何ビット必要なのか？1ビットは1と0から成るので、一番直観的な解答は2ビットですね（2^2 = 4 > 3より）。例えば、圧縮：00　言語モデル：01　その他：10　と割り振ってみましょう。
上の例を符号列で表すと、00(圧縮) 01(言語モデル) 10(その他)と3つの話題があるので6ビットになります。

ただここではそれぞれの話題を話す確率がわかっているので、「よく現れる話題には短い符号を割り当てる」ことで、符号列が短くなりますね。例えば
圧縮:0 言語モデル:10 その他:11
とした場合、符号列は
0(圧縮) 10(言語モデル) 11(その他)
と5ビットに短くなりますね。

では理論的に最小のビット列の長さは何でしょうか？情報理論の定義がそれを導きだしてくれます。

X_i:確率変数
P:確率

Xのエントロピーとは、
H(X) = -\sum_{i}P(X_i)\log_{2} (P(X_i))

これがよく教科書とかでも出てくる「情報理論的下限値」とかですね。実際に上の例を計算してみましょう。

X:話題であるとし、
H(X) = -(0.8 * log(0.8) + 0.15*log(0.15) + 0.05 * log(0.05))
=~ -(-0.258 + -0.411 + -0.216) ※下3桁で四捨五入してます
= 0.88

すなわち話題を表す符号列は一話題辺り平均0.88ビットで表せる、ということですね。「え、1ビット切ってる！？私のエントロピー低すぎ！？」と驚かれるかもしれませんが、これは「一つの話題に関してしか話さない人は話題の符号列はいらない=0ビット」より、1ビットを切っています。

つまり、上の例は理想的には約0.88 * 3 = 2.64ビットで表すことができます。5ビットの約半分ですね。どうやるんでしょうね。

ちなみに、上の定義では理論値はわかりますが、実際にどのように符号化すればいいかは教えてくれません。そのあたりの話を多分次回、符号化や圧縮の話の所で書きます。

あと、上の話題の確率が0.33ですと一話題辺り平均約1.5ビットになります。話題が豊富な人はエントロピーも高いんですね。