略论信息论之美

通信的基本问题是在一个点上精确地或近似地复制在另一个点上选择的消息。-克劳德·香农(Claude Shannon)，1948年。

想象一下，你的任务是在空间站和地球上的地面控制总部之间设计一个通信系统。该系统将发送和接收二进制编码的消息，即，作为1和0的序列。在信息传输过程中，可能会受到其他无线电信号的干扰，因此在地面控制中接收到的信息与原始信息并不完全相同。在这种情况下，有没有可能设计出一个可靠的通信方案呢？

一个简单的解决方法是添加冗余：将每个比特发送几次，比如5次：

如果地面控制收到消息11101，他们可以相当确定真正发送的是11111。虽然这个简单的系统可以工作(在一定程度上)，但我们可以看到它是非常浪费的：我们必须为原始消息中的每一位发送4个额外的位。因此，传输率只有20%。我们还能做得更好吗？

这里似乎有一个两难境地：如果我们想要准确，我们必须降低传播率。

这就是克劳德·香农在他1948年的论文“通信的数学理论”中解决的问题。在书中，他证明了在嘈杂的信道上可以可靠传输的信息速率是有极限的(香农极限)。然而，低于此限制，我们可以以越来越小的错误传输信息。这个重要的结果告诉我们，在给定的通信信道上存在允许任意精度的代码，但是它没有告诉我们如何构建它。

更准确地说，假设信道具有正确发送比特的概率p和相应的发送错误比特的概率1-p，香农证明了最佳传输速率为：

曲线图在p=0.5附近对称，最大值在p=0和p=1。p=0的情况很有趣，通道有完美的噪声：它翻转了原始消息中的所有比特。但如果我们知道了这一点，那么信息就会被简单地破译，我们就会把它们翻回来。

这个公式通常用信息熵来表示，信息熵是香农设计的一种衡量标准，可以解释为与频道相关的“不确定性”或“惊喜”程度。

我们可以看到，当p=1/2时，熵在1处有一个最大值，当p=0和p=1时，熵在0处有一个最小值。

更一般地，给定可以取n个不同值的随机消息M，概率为pᵢ，i=1，…。，n，我们将消息的熵定义为：

让我们采取一种不同的方法。假设你在玩Guess Who，在这个游戏中，你问是/不是关于你对手角色外观的问题，以便在一组角色中挑出他或她。你问自己：我应该按什么顺序提问才能最大限度地增加获胜的可能性？即兴地，你可以试着先问一下大多数角色都有哪些特征。

此外，最优问题是将总体平均分配的问题，也就是说，无论答案(是或否)如何，都会丢弃一半的字符。在任何其他情况下，每个问题都不能获得最佳信息量。

但是，如果你不能根据角色的特征平均划分角色怎么办？为了回答这个问题，我们首先回顾一下上面定义的熵的概念。我们可以把一个问题想象成一个变量X，它把人口分成几组，x，ᵢ，概率为p，ᵢ。例如，想一个关于角色眼睛颜色的问题(游戏中的问题在技术上只有是或否，但这是可以概括的)。记住这一点，问题的熵就变成了：

这里的直觉是，对于每个可能的答案，我们获得了信息量-logp(xᵢ)，这意味着如果我们以非常低的概率收到答案(即，我们询问角色是否具有极少数人共享的特征，而答案是肯定的)，我们获得的信息量就会高于概率更高的答案。

另一方面，熵与不确定性有关。例如，如果我们抛硬币，当p=0.5时，结果中的不确定性比p的任何其他值都高。在我们的情况下，不确定性越大越好。为什么？如果我们选择一个在人口中分布不均匀的问题，假设是0.7和0.3，那么我们的性格很有可能是在70%的人中，只有剩下的30%的人没有回答，但如果划分得更均匀(因此也更不确定)，我们总是倾向于放弃50%的人口，从而产生长期的优势。这意味着最好的问题是那些使熵最大化的问题，也就是那些不确定性更高的问题。

熵的一种常见用法是在决策树中，在决策树中，人们使用一组特征(将数据分割成不相交的集合的特征)来构建分类问题的流程图。这里，一个常见的问题是：我们应该按什么顺序“应用”这些功能才能获得最佳拆分？一种可能的解决方案是递归地始终使用最大化信息增益的功能。如果我们使用的是数据集S，并且我们的要素名为X，则X在S上获得的信息i(S，X)计算如下：

其中H(S|X)是给定X的S的条件熵。直观地说，如果我们知道X，这就是数据集S的熵的减少。因此，选择使该值最大化的特征X是有意义的，因为它们将最大限度地减少不确定性，有效地获得最佳分裂。

考虑每个节点的信息增益来选择下一个特征的算法称为贪婪算法。这类算法没有考虑总体信息增益，在某些情况下可能会导致次优查询，但它们行为良好，方法简单。

例如，考虑下图，其中对著名的鸢尾花数据集使用了决策树方法，并选择了两个特征，即花瓣宽度，首先以0.8 cm作为阈值，然后是1.75 cm。撇开这些特定功能的选择方式不谈，为什么要先使用≤0.8呢？通过我们描述的信息增益计算，我们可以提供答案。我们将把分隔0.8 cm X和Y的花瓣宽度的特征称为Y。

应用X首先将150个数据点(通常一个会在训练和测试集之间拆分，为了简单起见，我们使用整个集)分成两个集：一个包含整个setosa类(50点，对应于≤0.8 cm)，不包含其他任何内容，而另一个包含其余部分。在这种情况下，计算结果为：

另一种是先施Y，一套有刚毛50株，杂色49株，处女株5株(≤1.75 cm)，另一株无刚毛，杂色1株，处女株45株。这就给我们留下了：

因此，X(花瓣宽度小于或大于0.8 cm)的信息增益大于Y的信息增益，我们应该首先使用它。这在直觉上是有道理的，因为X将setosa类与其他两个完全分开，而首先使用Y则会产生更纠结的分裂。

很难夸大香农工作的重要性：信息论在统计推理和机器学习、自然语言处理、遗传学、数据压缩、编码理论和密码学等领域都有很多应用。由于被引用超过12万次，很少有论文能号称具有类似的影响。用信息理论家安东尼·埃弗莱米德斯(Anthony Ephremides)的话说：