資訊理論與機器學習

01-29

雖然標題中有機器學習，但這篇文章更主要講的是資訊理論的一些知識。在後面會對資訊理論中的一些理論在機器學習中的應用進行簡單的介紹。

寫這篇文章的原因在於總是在看書或者讀paper時遇到有關於資訊理論的一些知識，雖然已經學過資訊理論，但某些簡單的概念總是讓我感到混亂。這裡既是複習，也是整理。

編碼

談到資訊理論，就離不開編碼。談到資訊理論就離不開傳遞信息，傳遞信息的過程需要對信息進行編碼，而如何用最少的編碼表示所要傳遞的信息就是我們要研究的目標了。

假設兩地互相通信，兩地之間一直在傳遞 $A$ ， $B$ ， $C$ ， $D$ 四類消息，那應該要選擇什麼樣的編碼方式才能儘可能少的使用資源呢？如果這四類消息的出現是等概率的，都為 $frac{1}{4}$ ，那麼肯定應該採用等編碼方式，也就是

$begin{array}{|c|c|c|c|c|}nhlinenMessage&A&B&C&D hlinenCode&00&01&10&11 hlinenend{array}$

這樣就能達到最優的編碼方式，平均編碼長度為 $2timesfrac{1}{4}times4=2$ 。

但是，如果四類消息出現的概率不同呢？例如 $A$ 消息出現的概率是 $frac{1}{2}$ ， $B$ 是 $frac{1}{4}$ ， $C$ 是 $frac{1}{8}$ ， $D$ 是 $frac{1}{8}$ ，那應該怎樣編碼呢？直覺告訴我們，為了使平均編碼長度儘可能小，出現概率高的 $A$ 消息應該使用短編碼，出現概率低的 $C$ ， $D$ 消息應該使用長編碼。與等長編碼相比，這樣的編碼方式叫做變長編碼，它的效果更好，例如採用下表所示的編碼（其實這是最優編碼）

$begin{array}{|c|c|c|c|c|}nhlinenMessage&A&B&C&D hlinenProb&frac{1}{2}&frac{1}{4}&frac{1}{8}&frac{1}{8} hlinenCode&0&10&110&111 hlinenend{array}$

平均編碼長度為 $1timesfrac{1}{2}+2timesfrac{1}{4}+3timesfrac{1}{8}+3timesfrac{1}{8}=1.75$ ，顯然要優於等長編碼。

編碼空間

在對消息進行變長編碼時，可以看到對 $A$ 消息編碼後，後面的三類消息編碼都不是以 $0$ 開頭。這是因為在編碼時必須保證該編碼是唯一可解碼的。例如若 $A$ 消息編碼為 $0$ ， $B$ 消息編碼為 $01$ ，那麼 $0101$ 的編碼就會產生歧義，即不知道在何位置對接收到的編碼消息進行劃分。因此在進行變長編碼時，就必須保證任何編碼都不是其他編碼的前綴。符合這種特性的編碼稱為前綴碼（Prefix Codes）。

從上面的敘述可以看出，每當在某位置選取一個編碼以後，我們都要損耗一部分編碼空間，如圖

當我們在第2個bit選擇了編碼 $1$ ，那為了滿足前綴碼的特性，就會導致有 $frac{1}{4}$ 的編碼空間不能繼續使用了。事實上，長度為 $L$ 的編碼會使得 $frac{1}{2^L}$ 的編碼空間不能繼續使用。

因此，為了達到對信息進行最優編碼的目標，我們要在使用儘可能短的編碼與短編碼可能會導致編碼空間不可用的兩種情況中進行權衡。

我們可以把使用短編碼需要消耗的編碼空間稱為編碼代價。事實上，為了達到理論上的最優編碼，我們只需要根據不同消息 $X$ 出現的概率 $P(X)$ 給每類消息分配相應的編碼代價即可以達到最優編碼，假設 $X$ 的編碼長度為 $L(X)$ ，那麼

$begin{align}n&frac{1}{2^{L(X)}}=P(X)n&L(X) = log_2{frac{1}{P(X)}}nend{align}$

這樣，對於 $p$ 分布，我們的平均編碼長度就是

$H(p)=sum_{x}p(x)log_2(frac{1}{p(x)})$

在資訊理論中， $H(p)$ 被稱為熵，熵代表了理論上對符合 $p$ 分布的消息進行編碼的最優編碼的平均長度。

交叉熵與KL散度

若現在還有一種消息序列的概率分布滿足 $q$ 分布，但是它仍然使用 $p$ 分布的最優編碼方式，那麼它的平均編碼長度即為

$H(q||p)=H_p(q)=sum_{x}q(x)log_2(frac{1}{p(x)})$

其中 $H_p(q)$ 被稱為 $q$ 分布相對於 $p$ 分布的交叉熵（Cross Entropy），它衡量了 $q$ 分布使用 $p$ 分布的最優編碼方式時的平均編碼長度。

交叉熵不是對稱的，即 $H_p(q)neq H_q(p)$ 。交叉熵的意義在於它給我們提供了一種衡量兩個分布的不同程度的方式。兩個分布 $p$ 和 $q$ 的差異越大，交叉熵 $H_p(q)$ 就比 $H(p)$ 大的越多，如圖

它們的不同的大小為 $D_p(q)$ ，這在資訊理論中被稱為KL散度（Kullback-Leibler Divergence），它滿足

$D_p(q)=H_p(q)-H(q)$

KL散度可以看作為兩個分布之間的距離，也可以說是可以衡量兩個分布的不同程度。

多變數熵與互信息

和單變數相同，如果有兩個變數 $X$ ， $Y$ ，我們可以計算它們的聯合熵（Joint Entropy）

$H(X,Y)=sum_{x,y}p(x,y)log_2(frac{1}{p(x,y)})$

當我們事先已經知道 $Y$ 的分布，我們可以計算條件熵（Conditional Entropy）

$H(X|Y)=sum_{y}p(y)sum_{x}p(x|y)log_2(frac{1}{p(x|y)})=sum_{x,y}p(x,y)log_2(frac{1}{p(x|y)})$

$X$ 與 $Y$ 變數之間可能共享某些信息，我們可以把信息熵想像成一個信息條，如下圖

從中可以看出，單變數的信息熵 $H(X)$ (或 $H(Y)$ )一般比多變數信息熵 $H(X,Y)$ 要小。如果把條件熵也放進來，那麼可以從信息條更清晰的看出它們之間的關係

可以看出

$H(X,Y)=H(X)+H(Y|X)=H(Y)+H(X|Y)$

更細一點，我們把 $H(X)$ 與 $H(Y)$ 重疊的部分定義為 $X$ 與 $Y$ 的互信息（Mutual Entropy），記作 $I(X,Y)$ ，則

$I(X,Y)=H(X)+H(Y)-H(X,Y)$

互信息代表了 $X$ 中包含的有關於 $Y$ 的信息（或相反）。

將 $X$ 與 $Y$ 不重疊的信息定義為差異信息（Variation of Information），記為 $V(X,Y)$ ，則

$V(X,Y)=H(X,Y)-I(X,Y)$

差異信息可以衡量變數 $X$ 與 $Y$ 的差距，若 $V(X,Y)$ 為0，就意味著只要知道一個變數，就知道另一個變數的所有信息。隨著 $V(X,Y)$ 的增大，也就意味著 $X$ 與 $Y$ 更不相關。形象化的表示可以從下圖看出

交叉熵和KL散度在機器學習中的應用

資訊理論中有很多理論可以應用在機器學習中，其中交叉熵和KL散度在各類模型中出現的頻率非常高。

在分類任務中，我們想要的結果是使預測的分布和真實的分布盡量接近，交叉熵提供了一種非常好的衡量方式，在LR分類，SVM多分類等問題中經常用到，將交叉熵定義為損失函數

$L=H_p(q)=sum_xp(x)log(frac{1}{q(x)})$

其中 $p(x)$ 代表真實分布， $q(x)$ 代表預測分布，優化目標為 $min_{q(x)}L$ 。

在概率推斷中，經常使用變分推斷來近似隱變數 $Z$ 真實的後驗分布 $P(Z|X)$ 。利用如下公式

$lnP(X)=L(q)+KL(q||p)$

其中

$L(q)=int q(Z)ln{frac{p(X,Z)}{q(Z)}}dZ$

$KL(q||p)=-int q(Z)ln{frac{p(Z|X)}{q(Z)}}dZ$

上式中的 $L(q)$ 稱為證據下界（Evidence Lower Bound）。

這裡KL散度 $KL(q||p)$ 描述了估計分布 $q(Z)$ 與真實分布 $P(Z|X)$ 的差別，當 $KL(q||p)=0$ 時兩分布就是相同的。我們知道 $KL(q||p)geq0$ ，但因為我們不知道真實的後驗分布 $P(Z|X)$ 是什麼，因此無法直接最小化 $KL(q||p)$ ，但是我們可以通過最大化 $L(q)$ 來達到這個目的。而在求解最大化 $L(q)$ 的過程中，可以利用平均場方法（Mean Field）將最終目標可以轉化成最小化另外的一個KL散度（這裡省略推導了，具體可參見《機器學習》）。

參考

《機器學習》周志華
《Pattern Recognition and Machine Learning》Christopher Bishop