从第一性原理理解熵

2025年1月1日

我发现熵极其迷人。然而，将公式 $\sum p_{i} lo g \frac{1}{p _{i}}$ 与其与“直观”解释（如前缀自由码和信息内容）联系起来并不显而易见。在这里，我想探讨几种独立推导这一概念的方法。

信息的性质

假设我们想要定义一个函数 $I$ ，它表示事件的信息量。抛开事件的具体细节，我们可以使用一个度量来比较不同事件，即它们发生的概率。因此， $I$ 可以是从概率 $p \in [0, 1]$ 到 $R$ 的映射。基于这种框架，以下要求是合理的：

$I (1) = 0$ 。如果一个事件肯定发生，它并不有趣，提供的信息也很少。
$I$ 应该在 $[0, 1]$ 上连续且单调递减。更常见的事件提供的信息较少。
两个独立事件的概率分别为 $p$ 和 $q$ 时，它们的信息量应为 $I (p) + I (q)$ 。

最后一个要求最能说明问题。根据定义，两个独立事件同时发生的概率为 $pq$ 。因此，

I (pq) = I (p) + I (q) .

由于函数必须是连续的，这只有在以下情况下成立：

I (p) = c lo g p .

如果我们希望 $I$ 是单调递减的，

\frac{d I}{d p} = c / p

必须为负。由于 $p$ 为正， $c$ 必须为负。设 $c^{'} = ∣ c ∣$ ，则

I (p) = c^{'} lo g \frac{1}{p}

由于 $lo g_{a} b = \frac{l o g b}{l o g a}$ ，其中分母是常数，我们可以将 $c^{'}$ 视为对数的底数。为了方便起见，我们设 $c^{'}$ 为 1，并让 $lo g$ 表示以 2 为底的对数。

熵就是 $I$ 在分布 $p = (p_{1}, p_{2}, \dots, p_{n})$ 上的期望值：

H (p) = i = 1 \sum n p_{i} lo g \frac{1}{p _{i}}

我们还假设 $H (0) = 0 lo g \frac{1}{0} = 0$ ，这是基于连续性的考虑。

例如，考虑伯努利随机变量 $B_{p}$ ，它以概率 $p$ 取值 $1$ ，以概率 $1 - p$ 取值 $0$ 。如果我们绘制其熵

绘图代码

import numpy as np
import plotly.graph_objects as go

# 计算伯努利变量熵的函数
def bernoulli_entropy(p):
    return -p * np.log2(p) - (1 - p) * np.log2(1 - p)

# 生成从 0 到 1 的 p 值
p_values = np.linspace(0.01, 0.99, 100)
entropy_values = bernoulli_entropy(p_values)

# 创建绘图
fig = go.Figure()

# 添加熵的轨迹
fig.add_trace(go.Scatter(x=p_values, y=entropy_values, mode='lines', name='Entropy', line=dict(color='red')))

# 更新布局以适应暗黑模式
fig.update_layout(
    title='伯努利随机变量的熵',
    xaxis_title='p',
    yaxis_title='熵',
    template='plotly_dark'
)

# 将绘图保存为 HTML 文件
fig.write_html("bernoulli_entropy_plot.html")

我们可以看到，当分布均匀时，熵达到最大值；当分布几乎确定时，熵达到最小值。

前缀码

假设我们有一组符号 $X = {X_{1}, \dots, X_{M}}$ ，我们希望通过二进制信道传输这些符号。我们构建信道，使得每次可以发送一个 $1$ 或 $0$ 。我们希望为 $X$ 找到一个最优的编码方案，但有一个要求：它必须是前缀码。

我们定义一个编码函数 $f : X \to {0, 1}^{+}$ ，它将符号映射为长度 $\geq 1$ 的二进制字符串。如果没有任何一个码字是另一个码字的前缀，我们就说这个编码是前缀码。例如， ${0, 01}$ 不是前缀码，因为 $0$ 是 $01$ 的前缀。然而， ${0, 10}$ 是前缀码。

前缀码意味着该编码是唯一可解码的，无需在符号之间添加额外的分隔符，这是一个非常理想的特性。

我们还注意到，二进制前缀码可以由一棵二叉树唯一确定：

前缀码的二叉树 — 来源：https://leimao.github.io/blog/Huffman-Coding

其中，从根到符号的路径决定了码字，而符号始终是叶子节点。请确保自己理解，任何这样的构造都会产生一个前缀码。

我们现在将证明，任何前缀码在 $X$ 上的期望码字长度 $L$ 满足以下不等式：

H (X) \leq L < H (X) + 1.

其中， $X$ 是一个随机变量，它从集合 $X$ 中取值，概率为 $(p_{1}, \dots, p_{n})$ 。最重要的是，我们看到 $X$ 的熵是分布可以被压缩的下限，或者说，它包含的信息量的下限。

克拉夫特不等式

假设 $l_{i}$ 是第 $i$ 个码字的长度。如果该编码是前缀无关的：

i = 1 \sum M 2^{- l_{i}} \leq 1

证明：

设 $l_{max}$ 为最长码字的长度。我们注意到：

在第 $l_{max}$ 层最多有 $2^{l_{max}}$ 个节点。
对于任何长度为 $l_{i}$ 的码字，在第 $l_{max}$ 层有 $2^{l_{max} - l_{i}}$ 个后代。
每个码字的后代集合是互不相交的（因为一个码字永远不会是另一个码字的后代）。

这些意味着

⟹ i \sum 2^{l_{max} - l_{i}} \leq 2^{l_{max}} i \sum 2^{- l_{i}} \leq 1.

为什么是 $\leq$ 而不是等号？因为有可能在第 $l_{max}$ 层的某个节点不是任何码字的后代（考虑编码 ${10, 11}$ 的树）！

L 的下界

现在，我们考虑期望码字长度

L = i \sum p_{i} l_{i}

我们将证明熵是 $L$ 的下界，即

H (X) \leq L ⟺ L - H (X) \geq 0

证明:

L - H (X) = i \sum p_{i} l_{i} + i \sum p_{i} lo g p_{i} = - i \sum p_{i} lo g 2^{- l_{i}} + i \sum p_{i} lo g p_{i} = - i \sum p_{i} lo g 2^{- l_{i}} + i \sum p_{i} lo g p_{i} + i \sum p_{i} lo g (j \sum 2^{- l_{j}}) - i \sum p_{i} lo g (j \sum 2^{- l_{j}}) = i \sum p_{i} lo g \frac{p _{i}}{2 ^{- l_{i}} / \sum _{j} 2 ^{- l_{j}}} - i \sum p_{i} lo g (j \sum 2^{- l_{j}}) = D_{K L} [p ∣∣ q] + lo g \frac{1}{c} \geq 0

其中，最终不等式成立的原因有两个：1) KL 散度是非负的；2) 由于 Kraft 不等式， $c \leq 1$ 。需要注意的是，如果 $l_{i} = - lo g p_{i}$ ，则 $L = H (X)$ ，这是理论上的最小值。我们无法总是达到这个最小值的原因是 $- lo g p_{i}$ 不一定是整数，而这显然是必需的。

L 的上界

注意到可以构造一个长度如下的前缀码：

l_{i} = ⌈ - lo g p_{i} ⌉

因为它们满足 Kraft 不等式：

i \sum 2^{- l_{i}} \leq i \sum 2^{l o g p_{i}} = 1

根据取整函数的定义，

- lo g p_{i} \leq l_{i} < - lo g p_{i} + 1

对 $p$ 取期望，我们得到

- \sum p_{i} lo g p_{i} \leq \sum p_{i} l_{i} < - \sum p_{i} lo g p_{i} + 1 ⟹ H (X) \leq L < H (X) + 1

这表明 $H (X) + 1$ 是 L 的一个良好上界！

总结来说，熵是编码一个分布为前缀码所需的平均比特数的下界，也是一个合理的估计。

参考文献

Alon Orlitsky 的 ECE 255A 课程讲座，加州大学圣地亚哥分校
Cover, T. M., & Thomas, J. A. (2006). 信息论基础. Wiley-Interscience.

←

交互式高斯混合模型