情報理論、エントロピーからガウス型通信路まで：1

情報理論のメモ

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

参考文献

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

エントロピーと相互情報量

エントロピーの定義

${ \displaystyle H(X) = -\sum_{k = 1}^n p(x) \log p(x_k) }$
を離散的な確率変数Xに対するエントロピーと定める。logの底は2。つまり、この定義では0か1の二値しかとらずにともに等しい確率ならばその確率変数のエントロピーは1となる。

ex1 確率変数Yは

${ Y　＝　\left\{ \begin{array}{l} 0 p(0)=\frac{1}{2}\\ 1 p(1)=\frac{1}{4}\\ 2 p(2)=\frac{1}{4} \end{array} \right. \\ ならばこのYのエントロピーは H(Y) = -\sum_{k = 1}^3 p(x) \log p(x) = 1 + \frac{1}{2} + \frac{1}{2} = 2 }$

同時エントロピー

同時確率分布p(x,y)について
${ \displaystyle H(X,Y) = -\sum_{k = 1}^n \sum_{l = 1}^m p(x_k,y_l) \log p(x_k,y_l) }$
をXとYの同時エントロピーと定義する。

条件付きエントロピー

${ \displaystyle H(Y|X)\\ = -\sum_{k = 1}^n p(x_k) \log p(Y|X = x_k) \\ = -\sum_{k = 1}^n p(x_k) \sum_{l=1}^m p(y_l|x_k) \log p(y_l|X = x_k) \\ = -\sum_{k = 1}^n \sum_{l = 1}^m p(x_k) p(y_l|x_k) \log p(y_l|X = x_k) \\ = -\sum_{k = 1}^n \sum_{l = 1}^m p(x_k,y_l) \log p(y_l|X = x_k) (1) \\ = -\sum_{k = 1}^n \sum_{l = 1}^m p(x_k,y_l) \log \{ \frac{p(x_k,y_l)}{p(x_k) }\} \\ = -\sum_{k = 1}^n \sum_{l = 1}^m p(x_k,y_l) \{ \log p(x_k,y_l) - \log p(x_k) \} \\ = -\sum_{k = 1}^n \sum_{l = 1}^m p(x_k,y_l) \log p(x_k,y_l) + \sum_{k = 1}^n \sum_{l = 1}^m p(x_k,y_l) \log p(x_k) \\ = H(X,Y) + \sum_{k = 1}^n p(x_k) \log p(x_k) \\ = H(X,Y) - H(X) (2) }$ 　
(1)、(2)式がよく使う式。

相対エントロピー

${ \displaystyle D(p||q) = -\sum_{k = 1}^n p(x_k) \log \frac{p(x_k)}{q(x_k)} }$
これは、二つの分布p,qに関する尺度の一つでカルバックライブラー距離とも言う。そして、相対エントロピーを定義する。

相互情報量

${ \displaystyle I(X,Y)\\ = D(p(x,y) || p(x)q(x)) \\ = \sum_{x,y} p(x,y) \log \frac{p(x,y)}{p(x)p(y)} (1)\\ = \sum_{x,y} p(x,y) \log \frac{p(y|x)}{p(y)} \\ = \sum_{x,y} p(x,y) \{ \log p(y|x) - \log p(y) \} \\ = -\sum_{x,y} p(x,y) \log p(y) + \sum_{x,y} p(x,y)\log p(y|x) \\ = H(Y) - H(Y|X) (2-1)\\ = H(X) - H(X|Y) (2-2) }$
相互情報量はXがYの情報をどれだけ含んでいるかの尺度で、その数値をしらべるには「X、Yの同時分布」と「X、Yが独立だと仮定したときの分布」の二つの分布をくらべる。そのため、 D(p(x,y) || p(x)q(x))という式になると考える。あとここからしたは総和の範囲は明示しない限りX,Yなどのとりうる離散値すべてとする。また(2-1,2-2)の式から、一方の情報が分かっている時の残りのエントロピー（？）のような式の形になることからも、この定義がXがYの情報をどれだけ含んでいるかの尺度のひとつであると思い出せる。

エントロピーのチェイン規則

${ \displaystyle H(X_1,X_2)\\ = -\sum_{X_1,X_2} p(x_1,x_2) \log p(x_1,x_2)\\ = -\sum_{X_1,X_2} p(x_1,x_2) \log p(x_2|x_1)p(x_1)\\ = -\sum_{X_1,X_2} p(x_1,x_2) \{ \log p(x_2|x_1) + \log p(x_1) \} \\ = -\sum_{X_1,X_2} p(x_1,x_2) \log p(x_2|x_1) -\sum_{X_1,X_2} p(x_1,x_2) \log p(x_1) \\ = H(X_2|X_1) + H(X_1) }$
とわかる、変数が $X_1 , X_2 , X_3$ ならば、
${ \displaystyle H(X_1,X_2,X_3)\\ = H(X_3,X_2|X_1) + H(X_1) \\ = H(X_3|X_2,X_1) + H(X_2|X_1) + H(X_1) }$
とわかる。

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

イェンセンの不等式(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) ■ }$

一様分布がエントロピー界で最強

これを示すために離散確率変数Xの定義域 $\chi$ の要素数をnとすると任意の $x \in \chi$ について $p(x) = \frac{1}{n}$ である。ここで一様分布uniform(X)と任意の分布p(X)についての相対エントロピーを求めると
${ \displaystyle D(p||uniform) \\ = -\sum_{x \in \chi} p(x) \log \frac{p(x)}{uniform(x)}\\ = H_{uniform} (X) - H_p (X) \\ = n - \sum_{x \in \chi} p(x) \log p(x) \\ \geq 0 }$
だから、この不等式から一様分布のときにエントロピーが最大となることが分かる。これが証明。

データ処理不等式

この式はざっくりと「元のデータにどのような加工を加えても元データを越えた情報を含むことはない」という式らしい。そしてこの式が成り立つためにいくつか過程を導入、というかこの項目だけX->Y->Z (X,Y,Zの順でマルコフ連鎖になっている)と過程する。するとデータ処理不等式

$I(X;Y) \leq I(Z;Z)$

が成り立つ。
証明：
${ \displaystyle I(X;Y,Z) = I(X;Z) + I(X;Y|Z) = I(X;Y) + I(X;Z|Y) (1) }$
と式変形できる。ここで、X,Zは独立だからI(X;Z|Y)=0。さらに相互情報量は非負だからI(X;Y|Z)は零以上で(1)式より、

${ \displaystyle I(X;Z) + I(X;Y|Z) \leq I(X;Y) \Leftrightarrow I(X;Z) \leq I(X;Y) }$

である。等号が成り立つためには最後の式で I(X;Y|Z) ＝ 0である必要がある、つまりX->Z->Yでもマルコフ連鎖になっている必要がある。■

Fanoの不等式（ファノの不等式）

この不等式は確率変数Xが通信路を通じてYになったとするとき、X≠Yである（誤った情報になっている）かどうかに関係するエントロピーH(X|Y)とXを推測した際の誤り率 $P_e = Pr\{\hat{X} \neq X \}$ を結びつける不等式でもちろんあとから通信路関係で重要な式になるらしい。

【ファノの不等式】 $X->Y->\hat{X}$ 、 $P_e = Pr\{\hat{X} \neq X \}$ であるとする。この時、
${ \displaystyle H(P_e) + P_e \log | \chi | \leq H(X|\hat{X}) \leq H(X|Y) \\ \chi := 離散確率変数Xのとりうる値の集合の要素数 }$

が成り立つ。この式でエントロピーが最大1であることを考慮すれば、

${ \displaystyle 1 + P_e \log | \chi | \leq　H(P_e) + P_e \log | \chi | \leq H(X|\hat{X}) \leq H(X|Y) \\ }$

この式から、誤り率 $P_e = Pr\{\hat{X} \neq X \}$ には下界があることがわかる。
証明：
参考文献＊情報理論基礎と広がり p29より
誤りが発生したことを示す確率変数Eを用意して以下のように定義する。
${ \displaystyle E = \left\{ \begin{array}{l} 0 when \hat{X} = X\\ 1 when \hat{X}\neq X \end{array} \right. }$
つまり、誤りが発生したときには1になる確率変数である。いま、 $H(E,X | \hat{X})$ を考える。この式を考える理由はこの式を書き換えると元の不等式に含まれる $H(X|\hat{X})$ を引き出すことができるから。
${ \displaystyle H(E,X | \hat{X}) \\ = \left\{ \begin{array}{l} H(X| \hat{X} ) + H(E | X,\hat{X}) \\ H(E| \hat{X} ) + H(X | E,\hat{X}) \\ \end{array} \right. }$

ここで式の意味を考えると

$H(E | X,\hat{X})$ :Xを推測した値とXの真の値が条件なのでそれが誤りかどうかは明らかに分かるから、エントロピーは0
$H(E| \hat{X} )$ :真の値を知っているときに、推測する値が間違っていることを示すエントロピーはH(E)。これと比較すると条件つきエントロピーはかならずエントロピーを同じ（つまり条件つけしたけど意味ない）かエントロピーを小さくするので $H(E| \hat{X} ) \geq H(E)$
$H(X | E,\hat{X})$ :推測した値とそれが誤りかをしっているとき、Xが二値変数ならエントロピーは0だけど今は一般的な場合を言っているので $|\chi|-1$ 個のパターンの誤り方がある。エントロピーを最大にする時は一様分布の時だったことを踏まえて $H(X | E,\hat{X}) \geq P_e \log (| \chi | - 1)$ となる。

このことを踏まえて、もとの式に上であたらしく分かった大小関係を代入すると、

${ \displaystyle H(E,X | \hat{X}) \\ = \left\{ \begin{array}{l} H(X| \hat{X} ) + H(E | X,\hat{X}) = H(X| \hat{X} ) \\ H(E| \hat{X} ) + H(X | E,\hat{X}) \leq H(E) + P_e \log |\chi - 1| \end{array} \right.\\ ※|\chi - 1|は間違っているときは \hat{X} \neq X であり、\hat{X} \neq Xとなるような\hat{X}は|\chi - 1|パターンあるから。 }$