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

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：信息论与机器学习

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

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 230,825评论 6赞 546
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 99,814评论 3赞 429
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 178,980评论 0赞 384
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 64,064评论 1赞 319
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 72,779评论 6赞 414
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 56,109评论 1赞 330
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 44,099评论 3赞 450
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 43,287评论 0赞 291
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 49,799评论 1赞 338
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 41,515评论 3赞 361
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 43,750评论 1赞 375
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 39,221评论 5赞 365
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 44,933评论 3赞 351
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 35,327评论 0赞 28
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 36,667评论 1赞 296
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 52,492评论 3赞 400
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 48,703评论 2赞 380