# 什麼是熵(Entropy)？

Author : Xin

## 簡介

Entropy一詞有許多不同的含意，在數學、物理、資訊等理論中都會出現。在資訊理論中其代表了某個事件的「資訊含量」，並有個經典的數學定義如下：對於隨機變數 $X$ 和機率分布 $p_X$，$X$ 在 $p_X$ 上的Entropy為
$$
\text{H}(X) = -\sum_{x}p_X(x)\log_2(p_X(x))
$$ 乍看之下並不清楚上述公式是從哪裡蹦出來的，且到底代表了甚麼意思？但其實它背後有著容易直觀理解的緣由。本文將會介紹Entropy定義的由來，以及它的應用。

## Entropy

### 背景

Entropy最初是被Shannon引入用來計算訊息編碼所需要的平均編碼長度。當我們要發送和接收訊息時，因為機器只認識0和1所構成的編碼。因此我們必須將訊息利用0和1來編碼。在編碼時，有以下需要遵守的原則。

- (原則1) 每組訊息都必須對應至一個編碼，否則電腦就無法理解它。
- (原則2) 每組訊息的編碼都必須相異，否則若是兩則不同的訊息具有相同的編碼，在接收到此編碼時便無法分辨編碼背後的原始訊息為何。

根據上述原則，給定文本 $\mathcal{S}$，假定我們想要傳送由 $\mathcal{S}$ 所構成的長度為 $n$ 的訊息。令 $k$ 為所需編碼長度，一個自然的編碼方式為讓每則訊息都有相異且長度為 $k$ 的編碼，此時 $k$ 必須滿足
$$
2^{k-1} < |\mathcal{S}|^n \leqslant 2^k\Longrightarrow k = \lceil n\log_2|\mathcal{S}|\rceil
$$

舉例來說，假設我們想要傳送由A,B,C,D這四個字母所組成的訊息。此時 $\mathcal{S} = \{\text{A} , \text{B}, \text{C} , \text{D}\}$。由於電腦並不認識英文字母，它只認識0和1所構成的編碼。因此我們必須分別給A,B,C,D這四個字利用0和1來編碼。在上述例子中，有一個簡單的編碼方式如下：
- A : 00 , B : 01 , C : 10 , D : 11。此時要表達每個字母皆需要2 bits，
$$
k = \lceil n\log_2|S|\rceil = 1\times \log_24 = 2
$$
- 例如接收到了編碼00101101，根據上述編碼方式實際上它代表的訊息為ACDB。

自然的，我們會想問有沒有辦法可以壓縮編碼，使所需的編碼長度變短？這樣可以節省傳輸成本。
現實中每個字母出現的機率(或頻率)並不相同，因此可以利用不同訊息出現頻率的不同來編碼。
舉例來說，在英文中字母E出現的頻率遠大於字母Z，因此可以讓E的編碼短一點而Z的編碼長一點，平均來說便可以降低所需的編碼長度。
以上述例子 $\mathcal{S} = \{\text{A} , \text{B}, \text{C} , \text{D}\}$ 來說，假定A,B,C,D出現的機率各為50%、25%、12.5%、12.5%。可以利用下列編碼方式來縮短平均編碼長度：
- A : 0 , B : 10 , C : 110 , D : 111。此時表達每個字母平均來說只需要
$$
0.5\times 1 + 0.25\times 2 + 0.125\times 3 + 0.125\times 3 = 1.75 \text{ bits.}
$$ 比之前的2 bits 還要低。

但是必須注意編碼時不能違反原則1和原則2，因此無法任意地壓縮編碼長度。

- 以上述例子來說，若是選擇編碼 A : 0 , B : 10 , C : 11 , D : 111，當接收到編碼1110時無法分別原始訊息是CB還是DA。

此時問題自然出現：

- 平均最短的編碼長度是多少？
- 如何決定每個字母的編碼長度？

實際上，可以證明Entropy的值就是平均最短編碼長度，並且可以利用每個字母的出現機率(或頻率)來計算出每個字母所需的編碼長度。我們可以想像每個訊息都帶有「資訊」，而所需的最短編碼長度便自然是此訊息的「資訊量」。如果壓縮的更短就會損失某些「資訊」。此時問題就變成是計算出訊息本身的「資訊量」。

### 資訊量

甚麼是「資訊」？基本上獲得「資訊」就是「知道原本不確定的事」，例如出門後得知天氣如何，看電視得知球賽結果等等。

>Shannon: “*Information is the resolution of uncertainty.*”

對於一個事件 $E$，用 $I(E)$ 代表 $E$ 這個事件本身帶有的資訊。現在我們還並不清楚 $I(E)$ 會是甚麼，但可以藉由上述原則來想像$I(E)$ 應有的特性。在資訊理論中，一個事件所帶有的資訊量取決於其「不確定性」。由此對於「資訊量」本身有下列的直觀理解：

1. 必然發生的事件的資訊量為0。如果事件 $E$ 必然發生，那麼事件 $E$ 並不具有不確定性，因此也就不具有任何資訊。
1. 如果某事件更具不確定性，此事件相比更具確定性的事件來說應該有更多的「資訊」。換句話說，如果某事件發生的機率越低，那麼它的資訊量就越高。同樣的，如果某事件發生的機率越高，那麼它的資訊量就越低。
>[!Tip]Example
可以想像下列情景幫助理解：
>1. 編號一到一百的盒子中只有一個是大獎。參加者要從中選擇一個盒子。此時消息「一號盒子不會中大獎」和「一號盒子會中大獎」相比較顯然是後者含有較多的資訊量。
前者發生的機率為99\%，幾乎必定會發生，基本上對抽獎沒有太大的幫助。而後者發生的機率為1\%，是偶然發生的小機率事件，對抽中大獎有極大幫助。
>1. 假設擲一枚出現正面機率為 $p$ 的硬幣。參加者要猜擲完硬幣後是正面還是反面。
- 若 $p = 0.9$，由於擲出正面機率很高，參加者可以合理預期結果為正面。此時不確定性很低，因此「硬幣結果是正面」這一事件的資訊量較低
- 若 $p = 0.5$ ，由於擲出正面和反面的機率相同，無法預期結果為正面還反面。此時擲硬幣結果不確定性更高，因此「硬幣結果是正面」這事件的資訊量相較 $p = 0.9$ 時更高。
1. 如果 $A,B$ 為兩個獨立事件，那麼 $A$ 和 $B$ 同時發生的資訊等同於 $A,B$ 各自的資訊之和。簡單來說，$A, B$ 兩個事件互不干涉，因此他們的資訊量等同於各自的資訊量相加。

從上述幾點可看出，對 $I$ 來說某事件 $E$ 所含的資訊量只與 $E$ 發生的機率有關，不考慮其在現實中的任何意義。因此，若 $E$ 發生的機率為 $p$ 可以只把 $I(E)$ 寫成 $I(p)$。當然，此假設對現實來說是不真實的，舉例來說：
>[!Tip]Example
假設民主黨和共和黨總統候選人當選機率各為50\%，此時「民主黨總統候選人當選」和「擲一枚公平硬幣，出現正面」具有相同的「資訊量」，但是顯然此二者的現實意義是無法比較的。

### 數學定義下的資訊量

把上述三點翻譯成數學形式的話就變成

1. $I(1) = 0$。
1. $I(p)$為嚴格遞減函數。
1. 對於任意的 $p_1$ 和 $p_2$，$I(p_1p_2) = I(p_1) + I(p_2)$。

實際上條件三可以推得第一個條件：
$$
I(1) = I(1\times 1) = I(1) + I(1)\Longrightarrow I(1) = 0
$$ 有個常見的函數會滿足上述條件：$-\log$ 函數
1. $\log 1 = 0$。
2. $\log$ 為嚴格遞增，因此$-\log$ 為嚴格遞減。
3. 注意到對於任意 $a , b > 0$
$$
-\log ab = -(\log a + \log b) = (-\log a) + (-\log b)
$$ 由此可看出 $-\log$ 函數會是其中一個可能的 $I$。事實上可以證明，滿足上述條件的連續函數 $I$ 只會形如下列函數
$$I(p) = k\log(p) ~,~ k < 0$$
:::spoiler 證明
首先注意到對於任意 $x$ 和正整數 $n$，根據數學歸納法我們有
$$
I(x^n) = I(xx^{n-1}) = I(x) + I(x^{n-1}) = I(x) + I(x) + I(x^{n-2}) = \cdots = nI(x)
$$ 因此對於任意有理數 $a/b$，
$$
I(x^{a/b}) = \frac{1}{b}\times bI(x^{a/b}) = \frac{1}{b}I(x^a) = \frac{a}{b}I(x)
$$ 由於 $I$ 為連續函數，可以將此結果延伸至任意實數。因此對於任意 $x > 0$，
$$
I(x) = I(e^{\log x}) = I(e)\log x
$$ 從 $I(p)$ 為嚴格遞減且 $I(1) = 0$ 可以得知 $I(e) < 0$。
:::

根據 $\log$ 的性質，前面乘上係數後可以任意的更換想要的底數，例如
$$
-\frac{1}{\log 2}\times \log(x) = -\frac{\log x}{\log 2} = -\log_2 x
$$ 在資訊理論中為了配合編碼特性，通常會選取以2為底，此時$I(p) = -\log_2(p)$。這時我們明白了所謂的資訊函數 $I$ 其實就是$I(p) = -\log_2(p) = \log_2 (1/p)$。

### Entropy的定義

讓我們回到Entropy的定義，
$$
\text{Entropy} = \text{H}(X) = -\sum_x p_X(x)\log_2(p_X(x)) = \sum_x p_X(x) I(p_X(x)) = \mathbb{E}[I(p_X)]
$$ 從上述公式可看出，Entropy其實就是對於資訊函數 $I$ 取期望值的結果，換句話說，<font color="#f00">**Entropy的本質就是訊息中所含有的「期望資訊量」**</font>。

>[!Note]
當某些 $p_X(x) = 0$ 時，雖然 $\log 0$ 無法定義，但是由於$$\lim_{a\to 0^+}a\log a = 0.$$ 因此可以將 $p_X(x)I(p_X(x))$ 定義為0，從而避開這個問題。

## 應用

### 編碼長度計算

讓我們回顧下列例子：假設擲一枚出現正面機率為 $p$ 的硬幣，若擲出正面則 $X = 1$，若擲出反面則 $X = 0$。此時
$$
\text{H}(X) = -p\log_2 p - (1-p)\log_2(1-p)
$$

||
|:--:|
| $\text{H}(X) = -p\log_2 p - (1-p)\log_2(1-p)$ 之函數圖 [(圖片出處)](<https://commons.wikimedia.org/wiki/File:Binary_entropy_plot.svg>)|

- 正如之前所提到的，當 $p = 0.5$ 時由於正反面出現機率相同，此時擲硬幣結果的不確定性最高，因此Entropy會是最大的，需要1 bits(最簡單的編碼就是以1代表擲出正面、0代表擲出反面)。
- 而當 $p=0\text{ 或 }1$ 時，此時擲硬幣結果是可預測的，沒有不確定性，因此Entropy為0，同時並不需要任何編碼(因為結果是已知的，沒有傳送訊息的必要)。
- 當 $0 < p < 1$ 時，我們有 $0 < \text{H}(X) < 1$。這代表甚麼意思呢？難道可以有介於0和1 bits之間的編碼嗎？

在前面已經提到，Entropy被用來計算訊息編碼所需要的平均編碼長度，且實際上這就是平均來說所需最短的編碼長度。上述結果出自Shannon所提出的Source coding theorem：

>[!Note] Source coding theorem
假設訊息 $(X_i)$ 為Stationary Process (服從分布 $X$)。當 $n$ 足夠大時，訊息可以被壓縮至長度任意接近於 $n\text{H}(X)$ 的編碼，且幾乎不會失去原始訊息中的資訊。然而，一旦編碼長度小於 $n\text{H}(X)$，則幾乎不可避免的損失了原始訊息中的資訊。

根據上述定理，當訊息足夠長(也就是 $n$ 足夠大)時，每個字的平均最短編碼長度為$$\frac{1}{n}\times (n\text{H}(X)) = \text{H}(X)$$ 假設上述擲硬幣例子中 $\text{H}(X) = 0.001$，實際上這代表了當 $n$ 足夠大時(也就是擲硬幣足夠多次時)，訊息可以被壓縮至長度任意接近於 $n\text{H}(X) = 0.001n$ 的編碼，當 $n\geqslant 1000$ 時 $$n\text{H}(X) = 0.001n\geqslant 1$$ 因此並不是說真的存在一個介於0和1 bits之間的編碼，而是說每個字的平均最短編碼長度為
$$
\frac{1}{n} \times n\text{H}(X) = \text{H}(X) = 0.001
$$讓我們考慮在背景中提到的例子：假設我們想要傳送由A,B,C,D這四個字母所組成的訊息。
- 若每個字母出現機率相同(1/4)，此時 $X$ 的分布為
$$
p_X(\text{A}) = p_X(\text{B}) = p_X(\text{C}) = p_X(\text{D}) = 1/4
$$ 每個字母的資訊量為
$$
-\log_2(1/4) = 2
$$ Entropy則為
$$
\text{H}(X) = 4\times\left(-\frac{1}{4}\log_2(1/4)\right) = 4\times \frac{1}{2} = 2
$$ 當收到的訊息足夠長時，每個字所需的平均最短編碼長度為 $\text{H}(X) = 2$。
- 若A,B,C,D出現的機率各為50%、25%、12.5%、12.5%，此時 $X$ 的分布為
$$
p_X(\text{A}) = 1/2 ~,~ p_X(\text{B}) = 1/4 ~,~ p_X(\text{C}) = 1/8 ~,~ p_X(\text{D}) = 1/8
$$ A,B,C,D的資訊量各為
$$
-\log_2(1/2) = 1 ~,~ -\log(1/4) = 2 ~,~ -\log(1/8) = 3 ~,~ -\log(1/8) = 3
$$ Entropy則為
\begin{align*}
\frac{1}{2}(-\log_2(1/2)) + \frac{1}{4}(-\log_2(1/4)) + \frac{1}{8}&(-\log_2(1/8)) + \frac{1}{8}(-\log_2(1/8))\\
&= \frac{1}{2} + \frac{1}{2} + \frac{3}{8} + \frac{3}{8} = 1.75
\end{align*} 當收到的訊息足夠長時，每個字所需的平均最短編碼長度為 $\text{H}(X) = 1.75$。

我們已經知道了平均最短編碼長度，剩下的問題就是真的能設計出一種編碼使得它的長度接近於平均最短編碼長度嗎？目前已經有許多演算法實現了這一點，例如：
1. Lempel-Ziv-Welch Coding
1. Huffman Coding

### Cross-Entropy 和 K-L Divergence

對於兩個 $X$ 上的機率分布 $p_X(x)$ 和 $q_X(x)$， $q_X$ 對於 $p_X$ 的Cross-Entropy的定義為
$$
\sum_x p_X(x)I(q_X(x)) = -\sum_x p_X(x)\log_2(q_X(x))
$$ 上述定義與Entropy十分相似，不同的地方在於 $\log$ 裡面為 $q_X(x)$ 而非 $p_X(x)$。Cross-Entropy的意涵有以下兩種看法
1. 使用估計值 $q_X$ 所計算出的期望資訊量。
1. 使用估計值 $q_X$ 所計算出的平均編碼長度。

可以想像下列情景：
- 假設真實的資料背後的機率分布為 $p_X$，此時我們蒐集了一堆由 $p_X$ 的分布所產生的資料。目標為了解 $p_X$ 的分布為何。通過統計、機器學習等等方法所估計出的機率分布為 $q_X$，我們想要衡量 $q_X$ 是不是一個好的估計。
- 因為我們不清楚 $p_X$ 為何，這裡使用 $I(q_X)$ 來作為 $I(p_X)$ 的估計。但是由於蒐集到的資料真實分布為 $p_X$，因此估計出的Entropy實際為
$$
\sum_x \underbrace{p_X(x)}_\text{蒐集到的資料}\times \underbrace{I(q_X(x))}_\text{作為$I(p_X(x))$的估計} = -\sum_x p_X(x)\log_2(q_X(x))
$$

給定 $p_X$ ，我們想找出與 $p_X$ 夠接近的 $q_X$。在常見的應用情景如機器學習中，會使用Cross-Entropy作為Loss function。透過以下論證會說明Cross-Entropy的最小值正好成立於 $q_X = p_X$時，因此透過梯度下降找到Loss function的最小值時就相當於找到了 $p_X$ 的分布。

- 一個自然的想法是令Entropy與Cross-Entropy之間的差距足夠小，也就是真實期望資訊量(或真實平均編碼長度)與估計出的期望資訊量(或估計出的平均編碼長度)之間的差距越小越好。因此希望下列數值越小越好
\begin{align*}
\text{Cross-Entropy} - \text{Entropy} &= -\sum_x p_X(x)\log_2(q_X(x)) - \left(-\sum_x p_X(x)\log_2(p_X(x))\right)\\
&= \sum_x p_X(x)(\log_2(p_X(x)) - \log_2(q_X(x)))\\
&= \sum_x p_X(x)\log_2\left(\frac{p_X(x)}{q_X(x)}\right)
\end{align*} 此差距有一特殊名稱：K-L Divergence (Kullback–Leibler Divergence)，數學式寫做
$$
D_{KL}(p_X~~||~~q_X) = \sum_x p_X(x)\log_2\left(\frac{p_X(x)}{q_X(x)}\right)
$$ 可以證明$D_{KL}(p_X~~||~~q_X)$ 的最小值為零，且發生於 $p_X = q_X$ 時。
:::spoiler 證明
根據Jensen不等式，
\begin{align*}
\sum_x p_X(x)\log_2\left(\frac{q_X(x)}{p_X(x)}\right)&\leqslant\log_2\left(\sum_x p_X(x)\frac{q_X(x)}{p_X(x)}\right)\\
&= \log_2\left(\sum_x q_X(x)\right) = \log_2 1 = 0
\end{align*} 因此
$$
D_{KL}(p_X~~||~~q_X) = \sum_x p_X(x)\log_2\left(\frac{p_X(x)}{q_X(x)}\right) = -\sum_x p_X(x)\log_2\left(\frac{q_X(x)}{p_X(x)}\right)\geqslant 0
$$ 且根據Jensen不等式，等號成立於
$$
\frac{q_X(x_1)}{p_X(x_1)} = \frac{q_X(x_2)}{p_X(x_2)} = \frac{q_X(x_3)}{p_X(x_3)} = \cdots
$$ 令上述比值為 $a$，注意到
$$
1 = \sum_x q_X(x) = \sum_x ap_X(x) = a \sum_x p_X(x) = a \times 1 = a
$$ 因此 $a = 1$，換句話說，等號成立於 $p_X = q_X$。
:::

基本上K-L Divergence衡量了兩個機率分布之間的距離，當此距離為零時，我們有 $p_X = q_X$。因此想要找到好的估計 $q_X$ 只需要找到最小化K-L Divergence的 $q_X$。
- 當 $p_X$ 給定時，$p_X$ 的Entropy為一固定常數。$q_X$ 對於 $p_X$ 的Cross-Entropy和K-L Divergence之間只差了一個常數值，因為
$$
\text{Cross-Entropy} - \text{K-L Divergence} = \text{Entropy}
$$ 我們知道K-L Divergence的最小值發生於 $p_X = q_X$ 時，因此Cross-Entropy的最小值也發生於 $p_X = q_X$。
- 由上述兩點我們知道最小化Cross-Entropy和最小化K-L Divergence其實是相同的，其最小值皆發生於 $p_X = q_X$ 時。在應用時通常選擇最小化Cross-Entropy，因為所需的計算量較小。

## 參考資料
- [Entropy Wikipedia](<https://en.wikipedia.org/wiki/Entropy_(information_theory)>)
- S. M. Moser - [Information Theory (Lecture Notes), 6th Edition.](<https://moser-isi.ethz.ch/scripts.html>)