条件熵，相对熵，交叉熵，联合熵，信息增益

作者: sarai_c7eb | 来源:发表于2019-09-29 20:13 被阅读0次

条件熵，相对熵，交叉熵，联合熵，信息增益
ID3与C4.5算法
信息熵、交叉熵、联合熵、条件熵、信息增益
一文理解机器学习中的各种熵
决策树算法梳理
信息熵相关知识总结
机器学习-面试总结
熵、条件熵、信息增益（互信息）
决策树算法梳理
信息熵、条件熵、相对熵、交叉熵

1 条件熵

1.1 条件熵的定义

$X$ 给定的条件下， $Y$ 的条件概率分布的熵对 $X$ 的期望；
条件熵 $H(Y\mid X)$ 表示在已知随机变量 $X$ 的条件下随机变量 $Y$ 的不确定性。

$\begin{align*} H(Y\mid X)&=\sum_{x\in X}p(x)H(Y\mid X) \\ &=-\sum_{x\in X}p(x)\sum_{y\in Y}p(y\mid x)\log{p(y\mid x)} \\ &= -\sum_{x\in X}\sum_{y\in Y}p(x,y)\log{p(y\mid x)} \end{align*}$

因为条件熵中 $X$ 也是一个变量，意思是在一个变量 $X$ 的条件下（变量 $X$ 的所有值都会取），另一个变量 $Y$ 熵对 $X$ 的期望；

1.2 举例说明条件熵

帅？	性格好？	身高？	上进？	嫁？
帅	不好	矮	不上进	不嫁
不帅	好	矮	上进	不嫁
帅	好	矮	上进	嫁
不帅	爆好	高	上进	嫁
帅	不好	矮	上进	不嫁
帅	不好	矮	上进	不嫁
帅	好	高	不上进	嫁
不帅	好	中	上进	嫁
帅	爆好	中	上进	嫁
不帅	不好	高	上进	嫁
帅	好	矮	不上进	不嫁
帅	好	矮	不上进	不嫁

设 $Y$ ={嫁，不嫁}，统计“嫁”的概率6/12，“不嫁”的概率6/12；
计算 $Y$ 的熵 $H(Y)=-1/2\log(1/2)-1/2\log(1/2)=\log(2)$

为了引入条件熵，我们现在还有一个变量 $X$ ，代表长相是“帅”还是“不帅”。
不帅的情况有4个，有1个不愿嫁，3个愿意；
$H(Y\mid X=不帅)=-1/4\log(1/4)-3/4\log(3/4)$
$p(X=不帅)=4/12=1/3$

帅的情况有8个，不愿意嫁5个，愿意嫁的为3个；
$H(Y\mid X=帅)=-5/8\log(5/8)-3/8\log(3/8)$
$p(X=帅)=8/12=2/3$

$H(Y\mid X=长相)=p(X=帅)*H(Y\mid X=帅)+p(X=不帅)*H(Y\mid X=不帅)$

>>> -5/8*(np.log2(5)-np.log2(8))-3/8*(np.log2(3)-np.log2(8))
0.6780719051126378

1.3 条件熵的另一种解释

条件熵 $H(Y\mid X)$ 相当于联合熵 $H(X,Y)$ ，减去单独的熵 $H(X)$ ，即：
$H(Y\mid X)=H(X,Y)-H(X)$
证明过程参考^[1]。

从以上的推导可以看出： $H(X,Y)\geq H(X)\geq H(X|Y)$ 。

2 相对熵(Relative entropy)，也称为KL散度（Kullback-Leibler diver）

如何衡量两个概率分布之间的差异?（相对熵）

定义:
设 $p(x)$ ， $q(x)$ 是离散随机变量 $X$ 中取值的两个概率分布，则 $p$ 对 $q$ 的相对熵是：
$D_{KL}(p\|q)=\sum_x{p(x)\log{\frac{p(x)}{q(x)}}}=E_{p(x)}\log{\frac{p(x)}{q(x)}}$

如果 $p(x)$ 和 $q(x)$ 两个分布相同，那么相对熵等于0；
$D_{KL}(p\|q)\neq D_{KL}(q\|p)$ ，相对熵具有不对称性；
$D_{KL}(p\|q)\geq 0$

相对熵可以从来衡量两个概率分布之间的差异，上面公式的意义就是求 $p$ 与 $q$ 之差在 $p$ 上的期望；

3 交叉熵(Cross entropy)

用以衡量在给定的真实分布下，使用非真实分布所给定的策略消除系统的不稳定性所付出的努力的大小；

有两个概率分布 $p(x)$ 和 $q(x)$ ，其中 $p(x)$ 是真实分布， $q(x)$ 是非真实分布，如果用真实分布 $p(x)$ 来衡量一个样本所需要编码长度的期望（平均编码长度）为：
$H(P)=\sum_x{p(x)\log{\frac{1}{p(x)}}}$
如果使用非真实分布 $q(x)$ 来表示来自真实分布 $p(x)$ 的平均编码长度，则是：
$H(p,q)=\sum_x{p(x)\log{\frac{1}{q(x)}}}$
这就是交叉熵。

3.1 $H(P)$ 的含义^[2]

对于变长编码（如哈夫曼码），必须保证任何编码不是其他编码的前缀，符合这一特性的编码叫做前缀码(prefix codes)。
前缀码的意义在于解码简单，但是会带来个问题，就是编码损失（不是所有的组合都可以）。如当前编码为"01"，长度 $L=2$ ，那 $01$ 开始的其他编码如("010"，"011")(总长度为3举例)就不能再使用。
损失的长度为 $1/2^L$ 。
所以为了对信息进行最优编码的目的，往往需要对短编码和短编码损失进行权衡；

将短编码带来的损失称为编码代价，通常根据 $X$ 出现的概率 $P(X)$ 来分配编码代价，假设 $X$ 的编码长度为 $L(X)$ ：
$\frac{1}{2^{L(x)}}=P(X)\Rightarrow L(X)=\log_2(1/P(X))$
平均编码长度则为：
$H(p)=\sum_x{p(x)\log_2{\left(\frac{1}{p(x)}\right)}}$

3.2 如何理解交叉熵

如现在有另一个序列服从 $p$ 分布，但是它仍然使用 $q$ 分布的最优编码方式，那它的平均编码长度即为：
$H(p,q)=\sum_x{p(x)\log{\frac{1}{q(x)}}}$
上式称为 $p$ 分布相对 $q$ 分布的交叉熵，衡量了 $p$ 分布使用 $q$ 分布的最优编码方式时的平均编码长度。
交叉熵根据相对熵的公式可以得出：
$D_{KL}(p\|q)=H(p,q)-H(p)$
$D_{KL}(p\|q)\geq 0$ 可以理解为用其他方式的最优编码( $q$ )和自己方式的最优编码（ $p$ ）之差。

4 联合熵和互信息

定义联合熵如下：
$H(X,Y)=\sum_{x,y}{p(x,y)\log_2{\left(\frac{1}{p(x,y)}\right)}}$
根据条件熵定义：
$H(X,Y)=H(X)+H(Y\mid X)=H(Y)+H(X\mid Y)$

定义互信息(Mutual Entropy)如下：
$I(X,Y)=H(X)+H(Y)-H(X,Y)$
定义差异信息(Variation of Information):
$V(X,Y)=H(X,Y)-I(X,Y)$

对应关系

信息增益：
$MI(Y,X)=H(Y)-H(Y\mid X)$
$MI(X,Y)=H(X)-H(X\mid Y)$

信息增益
决策书中信息增益等于互信息。

参考1：通俗理解条件熵
 参考2：信息论与机器学习

证明过程参考《详解机器学习中的熵、条件熵、相对熵和交叉熵》 ↩
参考《信息论与机器学习》 ↩

条件熵，相对熵，交叉熵，联合熵，信息增益
1 条件熵 1.1 条件熵的定义给定的条件下，的条件概率分布的熵对的期望；条件熵表示在已知随机变量的条件下随机变...
ID3与C4.5算法
写在开始在开始决策树算法之前，我们需要准备一些信息论的知识：信息熵条件熵信息增益交叉熵相对熵信息熵 ...
信息熵、交叉熵、联合熵、条件熵、信息增益
1. 自信息自信息是信息不确定性的衡量指标。信息发生的可能性越高，包含的信息越少，信息发生的可能性越低，包含的信...
一文理解机器学习中的各种熵
本文的目录组织如下：【1】自信息【2】熵（香农熵）【3】联合熵【4】条件熵【5】互信息（信息增益）【6】熵、联...
决策树算法梳理
决策树算法梳理 1. 信息论基础（熵联合熵条件熵信息增益基尼不纯度） 1.1 熵（entropy）...
信息熵相关知识总结
前言学习决策树时会接触到一些信息熵,条件熵和信息增益的知识,此外还有互信息,相对熵,交叉熵和互信息,KL散度等等...
机器学习-面试总结
决策树问题 1）各种熵的计算熵、联合熵、条件熵、交叉熵、KL散度（相对熵）熵用于衡量不确定性，所以均分的时候熵最...
熵、条件熵、信息增益（互信息）
信息增益首先明确一点，信息熵是信息量的期望！期望！期望！（各种信息熵都是如此，像熵、条件熵、信息增益）熵：表示随...
决策树算法梳理
信息论基础（熵联合熵条件熵信息增益基尼不纯度）信息熵：信息熵是度量样本集合纯度常用的一种指标。在信息论中...
信息熵、条件熵、相对熵、交叉熵
自信息简单来说，自信息表述的是随机变量的某个事件发生带来的信息量（一个事件）image-2020040322174...