PLML1.6


#PLML1.6 情報理論

##これまでのあらすじ
確率論　不確実性を明示的に数的に証明する
決定理論　不確実性を鑑みたうえで最適なものを選択する
情報理論　得たデータがどれほどの科価値を持つかを数的に証明する


#用語
##情報量
観測できた事象に対してどれほどの価値があるのかを示す尺度
発生する確率が低いほど情報量は大きいと考える。

ある離散確率変数xを考えた場合に
情報量の関数をh(x)
確率分布をp(x)とする

h(x)はp(x)に依存
異なる事象を観測したときの情報は 

h(,x,y) = h(x) + h(y)
独立なのでp(x,y) = p(x)p(y)

よって

```math
h(x) = -\log_n p(x)\\
```
なお底nの選択は自由度がある。

底2の場合はビット
底が自然対数の場合はナット
という単位になる。
##エントロピー
簡単にいうと乱雑さを測る尺度

分布p(x)に対して期待値(平均)をとることで算出できる。

```math
H[x] = -\sum p(x)\log_n p(x)
```

詳しい性質は後述


#例　通信における符号長(p49)

８個の可能な状態{a,b,c,d,e,f,g,h}を取るとする。
これがすべて同じ確率で発生する場合のエントロピーは

```math
H[x]=-8 \times \frac{1}{8} \log_{2} \frac{1}{8} = 3
```
3ビット


それぞれの確率が

```math
{\frac{1}{2},\frac{1}{4},\frac{1}{8},\frac{1}{16},\frac{1}{64},\frac{1}{64},\frac{1}{64},\frac{1}{64}}
```

の場合
のエントロピーは

```math
H[x] = -\frac{1}{2} \log_2 \frac{1}{2} -\frac{1}{4} \log_2 \frac{1}{4} -\frac{1}{8} \log_2 \frac{1}{8} -\frac{1}{16} \log_2 \frac{1}{16} -\frac{4}{64} \log_2 \frac{1}{64} =2
```

2ビット

つまり、エントロピーは非一様分布の方が低く　一様分布のほうが高い

これをもとに起こりやすい事象には短い符号長を割り当てると考えてみる。

平均符号長

```math
\frac{1}{2} \times 1 + \frac{1}{4} \times 2 + \frac{1}{8} \times 3 + \frac{1}{16} \times 4 + 4 \times \frac{1}{64} \times 6 = 2
```

2ビット

これ以上短い符号を連続で送れない(ノイズなし符号化定理)
つまり、エントロピーは通信最低限必要なビットを示している。

#例　箱の中身(p50)
N個の同じ物体が存在しi番目の箱にn_i個の物体が入っているとする。
この時の場合の数を考えてみる。

物体の入れ方の総数は

```math
W=\frac{N!}{\prod_i n_i!}
```

これを多重度とよび
エントロピーは多重度の対数としてみることができる。

```math
H=\frac{1}{N}\ln W = \frac{1}{N}\ln N!-\frac{1}{N}\sum\ln n_i!
```

```math
スターリングの近似式\\
\ln N! \geqq N \ln N -N\\ より\\
\\
H = - lim_{M \to \infty} \sum_i \frac{n_i}{N} \ln \frac{n_i}{N} = -\sum p_i \ln p_i
```

箱の中の特定の物体の状態がミクロ状態
n_i/Nの比がマクロ状態　多重度Wがマクロ状態の重み

箱の中の状態を離散確率変数Xの状態x_iと解釈


p(X=x_i)=p_iより
変数Xのエントロピーは

```math
H[p]=-\sum_i p(x_i)\ln o(x_i)
```

図(1.30)より少ない値で鋭いピークを持つ分布ではエントロピーが低く
値の広がりがある場合はエントロピーは高い

0<=pt<=1より非負
どこかでpi=1となって i=jでpj=0となる分布が最小値なる。

最大のエントロピーを持つ確率分布は
Hの最大化で求まる。
ただし確率の総和が1となる制約付き
 ->ラグランジュの未定乗数法

p(xi)が1/M(等確率)になるときに最大となる。
この時H=lnM

この時停留点が最大であるかの確認のため
エントロピーの2階微分

```math
/frac{\delta^2 H}{\delta(x_i)\delta p(x_j)} = -I_ij\frac{1}{p_i}
```

#連続変数への拡張
xを等間隔区間のΔに分ける

p(x)が連続と仮定すると平均値の定理より各区間に対して

```math
\int_{(i+1)\Delta}^{i\Delta} p(x)dx = p(x_i)\Delta
```

となる値が存在する。

i番目の任意の値xをx_iと割り当てることで量子化すると
xを観測する確率は

```math
p(x_i)\Delta
```
離散分布のエントロピーは

```math
\sum p(x_i)\Delta \\
より\\
H_\Delta = -\sum_{i} p(x_i) \Delta \ln (p(x_i)\Delta) = - /sun_{i} p(x_i) \Delta - \ln \Delta \\
lim_{\Delta \to 0}{-\sum_{i}p(x_i)\Delta\ln p(x_i)} = \int p(x)\ln p(x)dx
```
Δ->0で極限を取るとエントロピーとなる

これを微分エントロピーと呼ぶ
制約

```math
H[x]=-/int p(x) /ln p(x)dx\\

\int_{-\infty}^{\infty} p(x)dx = 1\\
\int_{-\infty}^{\infty} xp(x)dx = \mu \\
\int_{-\infty}^{\infty} (x-\mu)^2 p(x)dx = \sigma^2
```



この制約のもと連続においてエントロピーが最大化される分布は

```math
p(x) = \frac{1}{(2\pi\sigma^2)^\frac{1}{2}} \exp{-\frac{(x-\mu)^2}{2\sigma}^2}
```

結果はガウス分布
つまり、微分エントロピーを最大化する分布はガウス分布となる。
このため、必ず非負になる。

ガウス分布のエントロピーは

```math
H[x]=\frac{1}{2}{(1+\ln(2\pi\sigma^2)}
```


#同時分布
同時分布(x,y)でxが既知の場合
yを特定するための情報量は

```math
-\ln p(y|x)
```

これの平均値は

```math
H[y|x]=-\int\int p(y,x)\ln p(y|x)dy dx
```

これを条件付きエントロピーという

確率乗法定理より

```math
H[x,y]=H[y|x] + H[x]
```

つまり、同時分布のエントロピーは
条件付きエントロピーと条件分布のエントロピーの和となる。

##1.61　相対エントロピーと相互情報量
分布p(x)をq(x)で近似したとする。

xの値を特定するための追加の情報量は

```math
KL(p||q)=-\int p(x)\ln q(x)dx -(\int p(x)\ln p(x) dx)
=-\int p(x) \ln {\frac{q(x)}{p(x)}}dx
```


これは相対エントロピーまたはカルバックライブラダイバージェンス略してKLダイバージェンスと呼ぶ

これが KL(p||q) > 0
を満たし、 p(x) = q(x) のみ等式が成り立つことをしめす。

凸関数の概念を導入する。凸の状態は弦に対して関数f(x)がすべて乗っているかそれより上にある状態を凸であるという。
図(1.31)参照

```math 
x=a x =b \\
0 \leq \lambda \leq 1\\
より

\lambda a + (1- \lambda)b \\
と書ける

したがって、弦上の値は\\ 

\lambda f(a) + (1 - \lambda)f(b) \\

関数値は\\
f(\lambda a + (1 - \lambda) b) \leq \lambda f(a) + (1 - \lambda ) f(b)
```

これを満たせば上に凸となる。
なお等式が

```math
\lambda = 0\\
\lambda = 1
```
のみで成立する場合、真に凸という。
これが真逆の性質を持つ場合は　凹関数　真に凹という。


凸関数f(x)は　任意の点集合に対して

```math
f (\sum_{i = 1}^{M} \lambda_i x_i) \leq \sum_{i=1}^{M} \lambda_i f(x_i)
```
満たす。
これをイェンセンの不等式という。

\lambda を 値{xi}を取る　離散確率変数x上の確率分布と解釈すると

```math
f(E[x]) \leq E[f(x)] \\
f(\int xp(x) dx) \leq \int f(x) p(x) dx\\

これにKLダイバージェンスを適用すると
KL(p||q) = - \int p(x) \ln { \frac{q(x)}{p(x)}} dx \geq - \ln \int q(x) dx = 0
```

lnxが清に凸な関数であることと　統合は　すべてのx について　p(x) = q(x) が成り立つことから
KLダイバージェンスはP(x)とq(x)の差の量と考えられる。

つまりKLダイバージェンスを減らせばいい。

KLダイバージェンスの最小化を考える。

未知の分布p(x)から生成されるデータのモデル化を考えるので、そのために、
可変なパラメータを持つθを持つパラメトリックな分布q(x|θ)を使って近似をすることが考えられる。
θの値を決定する方法は p(x)とq(x|θ)のKLダイバージェンスを最小化することになる。

しかし、p(x)は知らないので　P(x)から得られた訓練集合の点をでp(x)に関する期待値を近似して

```math
KL(p||q) \simeq \frac{1}{N} \sum_{n=1}^{N} {- \ln 1(x_n | \theta) + \ln p(x_n)}
```

θは独立であり、 q(x|θ)の下の負の対数尤度だから　KLの最小化は尤度の最大化と同義である。

次に変数が　独立か　独立でなければどれほど近いということを考えてみる。

二つの変数集合 x,yの同時分布をp(x,y)があるとする。
これの同時分布と周辺分布の席の間のKLダイバージェンスを考えると,


```math
I[x,y] \equiv KL(p(x,y) || p(x)p(y))\\
= - \iint p(x,y) \ln (\frac{p(x)p(y)}{p(x,y)}) dx dy
```

これはx,yの相互情報量と呼ばれる。
確率の加法、乗法定理を使うと条件付きエントロピーと関係して

I[x,y] = H[x] - H[x|y] = H[y] -H[y|x]
が成り立つ。

つまり相互情報量は　yの値を知ることでxの不確実性がどれだけ減少すrかを表し、逆のことも言える。

ベイズの観点からは、新たなyを観測したときの結果として、xに関する不確実性が減少した度合いを表している。




##参考
https://www.slideshare.net/sleepy_yoshi/prml1-6-suhara
https://www.slideshare.net/hiromasaohashi/prml4
http://d.hatena.ne.jp/wilsonia/20080904/1220542699
https://www.eidos.ic.i.u-tokyo.ac.jp/~tau/lecture/komaba_joho/gen2/slides/3-entropy.pdf
http://mathtrain.jp/meanvalue