機械学習で用いられるDivergence(KL-Divergence)やらEntropy (Cross-Entropy)の世界へ入門する

#0. 概要
分布を用いる際によく出てくるDivergenceやらEntropy、具体的にはKullback-Leibler DivergenceやJensen–Shannon Divergence、Cross Entropy等がある。彼らについて調べてみたのでまとめる。

# 1. Kullback-Leibler Divergence
ベイジアンニューラルネットワークなどの分布を用いる計算式に必ずでてくる分布間の類似度を測るものがKullback-Leibler Divergenceである。
日本語では、KL情報量なんていう風に呼ばれている。これは、端的にいうと2つの確率分布がどの程度似ているかを示すものである。似ている度合いを「距離」と表現する場合もあるが、厳密には距離の公理に反するためKL情報量は距離という尺度ではない。

# 1.1. 理論
KL情報量の理論を説明する。

## 1.1.1 定義
同じ確率空間上の離散確率分布を$P$及び$Q$とする。この時、この2つの確率分布の類似度は以下で定義される。

``` math
{D_{KL}(P||Q) = -\sum _{x\in X}P(x)\log \frac{Q(x)}{P(x)}}
```

確率間の対数差における期待値なので、符号を取れば分母と分子が以下のように入れ替わるだけである。

``` math
{D_{KL}(P||Q) = \sum _{x\in X}P(x)\log \frac{P(x)}{Q(x)}}
```

なお、連続確率分布である場合は以下のように定義される。

``` math
{D_{KL}(P||Q) = \int_{-\infty}^{\infty}p(x)\log \frac{p(x)}{q(x)}dx}
```

## 1.1.2 性質
代表的な性質としては、$P=Q$の場合、$D_{KL}(P||Q)=0$と定義されている。また、$D_{KL}(P||Q)\geq0$で非負である。
同じ確率分布が与えられた場合、以下のような展開式となる。

```math
D_{KL}(P||P) = \int_{-\infty}^{\infty}p(x)\log \frac{p(x)}{p(x)}dx
         = \int_{-\infty}^{\infty}p(x)\log(1)dx
         = 0
```

一致している場合は$\log(1)=0$となり、得られる値は0である。

他のもまとめると以下のように4つの性質を持つ。

<b>非負性</b>: 非負である。

``` math
0 \leq D_{KL}( Q \mid\mid P ) \leq \infty
```

<b>完備性</b>: 値が0のとき、2つの確率分布$P$及び$Q$は同等

``` math
D_{KL}( Q \mid\mid P ) = 0 ~~ \Leftrightarrow ~~ P = Q
```

<b>非対称性</b>: 値は$P$及び$Q$に対して対称性を持たない

``` math
D_{KL}( Q \mid\mid P ) \neq D_{KL}( P \mid\mid Q ) 
```

<b>絶対連続性</b>: 値が発散しない限り、$Q$は$P$に対して連続である。

```math
D_{KL}( Q \mid\mid P ) \lt \infty ~~ \Rightarrow ~~ P \gg Q 
```

距離の公理は「非負性」、「完備性」、「対称性」、「三角不等式」を満たすことであり、KL情報量は「非負性」及び「対称性」の2つのみしか当てはまらない。このため、Divergenceと呼ばれている。Divergenceの公理は距離の公理である「非負性」及び「対称性」を満たすものである。よって、情報量であったり、乖離度、逸脱度等の名称で呼ばれている。

## 1.1.3 導出
ある分布に従って得られる観測データ$x$を確率変数$P_{(x)}$とする。

``` math
P_{(x)} = p(X=x)
```

次に新たな観測$a$が得られた。この時、$a$を事前確率分布に追加した$x$が確率変数$X$に従っている確率を$Q_{(x)}$とする。

``` math
Q_{(x)} = p(X=x \mid a)
```

この時、KL Divergenceは$X=x$と$X=x \mid a$の差を知ることである。
よって、$a$を得る前と後の差分を計算すればよいので、

``` math
{\big(-\log Q(x) \big)-\big(-\log P(x) \big)= \log \frac{P(x)}{Q(x)}}
```

となる。最後に期待値を計算するために、各構成要素とそれらが生じる確率の積和を求める。

``` math
{D_{KL}(P||Q) = \sum _{x\in X}P(x)\log \frac{P(x)}{Q(x)}}
```

$\sum$で確率の積和を付けただけである。


## 1.2. 計算
2つの離散確率分布$P$及び$Q$を以下に定義する。なお、離散値は3つとする。また、対数の低に$e$を取るため、$\ln$を用いる。

| $x$| 0 | 1 | 2 |
|:-----------:|:------------:|:------------:|:------------:|
| Distribution $P(x)$ | 0.2 | 0.7 | 0.1 |
| Distribution $Q(x)$ | 0.3333 | 0.3333 | 0.3333 |

次に、$D_{KL}( P \mid\mid Q )$及び$D_{KL}( Q \mid\mid P )$を求めてみる。
まずは、$D_{KL}( P \mid\mid Q )$を求める。

``` math
D_{KL}(P \mid\mid Q) = \sum _{x\in X}P(x)\log \frac{P(x)}{Q(x)} = \sum _{x\in X}P(x)\ln \frac{P(x)}{Q(x)}\\
= 0.2 \ln(\dfrac{0.2}{0.333}) + 0.7 \ln(\dfrac{0.7}{0.333}) + 0.1 \ln(\dfrac{0.1}{0.333}) = 0.29679373
```

次に、$D_{KL}( Q \mid\mid P )$を求める。

``` math
D_{KL}(Q \mid\mid P) = \sum _{x\in X}Q(x)\ln \frac{Q(x)}{P(x)}\\
= 0.333 \ln(\dfrac{0.333}{0.2}) + 0.333 \ln(\dfrac{0.333}{0.7}) + 0.333 \ln(\dfrac{0.333}{0.1}) = 0.3242870
```

# 2. Jensen–Shannon Divergence
KL Divergenceは$D_{KL}( P \mid\mid Q )$及び$D_{KL}( Q \mid\mid P )$の対称性がないことからも分かる通り、距離として扱えなかった。
そこで、提案されたのがJensen–Shannon Divergenceである。Jensen–Shannon Divergenceの$D_{JS}(p, q)$及び$D_{JS}(q, p)$は同じ計算結果になり対称性がある。

よく言われるのは、KL Divergenceを平滑化+対称性を持たせたものがJS Divergenceである。

## 2.1. 理論
Jensen–Shannon Divergenceの理論について説明する。

## 2.1.1 定義
Jensen–Shannon Divergenceを以下のように定義する。

``` math
{D_{JS}(P||Q) = \alpha D_{KL}( P \mid\mid M ) + \alpha D_{KL}( Q \mid\mid M )}
```

ここで、$M$を以下のように定義する。

``` math
M=\alpha(P+Q)
```

$\alpha=\dfrac{1}{2}$の時に対称となるので、

``` math
D_{JS}(P||Q) = \dfrac{1}{2}D_{KL}( P \mid\mid M ) + \dfrac{1}{2}D_{KL}( Q \mid\mid M ) \\
=\dfrac{1}{2} \bigg\{  D_{KL}( P \mid\mid \dfrac{P}{2} + \dfrac{Q}{2} ) + D_{KL}( Q \mid\mid \dfrac{P}{2} + \dfrac{Q}{2} ) \bigg\}
```

となる。これは$D_{JS}(P||Q) == D_{JS}(Q||P) $であり、対称性を持つ。


# 3. Shanon Entropy
シャノンは、あらゆる事象が全て同じ確率で起こる場合に不確実性の高さを最大とした。これを表す尺度として$H$がある。
多くの情報量理論で用いられている基本的な定理である。

## 3.1. 理論
Shanon Entropyの理論について説明する。

## 3.1.1 定義
何らかの事象を示す離散確率変数$M$があった時に、この$M$の不確かさの尺度を$H$とする。

``` math
H(M) = \mathbf{E}_{\mathbf{M}}[- \log p(m)] = - \sum _{m\in \mathbf{M}} p (m) \log p(m)
```

全ての事象が同じ確率で発生する場合に、エントロピーは最大値$H(M)=\log |\mathbf{M}|$となる。

関数$H$を確率分布で表すと次のようになる

``` math
H(p)= - \sum^{k}_{i=1} p(i) \log p(i)  = \sum^{k}_{i=1} p(i) \log (\dfrac{1}{p(i)})
```

ここで$\sum^{k}_{i=1} p(i)=1$とする。

# 4. Cross Entropy
Cross Entropyは2つの確率分布の差を表す尺度である。主にニューラルネットワークのクラス分類等に用いられている。
基本的にはKullback–Leibler divergenceと同じ尺度を提供している。

## 4.1. 理論
Cross Entropyの理論について説明する。

## 4.1.1 定義
同じ確率空間における2つの離散確率変数$p$及び$q$のCross Entropyを以下のように定義する。

``` math
H(p, q)= - \sum_{x} p(x) \log q(x)
```

なお、連続値の場合は以下となる。

``` math
H(p, q)= - \int_{X} p(x) \log q(x)
```

## 4.2 Kullback–Leibler divergenceから見るCross Entropy

Shanonは不確実性を以下のように定量化した。

``` math
H(M) = \mathbf{E}_{\mathbf{M}}[- \log p(m)] = - \sum _{m\in \mathbf{M}} p (m) \log p(m)
```

次に、確率分布$P$及び$Q$の類似度を測る尺度として$D_{KL}$が以下のように定義された。

``` math
{D_{KL}(P||Q) = \sum _{x\in X}P(x)\log \frac{P(x)}{Q(x)}}
```

$D_{KL}$を展開し、$H$で整理すると、

``` math
D_{KL}(P||Q) = \sum _{x\in X}P(x)\log \frac{P(x)}{Q(x)}
```
``` math
= \sum _{x\in X} (-P(x)\log Q(x) + P(x)\log P(x)) \\
```
``` math
= -\sum _{x\in X} P(x)\log Q(x) + \sum _{x\in X} P(x)\log P(x) \\
```
``` math
= -\sum _{x\in X} P(x)\log Q(x) - \sum _{x\in X} P(x)\log \dfrac{1}{P(x)} \\
```
``` math
= -\sum _{x\in X} P(x)\log Q(x) - H(P) \\
```
``` math
=  \sum _{x\in X} P(x)\log \dfrac{1}{Q(x)} - H(P) 
```

となる。よって、$-\sum _{x\in X} P(x)\log Q(x) - H(P)$と整理することができ、
1項がクロスエントロピー$H(p, q)$と一致する。