杂文：什么是信息熵（WIP）

事件的信息熵

信息熵（下文简称熵）由香农提出，指的是无损编码事件信息的最小可能长度；换句话说，也可以认为是要传递某个概率性事件结果的信息时，我们所需要的期望比特数的最小值。记 $H(X)$ 表示事件 $X$ 的信息熵。

举个例子，投一个硬币，硬币正反面是概率性事件。在二进制下，我们可以用 $1$ 个 bit $\in {0, 1}$ 来传递“硬币的结果是正还是反”这个信息。因为传递该信息的期望 bit 数最少为 $1$，所以信息熵就是 $1$。

类似地，对一个“有 $n$ 种不同结果”的等概率事件，传递该信息的期望 bit 数最少为 $\log n$ 个，因此其信息熵为 $\log n$。虽然 $n = 5$ 时 $\log 5$ 不是整数，但我们仍然这么定义，原因会在之后说明。

接下来考虑不等概率事件。

例如一个正面概率 $0.2$、反面概率 $0.8$ 的硬币，我们可以分为两个事件考虑。对正面而言，发生正面的概率等于从 $5$ 个球中摸出第一个球的概率，故“传递正面”这个信息的信息熵为 $\log 5$；反面同理为 $\log 1.25$。因此传递该信息的期望 bit 数最少为

$$H(X) = 0.2\log 5 + 0.8\log 1.25$$

类似地，对有一个有 $n$ 个不同结果的事件（可以是等概率事件），设发生第 $i$ 个结果概率为 $P_i$，则该事件的信息熵

$$H(X) = -\sum_{i = 1}^n P_i\log P_i$$

为什么不需要上取整

在上节中，我们声称等概率事件的信息熵是 $\log n$。即使定义为 $\lceil \log n \rceil$，仍然符合我们先前的声明。

我们不进行上取整，是因为不等概率事件的信息熵不可以上取整。对于这一问题，笔者大胆做出如下推测（不保证正确性）：这是因为，在等概率事件中，我们用 $\lceil \log n \rceil$ 个 bit 实际上能表示 $2^{\lceil \log n \rceil} \geq n$ 种结果，还有多出来的一些信息被我们遗弃掉，不能使用；但在不等概率事件中，这部分多出来的信息可以被其他的结果利用。

下面举一个简单的反例：对一篇只有 abc $3$ 个字母的文章，假设 a 出现概率 $0.8$，b、c 出现概率 $0.1$，我们可以算出信息熵

$$H(X) = -0.8\log 0.8 - 0.1\log 0.1 - 0.1\log 0.1 \approx 0.9219$$

我们可以用 $1, 00, 01$ 分别表示 a, b, c（这个编码是前缀不重复的），则期望编码长度为

$$0.8 \times 1 + 0.1 \times 2 + 0.1 \times 2 = 1.2 > 0.9219$$

但如果采用上取整，则 $-0.8\lceil\log 0.8\rceil - 0.1\lceil\log 0.1\rceil - 0.1\lceil\log 0.1\rceil = 1.6 > 1.2$，计算错误。

特别注意：这里我们采用的编码之所以长度不同，是因为前缀不重复。也就是说，当接收者接收到 $1$ 时就能明白它对应 a，可以立即关闭接受，因此传递 a 只需要 $1$ 个 bit。我们不能采用 ${0, 1, 01}$ 编码，因为当接受 $0$ 时接收者不确定是否要关闭接受，除非告诉其是否关闭接受；然而告诉其是否接受也是传递一个信息 bit $\in {0, 1}$，所以这样的编码是无效的。

多个变量的熵

联合熵（Joint Entropy）：$H(X, Y) = -\sum \sum P(x, y) \log P(x, y)$

条件熵（Conditional Entropy）：$H(Y | X) = \sum P(x) H(Y | X = x) = -\sum \sum P(x, y) \log P(y | x)$

$$H(X, Y) = H(X) + H(Y|X)$$