猪喝毒水 信息熵
事情的起因是有这么一道题:
25桶水其中一桶有毒,猪喝水后会在15分钟内死去,想用一个小时找到这桶毒水,至少需要几头猪?
看到这个题,我直接就使用了二分法,25桶直接分成12桶+12桶+1桶,然后12分6,6分3,3分1,最终计算结果是需要5头猪,反过来理解,也就是 ,现在就25桶水,当然答案是5头猪。然而我这个答案是错的……
百度了一下,发现是一道leecode题目,正确答案是2。解法也很容易理解,这里借用百度到的一张图来帮助理解,如果我下面的解释没看懂,也可以去看一下博主原文: [leetcode]——哪桶水有毒
如图,把25桶水分成5行5列,派两头猪,一个逐行喝( 注意是一次性喝掉这一行的5桶水的混合物 ),一个逐列喝。以逐列的猪为例,15分钟后死了说明毒水在第1列,如果活着就继续去喝第2列,然后分别等到30、45、60分钟观察是否死亡来锁定是哪一列,如果60分钟还没死,说明前面4列都没毒水,那么用排除法就知道毒水只能在第5列。逐行猪同理,最终只要锁定了行列数,那么交叉点必然是毒水所在位置。
可以观察到,这种解法的关键是,一头猪充分利用了15分钟的间隔,在1个小时内直接辨明了5大桶水(实际是5桶混合水)是否有毒。如果题目改成是10分钟的间隔呢,那1个小时就能辨明7桶水了。此时7的2次方是49,仍然需要2头猪。
再扩展一下,仍然是15分钟间隔,但总共是1000桶水呢?实际上,一头猪只能辨明5,两个维度只能是5乘以5,再来一头,就是5的3次方;很容易发现,问题实际变成求5的多少次方能大于1000,答案易得是5头猪。其实这时候5的5次方是3125,也就是说即使是3000桶水,5头猪也是够的。
再扩展一下,如果是15分钟间隔,但要求是15分钟搞定,而不是一个小时呢?这时候会发现,15分钟结束后,猪只有两个状态,要么死要么活。也就是每一行或每一列实际上只能放2桶水。那么 问题就变成2的多少次方大于25,哎,此时的答案和我刚开始使用的二分法是完全一致的。这个时候,我才意识到,我的二分法,实际上不需要1小时,仅仅15分钟就能搞定辨明毒水的目的。因为题目中说了,每桶水是无限多的,那我可以先按二分的思路,把25桶水全部都拆好,然后一声令下,5头猪同时上去喝对应的分组,当然是15分钟后就知道结果了。
然而事情到现在,才刚刚开始……比如这个知乎3万赞的回答:
1000桶水,其中一桶有毒,猪喝毒水后会在15分钟内死去,想用一个小时找到这桶毒水,至少需要几头猪? - 苗华栋的回答 - 知乎
作者上来就丢出信息熵的定义和公式:
然后用这公式一顿计算,把我看懵逼了。这里建议先通过别的链接,来补一下基础知识。
参考 信息熵是什么? - 运筹之学的回答 - 知乎
信息熵,信息熵,怎么看怎么觉得这个“熵”字不顺眼,那就先不看。我们起码知道这个概念跟信息有关系。而它又是个数学模型里面的概念,一般而言是可以量化的。所以,第一个问题来了: 信息是不是可以量化?
起码直觉上而言是可以的,不然怎么可能我们觉得有些人说的废话特别多,“没什么信息量”,有些人一语中的,一句话就传达了很大的信息量。
有些事情本来不是很确定,例如明天股票是涨还是跌。如果你告诉我明天NBA决赛开始了,这两者似乎没啥关系啊,所以你的信息对明天股票是涨是跌带来的信息量很少。但是假如NBA决赛一开始,大家都不关注股票了没人坐庄股票有99%的概率会跌,那你这句话信息量就很大,因为本来不确定的事情变得十分确定。
而有些事情本来就很确定了,例如太阳从东边升起,你再告诉我一百遍太阳从东边升起,你的话还是丝毫没有信息量的,因为这事情不能更确定了。
所以说信息量的大小跟事情不确定性的变化有关。
一,跟事情的可能结果的数量有关;二,跟概率有关。
先说一。例如我们讨论太阳从哪升起。本来就只有一个结果,我们早就知道,那么无论谁传递任何信息都是没有信息量的。当可能结果数量比较大时,我们得到的新信息才有潜力拥有大信息量。
二,单看可能结果数量不够,还要看初始的概率分布。例如一开始我就知道小明在电影院的有15*15个座位的A厅看电影。小明可以坐的位置有225个,可能结果数量算多了。可是假如我们一开始就知道小明坐在第一排的最左边的可能是99%,坐其它位置的可能性微乎其微,那么在大多数情况下,你再告诉我小明的什么信息也没有多大用,因为我们几乎确定小明坐第一排的最左边了。那么,怎么衡量不确定性的变化的大小呢?怎么定义呢?这个问题不好回答,但是假设我们已经知道这个量已经存在了,不妨就叫做信息量,那么你觉得信息量起码该满足些什么特点呢?
那有什么函数能满足上面四个条件呢?
负的对数函数,也就是-log(x)!底数取大于1的数保证这个函数是非负的就行。前面再随便乘个正常数也行。
a. 为什么不是正的?因为假如是正的,由于x是小于等于1的数,log(x)就小于等于0了。第一个特点满足。
b. 咱们再来验证一下其他特点。三是最容易的。假如x是一个概率,那么log(x)是连续依赖于x的。donec。
四呢?假如有n个可能结果,那么出现任意一个的概率是1/n,而-log(1/n)是n的增函数,没问题。
d。最后验证二。由于-log(xy) = -log(x) -log(y),所以也是对的。学数学的同学注意,这里的y可以是给定x的条件概率,当然也可以独立于x。By the way,这个函数是唯一的(除了还可以多乘上任意一个常数),有时间可以自己证明一下,或者查书。
ok,所以我们知道一个事件的信息量就是这个事件发生的概率的负对数。最后终于能回到信息熵。信息熵是跟所有可能性有关系的。每个可能事件的发生都有个概率。信息熵就是平均而言发生一个事件我们得到的信息量大小。所以数学上,信息熵其实是信息量的期望。(表达式参考其它答案或者看下面)
参考 信息熵是什么? - D.Han的回答 - 知乎
赌马比赛里,有4匹马{A,B,C,D},获胜概率为{1/2,1/4,1/8,1/8}。接下来,让我们将哪一匹马获胜视为一个随机变量X。
假定我们需要用尽可能少的二元问题来确定随机变量 X 的取值。例如:问题1:A获胜了吗?问题2:B获胜了吗?问题3:C获胜了吗?最后我们可以通过最多3个二元问题,来确定X的取值,即哪一匹马赢了比赛。
那么很容易计算,在这种问法下,为确定X取值
当我们使用上述的信息熵公式,是这样的:
-1/2*log(1/2) + -1/4*log(1/4) + -1/8*log(1/8) + -1/8*log(1/8)
这里很容易计算结果,比如: -1/2*log(1/2) = -1/2 * (log1 - log2) = 1/2 * log2 = 1/2 ,最终结果就是:
1/2+1/2+3/8+3/8 = 7/4
可以发现,信息熵公式计算结果与之前计算是一致的。在二进制计算机中,一个比特为0或1,其实就代表了一个二元问题的回答。也就是说,在计算机中,我们给哪一匹马夺冠这个事件进行编码,所需要的平均码长为1.75个比特。
很显然,为了尽可能减少码长,我们要给发生概率较大的事件,分配较短的码长 。这个问题深入讨论,可以得出霍夫曼编码的概念。
扩展阅读可以参考 H264系列九 热力学熵 信息熵 哈夫曼编码 哥伦布编码 ,在这篇文章里,也有一个很有意思的例子:
我要抛一次骰子,在观测到结果之前,骰子六个面向上都有可能,而且概率完全一样(都是1/6).这时,这一事件的信息熵为 。这个结果用之前的信息熵公式也很好计算,相当于累加6次 -1/6*log(1/6) ,即 -log(1/6)=-(log1-log6)=log6 ,注意这个算法在之后算猪喝毒水时也会用到。
现在万能的女神给了我一个提示,这次骰子的结果一定是偶数,于是可能的结果由6种降低为3种,事件的熵也就变成了 。也就是说,当我得到提示后,对于事件结果的不确定性降低了。我们把信息熵降低的量规定为信息量I。上面那条提示对我的信息量是 ,正好是1比特,相当于对一个完全未知的命题做一次是非判断需要的信息量。而如果我要得到唯一确定的结果,P(x)就必须等于1,此时的信息熵为零。我们需要得到的信息量就是原本的熵 。
看到这里,聪明的你一定已经可以自己总结出另一个金光闪闪的结论:信息就是负熵。需要特别注意的是,这句话里的“熵”指而且仅指信息熵,试图将这个结论扩大到热力学熵的解释往往都缺乏足够的事实基础,并且含义也经常是含混的。
是时候回到知乎3万赞的回答了: 1000桶水,其中一桶有毒,猪喝毒水后会在15分钟内死去,想用一个小时找到这桶毒水,至少需要几头猪? - 苗华栋的回答 - 知乎
1000桶水,其中一桶有毒,猪喝毒水后会在15分钟内死去,想用15分钟内找到这桶毒水,至少需要几头猪?
首先,”1000桶水其中有一桶有毒“这个随机变量X的信息熵为: -(1/1000)*log(1/1000) 累加1千次。这个很容易理解吧,毒水出现在任意一桶之中是个等概率事件,累加起来的结果就是:
-log(1/1000) = log 1000 约等于9.966
1只猪喝水以后的要么活着,要么死去,一共有两种状态,所以”1只猪喝完水以后的状态“这个随机变量Y的信息熵为
n只猪喝完水会有2的n次方种状态,即"n只猪喝完水以后的状态"这个随机变量Y的信息熵为
所以,按照题目要求,如果至少需要n头猪能够找到这桶毒水,那么随机变量Y的信息熵必须要大于随机变量X的信息熵,也就是H(Y) >= H(X) ,也就是 n >= 9.966,即 n = 10
当我们用信息熵算出来了n的最小值以后,我们就可以坚信,理论上n=10一定是最优解,任何想方设法想找到小于10的值都是徒劳的。
其实,上面的信息熵计算的简化版本可以写成如下更好理解的形式 ,同样可以解得 n = 10 ,虽然形式简单,但我们一定要记住它背后的原理是信息熵。
至于到底采用什么方案,这涉及到术的层面,即使我们暂时想不到,我们也会有努力的方向,并且知道努力的边界在哪里,不会做类似寻找永动机的事情。
1000桶水,其中一桶有毒,猪喝毒水后会在15分钟内死去,想用一个小时找到这桶毒水,至少需要几头猪?
1000桶水其中有一桶有毒,和第一个问题相同,仍然是9.966。但是,猪的信息熵不同了。我们可以想象一下,一只猪在一个小时内会有几种状态?
可见,1只猪1个小时以后会有5种状态,所以”1只猪1个小时后的状态“这个随机变量Z的信息熵为
n只猪1个小时后会有 5的n次方 种状态,即"n只猪1个小时以后的状态"这个随机变量Y的信息熵为
所以,按照题目要求,如果至少需要n头猪能够找到这桶毒水,那么随机变量Y的信息熵必须要大于随机变
量X的信息熵,也就是H(Y) >= H(X) ,也就是 n >= 9.966 / 2.3219 = 4.292,即 n = 5
事实上,对于 n = 5来说,不仅可以检测1000桶水,甚至检测3000桶水都是没有问题的。有兴趣的童鞋
可以试着计算一下。
到此,香农给了我们一个理论极限,但是具体的方案还是需要我们自己进行构造。得出n=5是依靠我们的
理论功底,而得出具体的方案就是我们的工程水平了。
还是知乎3万赞的作者,参考 香农的信息论究竟牛在哪里? - 苗华栋的回答 - 知乎 ,老习惯,这里只介绍思路,具体方案看作者原文。
12个外表相同的球中有1个坏球,它的重量比其它11个好球要轻,现在有一台没有砝码的天平,问至少称几次能确保找出这个坏球?
我们可以思考一下,一个天平称量1次后会有3种结果:
所以“天平称量1次后的结果”这个随机变量Z的信息熵是
如果将上述式子简化,即
12个外表相同的球中有1个坏球,它的重量和其它11个球不同,现在有一台没有砝码的天平,问至少称几次能确保找出这个坏球?
这个问题和前面那个问题的不同之处在于不知道这个坏球的轻重。这对信息熵来说跟前面的已知坏球是轻的相比有什么影响呢?
如果有2个球放在天平两侧。如果已知坏球比较轻,当天平不平衡时,我就可以立刻知道坏球是轻的那一侧。而当不知道坏球是轻还是重时,如果天平不平衡,我无法判断坏球是重的那一侧还是轻的那一侧,我只能够知道坏球要么是轻的那一个,要么是重的那一个。所以,在不知道坏球是轻还是重时,每次测量多了一个坏球是轻还是重的不确定性。在上题的基础上,在最高位增加一位表示球的轻重。其中0表示轻,1表示重,如下表所示。于是虽然12个球,但是因为多了一个轻重的不确定性,所以变成24种状态。
于是“12个外表相同的球中确定1个不知轻重的球”这个随机变量X的信息熵为
而“天平称量n次后的结果”这个随机变量Y的信息熵没有变,因为天平每次还是只能确定三种状态,所以
同样,H(Y) >= H(X) ,即 n >= 2.893,即 n = 3可见,前面那道题并没有充分发挥天平的信息优势,3次还能测出不知轻重的坏球。这就是理论武装头脑的好处,先找到答案,再去想方案。这种自顶向下的思考方式的好处就是我们在思考方案之前有了目标,也有了努力的方向,而不是无头苍蝇一样。
如果看了文章开头1000桶水找毒药那道题的童鞋可能会发现,这道题的解题思路几乎是照搬那道题的解题思路,虽然表面上是不同类型的题目,但我们要像香农祖师爷学习,透过题目的表象直穿本质。
这两道题目的底层逻辑都是信息熵,当我们掌握了理论工具以后,人之间的差距就在于是否有足够的能力将现实问题抽象成数学或者其他问题,然后用我们熟知的理论工具去解决它。在这一点上,就和解方程式是一样的。解方程本身非常简单,难点是如何将现实的问题抽象成表达式,定义变量,列出方程式。关于这一点详细的陈述在我的另一篇文章 《数学思维在生活中有多大用处?》 中有更详细的描述。
参考 1000桶水,其中一桶有毒,猪喝毒水后会在15分钟内死去,想用一个小时找到这桶毒水,至少需要几头猪? - PlanarG的回答 - 知乎
考虑这样一个过程:假设现在给你两个数a,b,只允许你进行一次比较,将这两个数从小到大排序。你心想这个问题不是非常简单吗,直接拿这两个数比较一次,哪个数小哪个就排在前面。
我们来分析一下这个看似简单的问题的本质是什么。
如果我们只能进行一次比较,那么根据这一次比较,我们能够得到的信息实际上只有两种:要么第一个数较小,要么第二个数较小。而两个数最终从小到大的关系也只有两种情况:要么是 a,b ,要么是b,a 。也就是说,我们能够根据这一次比较的结果建立一个结果-最终排列的双射关系,每一种比较的结果都唯一地对应最终的一种大小关系。
现在考虑上面那个问题的升级版:如果现在给你四个数a,b,c,d 能否通过 4 次比较给它们从小到大排序?答案是否定的。因为通过四次比较我们能得到的信息最多只有2的4次方,即16种。而这4个数的排列一共有4!=24种。因此不可能将询问的结果与最终排列一一对应,我们就证明了 4 不可能是答案的下界。
我们再升级一次,考虑给n个数排序的情况。如果我们在最终的方案中使用了k次比较,那么可能得到的信息有2的k次方种,而n个数的排列有n!种。要建立结果-最终排列的双射关系,必须满足 即:
现在让我们用信息论的角度思考一下原问题。 1000桶水,只有一桶有毒,换言之,可能的答案只有 1000种。
每头猪在中毒之后 15分钟内死去,那么我们可以从每头猪获得的信息一共有5种:在[0,15) [15,30) [30,45) [45,60)中的哪一个时间段死去,或者最终存活下来。如果最终有k只猪,我们能获得的信息就有 种,换言之,k需要满足 ,即 ,因此 k的下界为 5。
曹菊比卡: 十八猜是我们茶余饭后常玩的游戏,有经验的同学都知道,这个游戏最固定也是最有效的猜题模式就是二分法.二分法的意思,大致就是把可能出现的情况,分尽可能成概率相等的两个区间.根据提问者的信息反馈,我们可以将答案归在其中一...
太康县19473406502: 某信息源有8种独立状态,其发生概率分别是1/8,1/8,0,1/4,0,0,0,1/2这时信息源传给信宿的总信息量 - ?
曹菊比卡: 对每个概率有信息熵-p*log(p),p为概率,对数的底数取为2(二进制数之意)p为0或1时0log0或1log1均取为0 因此总信息熵为3/8+3/8+2/4+1/2=7/4
太康县19473406502: 信息熵是什么?举例子说明 - ?
曹菊比卡: 信息的基本作用就是消除人们对事物了解的不确定性.多数粒子组合之后,在它似像非像的形态上押上有价值的数码,具体地说,这就是一个在博弈对局中现象信息的混乱.信息的基本作用就是消除人们对事物了解的不确定性.美国信息论创...
太康县19473406502: 信息熵是什么 - ?
曹菊比卡: 信息理论的鼻祖之一Claude E. Shannon把信息(熵)定义为离散随机事件的出现概率.所谓信息熵,是一个数学上颇为抽象的概念,在这里不妨把信息熵理解成某种特定信息的出现概率.而信息熵和热力学熵是紧密相关的.根据Charles H. ...
太康县19473406502: 为什么环境问题具有一定程度的不可逆性? - ?
曹菊比卡: 因为环境一经破坏,很难恢复原来的生态环境.
太康县19473406502: 香农熵的计算 - ?
曹菊比卡: 有了“熵”这个概念,我们就可以回答本文开始提出的问题,即一本五十万字的中文书平均有多少信息量.我们知道常用的汉字(一级二级国标)大约有 7000 字.假如每个字等概率,那么我们大约需要 13 个比特(即 13 位二进制数)表示一个...
太康县19473406502: 熵定律的定律简介 - ?
曹菊比卡: 熵的概念最早起源于物理学,用于度量一个热力学系统的无序程度.热力学第二定律,又称“熵增定律”,表明了在自然过程中,一个孤立系统的总混乱度(即“熵”)不会减小. 在信息论中,熵被用来衡量一个随机变量出现的期望值.它代表了在被接收之前,信号传输过程中损失的信息量,又被称为信息熵.信息熵也称信源熵、平均自信息量.在1948年,克劳德·艾尔伍德·香农将热力学的熵,引入到信息论,因此它又被称为香农熵. 熵在生态学中是表示生物多样性的指标.
太康县19473406502: 香农熵的介绍 - ?
曹菊比卡: 1948 年,香农提出了“信息熵”(shāng) 的概念,才解决了对信息的量化度量问题.一条信息的信息量大小和它的不确定性有直接的关系.比如说,我们要搞清楚一件非常非常不确定的事,或是我们一无所知的事情,就需要了解大量的信息.相反,如果我们对某件事已经有了较多的了解,我们不需要太多的信息就能把它搞清楚.所以,从这个角度,我们可以认为,信息量的度量就等于不确定性的多少.
太康县19473406502: 信息熵是指什么, - ?
曹菊比卡: 信息是个很抽象的概念.人们常常说信息很多,或者信息较少,但却很难说清楚信息到底有多少.比如一本五十万字的中文书到底有多少信息量.直到1948年,香农提出了“信息熵”的概念,才解决了对信息的量化度量问题.信息论之父克劳德...
太康县19473406502: 信息熵通俗的说法? - ?
曹菊比卡: 熵是用以解决信息量化度量问题,是信息量与信息价值的比值,熵值越低,代表用户获取信息价值越大.”这是手机QQ浏览器在全球移动互联网大会上的提出的.