本页目录

信息论 I · 熵与信源编码

信息论把"信息"变成可计算的量。全站已多次借用它的概念（决策树的熵、LLM 的交叉熵），本课给它们正式户口。第一页回答两个问题：不确定性怎么度量（熵——而且是公理逼出来的唯一答案）、数据最多能压到多小（信源编码定理：答案还是熵）。

先修入口：随机变量、矩与期望。本页先使用有限字母表、以 2 为底的对数；零概率项按 \(0\log0=0\) 处理。

1. 自信息与熵

二元熵曲线 — 图 1.1二元熵 \(H(p)\)：不确定性在 \(p=0.5\)（最难猜）时最大 1 bit、在确定事件（\(p=0\) 或 \(1\)）时为零——熵是"平均意外程度"。

学习层：先预测四符号码的平均长度

具体谜题：非二进概率怎样落到整数码长？

固定一个无记忆信源

\[ P(A,B,C,D)=(0.4,0.3,0.2,0.1). \]

先不看实验台，预测三件事：

定长码、一符号 Huffman 码、二符号分组 Huffman 码，哪一个每个源符号的平均码长最低？
下面这棵确定性 Huffman 树的 Kraft 和会不会超过 1？
熵 \(H\) 是不是每一条消息都能兑现的整数 bit 数？

这个分布是刻意选的：四个概率都不是 \(2^{-k}\) 的整齐边界。Huffman 保证最小平均码长，但最优码字、甚至各符号的码长都未必唯一。为复现实验中的确定性码字，优先队列先按“权重、子树中最早的原符号次序”排序；每次合并后，再把含较早原符号的子树放在左侧。于是

\[ A\mapsto0,\qquad B\mapsto10,\qquad C\mapsto110,\qquad D\mapsto111. \]

无 JavaScript 时的静态读法：对上述 \(P\)，一符号 Huffman 码的账本为

符号	\(P\)	码字	长度	理想长度 \(-\log_2P\)
\(A\)	0.4	0	1	1.321928
\(B\)	0.3	10	2	1.736966
\(C\)	0.2	110	3	2.321928
\(D\)	0.1	111	3	3.321928

因此

\[ \begin{aligned} H&=-\sum_i p_i\log_2p_i=1.846439\text{ bits},\\ L_1&=0.4(1)+0.3(2)+0.2(3)+0.1(3)=1.9\text{ bits},\\ \sum_i2^{-\ell_i}&=2^{-1}+2^{-2}+2^{-3}+2^{-3}=1. \end{aligned} \]

定长码需要 \(\lceil\log_2 4\rceil=2\) bits/符号。若把独立源符号两两分组，对 16 个块的乘积分布再作 Huffman，默认确定性树给出约 \(L_2/2=1.865000\) bits/源符号；分组长度 \(g=3\) 时约为 \(1.859000\)。分组的改善来自块级整数码长更细地逼近 \(gH\)，不是把单个符号的码长变成分数。

这里确实有

\[ H\le L_1=1.9<H+1=2.846439, \]

但它是平均值的定理。\(A\) 的这一条消息用 1 bit，\(D\) 的这一条消息用 3 bits；某一条消息的长度可以高于或低于 \(H\)。更不能把“渐近平均极限”读成“每条消息都能无损压到 \(H\) bits”：\(H\) 通常不是整数，信源编码定理说的是长序列、平均每符号码长可以逼近 \(H\)，并不承诺单次消息或任意有限 block 恰好达到它。

反例与迁移

如果把 \(P\) 换成带强上下文的字符流，独立乘积分布 \(P(a)P(b)\) 就不再是块的真实分布；此时更好的分组码可能只是错误模型的幻觉。迁移练习：保留同一四符号边缘分布，改变相邻符号的相关性，重新问“块 Huffman 的平均长度”和“熵率”分别由什么决定。

迁移核对：同一边缘分布，不同熵率

先在平稳初态抽一个 \(X_1\sim P\)，以后永远令 \(X_t=X_1\)。每个时刻的边缘仍为 \((0.4,0.3,0.2,0.1)\)，但 \(H(X_{1:n})=H(P)\)，故每符号熵率 \(\lim_n H(X_{1:n})/n=0\)。若解码器知道总长度，只需把首符号用平均 1.9 bit 编码，之后重复即可；真实两符号块只有 AA、BB、CC、DD，块 Huffman 的平均每符号长度为 \(1.9/2=0.95\) bit，而不是独立模型的 1.865 bit。不能用边缘熵替代熵率。

再看最优码长的非唯一性：对 \(P=(0.4,0.2,0.2,0.1,0.1)\)，长度组 \((1,3,3,3,3)\) 与 \((2,2,2,3,3)\) 的 Kraft 和都为 1，平均长度都为 2.2 bit；相应前缀码可取 \((0,100,101,110,111)\) 和 \((00,10,11,010,011)\)。两种合法 Huffman 并列选择会得到不同树。实验只是固定了一种可复现约定。

自信息：事件发生所携带的"惊讶度" \(I(x) = -\log p(x)\)（以 2 为底单位比特）。为什么必须是对数？三条公理锁死：惊讶度只依赖概率且随 \(p\) 递减、对 \(p\) 连续、独立事件的惊讶度相加（\(I(pq) = I(p) + I(q)\)）——柯西函数方程仅有对数解（与决策树页熵公理化同一论证的事件版）。比例常数由单位约定确定，例如 \(I(1/2)=1\) bit；并非仅凭三条性质就固定了对数底数。小概率事件信息量大："狗咬人"不是新闻。

熵：平均惊讶度

\[ H(X) = -\sum_x p(x)\log p(x) = E[-\log p(X)] \]

基本性质：

\(0 \leq H(X) \leq \log|\mathcal{X}|\)：下界当且仅当退化分布（毫无悬念），上界当且仅当均匀分布（Jensen 一行证——最大悬念是等可能）；
二元熵 \(h(p) = -p\log p - (1-p)\log(1-p)\)：在 \(p = \frac12\) 处峰值 1 比特——公平硬币是最难猜的硬币；
直觉标定：若每个问题对应前缀码的一位，最优二叉提问树的平均问题数 \(L^*\) 满足 \(H\le L^*<H+1\)；只有概率恰能由二叉树叶深表示（典型地 \(p_i=2^{-\ell_i}\)，即 dyadic 分布）时才可能达到 \(L^*=H\)。所以熵是下界，不总是某棵单符号提问树的精确平均深度。

联合熵与条件熵：\(H(X, Y) = E[-\log p(X,Y)]\)；\(H(Y \mid X) = E[-\log p(Y \mid X)]\)（知道 \(X\) 后对 \(Y\) 剩余的不确定性）。

链式法则：\(H(X, Y) = H(X) + H(Y \mid X)\)（对数把乘法概率变加法——概率 I 乘法公式取对数即得）。

信息不增原理：\(H(Y \mid X) \leq H(Y)\)，取等当且仅当独立——多看一眼不会更糊涂（平均意义；个别观测可以增加困惑）。差值就是下一页的互信息。

2. 信源编码：熵是渐近平均极限

问题：给字符分配 0/1 码字，要求前缀码（无码字是另一码字的前缀——即时可解），最小化平均码长 \(L = \sum p_i \ell_i\)。

Kraft 不等式：长度 \(\{\ell_i\}\) 的前缀码存在 \(\iff \sum_i 2^{-\ell_i} \leq 1\)。（证明直觉：把码字看作满二叉树的叶子，长度 \(\ell\) 的码字占据整棵树 \(2^{-\ell}\) 的"份额"，总份额不超过 1。）

定理（Shannon 信源编码定理） 令有效支撑为 \(\mathcal S=\{x:p(x)>0\}\)。当 \(|\mathcal S|\ge2\) 时，任何覆盖该支撑的前缀码都有 \(L \geq H(X)\)，且存在编码使 \(L < H(X) + 1\)。零概率标签不必占据码树叶；若 \(|\mathcal S|=1\) 且解码器从外部知道符号个数，可用空码字得到 \(L=H=0\)。

下界证明骨架（两行，值得记）：\(L - H = \sum p_i \ell_i + \sum p_i \log p_i = -\sum p_i \log\frac{2^{-\ell_i}}{p_i} \geq -\log\sum 2^{-\ell_i} \geq 0\)——中间是 Jensen（\(\log\) 凹），末尾是 Kraft。\(\blacksquare\)

上界与分组为什么成立：在正概率支撑上取 Shannon 码长 \(\ell_i=\lceil-\log_2p_i\rceil\)，则 \(2^{-\ell_i}\le p_i\)，Kraft 和不超过 1，因此存在相应前缀码；又因 \(\ell_i<-\log_2p_i+1\)，平均后得到 \(L<H+1\)。Huffman 的平均长度不会比这个可行码更大。若 \(g\) 个符号独立同分布，块熵为 \(gH\)，于是块最优码满足

\[ H\le \frac{L_g^*}{g}<H+\frac1g. \]

这才给出“分组把每符号冗余压到零”的推理链；有相关性时，先把 \(gH\) 换成真实块熵 \(H(X_{1:g})\)。

读法：最优码长 \(\ell_i^* \approx -\log p_i\)（高频短码、低频长码——摩尔斯电码的 e 是一个点，直觉先于理论一百年）；熵是压缩的渐近平均下界——它不是每条消息的长度，也不是“每条消息都能无损压到 \(H\) bits”的承诺。Huffman 算法（贪心：反复合并两个最小概率）构造最优前缀码；对块做 Huffman 则把整数码长的舍入摊到更长的 block 上。

3. 🔗 全站对账

决策树信息增益（ai 课 03）：选特征 = 最大化 \(H(Y) - H(Y\mid A)\)——本页条件熵的直接应用，那页的公理化证明与本页 §1 是同一个定理；
LLM 的困惑度（ai 课 07）：\(\mathrm{PPL} = 2^{H}\)（交叉熵的指数）——困惑度是交叉熵的指数，可理解为几何平均的有效不确定性，通常不是实际候选数的算术平均。BPE tokenizer 合并高频相邻片段以构建词表，Huffman 合并低概率节点以优化二进制码长；二者目标与对象不同，不能当作同一算法；
预测与压缩的联系（须约定同一概率模型与编码开销）：预测下一符号的分布越准，\(-\log q\) 平均越短——好的语言模型天然是好的压缩器（下一页交叉熵一节给出精确形式，第三页算术编码把它变成可运行的字面事实）。

4. 典型例题

例 1（二十问游戏） 8 个等可能候选：\(H = 3\) 比特 ⇒ 最优二分提问恰需 3 问。若分布为 \((\frac12, \frac14, \frac18, \frac18)\)：\(H = 1.75\)——先问"是不是第一个"的不均匀问法平均 1.75 问，比盲目二分（2 问）省：好的提问顺序 = 好的编码。

例 2（熵的计算与比较） \(X \sim B(1, 0.9)\)：\(h(0.9) = -0.9\log 0.9 - 0.1\log 0.1 \approx 0.469\) 比特——偏硬币悬念不到半比特；这表示长序列的平均极限约为每次 0.469 bit，不表示任意一条有限投掷记录都恰好需要这个长度。

例 3（Huffman 构造） 概率 \((0.4,0.3,0.2,0.1)\)：依次合并 \(0.1+0.2=0.3\)、\(0.3+0.3=0.6\)、\(0.4+0.6=1\)，可得码长 \((1,2,3,3)\)。于是 \(L^*=0.4+0.6+0.6+0.3=1.9\) bit，而 \(H\approx1.846\) bit，严格满足 \(H<L^*<H+1\)。差出的 \(0.054\) bit 来自整数叶深限制；对长块编码可把每符号舍入损失摊薄。\(\blacksquare\)

延伸：MIT 信息论讲义第 6 章：可变长无损编码。

下一页：两个分布之间的"距离"——KL 散度与互信息：MLE 的信息论真身、以及为什么整个机器学习都在最小化一个 KL。