首页天道酬勤妙语浅谈(有没有比浅谈更好的词)

妙语浅谈(有没有比浅谈更好的词)

admin 12-01 00:32 342次浏览

想象一下,你的任务是设计一个通信系统来帮助联系空间站和地面指挥总部。系统将发送和接收二进制编码信息,即1和0的序列。在信息传播过程中,可能会受到其他无线电信号的干扰,使地面指挥接收到的信息与原始信息不完全相同。在这种情况下,有没有可能设计一个方案来实现可靠的通信?

一个简单的解决方案是增加冗余:每个比特被发送几次,比如说五次:

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

“这里似乎有一个困境:如果我们想要准确性,就必须降低传输速率。」

这是克劳德香农在1948年的论文《通信的数学理论》中解决的问题。在书中,他证明了在噪声信道上可靠传输的信息速率是有极限的(香农极限)。但是,在这个限制下,我用越来越小的错误来传递信息。这个重要的结果告诉我们,有一种编码可以在给定的信道上实现任意精度,但它没有告诉我们如何构建它。

更准确地说,假设信道正确发送比特的概率为P,错误发送比特的概率为1-P,香农证明了最佳传输速率为:

该图围绕p=0.5对称,最大值在p=0和p=1处。p=0的情况很有趣,当通道有完美噪声时:它只是反转原始信息中的所有位。但是如果我们知道了这一点,那么信息就很容易被破译,我们只需要把它们重新找回来。

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

我们可以看到,当p=1/2时,信息熵的值最大,H(p)=1。当p=0和p=1时,熵最小。

更一般地,给定一条随机信息m,该信息m可以取n个不同的值,对应于概率p,i=1,n,我们消息的熵定义为:

关于“猜猜我是谁”游戏的例子

让我们采取不同的方法。假设你在玩“猜猜我是谁?”(猜猜是谁?)

游戏规则很简单,具体玩法是:

每个玩家在游戏底部安装一套24张角色卡,并让角色卡立起来。从自己的人物牌中选择一个神秘人物(不要让对方看到),这个人物就是你的答案。从问年轻人的问题开始,或者猜测对方选择了哪个角色。这个问题的答案必须是“是”或“否”,“是”或“否”

例如,"你选的人物是男的吗?"或者"这个人有戴帽子吗?"。而回复必须诚实的。一旦猜错答案,就换对方来问问题或是猜答案。提问者通过一系列问题,逐步缩小猜测的角色范围,先猜对者胜出。

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

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

但如果你不能将角色按他们的特征进行平均分为 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个样本,都属于鸢尾xddhh的三个亚属,分别是山鸢尾、变色鸢尾和维吉尼亚鸢尾。四个特征被用作样本的定量分析,它们分别是花萼和花瓣的长度和宽度。基于这四个特征的集合,费雪发展了一个线性判别分析以确定其属种。

例如,考虑下图,在著名的安德森鸢尾花卉数据集上使用决策树方法并选择两个特征,花瓣宽度,首先设置阈值为 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 万的引用,很少有论文能有类似的影响力。用信息理论家 zjdxy Ephremides 的话来说:

信息理论就像一个地震,而且hldym还没有结束!


作者:[遇见数学翻译小组]核心成员 方正,寂寞的画笔同学

Java设计模式之原型模式怎么实现关闭通道等K8S之StatefulSet有状态服务详解Android中WebView截图的实现方式雷士灯具管理系统
事业单位申论(行测数量关系排列组合) 数据结构树叶的定义(数据结构图和树的区别)
相关内容