從簡單的資訊理論談到機器學習

簡單的資訊理論

上一篇文章我們提到了用熵 Entropy [3] 來衡量隨機性。熵的定義如下： \[ H(x) = E[-ln(Pr(x))] = -\sum_{i=1}^{N} Pr(x_i) ln(Pr(x_i)) \] 連續函數的形式為： \[ H(x) = -\int_{-\infty}^{\infty} Pr(x)\cdot ln(Pr(x))dx \] 從資訊理論的角度來看熵的直覺是當一個事件隨機性越小時，帶給我們的資訊量越小，而熵即是描述這個事件所需要的資訊量，也可以說是要描述這個事件最少需要多少資訊，也就是多少 bits 或 nats [1] 。舉一個以前在臺大上資訊理論與編碼技巧時吳老師用過的例子：當一位同學每天都來上課時，這幾乎沒給我們任何資訊，因為你知道不管如何這位同學都會來上課。在這個情況下同學來上課這個事件的熵也就是零。

交叉熵 Cross Entropy

剛剛講熵是描述一個事件的資訊量，可以當成是描述一個事件所需的編碼長度 bits 或 nats ，假設 p 是這個事件的真實機率分布，熵 H(p) 是這個編碼長度的期望值。換句話說， \(ln(p(x_i))\) 是單獨事件 \(x_i\) 的編碼長度，單獨事件的機率是 \(p(x_i)\) ，因此熵就是事件編碼長度的期望值。

現在要來解釋交叉熵 [2] 了。交叉熵的意思是當用另一個機率分布 q 計算事件的平均編碼長度，也就是以下式子： \[ H(p,q) = -\sum_{i=1}^{N} p(x_i) ln(q(x_i)) \] 因為機率分布 q 不是真實的機率分布 p ，因此可以想像當用錯誤的分布 q 來衡量此事件的編碼長度期望值時，所需要的資訊量會比用真實分布 p 計算期望值比較多，也就是： \[ H(p,q) \geq H(p, p) = -\sum_{i=1}^{N} p(x_i) ln(p(x_i)) = H(p) \]

交叉熵與機器學習的關係

機器學習的目的是我們想要從手中的樣本中估計出一個機率分布 q ，讓 q 逼近於母體的真正機率分布 p 。這時候交叉熵 H(p,q) 就代表用 q 這個機率分布時得到的編碼長度，而 p 的熵 H(p) 是用真實分布 p 時的編碼長度期望值，也就是理論上能達到的最佳編碼長度；因此可以說機器學習的目的是讓 H(p,q) 逼近於 H(p) ，也就是讓 H(p,q) - H(p) 最小，這個式子就是大家常常聽到的 KL Divergence (Kullback-Leibler Divergence) [3] 。

Kullback-Leibler Divergence

KL Divergence 的式子為： \[ D_{KL}(p||q) = -\sum_{i=1}^{N} p(x_i) ln(\frac{q(x_i)}{p(x_i)}) \\ = - E_{x \sim p}[ln(q(x)) - ln(p(x))] \\ = E_{x \sim p}[ln(p(x)) - ln(q(x))] \] 驗證一下 KL Divergence 就是 H(p,q) - H(p) ： \[ D_{KL}(p||q) = -\sum_{i=1}^{N} p(x_i) ln(\frac{q(x_i)}{p(x_i)}) = -\sum_{i=1}^{N} p(x_i) (ln(q(x_i))) - ln(p(x_i))) \\ = -\sum_{i=1}^{N} p(x_i) ln(q(x_i)) - (- \sum_{i=1}^{N} p(x_i) ln(p(x_i))) = H(p,q) - H(p) \]

從 KL Divergence 推導至 Cross Entropy Loss Function

前面講說機器學習的目的是找到一個機率分布 q 使其趨近於真實分布 p ，也就是讓 H(p,q) 逼近於 H(p) ；因此我們能做的是用手上的樣本計算 q 與 p 的交叉熵 H(p,q) ，並且找到 q 的參數使得 H(p,q) 最小，也就是讓 KL Divergence \( D_{KL}(p||q)\) 最小： \[ \bar{q} = arg\ \underset{q}{min} D_{KL}(p||q) \\ = arg\ \underset{q}{min} -\sum_{i=1}^{N} p(x_i) ln(q(x_i)) - (- \sum_{i=1}^{N} p(x_i) ln(p(x_i))) \\ = arg\ \underset{q}{min} -\sum_{i=1}^{N} p(x_i) ln(q(x_i)) \] 以上式子跟深度學習中常看到的 Cross Entropy Loss Function 是同一個形式： \[ L = -\frac{1}{N} \sum_{i=1}^{N}( y_i\ ln(\hat{y}_i) + (1 - y_i)\ ln(1 - \hat{y}_i)) \] 上式中 \(y_i\) 是實際結果的 label ，而 \(\hat{y}_i\) 是用類神經網路模型預測的結果，而我們在訓練此類神經網路的目的是要讓預測的結果 \(\hat{y}_i\) 逼近於實際的結果 \(y_i\) ，因此類神經網路中的 Cross Entropy Loss Function 背後的概念就可以說是要讓訓練出來的類神經網路 q 趨近於 training set 的機率分布 \( \hat{p} \)，而這個 loss function 就是衡量這兩個機率分布的差異。（註：請注意 training set 背後的機率分布 \( \hat{p} \) 與真實的機率分布 \(p\) 的不同。）

最大似然估計 Maximum likelihood estimation 就是找到參數使得 KL Divergence 最小

這一段主要是 Ian Goodfellow 所寫的 Deep Learning [4] 書中 5.5 的內容。

在最大似然估計 MLE 中我們想要找到的是一組最佳的參數 \(\theta\) 讓 \(p(D|\theta)\) 最大，這裡的 p 是指在機率模型 model 之下的機率，以下用 \( p_{model} \) 表示： \[ \theta_{MLE} = arg\ \underset{\theta}{max}\ p_{model}(D|\theta) = arg\ \underset{\theta}{max}\ \prod_{i=1}^{N}\ p_{model}(x_i | \theta) \] 兩邊取對數： \[ \theta_{MLE} = arg\ \underset{\theta}{max}\ \sum_{i=1}^{N}\ ln(p_{model}(x_i | \theta)) \] 將上式的 \( \sum \) 除以所有的樣本數 N 的話會變成針對 training set 背後的機率分布 \( \hat{p} \) 的期望值\( E_{x\sim\hat{p}} \)： \[ \theta_{MLE} = arg\ \underset{\theta}{max}\ E_{x\sim\hat{p}}[ln(p_{model}(x_i | \theta))] \] 而上面提到 KL Divergence 的目的是要讓選定的機率分布 \( p_{model} \) 趨近於 training set 背後的機率分布 \( \hat{p} \) ，也就是： \[ D_{KL}(\hat{p}\ ||\ p_{model}) = E_{x\sim\hat{p}}[ln(\hat{p}(x)) - ln(p_{model}(x))] \] 我們的目的是要讓 \( p_{model} \) 逼近 \( \hat{p} \) ，因此在最佳化 KL Divergence 時可以忽略 \( ln(\hat{p}(x))\) 這一項，也就是說我們想要讓 \( -E_{x\sim\hat{p}}[ln(p_{model}(x))] \) 最小，那就是讓 \( E_{x\sim\hat{p}}[ln(p_{model}(x))] \) 最大了，也就是上面最大似然估計 MLE 的式子。這個推導的結論是最大似然估計 MLE 與最小化 KL Divergence 是同一件事。

小結

討論至此我們從簡單的資訊理論談到他們在機器學習中扮演的腳色，並且也討論了與前幾篇文章中一些與機率相關的內容。我們在前文中提到 MLE 可能會得到 overfitting 的結果，而 MLE 與最小化 KL Divergence 與 Cross Entropy Loss Function 都是等價的，也就是如果只用 Cross Entropy Loss Function 來訓練類神經網路的話很多可能得到 overfitting 的結果，這就是為什麼在深度學習中當講完 Cross Entropy Loss Function 後就會開始講如何避免 overfitting 了。

參考資料

[1] https://en.wikipedia.org/wiki/Nat_(unit)
[2] https://en.wikipedia.org/wiki/Cross_entropy
[3] https://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence 
[4] https://www.deeplearningbook.org/