熵

我们应该如何高效地编码信息？

我们不妨构建一个具体的、简单的场景。假设我正在与你进行秘密通信，通信内容只有四种可能的消息：A、B、C、D。为了能在信道里传输，我们必须将这些消息编码为二进制的 0 和 1。

最直接、最不动脑子的想法，我想应该是“等长编码”，比如下面这样：

A -> 00
B -> 01
C -> 10
D -> 11

这种方式很公平，每个消息都用 2 个比特来表示。但它一定是最高效的吗？答案显然是否定的。

如果这四种消息出现的概率并不均等，比如说，它们遵循一个真实的消息概率分布 $p$： $p(A)=\frac{1}{2},p(B)=\frac{1}{4},p(C)=\frac{1}{8},p(D)=\frac{1}{8}$

可以看到，消息A出现的频率非常高。在这种情况下，还给如此频繁的A分配一个长度为 2 的编码，似乎就有些浪费了。一个很自然的想法涌上心头：我们应该给越频繁出现的消息，分配越短的编码；给越罕见的消息，分配越长的编码。这样一来，从整体上看，我们传输的总比特数就会更少。

这就是“变长编码”思想的起源，也是信息论的基石。顺着这个思路，我们可以设计了一个可行的变长编码方案（这恰好是哈夫曼编码的结果）：

A -> 0
B -> 10
C -> 110
D -> 111

现在，让我们来算算这种新编码方式的“平均编码长度”。

熵：理论上最完美的平均编码长度

在上面的变长编码例子中，我们传输大量消息后，平均每个消息需要多少比特呢？这个期望值不难计算，我们只需将每个消息的概率与其编码长度相乘，然后求和：

$$L=p(A)\cdot 1+p(B)\cdot 2+p(C)\cdot 3+p(D)\cdot 3$$

代入具体的数值就是：

$$L=\frac{1}{2}\times 1+\frac{1}{4}\times 2+\frac{1}{8}\times 3+\frac{1}{8}\times 3=0.5+0.5+0.375+0.375=1.75\text{bit}$$

看，这个结果是 1.75 比特，比我们之前等长编码的 2 比特要短，说明我的策略是有效的。

这时候，一个更深刻的问题浮现了：1.75 比特是最好的结果吗？我们还能不能设计出更好的编码，让平均长度更短？

香农早已给了我们答案。他指出，对于一个给定的概率分布 $p(x)$，存在一个理论上的“最短平均编码长度”，任何无歧义的编码方案的平均长度都不可能比它更短。这个理论上的最优值，就被定义为该分布的信息熵（Entropy）。

它的计算公式是：

$$H(p)=\sum _{x}p(x)\cdot (-{\log }_{2}p(x))$$

这里的 $-{\log }_{2}p(x)$ 就代表了理论上编码一个概率为 $p(x)$ 的事件所需要的最优编码长度。这非常符合我们的直觉：概率 $p(x)$ 越小，事件越“出乎意料”，那么 $-{\log }_{2}p(x)$ 的值就越大，意味着需要更长的编码来表示它。

我们来为上面例子的真实分布 $p$ 计算一下它的熵：

$$H(p)=-\left(\frac{1}{2}{\log }_2\frac{1}{2}+\frac{1}{4}{\log }_2\frac{1}{4}+\frac{1}{8}{\log }_2\frac{1}{8}+\frac{1}{8}{\log }_2\frac{1}{8}\right)$$ $$H(p)=\frac{1}{2}\times 1+\frac{1}{4}\times 2+\frac{1}{8}\times 3+\frac{1}{8}\times 3=1.75\text{ bit}$$

这个计算结果非常奇妙：我们凭直觉设计的那个变长编码方案，其平均长度不多不少，正好等于这个分布的信息熵！这说明那个方案已经达到了理论上的最优状态，不可能再有比它更好的了。

所以，现在我们可以给熵一个更具体、更物理的解释了：

Note

熵 $H(p)$，是基于真实分布 $p$ 进行最优编码时，所需要的平均编码长度。它是我们能达到的最好性能的基准（Benchmark）。

交叉熵：用“错误”的尺子来度量

现在，关键的问题来了。在现实世界中，我们往往并不知道那个“真实”的分布 $p$ 究竟是什么。我们只能根据有限的观察，去猜测和构建一个模型，我们把这个模型产生的分布记为 $q$。

比如说，我们可能错误地以为A、B、C、D是等概率出现的，那么我们猜测的分布 $q$ 就是：

$$q(A)=\frac{1}{4},q(B)=\frac{1}{4},q(C)=\frac{1}{4},q(D)=\frac{1}{4}$$

如果我们基于这个错误的分布 $q$ 来设计我们的编码方案，那么根据最优编码长度的原则（长度 $\approx -{\log }_{2}q(x)$），我们会选择之前那个“等长编码”，因为对所有消息 $x$，$-{\log }_2(\frac{1}{4})=2$：

A -> 00 (长度为 2)
B -> 01 (长度为 2)
C -> 10 (长度为 2)
D -> 11 (长度为 2)

现在，我们拿着这套基于 $q$ 设计的编码方案，去编码实际上按照 $p$ 分布产生的消息。这时候，实际的平均编码长度会是多少呢？

我们还是用期望的公式来计算，只不过，事件发生的概率要用真实的 $p(x)$，而每个事件的编码长度则要用基于 $q(x)$ 设计的那个，也就是 $-{\log }_{2}q(x)$。于是，平均编码长度就变成了：

$$H(p,q)=\sum _{x}p(x)\cdot (-{\log }_{2}q(x))$$

这个量，就叫做分布 $p$ 和 $q$ 之间的交叉熵。它的物理意义很明确：用根据分布 $q$ 设计的最优编码，去编码来自真实分布 $p$ 的消息，所得到的平均编码长度。

我们来计算一下这个例子的交叉熵：

$$H(p,q)=p(A)(-{\log }_{2}q(A))+p(B)(-{\log }_{2}q(B))+p(C)(-{\log }_{2}q(C))+p(D)(-{\log }_{2}q(D))$$ $$H(p,q)=\frac{1}{2}\times 2+\frac{1}{4}\times 2+\frac{1}{8}\times 2+\frac{1}{8}\times 2=1+0.5+0.25+0.25=2\text{ bit}$$

这个结果是 2 比特，果然比我们之前计算出的最优长度 1.75 比特要长。

这里的交叉熵，其实也是我们在深度学习多分类任务里常常遇到的一个损失函数， p(x) 其实就是那个 OneHot, 而 q(x) 就是模型的输出。