想像一下你的任務是去設計一個幫助聯絡太空站和地面指揮總部的通信系統。該系統將發送和接收二進位編碼的信息，也就是說 1 和 0 的序列。在信息傳播的過程中，有可能會受到其他無線電信號的幹擾，以至於地面指揮部所收到的信息與原始信息並不完全相同。在這種情況下，有沒有可能設計出一種方案來實現可靠的通信呢？
一個簡單的解決方案是增加冗餘：每個比特發送若干次，比如說 5 次：
如果地面控制中心收到 11101 的信息，他們就可以相當確定發出的是 11111。雖然這個簡單的系統可以起作用(在一定程度上)，但我們可以看到它是非常浪費的:我們必須對原始信息中的每一個比特發送 4 個額外的比特。因此，實際傳播率只有 20%。我們還能做得更好嗎？
「這裡似乎有一個困境：如果我們想要精確，我們必須降低傳輸速率。」
這就是克勞德·香農在他 1948 年的論文《通信的數學理論》中解決的問題。在書中，他證明了在噪聲信道上進行可靠傳輸的信息速率是存在有一個極限的(香農極限)。然而，在這個限度之下，我是用越來越小的誤差來傳輸信息。這個重要的結果告訴我們存在一種編碼，它允許在給定的信道上實現任意精度，但它沒有告訴我們如何構建它。
更準確地說，假設信道正確發送一個比特的概率為 p，相應錯誤發送一個比特的概率為 1 - p， Shannon 證明了最優傳輸速率為:
該圖形圍繞 p = 0.5 對稱，最大值在 p = 0 和 p = 1 處。p = 0 的情況很有趣，這時候信道有完美的噪聲：它剛好將原始信息中的所有比特取反。但如果我們知道了這一點，那麼信息就很容易被破譯了，我們只要把它們再取反回來就行了。
這個公式通常用「信息熵(information entropy)」來表述，這是香農設計的一種度量，可以被解釋為與信道的「不確定性」或「驚奇」的水平。
我們可以看到，當 p = 1/2 時，信息熵的值最大， H(p)=1。而當 p = 0 和 p = 1 時，熵最小。
更普遍的是，給定一個隨機信息 M， 這個信息 M 可以採取 n 種不同的值，對應概率 p ，i = 1，…， n，我們消息的熵定義為:
關於「猜猜我是誰」遊戲的例子
讓我們採取不同的方法。假設你正在玩「猜猜我是誰？」(Guess Who？)
遊戲的規則很簡單，具體玩法：
玩家各將一組24人物卡裝在遊戲底板上，並讓人物卡都站立。從自己的人物卡中各抽一名神秘人物（不要對方看到〕，此人物為自己的答案謎底。由年齡較小的人開始問對方問題，或來猜測對方到底所選取的哪個人物。問題的回答必須是"是"或"不是"、"有"或"沒有"。例如，"你選的人物是男的嗎？"或者"這個人有戴帽子嗎？"。而回復必須誠實的。一旦猜錯答案，就換對方來問問題或是猜答案。提問者通過一系列問題，逐步縮小猜測的角色範圍，先猜對者勝出。如果想要玩轉這個小遊戲，就應該問自己：我應該按什麼順序提問才能最大限度地提高獲勝機率？直覺而言，似乎首先要問的是大多數角色所擁有的特徵，是這樣嗎？
《猜猜誰》的硬核玩家實際上是要用資訊理論的方法才能獲得更佳成績。如果作為猜測者一方，所要提出好問題最好是能將餘下角色一分為二的問題，也就是說，不管答案是「是」還是「否」，都要能將一半的角色丟棄。這樣也就能通過該問題獲得最佳的信息量。
但如果你不能將角色按他們的特徵進行平均分為 2 組呢？為了回答這個問題，我們首先回顧一下熵的概念。我們可以把一個問題作為一個變量 X。這個變量有 p 的概率可以將人群分為團體 x。例如，考慮一個關於角色眼睛顏色的問題：選擇人物的眼睛是否是藍色？考慮到這一點，問題的熵就變成:
直覺告訴我們， 對於每一個可能的答案， 我們會獲得一定的信息量 log p (x)， 這意味著如果我們得到答案發生該事件概率實際上相當低的話(即我們問這個角色有沒有一個很少見的特徵，並且答案是 yes 的話)，那麼獲得的信息量就要比發生高概率的情況下更大。
另一方面，熵與不確定性有關。例如，如果我們擲硬幣，p = 0.5 時結果的不確定性比 p 的任何其他值都要高。在我們的例子中，不確定性越大越好。為什麼？ 如果我們選擇一個無法使人口分布均勻的問題， 假設分布為 0.7 和 0.3， 很可能我們的角色是在 70%的角色中， 丟棄剩下 30%的回答 no 的團體，但隨著更平均的分布(因此不確定性更高)，我們總是傾向於放棄 50%的人口，這從全局而言是更優選擇。也就意味著最好的問題是那些能最大化熵，即不確定性較高的問題。
決策樹(Decision Trees)
熵的一個常見用途是在決策樹中，決策樹的工作原理也與"猜猜我是誰"類似，通過使用一組特徵(將數據分割成不相交集合的特徵)來為分類問題構建決策流程圖（決策樹）。
一般的，一棵決策樹包含一個根節點、若干個內部結點和若干葉子結點。葉子結點對應於決策結果，其他結點則對應於一個特徵的測試。根結點包含所有樣本，每個結點包含的樣本集合根據特徵測試的結果被劃分到子結點中。從根結點到葉子結點的路徑對應了一個決策的測試序列。例如，下圖是挑西瓜的決策樹。
▲ 上圖自周志華老師. 機器學習 [M]. 清華大學出版社, 2016. 73~79
在這裡，一個常見的問題是：我們怎樣找到發揮決定性作用的特徵，並按照什麼順序「應用」這些特徵才能更好地劃分數據？ 一種可能的解決方案是始終遞歸地使用最大化信息增益的特性。假設我們處理的數據集為 S ，我們選取的特徵為 X ，那麼在 S 上應用特徵 X 所獲得的信息增益為 I(S,X) （ I(S,X) 也稱為S與X的互信息），計算如下:
其中 H(S|X) 是給定 X 的情況下 S 的條件熵。直觀地，I(S,X) 就是我們知道特徵 X 的取值後數據集 S 熵的減少量。因此，選擇 X 的特性使這個值最大化是有意義的，因為他們將最大程度地減少不確定性，有效地獲取最佳的數據集劃分。
考慮每個節點上的信息增益來選擇下一個特徵的算法被稱為貪婪算法。這些算法並沒有考慮到總體信息增益，可能會導致一些情況下的次優查詢，但它們表現良好，而且有一個簡單的實現方法。
安德森鳶尾花卉數據集，也稱鳶尾花卉數據集，是一類多重變量分析的數據集。它最初是埃德加·安德森從加拿大加斯帕半島上的鳶尾屬花朵中提取的形態學變異數據，後由羅納德·費雪作為判別分析的一個例子，運用到統計學中。其數據集包含了150個樣本，都屬於鳶尾屬下的三個亞屬，分別是山鳶尾、變色鳶尾和維吉尼亞鳶尾。四個特徵被用作樣本的定量分析，它們分別是花萼和花瓣的長度和寬度。基於這四個特徵的集合，費雪發展了一個線性判別分析以確定其屬種。
例如，考慮下圖，在著名的安德森鳶尾花卉數據集上使用決策樹方法並選擇兩個特徵，花瓣寬度，首先設置閾值為 0.8 cm ，然後是 1.75 釐米。先不考慮這些特定的特性是怎麼選擇的，我們先思考為什麼要先使用 ≤0.8 ？通過計算上文所述的信息增益，我們可以找到答案。我們將以花瓣寬度 0.8 釐米為閾值的特徵稱為 X，另一個為 Y。
註：圖中使用的Gini係數與互信息類似，也是信息增益的度量，下文我們將用互信息作為信息增益的度量進行對決策樹的進一步說明。
首先應用特徵 X 劃分 150 個數據點(通常訓練集和測試集是分開的，在這裡為了簡單我們使用整個集合)為兩組: 一個包含整個山鳶尾類 (50 個點，對應於花瓣寬度≤0.8 cm)， 另一個包含其餘部分。在這種情況下，計算收益:
另一方面，若先使用特徵 Y 劃分數據點，得到的兩組： 花瓣寬度≤1.75 cm組有50 個山鳶尾， 49 個變色鳶尾和 5 個維吉尼亞鳶尾；另一組沒有 山鳶尾， 1 個變色鳶尾和 45 個維吉尼亞鳶尾。這給我們帶來的收益為:
因此，從 X(花瓣寬度小於或大於 0.8 cm)獲得的信息增益大於從 Y 獲得的信息增益，我們應該首先使用特徵X。這從直觀上想是有道理的，因為先 X 可以完全將 山鳶尾類從其他兩個類中分離出來，而首先使用 Y 則會帶來更複雜的劃分。
總結
香農的工作之重要性再怎麼強調都不為過：信息理論在不同的領域有著廣泛的應用，如統計推斷和機器學習、自然語言處理、遺傳學、數據壓縮、編碼理論和密碼學。這篇《通信的數學原理》有超過 12 萬的引用，很少有論文能有類似的影響力。用信息理論家 Anthony Ephremides 的話來說: 信息理論就像一個地震，而且餘震遠還沒有結束!
作者：[遇見數學翻譯小組]核心成員 方正，小倪同學