昨天的文章提到了信息的概念。今天我就寫一篇關于算法中對信息的考慮——信息熵的文章。

信息是一個非常抽象的概念。人們常說信息量大，或者信息量少，但很難說清楚到底有多少信息量。比如一個50萬字的中文文檔有多少信息量？直到1948年香農提出了“信息熵”的概念，才解決了信息的定量測量問題。

一條信息的信息量與其不確定性直接相關。例如，如果我們想找出一個非常非常不確定的東西，或者我們一無所知的東西，我們需要知道很多信息。相反，如果我們已經對某件事有了更多的了解，我們就不需要太多的信息來把它說清楚。因此，從這個角度來看，我們可以認為信息的度量等于不確定性。

香農計算信息熵的公式如下(本文中對數始終為2):

H (x) =-∑ p(xi) log (p (xi)) (i = 1，2，...n)(其中p (x)是X事件的概率)以位為單位。

數學的馬來西亞Miri，通過賽后如何知道32支隊伍中誰是冠軍來解釋信息熵的概念。在概率相等的情況下，對每次查詢使用對半搜索的原則(例如“冠軍隊在1-16嗎？”)你可以把隊伍減少一半，所以要五次才能知道結果。這是log32=5。而用信息熵來計算信息量確實是5。但是為什么信息熵的公式代表信息量呢？

據我所知，1/p(x)代表等概率情況下當時所有可能的量，在團隊的情況下，是32種可能。

在等概率的情況下，由于∑p(xi)=1，信息熵可視為:

信息熵h (x) =-∑ p (xi) log (p (xi)) (i = 1，2...n)=-log(p(I))=-(-log(1/p(x))= log(1/p(x))

也就是說，等概率事件中的信息量可以視為:

H(x)=log(所有可能性)

為了加深我們對信息量定義的理解，回到上面32隊的問題，我們已經知道他的信息量是5Bit。

問一次就能知道冠軍在哪個16隊，也就是說我們得到1bit的信息后，不確定性降低，也就是說信息熵變成了log16=4bit=5bit-1bit。

最大熵模型呢？它的原則是保留所有的不確定性，把風險降到最低。

最大熵原理指出，當我們需要預測一個隨機事件的概率分布時，我們的預測應該滿足所有已知的條件，不應該對未知做任何主觀的假設。重要的是不要主觀臆斷。在這種情況下，概率分布最均勻，預測的風險最小。因為此時概率分布的信息熵最大，所以人們把這種模型稱為“最大熵模型”。

我們常說的“不要把所有的雞蛋放在一個籃子里”其實是最大熵原理的簡單表述，因為當我們遇到不確定性的時候，我們要保留所有的可能性。

也就是說，在發現不確定信息時，不要對不確定產品做任何主觀假設，使其概率分布均勻，才能得到最客觀的結果。這個時候風險會最小，我們可以利用這個結果做出最客觀的決定。數學上是最優下界。

這個策略的精髓可以概括為“讓未知的世界乘虛而入”。它沒有“弱點”，答案的任何一個分支都是同樣可能的。反過來，一旦一個分支包含了更多的可能性，當情況落到那個分支上時，你就會抑郁。二分搜索法之所以好，是因為它每次排除一半的可能性，無論如何也能排除一半(在最壞的情況下是最好的)。

我用算法的時間復雜度來解釋一下最大熵原理。幾種主流算法對N個數據排序的時間復雜度基本是從O(nlogn)到O(n2)。一般來說，為什么O(nlogn)是最優的(據透露，快速排序的平均時間復雜度為O(nlogn))，因為N個數據的序列是隨機的，我們可以把它看成是等不確定性的，所以利用最大熵原理可以得到最優(最穩定)的結果。那么信息熵就是:

H(x)=log(所有可能性)=log(n！)而n-00是log(n！)近似lognn=nlogn

假設我們一次可以得到1bit的數據，那么我們至少需要得到(nlogn)bit的數據才能消除信息的不確定性，也就是說我們要比較nlogn次。但是由于各種排序算法的策略不同，我們不可能每次都得到1bit的數據，所以根據信息熵的定義，這是理論上最好的結果。最好的排序算法是一次得到1位數據，越接近1越有效。

雖然快速排序和堆排序都是時間復雜度為O(nlogn)的算法，但是快速排序一般比堆排序快，因為堆排序得到的平均信息比快速排序得到的低。

以上，我們根本沒有提到具體的算法，即使時間復雜度最優?，F實生活中很多時候，雖然沒有想到具體的策略，但至少可以知道極限在哪里，是否有提升的空間。任何對數字進行排序和猜測的算法，都可以理解為通過獲取信息來降低原有的熵。

總之，我們的考慮是在我們的編程過程中，讓每一個可能的結果都有相同的概率，這樣我們的算法才是相對最好的。

歡迎大家提問交流。共同進步。