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

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$ ）之差。