資訊理論（1）——熵、互信息、相對熵

05-23

資訊理論（1）——熵、互信息、相對熵

來自專欄哈工大計科小碩學習分享及筆記

開題詞

1948年Shannon博士的《A Mathematical Theory of Communication》（通信的數學理論）橫空出世，創世般地開闢了資訊理論，資訊理論從此便在通信領域發光發熱，為通信工程方面的成功奠定了堅實的理論基礎。然而資訊理論是一門普適性理論，它被認為當下熱潮的人工之能和機器學習修鍊「內功」，這是因為人工智慧本質是處理信息的，本人以為機器學習的演算法可以用資訊理論的思維去理解。有鑒於此，我對學習Information Theory感到期待和對Shannon博士充滿敬意，並對不斷補充資訊理論的學者們致以感激。

文章可以看做本人學習資訊理論的學習筆記（筆記將會以教授知識的形式給出），如有錯誤，還望大家指正。感謝！

熵

在引入熵的概念之前，我們可以思考這樣一個問題：

拋一枚有均勻正反面的硬幣，和擲一個均勻六面的骰子，哪一種試驗的不確定性更強一點呢？

粗略地看，我們感覺拋硬幣這個試驗的不確定性會更少一點，因為硬幣畢竟僅有2個結果，而骰子有6個結果，但是對於這樣一個直覺的事實，我們怎麼進行量化從而在數字層面上反映兩個隨機變數的不確定性的大小關係呢？

Shannon提出了熵的概念，解決了以上這個問題。對於上述離散型隨機事件，可以用離散熵定義其不確定性：

熵是一個隨機變數不確定性的度量，對於一個離散型隨機變數 $Xsim p(x)$ ，其離散熵可以定義為：
$H(X)=-sum_{xinchi}^{}{p(x)}log p(x)$
其中：花體 $chi$ 表示為包含所有小 $x$ 元素的集合，log以2為底。
註： $Hleft( X ight)$ 以公理化的形式給出，詳細推導請參考資訊理論（2）——熵的唯一性定理

下面用Shannon離散熵量化解決我們之前引入的兩個試驗：

設隨機變數 $X$ 為拋一枚均勻硬幣的取值，其中正面朝上用 $1$ 表示，反面朝上用 $0$ 表示，於是有：
$Pleft{ X=0，1 ight}= frac{1}{2}$ 註：由於 $X=0,X=1$ 概率均相等，為了版面整潔故合併表示。 $H(X)=- frac{1}{2} imes log frac{1}{2} - frac{1}{2} imes log frac{1}{2}=1$
設隨機變數 $Y$ 為擲一個六面均勻骰子的取值，其中 $Y=1,2,...,6$ ,於是有：
$Pleft{Y=1,2,...,6 ight}= frac{1}{6}$ $H(Y)=6 imesleft(- frac{1}{6}logfrac{1}{6} ight) =log6$

綜上我們有如下結論：
$H(X)=1=log2< H(Y)=log 6$
即隨機變數 $X$ 的不確定性確實比隨機變數 $Y$ 來的要小，符合我們的直覺。

我們可以更進一步地看，一個隨機變數的熵越大，意味著不確定性越大，那麼也就是說，該隨機變數包含的信息量越大，那到底信息量是什麼呢？拋一枚硬幣的信息量就是，正面朝上，反面朝上，這2就是信息量；同樣，擲骰子的信息量就是6個不同數字的面朝上，這6也是信息量。那麼，在計算機角度上看，熵到底是什麼，我們不妨看

$H(X)=1,H(Y)=log6$

其實就是意味著，在計算機中，要表示拋硬幣的結果，需要用1 bit，要表示擲骰子的結果需要用log6 bit（實際表示時為向上取整3 bit），也就是說熵是平均意義上對隨機變數的編碼長度。為什麼這麼說呢？

由熵的定義，我們知道：
$H(X)=-sum_{xinchi}^{}{p(x)}log p(x)=sum_{xinchi}^{}{p(x)}log frac{1}{p(x)}=Eleft[ log frac{1}{p(X)} ight]$
即，熵實際上是隨機變數 $X$ 的函數 $log frac{1}{p(X)}$ 的期望。

至此，我們已經了解到熵在資訊理論中的意義和在計算機編碼中的物理含義。最後我們再說明一下，必然事件的熵是多少呢？應該是0，因為必然是事件是確定無疑的，並不含有不確定性，也就是說，必然事件不含有信息量。

互信息

熵表明了單個隨機變數的不確定程度，那麼熵的值是確定不變的嗎？我們有辦法縮減這個不確定性嗎？如果能縮減那縮減多少可以量化嗎？

在這裡引一句題外話，吳軍老師《數學之美》一書曾提到。網頁搜索本質正是減少不確定性的一個過程，根據用戶的關鍵字和其他手段減少那些無關搜索，盡量接近用戶的搜索意圖，這種思維正可以體現資訊理論的「內功」本色。

我們舉一個例子來說明事件不確定性的變化：

假設現在我給你一枚硬幣，告訴你這是均勻的，請你拋100次然後告訴我結果，結果你拋了100次後，記錄的結果是：正面朝上90次，反面朝上10次，你就會開始懷疑「這真是一枚均勻的硬幣嗎？」

由第一部分熵中，我們知道，這一枚硬幣的熵應該是1 bit，但是這樣的試驗之後，這枚硬幣的熵還是1 bit嗎？我們可以假設正面朝上的概率為0.9，反面朝上的概率為0.1，計算一下這個熵：

$H(X|hat{X})=-0.9log 0.9-0.1log 0.1approx0.469$

其中， $H(X| hat{X})$ 表示為知道90次正面朝上的事實後，原硬幣的熵。

經過拋擲100次後，我們知道這麼硬幣可能是不均勻的，且新的熵為0.469 bit，也就是說我們在知道90次正面朝上，10次反面朝下的事實之後，這個硬幣的熵縮小了0.531 bit，這個0.531的信息量，我們就稱為互信息。

從而我們引入互信息的定義：

對於兩個隨機變數 $X$ 和 $Y$ ，如果其聯合分布為 $p(x,y)$ ,邊緣分布為 $p(x),p(y)$ ,則互信息可以定義為：
$I(X;Y)=sum_{xinmathcal{X}}^{}sum_{yinmathcal{Y}}^{}{p(x,y)log frac{p(x,y)}{p(x)p(y)}}$

乍一眼看，這個互信息的定義怎麼和我們說的例子不太一樣，其實這個定義是根據相對熵來下的定義，我們先不用管相對熵，我們看看這個定義能不能變成我們剛剛所說的縮減信息的形式，作如下推導：

$I(X;Y)=sum_{xinmathcal{X}}^{}sum_{yinmathcal{Y}}^{}{p(x,y)log frac{p(x,y)}{p(x)p(y)}}=sum_{xinmathcal{X}}^{}sum_{yinmathcal{Y}}^{}{p(x,y)log frac{p(y)p(x|y)}{p(x)p(y)}}$ $=sum_{xinmathcal{X}}^{}sum_{yinmathcal{Y}}^{}{p(x,y)log frac{p(x|y)}{p(x)}}=sum_{xinmathcal{X}}^{}sum_{yinmathcal{Y}}^{}{p(x,y)log p(x|y)}-sum_{xinmathcal{X}}^{}sum_{yinmathcal{Y}}^{}{p(x,y)log p(x)}$ $=-sum_{xinmathcal{X}}^{}{p(x)log p(x)}-left[ -sum_{xinmathcal{X}}^{}sum_{yinmathcal{Y}}^{}{p(x,y)log p(x|y)} ight]=H(X)-H(X|Y)$

經過推導後，我們可以直觀地看到 $H(X)$ 表示為原隨機變數 $X$ 的信息量， $H(X|Y)$ 為知道事實 $Y$ 後 $X$ 的信息量，互信息 $I(X;Y)$ 則表示為知道事實 $Y$ 後，原來信息量減少了多少。

為了更加形象地描述互信息，請允許我借用互聯網上的文氏圖來說明：

最後，如果隨機變數 $X,Y$ 獨立，那麼互信息是多少呢？應該是0，這意味著，知道事實 $Y$ 並沒有減少 $X$ 的信息量，這是符合直覺的因為獨立本來就是互不影響的。

相對熵

根據上面的敘述，我們了解到資訊理論中，對於孤立的一個隨機變數我們可以用熵來量化，對於兩個隨機變數有依賴關係，我們可以用互信息來量化，那麼對於兩個隨機變數之間相差多少？也就是說，這兩個隨機變數的分布函數相似嗎？如果不相似，那麼它們之間差可以量化嗎？

相對熵就是回答以上的問題，它給出了兩個分布之間的差異程度的量化，也就說相對熵代表的是這個兩個分布的「距離」。

我們引入相對熵的定義：

兩個概率密度函數 $p(x)$ 和 $q(x)$ 之間的相對熵定義為：
$D(p||q)=sum_{xin mathcal{X}}^{}{p(x)log frac{p(x)}{q(x)}}$

相對熵的一個應用場景就是，假設某一個樣本服從分布 $p(x)$ ，我們通過樣本擬合出來的分布是 $q(x)$ ,那麼他們之間的差異程度就是 $D(p||q)$ ，再一步而言，根據分布 $p(x)$ 我們得出表示隨機變數的碼長為其熵 $H(p)$ （該表達等價於 $H(X)$ ），而我們估計的分布為 $q(x)$ ,那麼他們的關係可以表達為：

$H(q)=H(p)+D(p||q)$

這樣我們就量化了兩個分布之間的「距離」了。

最後，我們解決互信息定義時候留下的疑團：

$I(X;Y)=sum_{xinmathcal{X}}^{}sum_{yinmathcal{Y}}^{}{p(x,y)log frac{p(x,y)}{p(x)p(y)}}=D(p(x,y)||p(x)p(y))$

由這樣的推導，我們知道互信息本質上其實是描述了聯合分布 $p(x,y)$ ，與兩個邊緣分布之積 $p(x)p(y)$ 的差異程度，如果差異程度為0，表示兩個隨機變數獨立，符合我們的直覺。