deep learning machine learning

[ML/DL]從計算機編碼的角度看Entropy, Cross Entropy和KL-Divergence

Posted by John on 2019-09-26
Words 2.6k and Reading Time 10 Minutes
Viewed Times

Shannon Entropy

簡介

Entropy概念最早被用於熱力學，在1948年由Shannon將此概念引入information theory中，被用來計算根據訊息的機率分布對訊息編碼所需要的平均編碼長度，也因此Entropy也被稱之Shannon Entropy。

情境思考

在早期計算機設備昂貴的年代，如果需要傳遞一段由26個英文字母組成的英文文本，按照ASCII code的編碼每一個字元共需要8個bit進行編碼，但實際上並不是每個字母出現的頻率(或機率)都是相等的，因此，如果可以讓越常出現的字元使用較少的bit數，而較不常出現的字元使用較多的bit數，就有機會整體傳送的bits數較少。

  • 你說節省傳送的bit數量有什麼好處? cost is money阿孩子
  • 根據鴿籠原理，任何無損壓縮技術不可能縮短任何訊息，如果有一些訊息變短，則至少有一條訊息變長。
  • 在實際使用中，由於我們通常只關注於壓縮特定的某一類訊息，一些編碼技術恰好使用了這特性。

對於上述的敘述，實際上，英文文本的平均編碼長度大約在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_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=0$
  2. 從資訊意義的角度，取自为什么信息量不能为负值？

因为，信息值为负的已经不能叫做信息，而被叫做干扰。
香农的理论是很简朴而典型的，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$估計的越準(越接近q)，平均編碼長度才會是最短的(接近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)$

那這個估計出來的編碼長度到底理想上的編碼長度差了多少?我們可以來算算看

驚!這不就是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?

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

>