情報理論について、エントロピーとか符号とか：めも

情報理論のメモ

あくまでメモなので、"定義域を○×として、..."といった記述はないです。

参考文献

ELEMENTS OF INFORMATION THEORY : Thomas M.Cover, Joy A.Thomas
情報理論基礎と広がり: Thomas M.Cover, Joy A.Thomas, 山本博資, 古賀弘樹, 有村光晴, 岩

エントロピーと相互情報量について

とりあえず、授業でつかうエントロピーの定義とその他定理や定義を紹介。
情報の概念をとらえる方法はいろいろあるけれど、確率分布に基づいた見方をしたらエントロピーの式が出てくる。エントロピーには直感的にも納得できるような性質もいくつかある。章を読み進めていけば、この定義が情報のやり取りに関する多くの疑問に自然な解答を与えてくれるでしょう。

${ \displaystyle H(X) = - \sum_{x \in z\chi} p(x) log_2 p(x) }$
この定義によると、確率1/2で表裏になるコイントスが与える情報量は1.この式を書き換えると、
${ \displaystyle H(X) = - \sum_{x \in z\chi} p(x) log_2 p(x) = E_p log \frac{1}{p(x)}\\ }$
つまり $\frac{1}{p(x)}$ の平均と見て取れる。そして不等式
${ \displaystyle H(X) \leq 0 }$
が成り立つ。なぜなら $\frac{1}{p(x)} \leq 0$ がいつも成り立つから。

以下では（すこし混乱を招くかもしれないけど）便利な記述
${ \displaystyle H(X) = -plog p - (1 - p) lg (1 - p) := H(p) }$
を導入する。この式を微分すると
${ \displaystyle \frac{dH(p)}{dp}\\ = -logp - 1 + log(1 - p) + 1\\ = -log \frac{1-p}{p} }$
この式はp=1/2のとき、最大となる。そのとき、エントロピーは1.

結合エントロピー（joint entropy)

${ \displaystyle H(X,Y) = - \sum_x \sum_y p(x,y) lg p(x,y) }$
とする、先と同じように
${ \displaystyle H(X,Y) = E_p log \frac{1}{p(X,Y)} }$

条件付きエントロピー

${ \displaystyle H(Y|X) = - \sum_x p(x) H(Y|X=x) }$
と定義する、この式も少し変形をすれば、
${ \displaystyle H(Y|X)\\ = - \sum_x p(x) H(Y|X=x) \\ = - \sum_x p(x) \sum_y p(y|x) lg p(y|x) \\ = - \sum_x \sum_y p(x,y) lg p(y|x)\\ = E lg \frac{1}{p(Y|X)} }$
と記述できる。そして、結合エントロピーはこの条件付きエントロピーを用いて、
「XとYによるエントロピー」＝「Xのみによるエントロピー」＋「Xが決まったときのYによるエントロピー」
に分解できる。
${ \displaystyle H(X,Y) \\ = \sum_x \sum_y p(x,y) lg p(x,y) \\ = \sum_x \sum_y p(x,y) lg p(y|x)p(x) \\ = \sum_x \sum_y p(x,y) \{ lg p(y|x) - lg p(x) \} \\ = \sum_x \sum_y p(x,y) lg p(y|x) - \sum_x \sum_y p(x,y) lg p(x)\\ = H(Y|X) + H(X) }$
である。

相対エントロピー（カルバック・ライブラー距離）

相対エントロピーを
${ \displaystyle D(p || q) \\ = \sum_x p(x) log \frac{p(x)}{q(x)}\\ = E_p log \frac{p(X)}{q(X)} }$
と定義する。これは、確率密度関数間の”違い”をはかりとる尺度と見て取れる。実際、pとqの分布が同じならこの式の値は０になる。

相互情報量

${ \displaystyle I(X;Y) \\ = \sum_x \sum_y p(x,y) log \frac{p(x,y)}{p(x)p(y)}\\ = D(p(x,y) || p(x)p(y) ) }$
と相互情報量を定義する。この式がゼロになるのはXとYが互いに独立であるとき。XとYの間に（独立、つまり全く関係ない時と比べて）どれくらいの関係を持っているかがこの指標からはかりとれる。もしこれが本当なら、Yを決めたときにその分Xのエントロピーが減少するはずである。
${ \displaystyle I(X;Y) \\ = \sum_x \sum_y p(x,y) log \frac{p(x,y)}{p(x)p(y)}\\ = \sum_x \sum_y p(x,y) log \frac{p(x|y)}{p(x)}\\ = - \sum_x \sum_y p(x,y) log \frac{p(x)}{p(x|y)}\\ = - \sum_x \sum_y p(x,y) logp(x) - (- \sum_x \sum_y p(x,y) log p(x|y)) \\ = - \sum_x p(x) log p(x) - (- H(X|Y))\\ = H(X) - H(X|Y) }$
で確認できる。さらに H(X,Y) = H(X) + H(Y|X) = H(Y) + H(X|Y)だった。
この式より　H(X|Y) = H(X,Y) - H(Y) .この式を代入すると、簡単な定理
I(X;Y) = H(X) + H(Y) - H(X,Y)
を得られる。

各エントロピーに関する不等式

イェンセンの不等式(Jensen's inequality)

下に凸の関数、Xは変数として
${ \displaystyle E f(X) \leq f(EX) }$
が成り立つ。この式を利用する。証明はテイラー展開を使ってもいいし、うまく式変形してもできる。

情報不等式

${ \displaystyle D(p||q) \leq 0 }$
証明：
${ \displaystyle - D(p||q) \\ = - \sum_x p(x) log \frac{p(x)}{q(x)} \\ = \sum_x p(x) log \frac{q(x)}{p(x)} \\ \geq log \sum_x p(x) \frac{q(x)}{p(x)} \\ = log \sum_x q(x)\\ \geq log \sum_{xのドメイン} q(x)\\ = log 1\\ = 0　■ }$
以上より、情報不等式（カルバック・ライブラー距離は非負）が成り立つ。

相互情報量は非負 $I(X;Y) \leq 0$

証明：
I(X;Y) = D(p(x,y) || p(x)p(y) )
カルバック・ライブラー距離は非負なので相互情報量も非負。■

$H(X|Y) \geq H(X)$

${ \displaystyle I(X;Y) \\ = \sum_x \sum_y p(x,y) log \frac{p(x,y)}{p(x)p(y)}\\ = \sum_x \sum_y p(x,y) log \frac{p(x|y)}{p(x)}\\ = - \sum_x \sum_y p(x,y) log \frac{p(x)}{p(x|y)}\\ = - \sum_x \sum_y p(x,y) logp(x) - (- \sum_x \sum_y p(x,y) log p(x|y)) \\ = - \sum_x p(x) log p(x) - (- H(X|Y))\\ = H(X) - H(X|Y) }$
が成り立つ。今、相互情報量は非負だから
${ \displaystyle 0 \geq I(X;Y) \geq H(X) - H(X|Y)\\ よって\\ H(X|Y) \geq H(X) ■ }$

データ処理不等式（Data processing inequality）

この不等式は、要するに元のデータにいかなる処理を加えてももとのデータよりも多い情報量にすることはできない。（もとのデータが一番情報量が多い）と、自分は解釈。データ処理不等式（まだ出てきていない）なるものが成り立つためには、それらがマルコフ連鎖に従っている必要がある。

マルコフチェイン（マルコフ連鎖）

確率変数X、Y、Zがこの順番でマルコフ連鎖に従っているとき、それを X -> Y -> Z と書くことにする。このことはつまりZの確率密度関数は直前のYにのみ依存していて、Yの確率密度関数は直前のXにのみ依存していることをいっている。つまり、マルコフ連鎖ならば P(Z|X,Y) = P(Z|Y) である。

マルコフ連鎖の簡単な性質

${ \displaystyle 　p(x,z|y) \\ = \frac{p(x,y,z)}{p(y)} \\ = \frac{p(x,y)p(z|x,y)}{p(y)}\\ = \frac{p(x,y)p(z|y)}{p(y)} \\ = \frac{p(y)p(x|y)p(z|y)}{p(y)}\\ = p(x|y)p(z|y) }$
ほかのは少し検索したらすぐに出ると思う。