如何理解熵、交叉熵、KL散度、JS散度

在机器学习、深度学习中，经常听见熵（entropy）、交叉熵（cross-entropy）、KL散度（ Kullback–Leibler divergence ）、JS散度（ Jensen-Shannon divergence ）这些概念。初次听见这些概念肯定一头雾水，在很多地方都能见到对这些概念 high-level 的解释，但 high-level 的解释并不能对这些概念更深入的理解。比如熵是信息的度量，但是为什么熵可以用来作为信息的度量，则不知其缘由。接下来则由浅入深，深入理解这些概念。

编码（Codes）

在计算机中，任何信息都是用0、1来存储。所以为了将信息存储在计算机中，我们要将信息编码为 0、1串以便存储在计算机中。

假设 Bob 是一个动物爱好者，住在美国，他只谈论四种动物：dog、cat、fish、bird

为了和 Bob 进行交流，我们之间需要建立一个 code 把单词映射为 0、1 串。

这些0、1串在网络上传输需要消耗一定的带宽，所以我们希望0、1串越小越好，这样消耗的带宽就越小。如何对信息进行编码呢？

第一种方案：定长编码

发送信息时，只需要将相应的单词替换为对应的编码就行，例如：

第二种方案：变长编码

假设 Bob 非常喜欢狗，他谈论狗的频率比其它动物要高，假设谈论每个动物的概率如下所示。

为了减少带宽，一个直觉的编码方式为：对频率比较高的单词用较短的编码长度，频率比较低的单词使用较长的编码长度，这样最后得到的总长度是最小的。使用变长编码时，为了让解码唯一，可以使用哈夫曼编码来实现。一种变长编码方式为：

熵（Entropy）

以横轴表示每个单词的编码长度，纵轴表示谈论每种动物的频率。

使用定长编码时可以得到下图：

则发送一个单词所使用编码长度的期望（也可以看成图中的面积）为：
$\frac{1}{2}*2+\frac{1}{4}*2+\frac{1}{8}*2+\frac{1}{8}*2=2\ bits$21​∗2+41​∗2+81​∗2+81​∗2=2 bits

使用变长编码时可以得到下图：

则发送一个单词所使用编码长度的期望（也可以看成图中的面积）为：
$\frac{1}{2}*1+\frac{1}{4}*2+\frac{1}{8}*3+\frac{1}{8}*3=1.75\ bits$21​∗1+41​∗2+81​∗3+81​∗3=1.75 bits
使用哈夫曼编码定义的变长编码可以达到最优的期望，证明略。

所以熵可定义为：最优的平均编码长度（即期望），也即是图中的面积。

如何计算熵？

长度为 1 的有 2 种编码：0、1

长度为 2 的有 4 种编码：00、01、10、11

长度为 3 的有 8 种编码：000、001、010、011、100、101、110、111

以此类推…

为了获得最优编码长度常使用变长编码，而使用变长编码时，会损失一部分编码空间。例如：使用 01 作为某一个编码时，以 01 开头的那些编码都不能用（例：010、011、0100、0110…）。在所有编码种，有 $\frac{1}{4}$41​ 的编码以 01 开头，所以我们损失了 $\frac{1}{4}$41​ 的编码空间。

以此类推，当我们想使用一个长度为 $L$L 的编码长度时，损失了 $\frac{1}{2^L}$2L1​ 的编码空间。
$cost(L)=\frac{1}{2^L}$cost(L)=2L1​

$L=log_2(\frac{1}{cost})=log_2(\frac{1}{2^L})$L=log2​(cost1​)=log2​(2L1​)

同理，为了获得某个单词 $x$x 的编码，花费了 $p(x)$p(x) （注：$p(x)$p(x) 为某一个单词的概率，这个概率可以看作 $cost$cost ）。单词 $x$x 的编码长度为：

$L(x)=log_2(\frac{1}{p(x)})$L(x)=log2​(p(x)1​)

设 $p$p 为单词词频的概率分布，$p$p 的最优平均编码长度定义为 $p$p 的 熵 $H(p)$H(p):
$H(p) = \sum_x p(x)\log_2\left(\frac{1}{p(x)}\right)=- \sum p(x)\log_2(p(x))$H(p)=x∑​p(x)log2​(p(x)1​)=−∑p(x)log2​(p(x))

交叉熵（Cross-Entropy）

假设我还有一个朋友 Alice，她喜欢猫，她的词频概率如下图 $q(x)$q(x) 所示：

当 Alice 使用 Bod 的编码和我进行通信时，她的平均编码长度为：
$\frac{1}{8}*1+\frac{1}{2}*2+\frac{1}{4}*3+\frac{1}{8}*3=2.25\ bits$81​∗1+21​∗2+41​∗3+81​∗3=2.25 bits
交叉熵可定义为：当某一个分布（ 这里为 $q(x)$q(x) ）使用另一个分布（ 这里为 $p(x)$p(x)）的最优编码长度进行编码时的平均编码长度。
$H_p(q) = \sum_x q(x)\log_2\left(\frac{1}{p(x)}\right)=-\sum_x q(x)\log_2\left(p(x)\right)$Hp​(q)=x∑​q(x)log2​(p(x)1​)=−x∑​q(x)log2​(p(x))

有四种情况：

• Bob 使用他自己的编码 ( $H(p)=1.75\ bits$H(p)=1.75 bits )
• Alice 使用 Bob 的编码 ( $Hp(q)=2.25\ bits $)
• Alice 使用她自己的编码 ( $H(q)=1.75\ bits$H(q)=1.75 bits )
• Bob 使用 Alice 的编码 ( $Hq(p)=2.375\ bits$Hq(p)=2.375 bits )

可以发现：$H_p(q) \neq H_q(p)$Hp​(q)​=Hq​(p) ，即：交叉熵并不对称。

我们为什么要关注交叉熵？因为交叉熵给我们提供了一个方式来度量两个概率分布有多相同。

如果概率分布 $p$p 和 $q$q 越不相似，$p$p 对 $q$q 的交叉熵比 $p$p 自己的熵更大，即：

同理，$q$q 对 $p$p 的交叉熵比 $q$q 自己的熵更大

KL散度（ Kullback–Leibler divergence ）

$p$p 对 $q$q 的KL散度定义为：分布 $p$p 使用 $q$q 的最优编码进行编码时的平均编码长度（ $p$p 对 $q$q 的交叉熵 ）与 分布 $p$p 的最优平均编码长度（ $p$p 的熵 ）的差值。
KaTeX parse error: No such environment: equation at position 8: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲}̲ \begin{split} …
KL散度有点像一种距离，用来度量两个分布之间的差距。如果 $p$p 和 $q$q 相同，则KL散度为0。$p$p 和 $q$q 越不相同，KL散度越大。

KL散度也是不对称的。

JS散度（ Jensen-Shannon divergence ）

JS散度基于KL散度，是一个对称平滑版本的KL散度。

$p$p 对 $q$q 的JS散度定义为：
$D_{JS}(p||q)=\frac{1}{2}D_{KL}(p||m)+\frac{1}{2}D_{KL}(q||m),\ where\ m=\frac{1}{2}(p+q)$DJS​(p∣∣q)=21​DKL​(p∣∣m)+21​DKL​(q∣∣m), where m=21​(p+q)