從計算機編碼的角度看Entropy

# 從計算機編碼的角度看Entropy - [blog version](https://meetonfriday.com/posts/216f7e20/) ## Shannon Entropy ### 簡介 Entropy概念最早被用於熱力學，在1948年由Shannon將此概念引入[information theory](https://zh.wikipedia.org/wiki/%E4%BF%A1%E6%81%AF%E8%AE%BA)中，被用來**計算根據訊息的機率分布對訊息編碼所需要的平均編碼長度**，也因此Entropy也被稱之Shannon Entropy。 ### 情境思考在早期計算機設備昂貴的年代，如果需要傳遞一段由26個英文字母組成的英文文本，按照[ASCII code的編碼](https://zh.wikipedia.org/wiki/ASCII)每一個字元共需要8個bit進行編碼，但實際上並不是每個字母出現的頻率(或機率)都是相等的，因此，**如果可以讓越常出現的字元使用較少的bit數，而較不常出現的字元使用較多的bit數，就有機會整體傳送的bits數較少。** - 你說節省傳送的bit數量有什麼好處? cost is money阿孩子 - 根據鴿籠原理，任何無損壓縮技術不可能縮短任何訊息，如果有一些訊息變短，則至少有一條訊息變長。 - 在實際使用中，由於我們通常只關注於壓縮特定的某一類訊息，一些編碼技術恰好使用了這特性。 - 對於壓縮編碼的技術，可以參考[霍夫曼編碼](https://zh.wikipedia.org/wiki/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81) 對於上述的敘述，實際上，英文文本的平均編碼長度大約在4.7bits，也就是說，給予一段長度為10的英文文本: - 不使用任何編碼壓縮技術，直接使用ASCII傳送的話需要 $8\times10 = 80$ bits - 使用Entropy的編碼技術來傳送的話平均只要$4.7\times10 = 47$ bits 所以要怎麼知道對於某些訊息，應該要用多少bit來編碼呢? Entropy可以幫助你 ### Entropy formula 先完整看一次Entropy的公式$$Entropy = -\sum_ip_ilog_b(p_i)$$ - 注意這裡log的底沒有限定是什麼，不同的b對應到不同單位，不過為了從information theory的角度出發，下面會用b=2來講解，此時的單位為**bit** ### 理解公式這鬼東西跟編碼長度到底有什麼鬼關係? 簡化一下剛剛提到的情境來思考這個問題，現在假設需要傳遞一個由$S=\{S_1, S_2, S_3, S_4\}$組成的字串，使用ASCII的話每個字元需要8 bits來進行傳遞，但實際上只有四種可能，也就是說我們只需要 $$log_2(4)$$ 2個bit就可以來進行四個答案的編碼了: {00, 01, 10, 11} 而我們又可以將上述的式子改寫一下$$log_2(4) = log_2(\frac{1}{\frac{1}{4}}) = -log_2(\frac{1}{4})$$ 這裡的1/4可以看成是一個隨機變數的機率，並且1/4其實對應到了上面這個例子沒有提到的一個假設: **4個字元出現的機率是相等的**，基於機率相等的假設下，$S_1, S_2, S_3, S_4$都可以透過上述的公式算出需要2個bit的編碼。不過並不是每個case都這麼是機率相等的，**為了可以套用在機率不同的情況下，需要引入期望值的概念**，也就是說式子變成了 $$\sum_ip_i\times S_i總共需要的編碼長度 = -\sum_ip_ilog_2(p_i)$$ - 實際上，將 $p_1 = p_2 = p_3 = p_4 = 1/4$ 帶入Entropy的公式也會得到2 - 在information theory中，$-log_2(\frac{1}{p})$也稱之為資訊本體(self-information)，也就是說，**越不常出現的訊息往往帶著越大的資訊含量**。所以到這裡我們可以說，**Entropy在算的是對於每個編碼，所需要長度的期望值**。 --- 接下來繼續考慮上述問題，但是這次$S=\{S_1, S_2, S_3, S_4\}$的機率並不相等了，假設: - $P(S_1)=1/4$ - $P(S_2)=1/8$ - $P(S_3)=1/2$ - $P(S_4)=1/8$ 在這種情況下，各別需要的編碼數為: - $S_1$需要2 bits編碼 - $S_2$需要3 bits編碼 - $S_3$需要1 bits編碼 - $S_4$需要3 bits編碼我們可以隨便編，例如給$S_1$:10、$S_2$:011、$S_3$:0、$S_4$:111之類的，只要沒有衝突到就好了，然後算一下編碼長度的期望值$$-\sum_ip_ilog_b(p_i) = 1/4\times2+1/8\times3+1/2\times1+1/8\times3 = 1.75$$ 所以平均編碼長度總共是1.75個bit。你說小數是什麼鬼?阿不都說了是平均==，如果還覺得哪裡怪怪的話，那接下來來個實際情境想一下。 --- 接續上述問題，假設由$S=\{S_1, S_2, S_3, S_4\}$組成的字串長度為200個字元，並且字元出現的次數恰好完全符合上述的機率分布，也就是說 - $S_1$出現了50次 - $S_2$出現了25次 - $S_3$出現了100次 - $S_4$出現了25次所以傳遞這個字串總共需要$50\times2+25\times3+100\times1+50\times2=375$個bit，平均每個字元只用了375/200 = 1.75個bit。 ### 結論簡介了從Information Theory的Encoding角度去看待Entropy這件事，並透過簡單的例子回顧公式的意義。重申一次，所以Entropy在Information Theory中的用途是**計算根據訊息的機率分布對訊息編碼所需要的平均編碼長度**。 ### 延伸討論: Entropy必不能為負? 1. 從數學的角度講，因為$0<p_i<1$，所以$-p_ilog_bp_i>=0$ 2. 從資訊意義的角度，取自[为什么信息量不能为负值？](https://www.zhihu.com/question/263824964) > 因为，信息值为负的已经不能叫做信息，而被叫做干扰。 > > 香农的理论是很简朴而典型的，A想要把某个信息a传递给B，但传播信息的信道存在种种异常，比如，A站在山顶喊话“我喜欢你”，结果因为风太大，B只听到“我喜欢”，虽然信息量丢失，但仍有一部分信息传达了，那就是“我（A）”和“喜欢（L）”。 > > 第二次，A还对B说，“我喜欢你”，但因为风太大，B听成了，“我喜欢隔壁老王”。那么B所得到的信息是什么呢？“我(A)”和“喜欢(L)”这两个信息的置信度提高了，而“你(B)”的置信度降低了。 > > 但是当A说，“我喜欢你”，B可能会因为风太大而听成“老李讨厌隔壁老王”么？可能性很低。 ## Cross Entropy 知道Entropy在information theory的意義後，後面就很好介紹了。先說結論，Cross Entropy可以這樣理解: **使用了估計出來的編碼後所得到的平均編碼長度**。 ### Cross Entropy formula 先完整看一次Entropy的公式$$Cross Entropy = -\sum_ip_ilog_b(q_i)$$ - 注意儘管公式很像Shannon Entropy，但不同的地方在於log裡面用的是q(x) ### 理解公式對於上述公式我們可以這麼理解: 對於某個需要被傳遞的資料，$p$是真正的機率分布，但這個機率分布我們事實上不知道，所以我們透過了神奇的Machine Learning / Deep Learning等黑技術去學習到了一個我們以為的機率分布$q$。所以接下來我們使用$-\sum_ilog_b(q_i)$來進行編碼，但事實上資料真正的機率分布是$p$，所以我們得到的平均編碼長度就變成了$-\sum_ip_ilog_b(q_i)$。也就是說，當$q$估計的越準(越接近p)，平均編碼長度才會是最短的(接近Shannon Entropy)。 ### 總結 - 實際上從ML/DL的角度來看，Cross Entropy Loss的概念就是，今天有一個資料真正的機率分布以及透過model學習出來的分布，我們希望這兩個機率分布越接近越好。 ### 延伸討論: Cross Entropy遇到$log0$? - 這在training中常常會遇到，implement上通常會採用$log(x+ \epsilon)$來handle這個狀況。 ## KL-Divergence 接下來來介紹KL-Divergence，一樣先說結論: KL-Divergence實際上是**當估出來的編碼方式和理想上的編碼有差時，而導致平均編碼差度的誤差值**。 - 實際上，這很常發生，因為我們不知道理想上的編碼方式應該是如何(不知道機率分布)，所以我們使用model估出來的編碼方式可能會產生誤差。 ### KL-Divergence formula 公式如下: $$KL-Divergence = \sum_ip_ilog_b(\frac{p_i}{q_i})$$ ### 理解公式再看一遍Cross Entropy的公式和它的定義: 使用了估計出來的編碼後所得到的平均編碼長度$$Cross Entropy = -\sum_ip_ilog_b(q_i)$$ 那這個估計出來的編碼長度到底理想上的編碼長度差了多少?我們可以來算算看$$Cross Entropy-Shannon Entropy \\=-\sum_ip_ilog_b(q_i) -(-\sum_ip_ilog_b(p_i)) \\=\sum_ip_ilog_b(p_i)-\sum_ip_ilog_b(q_i) \\=\sum_ip_ilog_b(\frac{p_i}{q_i})$$ 驚!這不就是KL-Divergency的公式嗎，再仔細看... 又驚!這不就是KL-Divergency的定義嗎 ### 結論 - 實際上KL-Divergence算的就是兩個機率分布的距離。 ### 延伸討論: 為何DL常使用Cross Entropy而不是KL? 簡單來說，在ML的task裡面，KL和CE是等價的，只是算KL的話還必須多算一個Entropy，所以大家都只算CE。詳細的解釋可以看下面這篇，取自[Why has cross entropy become the classification standard loss function and not Kullbeck Leibler divergence?](https://ai.stackexchange.com/questions/3065/why-has-cross-entropy-become-the-classification-standard-loss-function-and-not-k) > When it comes to classification problem in machine learning, the cross entropy and KL divergence are equal. As already stated in the question, the general formula is this:$$H(p,q)=H(p)+DKL(p||q)$$ > Where p a “true” distribution and q is an estimated distribution, H(p,q) is the cross-entropy, H(p) is the entropy and D is the Kullback-Leibler divergence. > Note that in machine learning, p is a one-hot representation of the ground-truth class, i.e.,$$p=[0,...,1,...,0]$$ > which is basically a delta-function distribution. But the entropy of the delta function is zero, hence KL divergence simply equals the cross-entropy. > In fact, even if H(p) wasn't 0 (e.g., soft labels), it is fixed and has no contribution to the gradient. In terms of optimization, it's safe to simply remove it and optimize the Kullback-Leibler divergence. ### 延伸討論: 為何DL常使用CE而不是LSE? 在gradient更新上速度的不同，有機會下次再說。 ## 總結從計算機編碼的角度來介紹Shannon Entropy的意義，並延伸介紹了Cross Entropy以及KL-Divergence，最後在總結三者之間的關係$$Cross Entropy = Shannon Entropy + KL-Divergence$$ 我們常常在做的Min Cross Entropy實際上就是是在Min KL-Divergence，當KL-Divergence = 0時，這代表這兩個機率分布是沒有差異的。 ## Reference - [ASCII](https://zh.wikipedia.org/wiki/ASCII) - [Shannon entropy(weki)](https://en.wiktionary.org/wiki/Shannon_entropy) - [霍夫曼編碼](https://zh.wikipedia.org/wiki/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81) - [熵(wiki)](https://zh.wikipedia.org/wiki/%E7%86%B5_(%E4%BF%A1%E6%81%AF%E8%AE%BA)) - [self-information](https://zh.wikipedia.org/wiki/%E8%87%AA%E4%BF%A1%E6%81%AF) - [熵和编码长度](https://www.cnblogs.com/frombeijingwithlove/p/5931750.html) - [为什么信息量不能为负值？](https://www.zhihu.com/question/263824964) - [交叉熵(Cross Entropy)](https://www.cnblogs.com/ljy2013/p/6432269.html) - [如何通俗的解释交叉熵与相对熵?](https://www.zhihu.com/question/41252833) - [Why has cross entropy become the classification standard loss function and not Kullbeck Leibler divergence?](https://ai.stackexchange.com/questions/3065/why-has-cross-entropy-become-the-classification-standard-loss-function-and-not-k) - [分类问题中损失函数为什么交叉熵用的多，而不是KL?](https://www.zhihu.com/question/336677048/answer/760789081)