關于“熵”的那些事

第一次見到機器學習中的“熵”還是在決策樹分類當中，熵用于衡量如何做最佳劃分。大家可能都知道，熵嘛，就是 -p*logp 咯，那麼熵有什麼含義，為什麼它能夠展現資訊量，資訊增益又是怎麼一回事，我們一起來學習。

熵這個概念在上中學的時候大家都學過，在熱力學當中用于描述一個系統的混亂程度，其實在機器學習領域當中兩者很相似，用于描述資訊的不确定性，而一條資訊的不确定性就決定了這條資訊所包含的資訊量。一句話當中包含了多少資訊，看起來是一件相當抽象的事。直覺上感覺就是，對于一件越不确定的事，我們所需要知道的資訊量就越大，如果一件事我們幾乎可以确定它的發生，那麼就不再需要什麼資訊量去做判斷。

在《數學之美》這本書當中（強行安利這本書），作者舉了這樣一個例子，假設我們沒有看世界杯的比賽，但是想知道哪支球隊會是冠軍，隻能去問已經看過比賽的觀衆，但是我們隻能猜測，然後觀衆用對或不對來回答，我們想要猜測次數盡可能少，方法大家應該都能想到，那就是二分法。假如有 16 支球隊，分别編号，先問是否在 1-8 之間，如果是就繼續問是否在 1-4 之間，以此類推，直到最後判斷出冠軍球隊是哪隻。如果球隊數量是 16，我們需要問 4 次來得到最後的答案。那麼世界冠軍這條消息的資訊量就是 4。在計算機中，這條資訊的資訊量就是 4 比特，如果一共是 32 支球隊參賽，那麼世界冠軍的資訊量就是 5 比特，可以看到資訊量跟可能情況的對數 log （本文所有對數預設以 2 為底）有關（這裡大概有點知道為什麼求熵的公式裡會有一個 log 了）。

但是以往經驗表示，如果世界杯有 32 支球隊參賽，有些球隊實力很強，拿到冠軍的可能性更大，而有些隊伍拿冠軍的機率就很小。我們在之前用二分法計算的時候其實是看做每個球隊奪冠的機率都相等，是以我們從最可能奪冠的幾支球隊中猜測冠軍球隊，實際需要的資訊量是小于我們之前方法計算的資訊量的。

而準确的資訊量應該是：H = -（p1 * logp1 + p2 * logp2 + … + p32 * logp32）

p1, …, p32 分别是這 32 支球隊奪冠的機率。我們再回頭驗算一下，當每支球隊奪冠機率相等都是 1/32 的時候，H = -（32 * 1/32 * log1/32） = 5，這裡有個最大熵原理，每個事件機率相同時，熵最大。

這裡我們隻是說了如何計算熵，也做了一點簡單的驗證，那麼為什麼求總資訊量就是所有 -p*logp 再求和呢？

因為實際上，一個事件總的資訊量就是每一種可能的情況的資訊量乘以它們發生的機率，其實就是随機變量的資訊量的數學期望。

說完資訊熵，現在可以來說說資訊增益了。可以回頭再從決策樹這裡說起。

決策樹想必大家都有了解，簡單說就是 if…then…。建構一棵決策樹的關鍵就是如何選擇結點的屬性，一種度量方法就是計算父結點和根據某個屬性劃分的子節點的熵，取內插補點，其熵相差越大越好（資訊增益越大越好）。

整理一下思路：我們建決策樹的目标是什麼——是使得一個結點中的資料盡可能屬于同個類别，直到最後葉結點隻包含一個類别的樣本。用書裡的話來說就是“純度”提升越高越好。我們知道，純度高就代表兩種情況（以二進制屬性為例 yes or no）當中，其中一種情況的機率盡可能大，盡可能偏向一邊，自然也就是子結點的熵盡可能小。是以當從一個父結點根據不同屬性再分出多個子結點的時候，用父結點的熵減去所有子結點的熵之和，選最大的那個屬性用于下一步的劃分就可以了。

從決策樹的根結點向下，每個結點都在減少不确定性，直到最後得到唯一的類别。

資訊的作用就是幫助我們減少不确定性，我們逐漸了解更多資訊，對一件事就越肯定。

我曾經分享過這樣一篇文章《網際網路時代的社會語言學：基于SNS的文本資料挖掘》，其中提到了一種不借助詞庫來分詞的算法，基于的方法就是資訊熵。我沒有原作者說的好，這裡直接引用一部分：

在人人網使用者狀态中，“被子”一詞一共出現了 956 次，“輩子”一詞一共出現了 2330 次，兩者的右鄰字集合的資訊熵分别為 3.87404 和 4.11644 ，數值上非常接近。但“被子”的左鄰字用例非常豐富：用得最多的是“曬被子”，它一共出現了 162 次；其次是“的被子”，出現了 85 次；接下來分别是“條被子”、“在被子”、“床被子”，分别出現了 69 次、 64 次和 52 次；當然，還有“疊被子”、“蓋被子”、“加被子”、“新被子”、“掀被子”、“收被子”、“薄被子”、“踢被子”、“搶被子”等 100 多種不同的用法構成的長尾⋯⋯所有左鄰字的資訊熵為 3.67453 。但“輩子”的左鄰字就很可憐了， 2330 個“輩子”中有 1276 個是“一輩子”，有 596 個“這輩子”，有 235 個“下輩子”，有 149 個“上輩子”，有 32 個“半輩子”，有 10 個“八輩子”，有 7 個“幾輩子”，有 6 個“哪輩子”，以及“n 輩子”、“兩輩子”等 13 種更罕見的用法。所有左鄰字的資訊熵僅為 1.25963 。因而，“輩子”能否成詞，明顯就有争議了。“下子”則是更典型的例子， 310 個“下子”的用例中有 294 個出自“一下子”， 5 個出自“兩下子”， 5 個出自“這下子”，其餘的都是隻出現過一次的罕見用法。事實上，“下子”的左鄰字資訊熵僅為 0.294421 ，我們不應該把它看作一個能靈活運用的詞。當然，一些文本片段的左鄰字沒啥問題，右鄰字用例卻非常貧乏，例如“交響”、“後遺”、“鵝卵”等，把它們看作單獨的詞似乎也不太合适。我們不妨就把一個文本片段的自由運用程度定義為它的左鄰字資訊熵和右鄰字資訊熵中的較小值。

看，根據一個字/詞左右鄰字的資訊熵就能判斷該字/詞是應該跟左右字連成一個詞還是單獨成詞。很巧妙，反正第一次讀的時候着實被驚豔了一下。

關于熵的介紹差不多就到這裡了，當然我們需要了解的遠不止這些，我隻是給了很直覺的概念，更多的比如嚴格的數學推導、互資訊、相對熵等等都很值得認真學習，畢竟資訊論是相當大的一部分。路漫漫其修遠兮，共勉。

參考資料：

《數學之美》

《資料挖掘導論》

《機器學習》

《網際網路時代的社會語言學：基于SNS的文本資料挖掘》

https://zh.wikipedia.org/wiki/%E4%BA%92%E4%BF%A1%E6%81%AF

https://zh.wikipedia.org/wiki/%E7%86%B5_(%E4%BF%A1%E6%81%AF%E8%AE%BA