如何測量這個世界的混亂-2-信息熵

02-24

信息熵： $S=-sum_{i}{p_{i}log{p_{i}}}$

一旦我們把信息熵的定義擺出來，意味著任意給定一個概率分布 $p_{i}$ ,我們都可以計算出一個對應的表徵這個概率分布的混亂度的量。這樣能玩的事情就很多了。很多含糊的問題現在可以開始嘗試解答了。

我們還是從最簡單的例子開始。假設現在 $p_{i}$ 中的i只有兩個取值。其中一個取值的概率為p，另一個自然是1-p。那麼隨著p的變化，信息熵的值是這樣的：

圖片來源：《A Mathematical Theory of Communication》

這個簡單例子給你帶來了信息熵的第一個直觀感受：概率均勻分布各為0.5的時候對應熵極大 $log(2) = 1$ ，系統的混亂度極大。這和日常經驗是相符的，「下雨/不下雨各佔50%」與「80%下雨/20%不下雨」顯然後者的信息更多，混亂度小。

常見的絕大多數系統，天氣，股票，語言文字，圖片，統計熱力學量，波函數模方。都可以通過各自的手段劃歸成各自對應的概率分布。而一旦有了這種概率分布，我們就能立即得到這種系統對應的混亂度。這正是資訊理論的強大之處。

下面我們就拿語言文字作為我們的第二個例子。

語言如何劃為概率分布？方法非常簡單，甚至有點土。每門語言都有一張自己的單詞表，我們就以單詞表的長度L作為 $p_{i}$ 中i的取值個數。然後想方設法找一個這種語言的巨大語料庫，比如一個累計 $N$ 個單詞的語料庫。然後就一個一個統計每個單詞在語料庫中出現的次數，除以 $N$ 得到頻率。如果語料庫足夠大足夠全面，我們可以假定每個詞的頻率忠實的反應了這個詞在這門語言中對應的概率。

得到概率分布之後，算出來的信息熵對應的意義是：這門語言的單詞平均信息量。

這不是很有意思嘛~可以試著讓不同語言pk下。

灰色柱表示單字信息密度，條紋柱表示每秒音節數，虛線表示每秒傳遞的有效信息量（注意圖中信息密度是相對值，數值上不等於信息熵）。來源：《A cross-language perspective on speech information rate》

根據圖中的信息，七大語言除了日語以外的其它語言每秒傳遞的信息其實是差不多的。（大概某種程度上反應了人腦對語言信息的平均處理速率）但中文的單詞信息密度最高，中文可以優哉游哉慢條斯理地講話，每秒音節數最少。

一場樸實的愛國主義教育~

我們的第三個例子聊一下信息編碼。

人類使用的語言是隨著時間自然演化出來的，在形成的過程中並沒有做過任何嚴謹的編碼優化。中文的編碼長度是七種語言中最短的。但它肯定不是所有可能語言中最短的。它們的編碼長度肯定還有進一步壓縮的空間。那麼有趣的問題又來了~

如何求出編碼長度的理論最小值？以及怎麼編碼來逼近這一最小值？

回憶一下，在上一篇文章裡面我們提到過，對一個均勻概率分布，我們可以把概率 $p_{i}$ 中的每一個i看作集合中的一個元素。這個分布的信息熵是集合的元素個數取log: $S=log N$ 。

其實你仔細觀察並不難發現， $S$ 剛好等於對集合元素進行二進位編碼的理論最小長度。

比如一個8個元素的集合我們可以把每個元素用010， 001， 110......這樣的3位二進位數完全編碼。且3是最小的平均編碼長度。

PS：請不要耍小聰明說八進位下的編碼長度只需1。八進位的一位等價於二進位的三位。事實上最緊湊編碼方式並不依賴於是多少進位。將二進位下的最緊湊編碼轉換成八進位後肯定也是八進位下最緊湊的(通過一一對應關係易證)。又比如，中文單字多達上萬個，可以等價成一個上萬進位，不過在unicode編碼規範中，一個漢字等價於二進位16位。所以一個長度為m的中文句子等價於一個長度為16 * m的二進位句子。我們只需找到這個二進位句子在二進位下的最緊湊編碼即可。

對均勻分布，信息熵的值即最短編碼長度。對非均勻概率分布，這個結論還成立嗎？

我給大家劇透一下，成立的~

舉個例子，比如現在 i有4個取值，它們的 $p_{i}$ 分別是1/2, 1/4, 1/8, 1/8。那麼它們的信息熵算出來是1.75。它們分別用0，10，110，111來編碼。這樣它的平均編碼長度就是1x1/2 + 2x1/4 + 3x1/8 + 3x1/8 剛好等於 1.75。

這個編碼方式的具體規則是：

1，對每個取值i用長度 $l_i = lceil -log p_{i} ceil$ 的二進位串來編碼。（這個奇怪括弧是向上取整的意思，當 $p_{i}$ 不是2的冪次的時候，由於實際編碼中長度只能是整數，所以長度向上取整（如果向下取整會導致無法給所有的i沒有歧義的編碼），這時候算出來的平均編碼長度會略大於理論極限 $S$ 。實際平均編碼長度等於 $sum_i{p_i l_i}$ ）

2，保證二進位串頭部獨佔。頭部獨佔是指，比如第一個取值首位是0，那麼其它所有取值的首位就必須以1開頭。同樣只有一個取值前兩位是10，剩下的一律以11開頭。如此一來即使每個取值的編碼長度不一樣，但在斷句的時候並不會產生歧義。比如011010110111隻能是0/110/10/110/111。因為0這頭部獨佔，所以看到0肯定要斷句，其它同理。

可以證明，在不產生歧義的情況下，這樣的編碼方式是最短的。

詳細的證明

雖然有很多具體工程學實踐上的小track，但上面這個基本上就是我們常用的文件壓縮軟體的底層原理。

為了方便把上面討論的東西進一步推廣，我們定義一個跟編碼方式相關的概率分布 $q_{i}$ 。

定義 $q_{i}$ :比 $p_{i}$ 小的最大的2的冪次。例如 $p_{i}=frac{1}{5}$ ,那麼 $q_{i}=frac{1}{8}$ 。

如此，實際的平均編碼長度就可以寫成

$S^prime = -sum_{i} p_{i}log q_{i}$

你可以很容易看到它一定會比信息熵 $S=-sum_{i}{p_{i}log{p_{i}}}$ 大，畢竟實際平均編碼長度大於理論最小平均編碼長度，當且僅當 $q_{i} = p_{i}$ 時兩者相等。

這個量有一個專有名：交叉熵。所謂交叉的意義來自於：這是用一個概率分布 $q_{i}$ 的理論最小編碼方式來編碼另一個概率分布 $p_{i}$ 所得到的實際編碼長度。通常這兩個概率分布差異越大，交叉熵就離理論最小編碼長度越遠。

所以我們可以用它來定義不同概率分布之間的「距離」。這個「距離「叫做KL 散度：

$KL(p||q) = sum_{i}{p_{i}log{q_{i}}}-sum_{i}{p_{i}log{p_{i}}} \ = sum_{i}{p_{i}log{frac{q_{i}}{p_{i}}}}$

繼續往前走，你會發現在實際的更一般的問題中，我們可能會很難得到 $p_{i}$ 的具體值。比如如果你要把圖片映射成一個概率分布的時候。你會遇到這樣的問題，你發現圖片不像文字那樣有有限的最小組成單元，也就是單詞表。對圖片，你的第一個出發點只能是窮舉像素點的所有組合方式，然後去數像素點的各個組合方式出現的次數，得到頻率。思路和語言類似，但這其實是辦不到的。因為像素點的組合方式會隨著像素點的數目以指數形式增長。這意味著你需要去數的圖片張數也要指數多。這對傳統計算機來說根本辦不到。所以你真的很難很難得到圖片的 $p_{i}$ 。

退而求其次的辦法是用一個 $q_{i}$ 先假設成圖片的概率分布，然後用 $q_{i}$ 算KL散度，然後變分 $q_{i}$ 使得KL散度不停變小。如此 $q_i$ 就會越來越接近 $p_i$ 。注意在變分 $q_{i}$ 的時候，KL散度的第二項其實是一個常數。所以實際計算的時候，我們直接變分第一項，也就是直接變分交叉熵就可以了。所以你明白了么，為什麼那麼多機器學習演算法要用交叉熵作為損失函數。

慢著，不是說 $p_i$ 得不到嘛？可是交叉熵裡面不也有一項 $p_i$ 么？

對的，在用交叉熵作為損失函數的機器學習演算法中，事實上一定會有一樣東西，這個東西可能名字叫「label」什麼的，它事實上起了跟單詞表一樣的作用。

對於那些徹徹底底沒有單詞表的問題，比如說非監督的生成型學習。 $p_i$ 得不到，交叉熵的確是算不了的。這時候我們會將交叉熵進一步退化，祭出一個叫做負對數似然度（negative-loglikelihood, NLL）的量：

$L = - frac{1}{N}sum_i log q_i$

用它來做損失函數。

最後一個有趣的問題是：如果有一天我們的射電望遠鏡接收到一門外星語言。請問我們要怎麼區分這是一門有意義的外星語言，還是一隻外星大猩猩在臉滾鍵盤生成隨機字元串？

信息熵可以幫你做到這一點，但首先你得有個足夠大的外星語料庫，大到能夠求出 $p_i$ 。求出 $p_i$ 之後你就有了每個詞在這個語料中出現的概率。這時候我們額外做一件事，我們將原來的單詞表i分成兩部分j和k。我們統計兩個詞出現在同一個句子裡面的概率 $p_{jk}$ 。如果第j個詞和第k個詞完全獨立，那麼應該有 $p_{jk} = p_j*p_k$ 。如果第j個詞和第k個詞存在某種關聯，那麼它們出現在同一個句子裡面的聯合概率應該不是簡單相乘。比如說「程序」「報錯」這兩個詞在中文語料庫中概率都不算高，但一個句子中出現了「程序」，那這個句子接下來出現「報錯」的概率就會高好多好多。

我們認為一門有意義的語言應該包含大量關聯的辭彙，相反隨機樣本的辭彙就幾乎是獨立的。為了定量刻畫這種關聯的大小，我們定義互信息：

$I = sum_{jk} p_{jk}log p_{jk} - sum_{j} p_{j}log p_{j} -sum_{k} p_{k}log p_{k} \ =S(X) + S(Y) - S(X, Y)$

兩個概率分布的信息熵減去聯合概率分布的信息熵。這個差值是兩個系統共享的熵，也反映它們關聯的大小。當一個系統被確定，他們共享的熵也沒有了，另一個系統的熵會變成 $S(Y) - S(X, Y)$ 。當 $I$ 等於0，兩個系統沒有共享的熵，沒有關聯， $p_{jk} = p_j*p_k$ 。 $I$ 越大，表明詞與詞的關聯越強。

所以我們直接計算 $I$ ，如果顯著，表明這個語言大概率是有意義的。如果約等於0，那它肯定是隨機字元串。確定一門語言有意義之後，接下來我們可以用詞頻比較，語法分析來逐個確定每個字元對應的實際意義~

題外話：看了資訊理論之後再看三體，我發現要理解三體人的語言，首先三體人得跟你先叨逼叨個幾百萬句，形成一個大語料庫，然後你明白了，呀！原來第一句話的意思是「不要回答」呀~

宇宙真是寂寞如雪。