ML的信息论基石-kraft不等式，信息熵，KL散度

一、基本名词与概念

1. 前缀码与前缀自由码

• 前缀码：没有一个码字是另一个码字的前缀。例如霍夫曼码。
• 重要性：前缀码满足即时唯一可译性（译码时不会二义并且即时解码AA）。

---

2. Kraft不等式

Kraft不等式是信息论中关于前缀编码（或者说前缀码树/二叉树）的一个重要结论。它说明任意一组前缀码的码长 $ l_1, l_2, \ldots, l_n $ 必须满足

$ \sum_{i=1}^n 2^{-l_i} \leq 1 $

反之，只有满足这个不等式才有可能存在对应的前缀码。

Kraft不等式证明

必要性（任何前缀码的一组码长都满足Kraft不等式）：

设$ D $为二叉树，每个码字可表示为树的一条路径。

• 码长为 $ l_k $ 的码字在树的第 $ l_k $ 层，是一个叶子。
• 每一层最多有 $ 2^{l_k} $ 个节点，叶子节点互不重叠。
• 所有码字实际占用的叶子数之和

$ \sum_{i=1}^n 2^{L-l_i} $

其中 $ L $ 为所有码长的最大值。

• 总叶子数为 $ 2^L $
• 所以有

$ \sum_{i=1}^n 2^{L-l_i} \leq 2^L \implies \sum_{i=1}^n 2^{-l_i} \leq 1 $

补充：什么叫码字实际占用的叶子数之和？

假设我们最大码长是 $ L $，再看一个码字长度是 $ l $。

• 一个长度为 $ l $ 的码字，从根到它走了 $ l $ 步。
• 如果继续从它往下走，走满长度 $ L $，还能走 $ (L-l) $ 步。
• 每多一步可分岔两路，$ (L-l) $_ 步一共可以分成 $ 2^{L-l} $ 个不同的终点（叶子）。_
• 所以长度为 $ l $ 的码字，等价于在最大深度 $ L $ 处“占用”了 $ 2^{L-l} $ 个叶子。

充分性（只要码长满足Kraft不等式，就能构造前缀码）：

• 将所有 $ l_i $ 从小到大排序。
• 从编码树顶部出发，依次分配以 $ l_i $ 为长度的唯一路径（即叶子结点）；因Kraft不等式成立，子树不会重叠，必能分配完全部码字且不会出现有一个码字是其他码字前缀的情况。
• 具体可采用“字典树”方式依次分配。

---

3. 信息熵（Shannon Entropy）

对离散信源$ X $（概率分布为 $ {p_1, p_2, …, p_n} $）：

$ H(X) = -\sum_{i=1}^n p_i \log_2 p_i $

• 渐进意义下，熵是最优平均编码长度的下界。

---

4. 最优编码定理

• 平均码长的最小值为熵或近似熵（$ \lceil l_i \rceil $ 情况下高于熵但不会超过1bit）：

$ H(X) \leq L^* < H(X) + 1 $

• 相关推导正是“在Kraft约束下极小化码长”——见“熵的最优性推导”小节。

---

5. 交叉熵与KL散度

• 交叉熵 $ H(P, Q) $：用$ Q $分布编码真实分布$ P $的信息平均长度：

$ H(P, Q) = -\sum_x p(x) \log q(x) $

• KL散度（相对熵）：

$ D_{KL}(P | Q) = \sum_x p(x) \log \frac{p(x)}{q(x)} = H(P, Q) - H(P) $

• 表示用$ Q $代替$ P $时的“额外码长”。

---

二、Kraft不等式、信息熵与最优编码

核心联系如下：

1. Kraft不等式规定了前缀码的结构界限。
2. 最优编码定理是在Kraft不等式约束下，令平均码长最小化，推导出平均码长的理论下界——即“熵”。
3. 信息熵本质上就是“前缀码最优情况下，每个符号理论上所需的最小bit数（平均）”。

---

熵的最优性：如何由Kraft不等式推出熵

极小化平均码长

$ \min \sum_{i=1}^n p_i l_i $

约束：

$ \sum_{i=1}^n 2^{-l_i} \leq 1 $

用拉格朗日方法或直接解得，最优解满足

$ l_i = -\log_2 p_i $

此时

$ L^* = \sum_i p_i l_i = H(X) $

这表明信息熵即为满足Kraft不等式的最优平均编码长度的理论极限。

---

三、各部分逻辑关系

1. Kraft不等式 —— 判断前缀码能否存在及如何分配码长；
2. 最优编码定理 —— 利用Kraft不等式约束，推导信息熵作为平均码长理论下界；
3. 信息熵 —— 度量信源不确定性，也限制度量最优编码效率；
4. 交叉熵/相对熵 (KL散度) —— 两个概率分布编码效率的度量，机器学习损失函数常用。

---

简要表格

概念	数学表达	目的/意义
Kraft不等式	$ \sum 2^{-l_i} \leq 1 $	判断能否分配码长形成前缀码
信息熵	$ H(X) = -\sum p_i \log_2 p_i $	不确定性度量、最优平均码长下界
最优编码定理	$ H(X) \leq L^* < H(X)+1 $	连接实际编码与熵的极限
交叉熵	$ H(P, Q) = -\sum p(x)\log q(x) $	“用Q表示P”的平均信息长度
KL散度	$ D_{KL}(P	Q)=\sum p(x)\log\frac{p(x)}{q(x)} $

参考

https://www.bilibili.com/video/BV1sV411k7qc/