資訊理論（一）

04-07

文章內容來自http://colah.github.io/posts/2015-09-Visual-Information/

可視化概率分布

$P( Weather = sunny ) = 0.75$ , $P( Weather = raining ) = 0.25$

$P( Cloth = T-shirt ) = 0.62$ , $P( Cloth = coat ) = 0.38$

若隨機變數 $Weather$ 和 $Cloth$ 相互獨立，可作出如下聯合概率圖，注意到分割線是直線，表達了相互獨立的含義

當隨機變數 $Weather$ 和 $Cloth$ 相關時，聯合概率發生了變化，因為 $sunny$ 和 $T-shirt$ 更配，它們的區域擴大了，同時擴大的還有 $raining$ 和 $coat$ ，而剩下的「不配」的區域縮小了

編碼

假設有一個朋友Bob，他只說4個單詞：dog、cat、fish、bird，並且交流時使用2進位碼錶示信息。使用2位二進位碼可表示4個單詞，此時的平均碼長為2。單詞和二進位編碼的對應關係如下

可將此編碼方式畫圖顯示如下，方塊的面積之和越大，表示平均碼長越長

上述編碼方式沒有考慮每個單詞出現的概率。現在已知Bob特別喜歡dog，他說的4個單詞的頻率分布如下

為了縮小平均碼長，考慮如下變長編碼

變長編碼可視化圖如下所示，方塊的面積之和為1.75，即平均碼長為1.75。對於這個概率分布，這種編碼方式已經達到最優。

The Space of Codewords

每定義一個編碼，都需要犧牲掉以此編碼為前綴的所有編碼空間。如下圖所示，假設我們定義了一個編碼01，為了使解碼無歧義，必須捨棄任何以01為前綴的編碼，如010、011010110等。在3位的編碼中（考慮3位是因為開始犧牲的空間位於3位編碼處），犧牲的比例為 $frac{1}{2^{L} }=frac{1}{4}$ ，其中 $L$ 為編碼01的長度，即 $L=2$ 。一個很直觀的理解是，定義的編碼長度越小，所犧牲掉的編碼空間也越大。因此，雖然對出現概率高的單詞定義長度小的編碼，縮短了平均碼長，獲得了好處，但是犧牲了較大的編碼空間，即產生了壞處。於是，我們需要在上述好處和壞處之間做權衡。

最優編碼

編碼長度 $L(x)$ 和其犧牲的編碼空間（理解為代價） $Cost$ 的函數圖像如下，呈指數級遞減關係。

短的編碼容易減少平均碼長（紫色部分），但是更「昂貴」（灰色部分），而長的編碼容易增加平均碼長，但是更「便宜」。那麼，應該怎樣權衡這個矛盾呢？

一個直觀的方法是，對於出現頻率高的單詞，我們甘願為之付出更大的代價，即根據不同單詞的頻率按比例付出不同的代價。如一個單詞的出現頻率 $p(x) = 0.5$ ，我們付出的代價也為0.5（代價總和為1），即有 $Cost = frac{1}{2^{L} } = p(x) = 0.5$ ，從而算出 $L = 1$ ，即對該單詞的編碼長度為1。可以證明這樣的策略是最優的。在上圖中，這樣的最優策略會使得紫色部分和灰色部分的高度相同。

熵的概念

總結上一節的最優編碼策略，對於一個單詞，其出現的概率為 $p(x)$ ，分配的編碼長度為 $L(x)$ ，付出的代價 $Cost = frac{1}{2^{L(x)} }$ ，令代價等於概率 $Cost = p(x)$ ，解得 $L(x) = log_{2}( frac{1}{p(x)} )$ ，為概率 $p(x)$ 對應的最優編碼的長度。

於是可以求出概率分布 $p(x)$ 的最優編碼的平均碼長，稱為熵，記作 $H(p)$ 。

$H(p) = sum_{x}^{}{p(x)log_{2}(frac{1}{p(x)} ) } = -sum_{x}^{}{ p(x) log_{2}( p(x) ) }$

熵除了數據壓縮方面的解釋，還有另外2種解釋。

1. 熵表達了信息的不確定度

考慮以下4種情況

(1) 太陽從哪邊升起， $H(p) = 0$

事件1：太陽從東方升起， $p(a) = 1$

事件2：太陽從西方升起， $p(b) = 0$

(2) 國足對陣德國隊的比賽結果（只考慮輸和贏）， $H(p) = 0.2864$

事件1：德國隊勝， $p(a) = 0.95$

事件2：國足勝， $p(b) = 0.05$

(3) 投擲硬幣猜正反面， $H(p) = 1$

事件1：硬幣正面朝上， $p(a) = 0.5$

事件2：硬幣反面朝上， $p(b) = 0.5$

(4) 投骰子猜點數， $H(p) = 2.5850$

事件1：1點， $p(a) = frac{1}{6}$

事件2：2點， $p(b) = frac{1}{6}$

事件3：3點， $p(c) = frac{1}{6}$

事件4：4點， $p(d) = frac{1}{6}$

事件5：5點， $p(e) = frac{1}{6}$

事件6：6點， $p(f) = frac{1}{6}$

熵越大，則事件的結果越難猜測，表示事件的不確定程度越高。

當我們被告知事件的結果時，熵越大，獲得的新信息就越多。對於(1)，熵為0，我們沒有獲得新信息，對於(2)，我們獲得了一點點新信息，對於(3)，我們獲得了更多的新信息，對於(4)，我們獲得的新信息最多。

2. 熵表達了數據集的「混雜」程度

考慮以下4個概率分布：

(1) $p(a) = 1$ , $p(b) = 0$ , $H(p) = 0$

(2) $p(a) = 0.95$ , $p(b) = 0.05$ , $H(p) = 0.2864$

(3) $p(a) = 0.5$ , $p(b) = 0.5$ , $H(p) = 1$

(4) $p(a) = 0.2$ , $p(b) = 0.2$ , $p(c) = 0.2$ , $p(d) = 0.2$ , $p(e) = 0.2$ , $H(p) = 2.3219$

從圖中可以看出，熵越大，數據越「混雜」，並且很容易得出以下2點結論：

對比(1)、(2)、(3)，事件類別數相同時，事件等概率發生對應的概率分布的熵越大。

對比(3)、(4)，事件等概率發生時，事件類別數越多，概率分布的熵越大。

交叉熵

假設我們還有一位朋友Alice，同樣只會說4個單詞：dog、cat、fish、bird。但Alice喜歡貓，她和Bob的單詞頻率分布有所不同，如下所示

Bob的編碼方式對他自己是最優的，平均碼長為1.75。

而Alice採用了Bob的編碼方式，此時平均碼長為2.25，顯然對Alice來說，因為她的概率分布不同於Bob，因此Bob的編碼方式對她不是最優的。

於是就有了交叉熵的定義：對於一個概率分布 $q(x)$ ，使用另一個概率分布 $p(x)$ 的最優編碼，得到的平均碼長，記作 $H_{p}(q)$ ，稱為 $q$ 對 $p$ 的交叉熵

$H_{p}(q) = sum_{x}^{}{ q(x) log_{2}( frac{1}{p(x)} ) }$

對於Alice和Bob，存在以下4種情況：

Bob使用自己的最優編碼， $H(p) = 1.75$
Alice使用Bob的最優編碼， $H_{p}(q) = 2.25$
Alice使用自己的最優編碼， $H(q) = 1.75$
Bob使用Alice的最優編碼， $H_{q}(p) = 2.375$

可以看出 $H_{p}(q) e H_{q}(p)$ ，即交叉熵是不對稱的。

交叉熵描述了2個分布的差異程度：

分布 $p$ 和 $q$ 之間的差異越大， $q$ 對 $p$ 的交叉熵 $H_{p}(q)$ 比 $q$ 的熵 $H(q)$ 大得越多

分布 $p$ 和 $q$ 之間的差異越大， $p$ 對 $q$ 的交叉熵 $H_{q}(p)$ 比 $p$ 的熵 $H(p)$ 大得越多

因此，交叉熵與熵的差值，表達了2個分布之間的差異程度，這個差值叫做KL divergence。

概率分布p對q的KL divergence，記作 $D_{q}(p)$ ，定義如下：

$D_{q}(p) = H_{q}(p) - H(p)$

$= sum_{x}^{}{ p(x) log_2{ ( frac{1}{q(x)} ) } } - sum_{x}^{}{ p(x) log_2{ ( frac{1}{p(x)} ) } } = sum_{x}^{}{ p(x) log_2{ ( frac{p(x)}{q(x)} ) } }$
推薦閱讀：

※學堂在線《應用資訊理論基礎》學習筆記01
※信息與香農...

TAG:資訊理論 |