如何实现可靠的通信？怎样做出更好的决策？浅谈信息论之美

想象一下你的任务是去设计一个帮助联络太空站和地面指挥总部的通信系统。该系统将发送和接收二进制编码的信息，也就是说 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？)

游戏的规则很简单，具体玩法：

1. 玩家各將一组24人物卡在游戏底板上，并让人物卡都站立。

2. 裝

3. 从自己的人物卡中各抽一名神秘人物（不要对方看到〕，此人物为自己的答案谜底。

4. 由年龄较小的人开始问对方问题，或来猜测对方到底所选取的哪个人物。

5. 问题的回答必须是"是"或"不是"、"有"或"没有"。例如，"你选的人物是男的吗？"或者"这个人有戴帽子吗？"。而回复必须诚实的。

6. 一旦猜错答案，就换对方来问问题或是猜答案。

7. 提问者通过一系列问题，逐步缩小猜测的角色范围，先猜对者胜出。

如果想要玩转这个小游戏，就应该问自己：我应该按什么顺序提问才能最大限度地提高获胜几率？直觉而言，似乎首先要问的是大多数角色所拥有的特征，是这样吗？

《猜猜谁》的硬核玩家实际上是要用信息论的方法才能获得更佳成绩。如果作为猜测者一方，所要提出好问题最好是能将余下角色一分为二的问题，也就是说，不管答案是“是”还是“否”，都要能将一半的角色丢弃。这样也就能通过该问题获得最佳的信息量。

但如果你不能将角色按他们的特征进行平均分为 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 的话来说：“信息理论就像一个地震，而且余震远还没有结束！”

作者：[遇见数学翻译小组]核心成员 方正，小倪同学