熵，交叉熵，KL散度的理解

参考博客：https://colah.github.io/posts/2015-09-Visual-Information/#fn1

什么是熵，什么是信息熵？在机器学习中一直都很难理解，最近读了一篇博客，它用可视化的方法帮助我们更好的理解什么是信息熵。

可视化概率分布

首先举个例子，这个例子在后文中也会用到。假设我在重庆，有时候它会下雨，但是大多数时候是晴天，下雨的概率大概是25%，晴天的概率是75%。简单的用图表示如下：

然后大部分时间，我穿的是短袖，概率为62%，有时候穿雨衣，概率为38%。

假如穿衣服和天气是相互独立的，那么我们可以很好的将这两个变量分布用一个图可视化出来。

图中横轴表示穿什么衣服的概率，竖轴表示天气的概率。正方形内部被整齐的划分为4块，这4块都是互相独立的，即穿什么衣服和什么天气是没有关系的。

但是现实生活中不是这样的，这两个条件是相互影响的，比如说上图中的4个子块会因为两个变量之间的相互影响导致有的子块概率变小（下雨导致穿短袖的概率变低）；有的子块概率变大（下雨导致穿雨衣的概率变大）。所以我们实际得到的这些子块有的是膨胀的，有的是缩小的，可视化出来如下图：

既然两个变量是相互影响的，那么此时，我们考虑引入条件概率，假设天气已知，此时穿衣服的条件概率为：

• $p(穿雨衣|下雨)=75\%$p(穿雨衣∣下雨)=75%
• $p(穿短袖|下雨)=25\%$p(穿短袖∣下雨)=25%
• $p(穿雨衣|晴天)=25\%$p(穿雨衣∣晴天)=25%
• $p(穿短袖|晴天)=75\%$p(穿短袖∣晴天)=75%

则上图可以转换为（规则化）

由条件概率公式$p(x,y)=p(x)*p(y|x)$p(x,y)=p(x)∗p(y∣x)，我们可以得到，

• $p(穿雨衣,下雨)=p(下雨)*p(穿雨衣|下雨)=25\%*75\%=0.1875\approx19\%$p(穿雨衣,下雨)=p(下雨)∗p(穿雨衣∣下雨)=25%∗75%=0.1875≈19%
• $p(穿短袖,下雨)=p(下雨)*p(穿短袖|下雨)=25\%*25\%=0.0625\approx6\%$p(穿短袖,下雨)=p(下雨)∗p(穿短袖∣下雨)=25%∗25%=0.0625≈6%
• $p(穿雨衣,晴天)=p(晴天)*p(穿雨衣|晴天)=75\%*25\%=0.1875\approx19\%$p(穿雨衣,晴天)=p(晴天)∗p(穿雨衣∣晴天)=75%∗25%=0.1875≈19%
• $p(穿短袖,晴天)=p(晴天)*p(穿短袖|晴天)=75\%*75\%=0.5625\approx56\%$p(穿短袖,晴天)=p(晴天)∗p(穿短袖∣晴天)=75%∗75%=0.5625≈56%

类似的，假设穿着已知，给定天气的条件概率如下：

• $p(下雨|穿雨衣)=50\%$p(下雨∣穿雨衣)=50%
• $p(下雨|穿短袖)=25\%$p(下雨∣穿短袖)=25%
• $p(晴天|穿雨衣)=8\%$p(晴天∣穿雨衣)=8%
• $p(晴天|穿短袖)=92\%$p(晴天∣穿短袖)=92%

则可以用另一个方式可视化上述的联合分布

编码 Code

在简单介绍了一个可视化概率的例子之后，我们将利用它进一步研究信息熵。信息熵从文字的编码（Code）讲起，现在假设你（Bob）要与你美国的朋友（Alice）通信，因为你是一个狗（dog）的爱好者，所以在你发给Alice的信件中dog的词汇出现频率较高；Alice是猫（cat）的爱好者，所以在她给你的信件中cat出现的频率较高。假设Bob的词向量词频分布为$p(x)$p(x)，Alice的词频分布为$q(x)$q(x)，则他们的分布如下(仅针对动物的词频)：

他们的词向量相同，不同的仅仅是词频的分布。现在Bob使用如下的编码格式进行发送，将每个单词用0-1来编码。

在发送的时候，将每个字符根据上述编码进行替换即可：

可变长度-编码（Variable-Length Code）

使用上述编码策略，我们平均需要2比特长度，对于每个字符：
$Average(L_{old})=\sum_{x\in X}p(x)L(x)=\frac{1}{2}\times 2+\frac{1}{4}\times 2+\frac{1}{8}\times 2+\frac{1}{8}\times 2=2 bit$Average(Lold​)=x∈X∑​p(x)L(x)=21​×2+41​×2+81​×2+81​×2=2bit
注意到上述编码并没有考虑词频的不同，而是统一用两个字符来编码，如果再多一个单词的话，则平均需要3个bit。学习过哈夫曼树的同学对于带权最短路径会想到，可以通过构建哈夫曼编码缩短上述的平均编码长度$Average(L_{old})$Average(Lold​)。新的编码策略如下：

在下图中，我们使用横轴表示编码长度$L(x)$L(x)，纵轴表示词频分布$p(x)$p(x)。则对比新旧的平均编码如下（矩形的面积）：

 

新的平均编码长度如下：
$Average(L_{new})=\sum_{x\in X}p(x)L(x)=\frac{1}{2}\times 1+\frac{1}{4}\times 2+\frac{1}{8}\times 3+\frac{1}{8}\times 3=1.75 bit$Average(Lnew​)=x∈X∑​p(x)L(x)=21​×1+41​×2+81​×3+81​×3=1.75bit
通过分析会发现，针对上述的词频分布，平均至少需要$1.75$1.75 bit，无论我们如何优化，都不可能小于这个值，这里可以将它理解为平均编码长度的一个下限。这个下限就是该分布的熵。

编码空间（The Space of Codewords）

针对老版本的编码，一个$bit$bit可以编码的字符数为$2^{1}$21；$n个bit$n个bit可以编码的长度为$2^{n}$2n个字符；但是在哈夫曼编码中，可变长的编码的空间是多少呢？ 答案是$2^{n-1}$2n−1 ，因为它需要另外$1 bit$1bit来保证前缀码的不同。

前缀码：在可变长的编码中，如果前缀码相同，是会引起歧义的，比如假设0 和 01 都在可变长的编码中都编码不同的字符，此时，当接收方解码的时候，它不知道是应该解码为{0和1}还是{01}为整体。换句话说，每个字符的编码都不应该是其它字符的前缀码。假设我们想编码4个字符(看作完全二叉树)，需要2个bit，为了保证前缀码不同，在两个分支上加1bit，保证前缀码不同。

为了缩小平均的编码长度，引入了可变长度的编码，但由于前缀码的原因，会损失掉一部分编码空间。例如假设我们使用了01编码一个字符，那么010,011…等等都不能再编码其它字符，如下图：

图中是3个bit编码的空间，因为拥有了一个2bit的编码(01)，我们损失了$\frac{1}{4}$41​的编码空间，同时这种损失也意味着其它字符需要更长的字符来编码。而且可以看到，越短的编码，它损失的空间越大，但是越短的编码，意味着越少的花费。此时有两个矛盾需要平衡：短编码花费少，但是损失了其它短编码的编码空间，使得其它字符需要更长的编码，其它字符则需要更多的花费。我们需要找到一种最优的编码来解决这个问题。

优化编码（Optimal Encodings）

单独考虑一个字符的编码。假设我们选择了1个长度的编码0，那么有0开头的任意长度的编码将不能使用，损失的空间是$\frac{1}{2}$21​；若继续选择长度为2的编码10，则损失的空间为$\frac{1}{4}$41​。随着编码长度$L$L的增加，损失呈指数型降低。如下图：

注意到一个字符如果用短的编码，它会减少信息长度，但是编码损失较高，比较
我们知道平均编码长度为$Average(L_{old})=\sum_{x\in X}p(x)L(x)$Average(Lold​)=∑x∈X​p(x)L(x)，可以用如下矩形的面积表示：

那怎么求解$L(x)$L(x)呢? 如下图， 因为是指数分布，函数图像为$y=2^{-x}$y=2−x,已知$y=p(a)=cost=\frac{1}{2^{L}}$y=p(a)=cost=2L1​, $x=-log_{2}^{y}=-log_{2}^{p(a)}$x=−log2y​=−log2p(a)​; 即$L(x)=log{(\frac{1}{p(x)})}=log{(\frac{1}{cost})}$L(x)=log(p(x)1​)=log(cost1​)。这里$y=p(a)=cost$y=p(a)=cost还可以这样理解，就是一个字符出现的概率越高，那么它的不确定性就越低，提供的信息就越少，所以和损失是正比的。

信息熵计算公式如下：$H(p)=\sum_{x}p{(x)}log_{2} \left(\frac{1}{p(x)}\right)$H(p)=x∑​p(x)log2​(p(x)1​)

交叉熵（Cross-Entropy）

交叉熵： 使用概率分布A进行最佳编码，使用分布B进行解码的平均长度。公式定义如下：$H_{p}(q)=\sum_{x}q(x)log_{2} \left(\frac{1}{p(x)}\right)$Hp​(q)=x∑​q(x)log2​(p(x)1​)
回顾Bob和Alice，他们的词向量一样，只是说的频率不一样，Bob的是$p(x)$p(x), Alice的是$q(x)$q(x)，则交叉熵可以用如下的图表示：

Bob和Alice都各有自己的最优编码，所以可以组合出2种熵和交叉熵(右下角编码器，括号内解码器)，如下：

• Bob使用Bob的编码 （$H_{p}(p)=1.75 bits$Hp​(p)=1.75bits ）
• Bob使用Alice的编码 （$H_{q}(p)=2.375 bits$Hq​(p)=2.375bits ）
• Alice使用Bob的编码 （$H_{p}(q)=2.25 bits$Hp​(q)=2.25bits ）
• Alice使用Alice的编码（$H_{q}(q)=1.75 bits$Hq​(q)=1.75bits ）

注意到交叉熵不是对称的，$H_{q}(p)\neq H_{p}(q)$Hq​(p)̸​=Hp​(q)，它衡量的是两个分布的不同。两个分布越接近，他们的交叉熵越小。当两个分布不同的时候，多出来的部分我们称之为Kullback–Leibler divergence (KL散度)，定义如***意解码器一致）：
$D_{q}(p)=H_{q}(p)-H(p)$Dq​(p)=Hq​(p)−H(p) $D_{p}(q)=H_{p}(q)-H(q)$Dp​(q)=Hp​(q)−H(q)
图示如下：

                

多变量的熵（Entropy and Multiple Variable）

会议之前穿衣服和天气的例子，它是一个多变量的分布，如图：

可以看出这个联合分布中一共包含4块内容，每块内容的概率也是知道的，知道了每块的概率，有上述熵的定义，我们可以求得它的编码长度，可视化如下：

我们称该联合分布的平均最短编码为$X$X和$Y$Y的联合熵，定义如下：
$H(X,Y)=\sum_{x,y}p(x,y)log_{2}\left(\frac{1}{p(x,y)}\right)$H(X,Y)=x,y∑​p(x,y)log2​(p(x,y)1​)

如果我们不把概率扁平化，采用三维的方式来可视化，那么熵就是下图中的体积。

假设现在我已经从天气预报中得知了天气状况，那么现在我还需要提供多少穿衣信息呢？【$p(x,y)\leq p(x|y)$p(x,y)≤p(x∣y)，因为后者乘了一个小于等于1的数$p(y)$p(y); 也就是说$p(x|y)$p(x∣y)概率更大，提供了更少的不确定性(只需提供更少的信息)，$L(x,y)=\log_{2}\left(\frac{1}{p(x|y)}\right)$L(x,y)=log2​(p(x∣y)1​) 越小】

从编码的角度讲，因为天气已知，我穿衣服的概率变了，也就是说 $p(x,y)$p(x,y) 变成了 $p(x|y)$p(x∣y)，我们需要重新设立一套更短编码，解码的概率是不变的，所以条件熵 就定义出来了，如下：
$H(X|Y)=\sum_{x,y}p(x,y)log_{2}\left(\frac{1}{p(x|y)}\right)$H(X∣Y)=x,y∑​p(x,y)log2​(p(x∣y)1​)

互信息（Mutual Information）

在上一节中，我们发现两个变量之间如果不独立，是存在一定的影响的。假设每个变量都包含了一定量的信息，用一个矩形条表示，那么联合概率 $H(X,Y)$H(X,Y) 包含的总信息应该是 $H(X)$H(X) 和 $H(Y)$H(Y) 的并集。如下图：

那缺掉的部分是什么呢？如图：

从图中可以看出 $H(X,Y)=H(Y)+H(X|Y)$H(X,Y)=H(Y)+H(X∣Y)，它表示 变量 $X$X 和 $Y$Y 包含的信息是由变量 $Y$Y 包含的信息 加上 在变量 $X$X 但不在 $Y$Y 中的信息 。如图：

通过进一步对变量 $X$X 和 $Y$Y 中包含的信息进行分析，可以得到如下图：
持续更新。。。