信息熵

2020-11-06 本文已影响0人郑小才

介绍

信息的基本作用就是消除人们对事物的不确定性。信息熵，可以理解为信息的不确定程度，信息的不确定程度越大，信息熵也就越大，把它搞清楚所需要的信息量也就越大。

什么样的信息不确定程度大呢？
如果中国男足和巴西男足比赛，让我来猜胜负，那么我几乎可以断言，巴西队一定会赢，也就是巴西队和中国队胜负这个事件的不确定程度很小，信息熵也就很小。

如果抛一枚硬币，正反的概率都为0.5，它的不确定性很大，所以信息熵就很大。

定义

信息熵 是一个绝对值，用来衡量信息不确定程度的绝对大小。
信息凡是在一种情况下能减少不确定性的任何事物都叫信息。
信息量 是一个相对值，表示的是在某个具体事件发生以后所带来的的信息。（如果大家都知道的消息，信息量就小。如果大家都不知道的消息，如果后面被证实，那这个消息的信息量就大）

一般而言，当一种信息出现概率更高的时候，表明它被传播得更广泛，或者说，被引用的程度更高。我们可以认为，从信息传播的角度来看，信息熵可以表示信息的价值。这样子我们就有一个衡量信息价值高低的标准，可以做出关于知识流通问题的更多推论。

计算公式

$H_{(x)} = -{\sum_i} P_{(xi)}\log_bP_{(xi)}$

变量	解释
$b$	对数所使用的底。当 $b$ = 2，熵的单位是bit。
$P$	$x$ 的概率质量函数（probability mass function），我们可以理解为事件xi 发生的概率。
$x$	随机变量，与之相对应的是所有可能输出的集合。定义为符号集,随机变量的输出用x表示。
$P_{(x)}$	表示输出概率函数。

变量的不确定性越大，熵也就越大，把它搞清楚所需要的信息量也就越大。

公式看起来可怕，其实非常简单。
让我们用抛硬币来举例，“抛一次硬币是正面”这个随机变量x的信息熵为
$H_{(x)} =-({{1} \over {2}}log_2{{1} \over {2}} + {{1} \over {2}}log_2{{1} \over {2}} ) = {-log_2{{1} \over {2}} } = 1$

也就是抛一次硬币是正面这个事件的信息熵只需要1 bit，也就是只需要用1位的二进制数就可以表示这个信息大小。

经典题目

1000桶水，其中一桶有毒，猪喝毒水后会在15分钟内死去，想用15分钟内找到这桶毒水，至少需要几头猪？

1000桶水其中有一桶有毒 这个随机变量X的信息熵为
$H_{(X)} = -log_2{{1} \over {1000}} = 9.966$

//对数计算
   public static double log(double basement, double n) {
        return Math.log(n) / Math.log(basement);
    }

    public static void main(String[] args) {
        double res = 0 -log(2, 1d/1000d);
        System.out.println(res);
    }
//输出
9.965784284662087
Process finished with exit code 0

1只猪喝水以后的要么活着，要么死去，一共有两种状态，所以”1只猪喝完水以后的状态“这个随机变量Y的信息熵为
$H_{(Z)} =-({{1} \over {2}}log_2{{1} \over {2}} + {{1} \over {2}}log_2{{1} \over {2}} ) = {-log_2{{1} \over {2}} } = 1$

n只猪喝完水会有 $2^n$ 种状态，即"n只猪喝完水以后的状态"这个随机变量Y的信息熵为
$H_{(Y)} =-{\sum^{2^n}_{i=1}} {{1} \over {2^n}} log_2{{1} \over {2^n}} = -log_2{{1} \over {2^n}} = n$

所以，按照题目要求，如果至少需要n头猪能够找到这桶毒水，那么随机变量Y的信息熵必须要大于随机变量X的信息熵。
也就是 $H_{(Y)}\geq H_{(X)}$ ，也就是 n >= 9.966，即 n = 10
上面的信息熵计算公式可以简化为
$2^n\geq10000$
同样可以解得 n = 10 ，虽然形式简单，但我们一定要记住它背后的原理是信息熵。

具体的方案

我们将1000桶水按照二进制进行编码，需要十位二进制数。

第1桶水对应的二进制数为 0000000001
第2桶水对应的二进制数为 0000000010
...
第1000桶水对应的二进制数为 1111101000
任意一桶水都可以对应唯一的一个二进制数，然后我们按以下方案让猪喝水
1号猪喝位置1的数字为1的桶中的水。
2号猪喝位置2的数字为1的桶中的水。
...
10号猪喝位置10的数字为1的桶中的水。
如下图示：

如果15分钟后1，3，5号猪被毒死，那么对应的二进制编码就是00000 10101b，也就是21号水桶有毒，猪死的任何一种排列方式都对应了二进制的唯一编码。
这里为什么采用二进制的编码方式？
因为猪的生死正好对应二进制的0和1所以这里可以彩二进制的编码方式。

题目进阶

如果这里不是15分钟内找出这桶毒水，而是1个小时内呢？
有了前面的题目的基友我们知道
1000桶水其中有一桶有毒 这个随机变量X的信息熵为
$H_{(X)} = -log_2{{1} \over {10000}} = 9.966$

而对于猪的状态就不太一样了，我们可以想象一下，一只猪在一个小时内会有几种状态？

在第0分钟的时候喝了一桶水以后，第15分钟死去。
第15分钟依然活着，喝了一桶水以后，第30分钟死去。
第30分钟依然活着，喝了一桶水以后，第45分钟死去。
第45分钟依然活着，喝了一桶水以后，第60分钟死去。
第45分钟依然活着，喝了一桶水以后，第60分钟依然活着。

可见，1只猪1个小时以后会有5种状态，所以”1只猪1个小时后的状态“这个随机变量Z的信息熵为
$H_{(Z)} =-(5\times{{1} \over {5}}log_2{{1} \over {5}} ) = {log_25 } = 2.3219$

n只猪1个小时后会有
$n \times log_25 = 2.3219n$

照题目要求，如果至少需要n头猪能够找到这桶毒水，那么随机变量Y的信息熵必须要大于随机变量X的信息熵，也就是
$H_{(Y)}\geq H_{(X)}$ ，也就是 $n \geq 9.966/2.3219 = 4.292$ ，即 n = 5
根据前面简化版本的二进制编码方式的思路，我们可以利用猪的5种状态构造一个5进制编码方式。
首先，将1000桶水按照5进制编码的方式排列，需要5位5进制数。
然后按照如下方案让猪进行喝水：

1号猪第0分钟喝位置1的数字是1的水，如图所示，也就是1、6、11、16、21...
如果第15分钟活着，喝位置1的数字是2的水，如图所示，也就是2、7、12、17、22...
如果第30分钟活着，喝位置1的数字是3的水，如图所示，也就是3、8、13、18、23...
如果第45分钟活着，喝位置1的数字是4的水，如图所示，也就是4、9、14、19、24...
类似的，2号猪喝位置2的水...

猪的编号代表5进制编码数字所在的位数

1号猪代表最低位
5号猪代表最高位

第几分钟死代表当前位数的权重，

15分钟死表示权重是1
30分钟死表示权重是2
45分钟死权重为3
60分钟死表示权重是4
60分钟依然活着表示权重是0

如果1号猪第30分钟死了，2号猪第15分钟死了，3号猪第45分钟死了，4，5号都活到了最后。则毒水对应的5进制编码是
$5^0\times2 + 5^1\times1 + 5^2\times3 + 5^3\times0 + 5^4\times0 = 82$

到此，这个问题从理论和工程上都给出了答案。信息熵让我们明确了工程上努力的方向并明确了那条不可逾越的鸿沟。

为什么题目中在计算猪的信息熵时采用了等概率？

首先要明确的是，猪在喝毒水的时候生和死的概率确实不一定是等概率的，这个是对的。
比如原题中，对于5号猪来说，因为它喝的水位于5进制的最高位上，所以它活的概率是
${624\over1000}= 0.624$

既然不是等概率，那正文中为什么采用等概率的方式呢？这是因为在计算信息熵的时候，我们考虑的是n只猪所能表达的最大信息熵。
数学上可以证明，当随机事件等概率发生的时候，信息熵是最大的。
题目要求最少n只猪，意思就是在最差情况下用n只猪也能找到毒水。而最差的情况就是每只猪生死的概率是相等的。
所以我们用等概率的方式求出最大信息熵时最小的n，当n再小，最差情况下已经无法测出1000桶水了。

参考：https://www.zhihu.com/question/60227816/answer/1274071217

信息熵

介绍

定义

计算公式

经典题目

具体的方案

题目进阶

为什么题目中在计算猪的信息熵时采用了等概率？

猜你喜欢

热点阅读