编程算法-信息熵的理解

昨天的文章提到了信息的概念。今天我就写一篇关于算法中对信息的考虑——信息熵的文章。

信息是一个非常抽象的概念。人们常说信息量大，或者信息量少，但很难说清楚到底有多少信息量。比如一个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)的算法，但是快速排序一般比堆排序快，因为堆排序得到的平均信息比快速排序得到的低。

以上，我们根本没有提到具体的算法，即使时间复杂度最优。现实生活中很多时候，虽然没有想到具体的策略，但至少可以知道极限在哪里，是否有提升的空间。任何对数字进行排序和猜测的算法，都可以理解为通过获取信息来降低原有的熵。

总之，我们的考虑是在我们的编程过程中，让每一个可能的结果都有相同的概率，这样我们的算法才是相对最好的。

欢迎大家提问交流。共同进步。