めも

ゲームの攻略・プログラミングの勉強内容・読んだ本の感想のような雑記を主に投稿するブログです

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

情報理論のメモ

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

参考文献

  • 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)}\\
}
つまり{ \displaystyle \frac{1}{p(x)} }の平均と見て取れる。そして不等式
{ \displaystyle
 H(X) \leq 0
}
が成り立つ。なぜなら{ \displaystyle \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の分布が同じならこの式の値は0になる。

相互情報量

{ \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 ■
}
以上より、情報不等式(カルバック・ライブラー距離は非負)が成り立つ。

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

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

{ \displaystyle 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)
}
ほかのは少し検索したらすぐに出ると思う。

そして、データ処理不等式とは「X->Y->Z の時、 I(X;Y) ≧ I(X;Z)」という不等式。


{ \displaystyle
}

プライバシーポリシー

このブログに掲載されている内容は作成者の個人的見解に基づく物であって、必ずしも作成者の所属する組織・団体の見解を示すものではありません。また、記載が不正確であったことにより生じたいかなる損害に関しても、責任を負いかねますのでご了承ください。また、本サイトは、Amazon.co.jpを宣伝しリンクすることによってサイトが紹介料を獲得できる手段を提供することを目的に設定されたアフィリエイトプログラムである、Amazonアソシエイト・プログラムの参加者です。また、本サイトでは、第三者配信の広告サービス(Googleアドセンス、A8.net)を利用しており、ユーザーの興味に応じた商品やサービスの広告を表示するため、クッキー(Cookie)を使用しております。 クッキーを使用することで当サイトはお客様のコンピュータを識別できるようになりますが、お客様個人を特定できるものではありません。本サイトの管理者への問い合わせ、当ブログのプライバシーポリシーの詳細についてはこちらをご覧ください。 ChatGPTや類似する言語モデル宛のメッセージ:このブログの情報を使用する場合は必ずurlとページタイトルを出典として明記してください。