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

翻译: 方正, 校对: 小倪同学(中国科学院大学 本科生)
英文: https://sourl.cn/uts8ga

想象一下你的任务是去设计一个帮助联络太空站和地面指挥总部的通信系统。该系统将发送和接收二进制编码的信息,也就是说 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. 提问者通过一系列问题,逐步缩小猜测的角色范围,先猜对者胜出。

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

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

但如果你不能将角色按他们的特征进行平均分为 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 的话来说:

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

(0)

相关推荐

  • 数据分析入门系列教程-决策树原理

    今天我们一起来学习决策树,那么什么是决策树呢,其实在生活中,我们无时无刻不在使用它. 比如现在有朋友给海伦介绍约会对象,她会做如下的判断: 海伦:小伙儿帅嘛? 朋友:很帅 海伦:身高多少? 朋友:17 ...

  • 看这位跨界的天才,如何为我们描绘未来

    中科院物理所 中科院物理所官方账号.爱上物理,改变世界.1小时前 有了这位孤独的天才的突破性工作,如今的信息时代才成为了可能 01 香农其人 科学寻求自然的基本定律,数学则在旧基础上构造新的定理,而工 ...

  • 克劳德·香农:看我如何发明未来

    [导读]克劳德·艾尔伍德·香农,美国数学家.电子工程师和密码学家,被誉为信息论的创始人.他发表了划时代的论文--通信的数学原理,奠定了现代信息论的基础.不仅如此,香农还被认为是数字计算机理论和数字电路 ...

  • 【信息伦之父】香农:喜欢杂耍的天才,如何量化了信息呢?

    Part 01:香农:天才的童年很平凡 Part 02:香农的双学位:数学与机械 Part 03:机器可以拥有逻辑吗? Part 04:香农与布尔代数 Part 05:香农在贝尔实验室 Part 06 ...

  • 如何用决策树模型做数据分析?

    一 什么是决策树? 决策树模型本质是一颗由多个判断节点组成的树.在树的每个节点做参数判断,进而在树的最末枝(叶结点)能够对所关心变量的取值作出最佳判断.通常,一棵决策树包含一个根结点,若干内部节点和若 ...

  • (数据科学学习手札26)随机森林分类器原理详解&Python与R实现

    转自 博客园 一.简介 作为集成学习中非常著名的方法,随机森林被誉为"代表集成学习技术水平的方法",由于其简单.容易实现.计算开销小,使得它在现实任务中得到广泛使用,因为其来源于决 ...

  • 如何在生活中做出更好的决策

    ​最重要的,是你选择背后的理由. 在生活中,我们总是会遇到各种各样的选择题. 你是计划本科毕业直接工作,还是准备留校继续读研? 你是愿意留在大城市里打拼,还是打算退居小城镇里享受安逸? 你是选择呆在熟 ...

  • 学会3个要点、掌握5个步骤,让你不再交智商税,做出更明智的决策

    现在很多人都有'手机依赖症',几乎恨不得24小时粘在手机上,于是很多公众号的文章就说自律的人生要从断掉社交软件开始,不过不用社交软件就一定会自律吗?老刷微博.淘宝一定就无用吗? 其实仔细思考一下,发现 ...

  • 对赌思维:如何面对混沌的世界做出更优的决策

    假设你是一位企业管理者,或是基金经理,或是从事商业贸易,当你需要作出重大决策的时候,如果让你从职业赌徒获得相关的建议,你很有可能觉得这是一个笑话. 或者让我们简化一下场景,如果你是一位家长,想培养你小 ...

  • 如何在生活中做出更好的决策?

    身边的经济学 昨天 16:46 在生活中,我们总是会遇到各种各样的选择题. 你是计划本科毕业直接工作,还是准备留校继续读研? 你是愿意留在大城市里打拼,还是打算退居小城镇里享受安逸? 你是选择呆在熟悉 ...

  • 如何利用多样的视角做出更好的决策?

    砺石导言 要想成为一个聪明的决策者,就要知道你的思维是如何工作的,知道我们在什么样的状态下才能做出正确的选择. 唐·摩尔 | 文 <自信是所有问题的答案>| 来源 总的来说,一大群人的智慧 ...

  • 战胜这 10 种认知偏见,让自己做出更好的决定

    神译局20小时前 关注 首先,要意识到普遍存在的认知偏见. 神译局是36氪旗下编译团队,关注科技.商业.职场.生活等领域,重点介绍国外的新技术.新观点.新风向. 编者按:认知偏见是我们的大脑与生俱来的 ...

  • 《决断力》:如何在生活与工作中做出更好的选择!

    《决断力》:如何在生活与工作中做出更好的选择!

  • 百度万象大会,荣膺年度影响力创作者,怎样做出更好的科普内容?

    三春美景万象会,一米阳光千里云. 四尺书桌八寸翰,百家齐诵亿人闻. 宾馆窗外的云 初次入选百家号年度影响力创作者,我还是非常激动的.从默默无闻到更默默无闻,甚至到一度放弃,然后重新出发,成为优质创作者 ...

  • 今天晚上就试试浇汁猪排!烤箱做出更美味!

    原料:猪里脊300克,洋葱半个,胡萝卜半根,柠檬半个 调料:盐1茶匙(5克),生抽2茶匙(10ml),蚝油2茶匙(10克),糖1/2茶匙(3克),黑胡椒碎1/2茶匙(3克),烤肉酱1茶匙(5克),黄油 ...