---
tags: information theory
---
# 由大數法則理解訊息熵(entropy)的數學意義
## 前言

網路上多數的文章大多以較為概念性的方式來講述資訊熵（entropy）：熵即訊息本身不確定性的量度。對於一個離散型的隨機變數$X$，[Claude Shannon](https://en.wikipedia.org/wiki/Claude_Shannon)（資訊理論的奠基者）將其熵值定義為
$$
\begin{align*}
H(X) = \mathsf E_{x \sim X} \left[-\log \mathsf P_X(x) \right] =
\sum_{x}- \mathsf P_X \log \mathsf P_X (x) \label{entropy}
\end{align*}
$$
其中$\mathsf E$代表的是期望值， $P_X$為定義於$X$上的機率質量函數（probability mass function，簡寫為pmf)，而$\log$則為底數為$2$的自然對數（為了簡化表示，本文中的$\log$底數都默認為$2$)，雖然我們可以舉例子來直觀的理解上式，但心中卻不免會浮現出一系列的疑問：為什麼訊息的不確定性非得是上面這樣的定義呢？難道不能定義成兩倍的$H(X)$？又或者，應該還有其他度量不確定性的數學式子吧，為何偏偏是Shannon所定義的entropy？

本文一開始並不會直接使用熵的定義，而是先從將訊息做編碼（encode）的問題（亦即，如何將資料壓縮）談起。接著，我們開始探討如何做一個有效率的編碼，並且對何謂做“有效率”規範出一個明確的準則，而為了達到此準則，機率論中著名的大數法則（law of large numbers）帶給了我們一些重大的啟示和方向上的指引，此時，熵的定義便自然而然的浮現而出，並將為資訊的本質做出一個深遠的刻畫。

## 先備知識

在閱讀本文之前，筆者預設讀者對機率中的離散隨機變數（discrete random variable）和機率質量函數（pmf）有基本的了解，不過無需知道太多的相關數學定理，只要能從骰子擲出點數和各自代表的機率是多少做出簡單的類比即可。而在證明的部分中，會用到一點點簡單的集合和元素的觀念。此外，如果你對大一微積分中的極限（limit）有點概念的話對於概念上的理解會有一定的幫助，但筆者也會盡量用口語化的方式來解釋其中蘊含的道理所在。

## 壓縮：將訊息做有效率的編碼

在傳遞訊息的方法之中，其中一種簡單的通訊模型由以下五個部份所構成：

1. 訊息源（source）：負責製造訊息（可能是文字或者圖像等形式）的源頭。
2. 編碼器（encoder）：負責將訊息源產生出來的訊息做編碼（encode)，轉換成適合傳輸的形式（例如0或1所構成的數位訊號）。
3. 通道（channel）：作為編碼器轉換完成後訊號的傳輸媒介。
4. 解碼器（decoder)：訊息通過通道傳輸過來之後，會透過它解碼（decode）轉換回原本訊息源所產出的訊息型式。
5. 目的地（destination）：最終訊息的接收者或是傳送終點。

從生活中的例子來說明，我們可以用傳遞簡訊的例子來類比上述的五個元件：當Alice（訊息源）想傳送一段文字訊息給Bob時，他輸入的文字會被手機（解碼器）轉換為數位訊號，經由無線通訊（通道）的傳送下到達Bob的手機，手機接著將數位訊號轉換回Bob（目的地）看得懂的文字，成功的完成了一次通訊。在現實世界中，訊號的傳輸經常是以電腦或晶片能理解的0和1構成的樣態做傳輸，也因此，當我們的訊息是由英文字母所構成的形式，諸如"Hello"這樣的一段訊息，勢必得將它編碼成"01011011..."這樣的形式，除此之外，解碼那方也必須擁有知道如何將這段轉換過的訊息還原成原本訊息樣貌的知識，一個直觀的想法就是：將每個字母分別用固定長度的位元字串（即只包含0或1的字串，稱為bit string）表示，比如`000001`代表字母`a`，`000101`代表字母`c`這樣的規則，如此一來，即使訊息在通道中是用01的方式傳輸，解碼器也能成功的將它還原回最初始的文字行式，舉上面的例子來說，`000001000001000101`這個訊息可被直接解碼為`cca`這個字串。

當我們將原始想傳送的訊息（字串形式）以及編碼後的長度分別固定為$n$和$k$時，且令字串中可能出現字元所構成的集合為$\mathcal S$（稱作字母集，alphabet set），對於所有可能從此字母集所產生出來的字串構成的集合我們記作$\mathcal S^n$，在這個集合中的任意元素$s^n$（即長度為$n$的字串），我們都可用一個$n$-tuple來將字串表示為序列的形式：
$$
\begin{align}
s^n = (s_1, s_2,..., s_n) \in \mathcal S^n,
\end{align}
$$
其中$s_1, s_2, ... s_n$皆為從$\mathcal S$取出的元素。 在這樣的架構下，我們可以將編碼這件事視為一個由$S^n$映射到長度為$k$之位元字串構成之集合（記作$\{0, 1\}^k$）的一個函數$\text{enc}_n$：
$$
\text{enc}_n: \mathcal S^n \rightarrow \{0, 1\}^k.
$$
相對地，解碼就是將編過的位元字串轉換回原本字串形式的一個函數$\text{dec}_n$：
$$
\text{dec}_n: \{0, 1\}^k \rightarrow \mathcal S^n .
$$
我們將編碼前的序列和解碼後的序列分別記做$s^n$和$\hat s^n$，這裡必需注意的一點是，根據上面的定義，我們並**沒有**強制規定$s^n$要等於$\hat s^n$，也就是說編碼前和解碼後的序列未必是一致的，當$s^n \neq \hat s^n$的情形發生時，我們可以將它理解為訊息的丟失（loss），而這種所有相同長度序列經過編碼後都擁有一樣的長度的編碼方式，我們稱之為fixed-to-fixed source coding（當然也有fixed-to-variable的編碼方式，也就是output的長度未必是一樣的，但為了分析上的方便故先略過不提）。

在現實世界中，我們必須耗費能量和成本來傳輸訊息，因此，為了節省資源，傳輸的訊息長度$k$當然是越少越好，而資料壓縮的程度，我們可以用編碼前的序列長度除以編碼後的序列，亦即
$$
R= \frac{k}{n}.
$$
上面的$R$我們稱之為訊息的壓縮比（compression ratio），顯然的，在此定義下，主要的目標就是降低壓縮比。我們可以透過觀察原始資料的某些特性來對原始訊息做更有效率的表達，假設從Alice多次傳送訊息的結果中，我們觀察到`a`這個字母出現的頻率遠比`z`出現的頻率還高，因此如果我們讓`a`經過編碼的訊號的表示長度從原本的$6$縮小為$3$（例如`001`)，那將能降低傳出一個固定長度英文字串所需的**平均**位元數量（這裡我們用fixed-to-variable source coding的例子說明，不過也能類比在fixed-to-fixed的例子中）。但是這種作法可能帶來的負面影響就是：當我們將資料的表達簡化到一定的程度時，有可能會造成解碼上的困難，一個極端的例子是當我們將英文字母`a`，`b`和`c`編碼成`0`，而其餘部分則編碼成`1`，則`cat`這個序列經過編碼後的序列為`001`，儘管需要傳輸的位元數只有3個（$k = 3$），解碼器在沒有其他編碼規則以外的訊息下接收到`001`這個序列之後卻不知道該還原成`cat`還是`bar`（因為他們的編碼都相同），也因此當解碼器把它轉成`bar`時，便造成了信息的丟失。

從上面的例子可以得知兩件事：

1. 當訊息呈現某種**規則或模式**時，資料是可能被壓縮的。
2. 訊息*壓縮的程度*與還原訊息之間的*準確性*存在著某種程度上的**trade-off**。

同時，兩個基本的問題也隨之而生：

1. 訊息在特定的訊息模式以及對解碼準確率有某種程度的要求下，當序列長度$n$很大時，我們所能達到的最低壓縮比$\frac{k}{n}$為何？
2. 如何設計一個編碼的演算法來達到此最低的壓縮比，且滿足對解碼準確率的要求？

為了簡化問題的分析，我們首先對訊息的模式做出以下假設：

> source產生出來的任意長度訊息序列（下文稱作source codeword）中的每一個字元都是從同一個定義於字母集$\mathcal S$上的機率分佈$P_S$所隨機生成，且彼此互相獨立（即機率中的i.i.d.）。

上述條件用較為formal的寫法即為：
$$
\begin{align}
S_i \overset{\text{i.i.d.}}\sim P_S, \forall i = 1, 2, ...
\end{align}
$$
我們稱滿足此性質的source為***discrete memoryless source***(DMS)。而對於解碼演算法所設計出的encoder限制如下：

> encoder解碼後之訊息與原訊息不同的機率$\mathsf {Pr} \{S^n \neq \hat S^n \}$（error probability，計為$P_e^{(n)}$）必須隨著序列長度$n$的增加而逐漸趨近於0，亦即
> $$
> \begin{align}
> \lim_{n \to \infty} \mathsf{Pr} \{ \hat S^n \neq S^n \} = 0.
> \end{align}
> $$

上面的敘述可等價地用極限的方式來嚴謹地表達：
$$
\begin{align}
\forall \epsilon \in (0, 1), \exists n_0 (\epsilon) \in \mathbb N \
\text{ such that } \
\mathsf{Pr} \{ \hat S^n = S^n \} \ge 1 - \epsilon, \forall n \ge n_0 (\epsilon). \tag{1}
\end{align}
$$
乍看之下好像有點複雜，但我們可以用較為直觀的方式來理解式$(1)$的含義：對於特定$n$下decoder的error probability，我們並不要求其必須為零，而是給定一個允許的額度$\epsilon$讓endoder能有犯錯的空間，為了使得演算法產生出來的decoder解碼錯誤的機率逐漸降低至$0$，我們規定當source codeword的長度超出$n_0(\epsilon)$時，演算法生出的decoder $\text{dec}_n$之error probability必須降低至$\epsilon$以下（亦即正確率要大於$1 - \epsilon$），而對於任意大於$0$的$\epsilon$，都必須滿足這個條件，也就是說，不管允許的錯誤機率有多大，只要序列的長度夠大，必能將解碼錯誤的機率控制在$\epsilon$之下。如此一來，假設真的存在某種演算法能達到$(1)$的條件，我們就能期望演算法的error probability能隨著序列長度$n$的增加而趨近於$0$。必須注意的是，我們要求演算法對於不同的長度$n$的序列集合$S^n$會產生不同的encoder $\text{enc}_n$和decoder $\text{dec}_n$（可視為兩個函數），而我們探討的是encoder和decoder隨著$n$增大的趨勢，而非針對單一的$n$值（例：$n=1000$）所產出的encoder和decoder做分析。

既然目前問題中的source為DMS，對於長度為$n$的某個特定序列$s^n = (s_1, ..., s_n)$，我們可以簡單的算出當source生成的序列長度為$n$時，產生的序列為$s^n$的機率$\mathsf{P}(s^n)$：
$$
\mathsf P (s^n)
= \mathsf P_{s_1 \sim P_S}(s_1) \times \mathsf P_{s_2 \sim P_S}(s_2) \times \cdots \times \mathsf P_{s_n \sim P_S}(s_n).
\tag{2}
$$
當式$(1)$的$\epsilon$和$n$被任意給定之後，一個將error probability將至$\epsilon$以下的直觀方式就是不斷收集$S^n$之中的元素（亦即序列），直到這些序列出現的總機率超過$1 - \epsilon$，如此一來只要對收集起來的每個元素做獨一無二的編碼傳入channel，decoder只要記得把這些二進制編碼還原回這些序列，就算不知道其餘同樣長度的編碼應該解碼成什麼序列，也能將error probability限制到至少在$\epsilon$之下。在這樣的概念下，我們結合式$(2)$給出以下定義：

給定$\epsilon \in (0, 1)$及$n \in \mathbb N$，我們稱集合 $\mathcal B (n, \epsilon) \subseteq \mathcal S^n$為一個$\mathbf{\epsilon}$***-high-probabitlity set***若且唯若
$$
\mathsf{Pr} \{ s^n \in \mathcal B (n, \epsilon) \}
\overset{(2)}
= \sum_{s^n \in \mathcal B(n, \epsilon)}
\left(
\prod_{i = 1}^n \mathsf P_S(s_i)
\right)
\ge 1 - \epsilon.
$$
延續上面的想法，為了達到error probability小於$\epsilon$，我們只需要$\left| \mathcal B(n, \epsilon) \right|$個獨一無二的二進制編碼即可，也就是說，我們一旦找到最小的$k$使得$2^k \ge \left| \mathcal B(n, \epsilon) \right|$，即可用$k$個位元的代價完成一個error probability在$\epsilon$之下的訊息壓縮。如此一來，只要我們能找到擁有越少元素的$\epsilon$-high-probability set，就能在error probability小於$\epsilon$的情況下達到越好的壓縮。在給定一個$n$的情況下，我們可以用貪婪演算法（greedy algorithm）的方式來獲得擁有最小size的$\epsilon$-high-probability set：只要暴力的將$\mathcal S^n$中的每個序列出現機率用式$(2)$算出來，並且由出現機率最高的序列開始收集，直到收集好的序列集其總發生機率大於$1 - \epsilon$即可。的確，這樣的作法能針對特定的$n$直接找到最小size的$\left| \mathcal B(n, \epsilon) \right|$（以及該$n$下可達到的最佳壓縮比），然而此方式很難用來估測當$n$越來越大時，可達到壓縮比變化的趨勢為何，也因此，我們需要另一種較易於分析的策略。

## 大數法則：分析問題的曙光

為了解決上一節分析上的困難，我們可以將收集$\epsilon$-high-probability set元素的方式放寬，一個可能的想法如下：只要發現某一序列出現的機率大於某個固定的下限值，就將它收集起來，直到收集的序列集成為一個$\epsilon$-high-probability set，這種策略直覺上亦能在某種程度上限縮我們最後得到之$\epsilon$-high-probability set的大小（假設此下限值為$p$且我們真的能用此法收集到某個$\epsilon$-high-probability set $\mathcal B (n, \epsilon )$，則$| \mathcal B (n , \epsilon) |$必定會在$\frac{1- \epsilon}{p}$以下），而為了要有理論上的依據，大數法則提供了一個強而有力的保證。

再繼續說下去之前，我們首先要知道什麼是大數法則，更精確的來說，接下來要使用到的是所謂***弱大數法則***（weak law of large numbers，WWLN），在這個問題的框架下，這個定理可以被理解為：

>對於一個函數$f: \mathcal S \rightarrow \mathbb R$（將字母集映射到實數的函數）且期望值是某個有限實數（$\mathsf E_{S \sim \mathsf P_S} [ | f(S)| ] < \infty$），則對於一個memoryless source $S_i \overset{\text{i.i.d}}\sim \mathsf P_s \forall i = 1, 2, ...$，以下必成立：
>$$
>\begin{align}
>\frac{1}{n} \sum_{i = 1}^n f(S_i) \overset{P}\rightarrow \mathsf E[f(S)]
>\quad \text{as } n \rightarrow \infty.
>\end{align}
>$$

與上一節極限的概念類似，上式亦等價於：

> $$\forall \delta > 0, \forall \epsilon \in (0, 1), \exists n_0 \in \mathbb N $$ 使得當$n \ge n_0$時，
> $$
> \begin{align}
> \mathsf{Pr} \left\{
> \frac{1}{n} \sum_{i=1}^n f(S_i) \in
> \left[
> \mathsf E [f(S)] - \delta, \mathsf E[f(S)] + \delta
> \right]
> \right\}
> \ge 1 - \epsilon.
> \tag{3}
> \end{align}
> $$

簡單來說，給定一個大於零的誤差$\delta$，當我們將一個memoryless source可能產出的字母都用某個函數對應到固定實數，則當source產出的序列長度$n$越來越大時，序列中每個字母的函數值平均與$f$本身期望值的差值在$\delta$以下的機率會逐漸趨近於$1$，而趨近的快慢程度就取決於分佈$P_s$的模樣了，一個很好想像的例子是，當我們丟擲非常多次的公正骰子，將出現過的點數（即$f(S_i)$）之和除以$n$，其結果趨近於骰子點數的期望值$3.5$（即$\mathsf E[f(S)]$）的可能性會趨近於$1$（定理結果非常直觀，有興趣的讀者可自行查閱它的證明）。

如果仔細一看，會發現式$(3)$其實提供了另一個尋找$\epsilon$-high-probability set的想法：只要將序列$s^n$中每個字母的函數均平均起來（即$\frac{1}{n} \sum_{i=1}^n f(s_i)$），如果它與$\mathsf E[f(S)]$相減結果的絕對值不超過$\delta$就收集起來，如此一來，得到的集合套用弱大數法則的結果不就是一個$\epsilon$-high-probability set了嗎？結合本節一開始的概念，如果$\frac{1}{n} \sum_{i=1}^n f(s_i)$能夠在某種程度上代表序列$s^n$出現機率的高低，那這個收集好的$\epsilon$-high-probability set內的每個元素出現的機率就有了一個理論上的上下界，進而達成限縮$\epsilon$-high-probability set大小的目的了！那到底$f$該怎麼定義才能跟序列出現的機率有所關聯呢？從式$(2)$我們知道序列出現的機率是以連乘序列中每個symbol出現機率的形式存在，然而$\frac{1}{n} \sum_{i=1}^n f(s_i)$卻是序列中每個symbol對應函數值的連加，究竟要如何把連乘轉換成連加呢？答案很簡單！只要把式$(2)$取對數即可：
$$
\begin{align}
\log\mathsf P (s^n)
& = \log \left[
\mathsf P_{s_1 \sim P_S}(s_1) \times \mathsf P_{s_2 \sim P_S}(s_2) \times \cdots \times \mathsf P_{s_n \sim P_S}(s_n)
\right] \\
& = \sum_{i=1}^N \mathsf \log P_S (s_i).
\end{align}
$$
也就是說，當我們把$f(s)$定義為
$$
f(s) := \log \mathsf P_{S}(s)
$$
的時候，代表剛剛收集好的$\epsilon$-high-probability set中每個序列出現的機率都得到了一個上下界，為什麼呢？因為任何一個$\epsilon$-high-probability中的元素$s^n = (s_1, ..., s_n)$都會滿足
$$
\begin{align}
& \left|
\frac{1}{n} \sum_{i=1}^n\log \mathsf P_s(s_i) - \mathsf E [ \log \mathsf P_s(s) ]
\right| \le \delta \\
\iff &
\mathsf E [\log \mathsf P_s(s) ] - \delta
\le \frac{1}{n} \sum_{i=1}^n \log \mathsf P_s(s_i)
\le \mathsf E [\log \mathsf P_s(s) ] + \delta \\
\iff &
\mathsf E [\log \mathsf P_s(s) ] - \delta
\le \frac{1}{n} \log \mathsf{Pr} \{ S^n = s^n \}
\le \mathsf E [\log \mathsf P_s(s) ] + \delta \\
\iff &
2^{n(\mathsf E [\log \mathsf P_s(s) ] - \delta)}
\le \mathsf{Pr} \{ S^n = s^n \}
\le 2^{n(\mathsf E [\log \mathsf P_s(s) ] + \delta)}. \tag{4}
\end{align}
$$
由上可知，集合中的任一個序列其出現機率都會大於$2^{n(\mathsf E [\log \mathsf P_s(s) ] - \delta)}$這個下界，也因此我們成功地替任意的序列長度$n$都找到一個足夠小的$\mathcal B (n, \epsilon )$了！巧合的是，這個下界竟然是Shannon entropy的函數！因為根據entropy的定義，我們得出
$$
\mathsf E_{s \sim P_s} [f(s)]
= \mathsf E_{s \sim P_s} [\log \mathsf P_S(s)]
= - H(S).
$$
結合$(4)$的結果，當$n$大到$\epsilon$和$\delta$都夠小的時候，集合中的每一個序列出現的機率都會大致落在$2^{-nH(S)}$附近，而由於它們加總起來的機率接近於$1$，集合的元素數量大約會是$1 \div 2^{-nH(S)} = 2^{nH(S)}$這麼多，所以我們共需要$nH(S)$這麼多個位元來為長度為$n$的序列進行編碼，也就是說，平均每個字母需要$H(S)$這麼多個位元來表示。

經過了一番推導，大數法則告訴了我們一件重要的事情：當序列長度很大時，理論上我們可以做到壓縮比為$H(S)$（即entropy）的資訊壓縮，而事實上在數學上也可以證明entropy也恰好是我們可以達到最好的壓縮比。另一個重要的啟示是越混亂（entropy越大）的資訊，我們越難將它進行壓縮，也因此事件的混亂程度相當於對該事件編碼所需的資訊量。

## 參考資料

[1] I-Hsiang Wang. (2021). *Representing Information Losslessly* [lecture slides]. Department of Electrical Engineering, National Taiwan University.

[2] *Elements of Information Theory*, Second Edition. *Thomas* M. Cover. Joy A. *Thomas*.

[3] Aerin Kim. (Sep 30, 2018). [The intuition behind Shannon’s Entropy](https://towardsdatascience.com/the-intuition-behind-shannons-entropy-e74820fe9800\>)