最近在学习算法的过程中频繁接触到信息论，有碍于自己的数学水平，无力窥其全貌。但仅仅是一个入门级的了解便足以让我为之倾倒。这篇文章简单介绍信息论，之后来看看如何利用它秒解一些智力题。

一.老鼠喝药问题

先来看看要解决的问题:

有 1000 个一模一样的瓶子，其中有 999 瓶是普通的水，有一瓶是毒药。你有一些小白鼠用来找出毒药，喝下毒药的老鼠将会在第二天死亡，最少需要多少只小白鼠才能保证在第二天找出哪一瓶是毒药？

你可以带着这个问题阅读接下来的文章，如果你善于思考，有可能在中途就已经得到答案。

二.信息的量化与信息熵(读音为shang,英文是entropy)

首先不要被这个标题所吓倒，它的概念非常的简洁。这里引用吴军博士在数学之美系列文章中所举的例子来介绍这个概念。

假设你错过了2014年的世界杯，你可以问一个知道比赛结果的观众，但他只回答是或否。你最多需要问多少个问题才能知道哪支球队是冠军？
你可以先对所有球队进行编号，先问“冠军球队在1-16号中吗？”如果他回答是，就继续问“冠军在1-8号中吗？”整个过程类似于二分查找，这样最多需要问5次就能得到结果。因此“谁是世界杯冠军”这条信息的信息量就是5比特(bit)，如果某一年有64支球队进入决赛阶段，那么你需要多问一次，此时该条信息的信息量变成6比特。至此你可以发现信息量的大小与所有可能情况的对数函数有关(log32=5，log64=6，注：本文所有对数以2为底)

懂球的读者会发现可能不需要5次就能猜出谁是冠军，因为像巴西，西班牙，意大利这样的球队夺冠的概率比某些亚洲国家要大，因此可以把少数几支夺冠热门球队分成一组，其它球队分成另一组，然后猜冠军球队是否在这几支热门球队中。重复这个过程。也许三次或者四次就能得到结果。因此当每支球队夺冠概率不等时，“谁是世界杯冠军”的信息量小于5比特。
香农在他著名的论文“通信的数学原理(A Mathematical Theory of Communication)”中指出，它准确的信息量应该通过如下方式计算：$$ H=-(p_1\log p_1+p_2\log p_2+\cdots +p_{32}\log p_{32}) $$其中$p_1,p_2,\ldots ,p_{32}$分别代表每支球队夺冠的概率，H则被香农定义为“信息熵”，它的单位是比特。这里使用“熵”这个字是因为它与热力学中的熵有一定联系，信息熵用于表示信源随机系统的不确定程度。而热力学的“熵”用于表示系统中无序(无法再利用)的能量。
如果以上看不懂也没关系，当所有球队夺冠概率相等时，p=1/32，以上公式可以简化成：$$H=-\log (\frac{1}{32})=5(bit)$$你可以将“谁是世界杯冠军”这条信息的信息量大小理解成它的不确定性，越是不确定的事件则需要越大的信息量来将它确定。比如说彩票双色球的中奖号码，我没买过彩票，有兴趣的读者可以自己计算一下。再比如有人告诉你明天太阳从东边出来(假设其概率为100%)。套用公式计算其信息量就是：$$H=-\log (1)=0(bit)$$于是我们严格的证明了它是一句废话。

三.条件熵(Conditional Entropy)与互信息(Mutual Information)

这进行这一节的叙述之前，先来了解一些数学知识，由于我大概只有初中毕业的数学水平，因此你应该有自信能够理解它们，如果你感觉到难以理解，很有可能是因为我的表达有问题，建议你继续在网上阅读一些其它的资料。

  • 条件概率分布(Conditional Probability)
    条件概率分布描述了已知第二个随机变量Y的前提下，X的概率分布，用P(x|y)表示。比如我用P(x)表示世界杯足球赛1号队伍夺冠的概率，P(y)表示冠军在1-16号队伍之间的概率，假设所有球队夺冠概率相等，可以得到P(x)=1/32，P(y)=1/2，P(x|y)=1/16。用语言描述就是1号队伍夺冠的概率为1/32，但是如果已知冠军在1-16号队伍之中，则1号队伍夺冠的概率变为1/16。
  • 联合概率分布(JointProbability))
    假设存在两个随机变量X和Y，则我们将X=x并且Y=y的概率称为联合概率分布，用P(x,y)表示。结合上面的概念可以得到：$$P(x,y)=P(x)\times P(y|x)=P(y)\times P(x|y)$$用语言来描述就是x,y两件事同时发生的概率等于x单独发生的概率乘以在已经发生x的前提下，y发生的概率。继续用上面的例子来看，可以得到：$$P(x,y)=P(y)\times P(x|y)=1/32$$即世界杯1号队伍夺冠(x)与冠军在1-16号之间(y)这两件事同时发生的概率为1/32(别忘了假设所有球队夺冠概率相等)。

如果理解了上面的数学概念，后面的内容就非常容易解释了，世界杯32支球队中谁是冠军的不确定性(信息量)是5bit，我们必须通过引入外部信息（即提问）来消除这个不确定性，提问的过程可以看做是降低它的不确定性的过程，但我们具体应该提什么样的问题呢？我们可以直接了当的问谁是冠军，当得到回答后事件的不确定性直接降为0，也可以问诸如“今天天气怎么样？”，“你吃过饭了吗？”之类的不相干的问题，得到回答后它的不确定性仍然是5bit。此时如何来量化我们提出的问题与事件本身的相关性？这就需要引入条件熵与互信息的概念。

  • 条件熵(Conditional Entropy)
    条件熵描述了在已知第二个随机变量Y的前提下，随机变量X的不确定性还剩多少，用H(X|Y)表示，计算公式为：$$H(X|Y)=-\sum_{x\in\mathcal X, y\in\mathcal Y}p(x,y)\log\,p(x|y)$$假如我们用X来表示“谁是世界杯冠军”，用Y来表示“世界杯冠军是否在1-16号球队之中”，那么综合我们学到的内容可以得到p(x)=1/32，p(y)=1/2，p(x,y)=1/32，p(x|y)=1/16。套用公式后得到H(X|Y)=4bit。这意味着假如我们知道了“世界杯冠军是否在1-16号球队之中”，那么“谁是世界杯冠军”这件事的不确定性就只剩4bit了。
  • 互信息(Mutual Information)
    互信息量化了两个随机变量之间的相关性，它的定义其实与条件熵很类似，它表示在已知第二个随机变量Y的前提下，随机变量X的不确定性应该减去多少。用I(X;Y)来表示。根据定义很容易得到：$$I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)$$同样用上面的例子。已知H(X)=5bit，H(X|Y)=4bit，因此I(X;Y)=1bit。这意味着“世界杯冠军是否在1-16号球队之中”与“谁是世界杯冠军”这两个问题之间的相关性是1bit，你可以自己计算一下“今天天气怎么样？”这个问题与“谁是世界杯冠军”的相关性。

如果你感觉已经理解了上面的内容，下面咱们不妨来做一个小测验，这是一道经典的智力题。

假设有27个小球，其中一个小球质量高于其它小球，你有一个天平，请问要找出质量较高的小球。最少需要称多少次？

我们可以用X代表“27个小球哪一个质量比其它小球大？”，用Y表示用天平进行一次称重，容易计算出X的信息量H(X)=log27(bit)，Y的信息量H(Y)=log3(bit)(称重的结果有大于，小于，等于)，因此互信息I(X;Y)的最大值也是log3，使用H(X)除以I(X;Y)可以得出理论上最少需要称量的次数，即log27/log3。依据对数的性质，该式等于$\log _327$，最少需要称3次。

四.信息论的应用场景

信息论目前广泛应用于物理学，统计学，密码学等领域，包括今天的整个移动通讯与互联网都是建立在它的理论基础之上的。然而对于以上领域我几乎一窍不通，下面列举一些它在码农领域的作用。

  • 数据压缩，编码，解码
    信息论直接决定了无损压缩的极限。假设你现在要将“谁是世界杯冠军”这条信息压缩并通过网络传输，那么它的极限是5bit。低于5bit则无法涵盖所有可能性(具体的传输方式是发送端与接受端先约定好编码规则，比如用00001表示巴西获胜，00010表示意大利获胜，根据二进制规则，5位二进制数最大能表达32种可能)。人类之间的沟通也可以看做是编码-传输-解码的过程，即我将我想表达的内容通过一种语言进行编码，使用一些媒体介质传输给听众，听众再通过相同的语言进行解码。好的作家往往具备高超的编码技巧，使用较少文字就能准确表达意图，带给读者身临其境的感觉，当然这同时也要求读者具有一定的解码技巧，否则数据在这次传输过程中就会失真。因此高压缩率的语言虽然便于传输与存储，但它的缺点是容易受到噪声干扰，编码与解码的运算量比较大，比如说文言文。
  • 弱人工智能
    这里我暂且把基于概率与统计而形成的人工智能称为弱人工智能，比如说机器翻译，其实机器并不能理解它所翻译的内容，它是一个根据海量的数据模型与上下文相关词汇来降低语义的不确定性的过程。比如说football，计算机可以选择将它翻译成足球或者橄榄球，但如果在上下文中带有Maradona(马拉多纳)，则大大降低了这个不确定性。（计算机又是如何认识Maradona的呢？它先从大量文本中找出与足球一起出现的互信息较高的词。更详细的内容还是推荐阅读《数学之美》）。类似的领域还有语音识别，聊天机器人，搜索引擎关键字分析等等。
  • 算法分析
    在聊聊4种主流排序算法这篇文章中曾经提到如何证明基于比较的排序算法复杂度不可能优于$\theta(NlogN)$。证明过程使用了二叉决策树，而使用信息论的证明更加简洁明了，一个大小为N，所有元素都不相等的数组，其信息量为log(N!)，而每一次比较的互信息是1bit，因此至少需要log(N!)(约等于NlogN)次比较。如果你也是码农的话，这方面应用场景应该也不用我多做解释了。我也正是因为在学习算法的过程中才开始了解信息论的。

如果以上还不足以说服你，或者说你对上面这些领域都不感冒，我再说一个你可能感兴趣的。
上世纪90年代初，改进最大熵模型训练算法的Della Pietra兄弟退出学术届，和一些当时在IBM做语言识别的同事一起加入詹姆斯·西蒙斯领导的文艺复兴公司(Renaissance Technologies Corp.)。利用最大熵模型和一些其它数学理论对股票进行预测。1988-2008二十年里，该公司的大奖章(Medallion)对冲基金年均回报率高达34%，文艺复兴公司现在也成了世界上最成功的对冲基金公司。

五.正确姿势

回到我们要解决的问题，1000个瓶子中哪一瓶是毒药的信息量是log1000，向上取整得到10bit，一支老鼠的生死正好能表示1bit。最终得出答案10支老鼠。具体的操作流程在知乎：老鼠喝药问题中已经有无数大神进行解答了，本文也就不再赘述。
最后再说一些题外话，这个问题最开始是在与同事聊天过程中被问到的，我经过一晚上的冥思苦想，最终没能得到答案，第二天同事在告知正确解法后随口又问了一句：“假设把时限放宽到两天，那么至少需要多少支老鼠？”于是又是一晚上的冥思苦想……
智商上的缺陷常常需要后天努力来弥补，在学习了信息论之后，类似的问题无论如何变化，都很容易套用公式计算出理论最优解。

参考链接：