---
disqus: ierosodin
---

# Information theory

> Organization contact [name= [ierosodin]([e-mail])]
###### tags: `machine learning` `學習筆記`

==[Back to Catalog](https://hackmd.io/@ierosodin/Machine_Learning)==

又稱作亂度 (randomize)，用來反應資訊的重要性，或者是描述我們可以從中獲取多少訊息。可以想像，當一件事情發生的機率很高，那我們可以從這個機率中得到的訊息就很少，反之，若我們得到一個很低的機率，代表我們獲得了一個很重要的資訊。
> 就像是前面的辨識手寫數字的作業，如果有一個 pixel 的顏色總是白色，那我們可以從這個 pixel 得到的訊息就相對少，也就是一個不重要的 pixel。

## 單位

當我們對一個機率取 ${-logP(x)}$，可以看出一個資料的訊息量，以擲硬幣來說，我們用兩進位（正反）來描述的這個事件，所以比較 ${\frac{1}{4}}$ 與 ${\frac{1}{1024}}$，前者取 ${-log}$ 後得到 2，後者則得到了 10，這個數字代表了我們得到的訊息量 (bits)，也就是如果今天後者的事件發生了，代表連續十次都擲到正面，這樣的訊息就大於了前者連續兩次擲到正面（例如今天運氣很好，或者是這個硬幣是有問題的）。
所以 bits 數代表描述一件事情所需的資料量，越大代表得到的訊息量也越大。
> ${-log_k}$ 的底數 ${k}$ 可以根據事件的不同而設計，例如擲骰子就可以用 ${-log_6P(x)}$

## Entropy: the expectation of information in events

這樣訊息量的評估方式由 Shannon 提出，稱為熵 (entropy)，或有人稱為亂度 (randomize)，其實就是前面提到 information 的期望值。
下面是一個骰子直到六面的機率，從中可以看出，當資料分佈的越平均，則其得到的平均值就越大，反之若有其中一面的機率異常，那它對整體期望值得貢獻就會很小，也就是這組資料的亂度很大，而我們可以得到的訊息就越大（越容易預測結果）。
1 | 2 | 3 | 4 | 5 | 6 | entropy
:---: | :---: | :---: | :---: | :---: | :---: | :---:
${\frac{1}{6}}$ | ${\frac{1}{6}}$ | ${\frac{1}{6}}$ | ${\frac{1}{6}}$ | ${\frac{1}{6}}$ | ${\frac{1}{6}}$ | 2.58
${\frac{2}{7}}$ | ${\frac{1}{7}}$ | ${\frac{1}{7}}$ | ${\frac{1}{7}}$ | ${\frac{1}{7}}$ | ${\frac{1}{7}}$ | 2.52
${\frac{1}{21}}$ | ${\frac{2}{21}}$ | ${\frac{3}{21}}$ | ${\frac{4}{21}}$ | ${\frac{5}{21}}$ | ${\frac{6}{21}}$ | 2.39
${\frac{1}{15}}$ | ${\frac{1}{15}}$ | ${\frac{1}{15}}$ | ${\frac{1}{15}}$ | ${\frac{1}{15}}$ | ${\frac{10}{15}}$ | 1.69

> 這裡容易跟前面搞混，前面說 entropy 越大資料量越大，指的是對不同事件間==重要性的評估==，然而這裡是只對於同一事件==各種 outcomes 機率分佈的評估==。
> 期望值越大代表需要越多的 bits 來描述這個是事件，所以越接近零就代表資料越亂，我們不需要這個多位元就可以描述或是預測這個事件，反之，期望值大，資料越穩定，也越無法被預測，因此需要更多的位元才能描述。（可以想像今天一個不公平的骰子會比一個普通的骰子來得容易預測結果）
> ==期望值越大代表需要越多的 bits 來描述這個是事件是不變得道理==，只是用在的地方不一樣，意義也不同。
> 所以亂度大跟 entropy 小是兩個相反的指標，當 entropy 越小，就代表這筆資料的亂度越大，相對的隨機性也就越小，結果越容易被預測。

### Condition entropy

接下來想知道的就是，如果我已經知道事件 X 所需要的資訊位元數，那當今天來了一個 Y，我還需要多少額外的位元數，才能表達這件事。
${\begin{split}
H(Y|X)\ &=\ -\sum_iP(x_i)H(Y|X=x_i) \\
&=\ -\sum_iP(x_i)\sum_iP(y_i|x_i)logP(y_i|x_i) \\
&=\ -\sum_i\sum_jP(x_i)P(y_j|x_i)logP(y_j|x_i) \\
&=\ -\sum_i\sum_jP(x_i,y_j)logP(y_j|x_i) \\
&=\ -\sum_i\sum_jP(x_i,y_j)log\frac{P(x_i,y_j)}{P(x_i)} \\
&=\ \sum_i\sum_jP(x_i,y_j)log\frac{P(x_i)}{P(x_i,y_j)}
\end{split}}$

這又稱為 Information gain，也就是從一個事件到另一個世間，你會增加多少資料量。

### Joint entropy

從 conditional entropy 其實可以推出，${H(x,y)\ =\ H(y|x)\ +\ H(x)}$，也就是要描述一個 joint 事件的資料量，其實就是原本 X 事件的資料量，再加上從 X 到 Y 所需要增加的資料量。

### Cross entropy

假設今天有兩個事件 X、Y，他們有各自的機率分佈與各自的資料量，cross entropy 指的就是，將別人的分佈套用在自己的資料量上，來算算看自己的總資料量為多少，數學式為：
${H_y(x)\ =\ -\sum_iP(y_i)logP(x_i)}$

表示，在 Y 的分佈下，X 的資料量為多少，理論上，如果別人的分佈與自己最佳的分佈不同，則得出的資量總量會比較小。

> 這裡必須注意，${H_y(x)}$ 與 ${H_x(y)}$ 不同

### Relative entropy

又叫做 KL divergence，其實就是 cross entropy 與原本 entropy 的差（在同一個分佈下）：
${\begin{split}
KL(x||y)\ &=\ H_x(y)\ -\ H(x)\ \\
&=\ -\sum_iP(x_i)logP(y_i)\ -\ (-\sum_iP(x_i)logP(x_i)) \\
&=\ -\sum_iP(x_i)log\frac{P(y_i)}{P(x_i)}
\end{split}}$

KL divergence 代表兩組資料的距離，不過這種評估方式最大的問題在於，X 到 Y 的距離與 Y 到 X 的距離不相同。

### Mutual information

代表兩組資料重複的部份：
${I(X:Y)\ =\ H(X)\ -\ H(X|Y)\ =\ H(Y)\ -\ H(Y|X)}$


### Maximum entropy principle

如果在甚模都不知道的情況下 (prior is none)，最大的 entropy 會出現在當分佈是 uniform 的情況下。

#### 證明 Expectation value of entropy

這裡要證明最大的期望值會出現在，當資料分佈隨機性是 uniform distribution。

所以我們想得到 ${H(x)\ =\ -\int_a^bP(x)log_2P(x)dx}$ 的最大值

其中，
${\int_a^bP(x)dx\ =\ 1}$

這裡用到 Langrage multiplier 來解有條件的最大值，我們寫出限制條件 g 與函數 f 取 gradient，求解：${\nabla f\ -\ \lambda \nabla g\ =\ 0}$

在這裡就是：${L\ =\ -\int_a^bP(x)log_2P(x)dx\ +\ \lambda (\int_a^bP(x)dx\ -\ 1)}$

要解這個式子必須使用變分法：
https://zh.wikipedia.org/wiki/%E5%8F%98%E5%88%86%E6%B3%95

${\Rightarrow\ \frac{\partial}{\partial L}\ =\ -(logP(x)\ +\ 1)\ +\ \lambda\ =\ 0 \\
\Rightarrow\ P(x)\ =\ e^{(\lambda\ -\ 1)} \\
\therefore\ \int_a^be^{(\lambda\ -\ 1)}dx\ =\ 1\ \Rightarrow\ e^{(\lambda\ -\ 1)}x|_a^b\ =\ 1 \\
e^{(\lambda\ -\ 1)}\ =\ \frac{1}{b-a}\ =\ P(x)}$

因此可以得到，當分佈是一個 uniform distribution 時，可以得到最大的 entropy。

> 再次強調，這意味著需要最大的 bits 數才能描述這件事，也就是說這件是的亂度很低，無法預測。

#### prior: ${\mu}$

若我們的 prior 再加上 ${\int_a^bxP(x)dx\ =\ \mu}$

則 ${L\ =\ -\int_a^bP(x)log_2P(x)dx\ +\ \lambda_0 (\int_a^bP(x)dx\ -\ 1)\ +\ \lambda_1 (\int_a^bxP(x)dx\ -\ \mu) \\
\Rightarrow\ \frac{\partial}{\partial L}\ =\ -(logP(x)\ +\ 1)\ +\ \lambda_0\ +\ \lambda_1 x\ =\ 0 \\
\Rightarrow\ P(x)\ =\ e^{(\lambda_0\ +\ \lambda_1 x\ -\ 1)}}$

這裡將上下界換成 0 到無限，方便計算，帶入第一個條件：
${\int_0^\infty e^{(\lambda_0\ +\ \lambda_1 x\ -\ 1)}dx\ =\ 1\ \\
\frac{e^{\lambda_0\ -\ 1}}{\lambda_1}(e^{\lambda_1 \infty}\ -\ 1)\ =\ 1}$
由於 ${\lambda_1\ <\ 0}$
${\Rightarrow\ -\frac{e^{\lambda_0\ -\ 1}}{\lambda_1}\ =\ 1 \\
\Rightarrow\ -e^{\lambda_0\ -\ 1}\ =\ \lambda_1}$

第二個條件：
${\int_a^bxP(x)dx\ =\ \int_a^bxe^{\lambda_0\ +\ \lambda_1 x\ -\ 1}dx\ =\ e^{\lambda_0\ -\ 1}\int_a^bxe^{\lambda_1 x}dx}$

這裡要用 partial differential：
${\begin{split}
e^{\lambda_0\ -\ 1}\int_a^bxe^{\lambda_1 x}dx\ &=\ e^{\lambda_0\ -\ 1}(\frac{x}{\lambda_1}e^{\lambda_1 x}\ -\ \int_0^\infty\frac{1}{\lambda_1}e^{\lambda_1x}dx)|_0^\infty \\
&=\ e^{\lambda_0\ -\ 1}(-\int_0^\infty\frac{1}{\lambda_1}e^{\lambda_1x}dx)|_0^\infty \\
&=\ -\int_0^\infty\frac{1}{\lambda_1}e^{\lambda_0\ +\ \lambda_1x\ -\ 1}dx|_0^\infty \\
&=\ -\frac{1}{\lambda_1}\ =\ \mu
\end{split}}$

由第一個條件：
${-e^{\lambda_0\ -\ 1}\ =\ \lambda_1 \\
\Rightarrow\ P(x)\ =\ e^{\lambda_0\ +\ \lambda_1 x\ -\ 1}\ =\ -\lambda_1 e^{\lambda_1 x}}$

再帶入第二個條件：
${\Rightarrow\ P(x)\ =\ \frac{1}{\mu}e^{\frac{-1}{\mu}x}}$

因此如果 prior 包含整筆資料的平均，則最大的 entropy 會出現在當分佈呈現 exponential 時。

#### prior: ${\mu, \sigma^2}$

當給定 prior 為 ${\mu\ =\ \int_a^bxP(x)dx,\ \sigma^2\ =\ \int_a^bx^2P(x)dx}$ 時，最大的 entropy 會出現在當分佈為高斯分佈時。

也就是
${L\ =\ -\int_a^bP(x)log_2P(x)dx\ +\ \lambda_0 (\int_a^bP(x)dx\ -\ 1)\ +\ \lambda_1 (\int_a^bxP(x)dx\ -\ \mu)\ +\ \lambda_2(\int_a^bx^2P(x)dx\ -\ \sigma^2) \\
\Rightarrow\ \frac{\partial}{\partial L}\ =\ -(logP(x)\ +\ 1)\ +\ \lambda_0\ +\ \lambda_1 x\ +\ \lambda_2 x^2\ =\ 0 \\
\Rightarrow\ P(x)\ =\ \frac{1}{\sqrt{2\pi\sigma^2}}e^{-\frac{(x\ -\ \mu)}{2\sigma^2}}}$