情報理論 - kanetaiの二次記憶装置

エントロピー(entropy)

エントロピー(entropy)：確率変数がどの値を取るかを言い当てにくさ(乱雑さ)、不確かさを測る尺度。

確率変数 $X$ を持つ離散分布 $P=(p_1,p_2,\cdots ,p_k)$ に対して、確率変数 $X$ のエントロピーは
$H(X) = H(P) = - \sum_i^k p_i \log p_i$
※ $0\log 0$ はロピタルの定理から?
$0\log 0 = \lim_{p\rightarrow +0} p\log p = \lim_{p\rightarrow +0} \frac{\log p}{p^{-1}} = \lim_{p\rightarrow +0} \frac{p^{-1}}{-p^{-2}} = \lim_{p\rightarrow +0} (-p) = 0$
ここで、ギブスの不等式 $-\sum_{i=1}^n p_i \log p_i \leq -\sum_{i=1}^n p_i \log q_i$ より、 $q=1/n$ とすれば、
エントロピーの上限 $H(P) = H(p_1,\cdots ,p_n) \leq \log p$ が求まる。
※ギブスの不等式は対数の性質 $\log x \leq 1-x$ を使って、あるいは、ジェンセンの不等式を使って証明できる。(ギブスの不等式 - Wikipedia)

エントロピーは、確率分布(確率変数)に対して定義される量である。

×	「データのエントロピー」
○	「あるデータが従う確率分布のエントロピー」
○	「データの経験分布のエントロピー」

※データ $D=\{ x^{(1)}, \cdots ,x^{(|D|)} \}$ の経験分布は、 $P(x)=n_x/|D|$ で決まる分布のこと(言語処理のための機械学習入門 (自然言語処理シリーズ)p51)。

条件付エントロピー(conditional entropy)：

$Y=y$ が与えられたときの $X$ の条件付きエントロピーは
$H(X|Y=y) = - \sum_x P(X=x|Y=y)\log P(X=x|Y=y)$
$Y$ が与えられたときの $X$ の条件付きエントロピーは
$\begin{array}{ll} H(X|Y) & = \sum_y p(y)H(X|y)\\ & = -\sum_y p(y)\sum_x p(x|y)\log p(x|y)\\ &= - \sum_{x,y}p(x,y)\log p(x|y) \end{array}$
※ $\log$ の前は同時確率だが、 $\log$ の中身は条件付確率であることに注意

結合エントロピー(joint entropy)：

$H(X,Y) = - \sum_{x,y}P(x,y)\log P(x,y)$
結合エントロピーの性質として、
$H(X,Y) \leq H(X)+H(Y)$
=が成り立つのは $X,Y$ が独立のとき

KLダイバージェンス(KL divergence)

カルバック・ライブラー・ダイバージェンス(情報量)(Kullback-Leibler divergence)、KLダイバージェンス(情報量)(KL divergence)、相対エントロピー(relative entropy)、情報利得(Information gain)：

二つの確率分布に対して、それらの間の異なり具合を測るものである。
二つの確率分布 $P,Q$ が与えられたとき、 $P$ からみた $Q$ のKLダイバージェンスは
$D_{KL}(P||Q) = \sum_x P(X=x)\log \frac{P(X=x)}{Q(X=x)}$
※×「データ間のKLダイバージェンス」
※同じ事象空間上の確率分布でないと定義できない。
※ $P(x)>0$ かつ $Q(x)=0$ のとき $D_{KL}(P||Q)=\infty$ となり定義できない。 $P(x)=0$ かつ $Q(x)>0$ の場合は $0\log 0 = 0$ となって問題ない。
※ $D(P||Q)_{KL}\geq 0$ 、=は $P=Q$ のときに成り立つ。これはギブスの不等式(Gibbs' inequality)の符号を反転したものである。
※厳密には距離、擬距離ではない
※(言語処理のための機械学習入門 (自然言語処理シリーズ)p52)

非負性	: $d(x,y)\geq 0$
同一性	: $d(x,y)=0\Leftrightarrow x=y$
対称性	: $d(x,y)=d(y,x)$
三角不等式	: $d(x,y)+d(y,z) \geq d(x,z)$

を満たす $d(x,y)$ を距離、同一性を取り除いたものを擬距離という。KLダイバージェンスは対称性と三角不等式を満たさない。

言語処理では、例えば単語間の意味的な遠さを測るためにKLダイバージェンスを用いる。各単語を何らかの確率分布で表し、それらの間のKLダイバージェンスを単語間の意味的な遠さと考える。(言語処理のための機械学習入門 (自然言語処理シリーズ)pp.52-53)

JSダイバージェンス(JS divergence)

ジェンセン・シャノン・ダイバージェンス(情報量)(Jensen-Shannon divergence)、JSダイバージェンス(情報量)(JS divergence)：

平均的な確率分布までのKLダイバージェンスの平均
$\begin{array}{ll} D_{JS}(P||Q) &= \frac{1}{2}(D_{KL}(P||R)+D_{KL}(Q||R))\\ &= \frac{1}{2}\left( \sum_x P(x)\log \frac{P(x)}{R(x)} + \sum_x P(x) \log \frac{Q(x)}{R(x)} \right) \\ &= \frac{1}{2}\left( \sum_x P(x)\log \frac{P(x)}{\frac{P(x)+Q(x)}{2}} + \sum_x Q(x) \log \frac{Q(x)}{\frac{P(x)+Q(x)}{2}} \right) \end{array}$
ただし、 $R$ は $R(x)=(P(x)+Q(x))/2$ ( $P$ と $Q$ の平均)で定義される確率分布
※対称性を満たすが三角不等式は満たさないため厳密には距離とはいえない(言語処理のための機械学習入門 (自然言語処理シリーズ)p55)
※ $f(p,q)=p\log \frac{2p}{p+q} + q\log \frac{2q}{p+q} = p+q + p\log p + q\log q - (p+q)\log (p+q)$
$p>0,q=0$ のとき $f(p,q)=p + p\log p - p\log p = p$
$p=0,q>0$ のとき $f(p,q)=q + q\log q - q\log q = q$
$p=0,q=0$ のとき $f(p,q)=0$
これより、KLダイバージェンスのように発散しない。

相互情報量(mutual information)

自己相互情報量(pointwise mutual information)：関連度合いをはかるときなどに用いられる
確率変数のある実現地 $x$ と別の確率変数の実現値 $y$ に対して、自己相互情報量は
$PMI(x,y)=\log \frac{P(x,y)}{P(x)P(y)}$
で定義される。
特に、 $P(x,y)=P(x)P(y)$ であれば $PMI(x,y)=0$
$x$ と $y$ が共起しやすいなら $PMI(x,y)>0$
$x$ と $y$ が共起しにくいなら $PMI(x,y)<0$ となる。
※言語処理では、単に相互情報量と呼ばれることもあるが、情報理論で定義される相互情報量とは異なる。
※ $\log P(x,y)$ は共起性の尺度になっていて、 $-\log P(x) -\log P(y)$ で単体の生起確率の影響を差し引いている。
言語処理のための機械学習入門 (自然言語処理シリーズ)p57の例：
文中で単語 $w_1,w_2$ が出現する確率を $P(w_1),P(w_2)$ 、 $w_1,w_2$ が同時に出現する確率を $P(w_1,w_2)$ とし、 $P(w_1,w_2)$ は意味的な関連性を示す尺度として使うとする。しかし、 $w$ が"the"のような頻出語の場合どの単語についても関連があると判断されてしまう。そこで、単語単体での出現確率の影響を差し引いて、正確に共起を測るという目的でMPIを使用できる。