信息熵

作者: 郑小才 | 来源:发表于2020-11-06 16:31 被阅读0次

熵、条件熵、信息增益（互信息）
一文理解机器学习中的各种熵
ID3与C4.5算法
决策树算法梳理
信息熵（香农熵）、条件熵、信息增益的简单了解
信息熵与最大熵模型
机器学习之决策树
熵之道
联合信息熵和条件信息熵
cross entropy交叉熵和ground truth总结

介绍

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

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

如果抛一枚硬币，正反的概率都为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

熵、条件熵、信息增益（互信息）
信息增益首先明确一点，信息熵是信息量的期望！期望！期望！（各种信息熵都是如此，像熵、条件熵、信息增益）熵：表示随...
一文理解机器学习中的各种熵
本文的目录组织如下：【1】自信息【2】熵（香农熵）【3】联合熵【4】条件熵【5】互信息（信息增益）【6】熵、联...
ID3与C4.5算法
写在开始在开始决策树算法之前，我们需要准备一些信息论的知识：信息熵条件熵信息增益交叉熵相对熵信息熵 ...
决策树算法梳理
信息论基础（熵联合熵条件熵信息增益基尼不纯度）信息熵：信息熵是度量样本集合纯度常用的一种指标。在信息论中...
信息熵（香农熵）、条件熵、信息增益的简单了解
信息熵（香农熵） 1948年，香农提出了 “信息熵（entropy）”的概念信息熵是消除不确定性所需信息量的度量，...
信息熵与最大熵模型
信息熵是什么？机器学习入门：重要的概念---信息熵（Shannon’s Entropy Model）信息熵信息论中...
机器学习之决策树
信息熵: 信息熵描述信息源的不确定程度，信息熵越大、越不确定. 信息熵公式: 例子: 假设中国乒乓球队和巴西乒乓球...
熵之道
熵的定义如下：互信息 = H(D) - H(D|A) 信息增益 = 经验熵 - 经验条件熵；互信息和信息增益理...
联合信息熵和条件信息熵
下面这几个熵都是描述联合分布中的两个变量相互影响的关系。联合信息熵联合信息熵的定义如下：条件信息熵条件信息...
cross entropy交叉熵和ground truth总结
一.cross entropy 交叉熵交叉熵的概念得从信息熵的概念说起，我们都知道信息熵，简而言之就是信息量多少...