4.1 基础熵与互信息

概率论用分布描述不确定性，但没有给出不确定性的数量指标。两个随机变量哪个更不确定、观测到 $Y$ 之后关于 $X$ 还剩多少不确定性、两个变量共享多少信息，这些问题需要新的量来回答。信息论从最基本的度量出发，构造出熵（entropy）、条件熵（conditional entropy）与互信息（mutual information）三个互相联系的量，并证明它们满足一组结构清晰的恒等式与不等式。

本节的组织顺序是：先定义单个结果的意外程度（自信息），再取其平均得到熵；随后引入两个变量的联合熵与条件熵，推导链式法则；再由三者的差定义互信息，说明互信息的四种等价表达与核心性质；最后讨论两个信息论中最有用的不等式（数据处理不等式与 Fano 不等式），并把熵的概念从单个变量推广到随机过程（熵率），介绍长序列行为的基本结论（渐近均分性质与典型性）。典型性理论是后面编码与信道容量两节的技术基础，本节给出它的直观与结论，详细的编码构造留到 4.4 节与 4.5 节。

4.1.1 自信息

从意外程度到对数

一个事件的信息量应当由它的意外程度决定。抛一枚均匀硬币得到正面，这一结果的意外程度低；掷骰子得到六点，意外程度高一些；抽卡得到概率为 $0.01$ 的稀有物件，意外程度更高。把意外程度量化，需要三条要求。

第一，概率越小的事件带来的信息越多，函数应当关于 $p$ 递减。第二，必然发生的事件不带来任何信息，即 $p=1$ 时信息量为零。第三，两个独立事件同时发生所带来的信息，应当等于各自信息之和，因为两者之间没有相互提示。

满足这三条要求的函数形式唯一，就是对数的负值：

$$i(x)=\log \frac{1}{p(x)}=-\log p(x)$$

把 $i(x)$ 称为结果 $x$ 的自信息（self-information）。第三条要求的作用是确定函数为对数形式：若 $g(p_1{p}_2)=g(p_1)+g(p_2)$ 且 $g$ 关于 $p$ 连续递减、$g(1)=0$，则 $g(p)=-c\log p$。

底数与单位

对数的底数决定信息的单位。取底 $2$ 时单位为比特（bit），一个等概率的二元结果恰好携带 $1$ 比特信息；取底 $e$ 时单位为奈特（nat）；取底 $10$ 时单位为 dit。换算关系为

$$1\text{ nat}={\log }_{2}e\approx 1.4427\text{ bit},1\text{ bit}=\ln 2\approx 0.6931\text{ nat}$$

底数的选择不影响结论的结构，只改变数值的换算。涉及两个分布之比的量（KL 散度、互信息）对底数不敏感，因为比值在换底时同时出现在分子与分母上而抵消；只有单独的熵与自信息需要说明单位。

import numpy as np

def self_information(p, base=2):
    """自信息，默认单位为比特"""
    return -np.log(p) / np.log(base)

print(f"抛均匀硬币正面：{self_information(0.5):.3f} 比特")
print(f"掷骰子得六点：  {self_information(1/6):.3f} 比特")
print(f"概率 0.01 的结果：{self_information(0.01):.3f} 比特")
print(f"必然事件：      {self_information(1.0):.3f} 比特")
# 概率每减半，信息量增加 1 比特

4.1.2 信息熵

定义

自信息描述单个结果，信息熵（information entropy，也称香农熵）描述整个随机变量的平均意外程度，定义为自信息的期望：

$$H(X)=E[i(X)]=-\sum _{x\in \mathcal{X}}p(x)\log p(x)$$

连续情形用微分熵（differential entropy）替代（4.4 节讨论它的性质差异）：

$$h(X)=-\int f(x)\log f(x)dx$$

定义中 $p(x)=0$ 的项约定取 $0$，即 $0\log 0=0$。这一约定不是随意规定的：由洛必达法则 $p\log p\to 0$（$p\to 0^{+}$），把零概率项计入求和会破坏连续性，约定取零可以使熵关于分布的扰动连续。

基本性质

非负性：$H(X)\ge 0$，因为每一项 $p\log p\le 0$。等号成立当且仅当某个结果的概率为 $1$，此时随机变量退化，没有不确定性。

上界：若 $X$ 取值于大小为 $|\mathcal{X}|$ 的集合，则

$$H(X)\le \log |\mathcal{X}|$$

等号当且仅当分布均匀。证明用 KL 散度的非负性（4.2 节）：设 $u(x)=1/|\mathcal{X}|$ 为均匀分布，

$$\log |\mathcal{X}|-H(X)=\sum _{x}p(x)\log \frac{p(x)}{u(x)}\ge 0$$

这就是 $p$ 与均匀分布之间的 KL 散度。直观上的含义是：在给定取值集合的前提下，均匀分布最不确定，任何偏向都会降低不确定性。

凹性：$H(X)$ 是关于分布 $p$ 的凹函数，即对任意两个分布 $p_1,p_2$ 与 $\lambda \in [0,1]$，

$$H(\lambda p_1+(1-\lambda )p_2)\ge \lambda H(p_1)+(1-\lambda )H(p_2)$$

凹性的实际意义是混合两个分布不会减少不确定性。证明用对数函数的凹性与 Jensen 不等式。作为推论，在约束下最大化熵的问题（4.3 节的最大熵原理）是一个凸优化问题，可以用第三章的工具求解。

对称性：熵只依赖概率的取值，与结果的具体标签无关。把 $\{1,2,3\}$ 换成 $\{\text{晴},\text{雨},\text{阴}\}$ 不改变熵。这一点说明熵度量的是分布的形状而非结果的内容，也说明熵无法区分语义相似的取值与完全无关的取值，这是它在文本与图像处理中需要结合其他工具的原因。

伯努利分布的熵

取 $X\sim \mathrm{Bernoulli}(p)$，熵为

$$H(p)=-p\log p-(1-p)\log (1-p)$$

函数关于 $p=0.5$ 对称，在端点取零、在中点取最大值 $1$ 比特。这条曲线是整个信息论中最常用的函数之一：任何二元决策的不确定性都不超过 $1$ 比特，接近确定性时不确定性迅速下降。

import numpy as np
import matplotlib.pyplot as plt

def entropy(p):
    """离散分布的熵，输入为概率数组，单位为比特"""
    p = np.asarray(p, dtype=float)
    p = p[p > 0]
    return float(-(p * np.log2(p)).sum())

p_grid = np.linspace(1e-6, 1 - 1e-6, 400)
h_bern = [entropy([p, 1 - p]) for p in p_grid]
print(f"伯努利分布的最大熵（p = 0.5）：{entropy([0.5, 0.5]):.4f} 比特")
print(f"p = 0.9 时的熵：{entropy([0.9, 0.1]):.4f} 比特")

fig, ax = plt.subplots(figsize=(5, 3))
ax.plot(p_grid, h_bern)
ax.set_xlabel("p")
ax.set_ylabel("H(p) / bit")
ax.grid(alpha=0.3)
print("曲线在 p = 0.5 处取最大值 1 比特，在两端趋于 0")

4.1.3 联合熵、条件熵与链式法则

联合熵

两个随机变量的联合熵（joint entropy）按联合分布定义：

$$H(X,Y)=-\sum _x\sum _{y}p(x,y)\log p(x,y)$$

它度量一对结果的整体不确定性。把 $(X,Y)$ 视为取值于笛卡尔积的单个随机变量，联合熵就是它的熵，因此 $0\le H(X,Y)\le \log (|\mathcal{X}|\cdot |\mathcal{Y}|)$。

条件熵

条件熵（conditional entropy）定义为给定 $X$ 后 $Y$ 的平均剩余不确定性：

$$H(Y\mid X)=\sum _{x}p(x)H(Y\mid X=x)=-\sum _x\sum _{y}p(x,y)\log p(y\mid x)$$

计算时先算出每个 $x$ 下的条件分布的熵，再按 $p(x)$ 加权平均。注意 $H(Y\mid X)$ 是一个数值，不是随机变量；若写成 $H(Y\mid X=x)$ 才是关于 $x$ 的函数。

链式法则

联合熵与条件熵由链式法则（chain rule）联系：

$$H(X,Y)=H(X)+H(Y\mid X)=H(Y)+H(X\mid Y)$$

推导直接从条件概率的乘积分解得到：

$$\log p(x,y)=\log p(x)+\log p(y\mid x)$$

两边取负期望即得结论。推广到 $n$ 个随机变量，

$$H(X_1,\dots ,X_n)=\sum _{i=1}^{n}H(X_i\mid X_1,\dots ,X_{i-1})$$

链式法则把联合熵展开为逐步条件熵之和，是信息论中使用频率最高的恒等式。语言模型的困惑度、序列压缩比、熵率的存在性都由它推出。

次可加性与条件作用减少熵

由链式法则与条件熵的定义可以推出两条不等式。

次可加性：$H(X,Y)\le H(X)+H(Y)$。成立的原因可以写成 KL 散度的形式：

$$H(X)+H(Y)-H(X,Y)=\sum _{x,y}p(x,y)\log \frac{p(x,y)}{p(x)p(y)}\ge 0$$

右边的量正是互信息，非负性在 4.1.4 节证明。等号成立当且仅当 $X$ 与 $Y$ 独立。直观含义是两个变量的整体不确定性不超过各自不确定性之和，只有在互不相关时两者相等。

条件作用减少熵：$H(Y\mid X)\le H(Y)$，由次可加性与链式法则直接得到。等号成立当且仅当独立。观测到 $X$ 不会增加关于 $Y$ 的不确定性，这是常识中知道得越多，不确定性越小的定量版本。

条件化的两个方向

条件作用减少熵 $H(Y\mid X)\le H(Y)$ 与增加条件只会减少熵是两件不同的事。后者不成立：$H(Y\mid X,Z)$ 与 $H(Y\mid X)$ 之间没有固定的大小关系，加入 $Z$ 可能使熵增大。原因是条件化包含两次操作：把 $Y$ 的信息换成 $Y$ 与 $Z$ 的联合信息，同时把已知集合从 $X$ 扩大为 $(X,Z)$。两者对熵的影响方向不确定。

一个具体的例子来自 2.6 节的对撞结构：才华 $X$ 与外貌 $Y$ 在人群中近似独立，条件化于是否获奖 $Z$ 之后两者产生依赖。此时 $I(X;Y\mid Z)>I(X;Y)$，条件化增大了互信息。判断条件化的效果需要具体分析依赖结构，而不是套用单调性。

import numpy as np

def joint_entropy(P):
    """联合熵，输入为联合概率矩阵"""
    P = np.asarray(P, dtype=float)
    P = P[P > 0]
    return float(-(P * np.log2(P)).sum())

def entropy(p):
    p = np.asarray(p, dtype=float)
    p = p[p > 0]
    return float(-(p * np.log2(p)).sum())

# 一个 2x2 的联合分布：两个二元变量
P = np.array([[0.4, 0.1],
              [0.1, 0.4]])

px = P.sum(axis=1)
py = P.sum(axis=0)
H_xy = joint_entropy(P)
H_x, H_y = entropy(px), entropy(py)
H_y_given_x = H_xy - H_x

print(f"H(X)     = {H_x:.4f}")
print(f"H(Y)     = {H_y:.4f}")
print(f"H(X, Y)  = {H_xy:.4f}")
print(f"H(Y|X)   = {H_y_given_x:.4f}   链式法则验证：H(X) + H(Y|X) = {H_x + H_y_given_x:.4f}")
print(f"次可加性：H(X, Y) ≤ H(X) + H(Y)，即 {H_xy:.4f} ≤ {H_x + H_y:.4f}")
print(f"互信息 I(X;Y) = H(X) + H(Y) - H(X, Y) = {H_x + H_y - H_xy:.4f}")

4.1.4 互信息

定义与四种表达

互信息（mutual information）度量两个随机变量共享的信息量，定义为联合分布与边缘分布乘积之间的 KL 散度：

$$I(X;Y)=\sum _x\sum _{y}p(x,y)\log \frac{p(x,y)}{p(x)p(y)}=D_{\mathrm{KL}}(p(x,y)\parallel p(x)p(y))$$

这一形式说明互信息度量的是实际联合分布与独立假设下的联合分布之间的差异。由 KL 散度的非负性（4.2 节给出证明）立即得到 $I(X;Y)\ge 0$，且等号成立当且仅当 $X$ 与 $Y$ 独立。

由链式法则可以推出四种等价表达：

$$I(X;Y)=H(X)-H(X\mid Y)=H(Y)-H(Y\mid X)=H(X)+H(Y)-H(X,Y)$$

第一种表达解释为知道 $Y$ 之后 $X$ 的不确定性减少了多少，第二种是对称的版本，第三种把互信息写成熵的线性组合，便于从联合分布的熵直接计算。三种表达在推导中交替使用，选择哪一个取决于已知量是什么。

关系	表达式	含义
互信息	$I(X;Y)$	共享的信息量
边缘熵	$H(X)$、$H(Y)$	各自的不确定性
联合熵	$H(X,Y)$	整体不确定性
条件熵	$H(X\mid Y)$、$H(Y\mid X)$	剩余不确定性
等价式	$H(X,Y)=H(X\mid Y)+I(X;Y)+H(Y\mid X)$	三者之和等于联合熵

性质

对称性：$I(X;Y)=I(Y;X)$，从定义中 $p(x,y)$ 与 $p(y,x)$ 的对称性直接得到。

非负性：$I(X;Y)\ge 0$，等号当且仅当独立。

自信息量：$I(X;X)=H(X)$，即变量与自身共享的信息就是它的全部不确定性。

有界性：$I(X;Y)\le min\{H(X),H(Y)\}$，由 $I=H(X)-H(X\mid Y)\le H(X)$ 与对称性得到。互信息不会超过任一变量的熵，这一上界在特征选择的讨论中反复出现。

与相关性的对比：互信息为零等价于独立，而相关系数为零只意味着没有线性关联。$Y=X^2$ 与 $X$ 的相关系数为零，但互信息明显大于零。互信息能捕捉任意形式的依赖，代价是需要估计完整的联合分布，计算与样本量要求都高于相关系数。

条件互信息

条件互信息（conditional mutual information）定义为在已知 $Z$ 的条件下的互信息：

$$I(X;Y\mid Z)=\sum _{z}p(z)\sum _{x,y}p(x,y\mid z)\log \frac{p(x,y\mid z)}{p(x\mid z)p(y\mid z)}$$

它满足与互信息平行的一组性质：非负、对称、在给定 $Z$ 下为零当且仅当 $X$ 与 $Y$ 条件独立。与互信息不同的是，条件互信息与互信息之间没有固定的大小关系，两个方向都可能出现：共因结构下条件化会减小互信息，对撞结构下条件化会增大互信息（见 4.1.3 节的说明）。

互信息也有链式法则：

$$I(X_1,\dots ,X_n;Y)=\sum _{i=1}^{n}I(X_i;Y\mid X_1,\dots ,X_{i-1})$$

它把多样本对同一目标的信息分解为逐项贡献之和，每一项是在已知前序变量的条件下的新增信息。这一形式在特征选择的贪心算法中直接使用。

import numpy as np

def mutual_information(P):
    """联合分布矩阵的互信息（比特）"""
    P = np.asarray(P, dtype=float)
    px = P.sum(axis=1, keepdims=True)
    py = P.sum(axis=0, keepdims=True)
    with np.errstate(divide="ignore", invalid="ignore"):
        ratio = np.where(P > 0, P / (px * py), 1.0)
        terms = np.where(P > 0, P * np.log2(ratio), 0.0)
    return float(terms.sum())

# 独立情形
P_indep = np.outer([0.5, 0.5], [0.3, 0.7])
# 强相关情形
P_dep = np.array([[0.45, 0.05],
                  [0.05, 0.45]])
# 对撞结构下的情形：X、Y 独立，条件化于 Z 后相关（这里只比较边缘互信息）
print(f"独立时互信息     = {mutual_information(P_indep):.6f}")
print(f"相关时互信息     = {mutual_information(P_dep):.4f}")

# 用模拟样本估计互信息（直方图法，含有限样本偏差）
rng = np.random.default_rng(3)
n = 200_000
x = rng.normal(size=n)
y = x + 0.8 * rng.normal(size=n)         # 强相关
bins = 40
H, _, _ = np.histogram2d(x, y, bins=bins, density=False)
P_hat = H / H.sum() + 1e-12
print(f"模拟样本的互信息估计 = {mutual_information(P_hat):.4f}")
print(f"同样本量下独立数据的估计值 = {mutual_information(np.outer(np.histogram(x, bins=bins)[0] / n, np.histogram(rng.normal(size=n), bins=bins)[0] / n) + 1e-12):.4f}")
# 独立数据的估计值应接近 0，但仍为正，这是有限样本的偏差

4.1.5 数据处理不等式与 Fano 不等式

马尔可夫链与数据处理不等式

若给定 $Y$ 时 $X$ 与 $Z$ 条件独立，则称 $X,Y,Z$ 构成马尔可夫链（Markov chain），记作 $X\to Y\to Z$。它的含义是 $Z$ 只通过 $Y$ 获取关于 $X$ 的信息，$Y$ 是信息传递的中间环节。

数据处理不等式（data processing inequality）：若 $X\to Y\to Z$，则

$$I(X;Z)\le I(X;Y)$$

直觉是信息经过任何处理只会损失，不会增加。证明思路是把 $I(X;(Y,Z))$ 用两种链式分解写出，比较两者的差：

$$I(X;Y,Z)=I(X;Y)+\underset{=0}{\underbrace{I(X;Z\mid Y)}}=I(X;Z)+\underset{\ge 0}{\underbrace{I(X;Y\mid Z)}}$$

第一行中 $I(X;Z\mid Y)=0$ 来自马尔可夫性质，第二行中的条件互信息非负，两式相减即得结论。等号成立当且仅当 $I(X;Y\mid Z)=0$，也就是 $Z$ 保留了 $Y$ 中关于 $X$ 的全部信息，此时称 $Z$ 是 $X$ 的充分统计量（2.9 节的定义在这里得到信息论表述：充分统计量是不损失信息的压缩）。

数据处理不等式有大量直接推论。对数据做任何确定性变换（特征工程、量化、哈希）都会使互信息不增，这解释了为什么精细量化会损害分类性能。对数据进行可逆变换不改变信息量，这解释了为什么特征标准化、坐标旋转不影响理论上限，只影响算法的收敛速度。

Fano 不等式

Fano 不等式（Fano's inequality）把条件熵与推断误差联系起来。设 $X$ 取值于大小为 $|\mathcal{X}|$ 的集合，$\hat{X}(Y)$ 是依据 $Y$ 对 $X$ 的估计，误差概率为 $P_e=P(\hat{X}\ne X)$。则

$$H(X\mid Y)\le H(P_e)+P_e\log (|\mathcal{X}|-1)$$

其中 $H(P_e)$ 是参数为 $P_e$ 的伯努利熵。常见的形式是解出误差下界：

$$P_e\ge \frac{H(X\mid Y)-1}{\log |\mathcal{X}|}$$

推导思路是用 $\hat{X}$ 作为中间变量构造马尔可夫链 $X\to Y\to \hat{X}$，把 $H(X\mid Y)$ 与 $H(X\mid \hat{X})$ 比较，后者可以用误差概率界住。

Fano 不等式的用途是给出误差下界。它说明无论用什么方法从 $Y$ 推断 $X$，只要条件熵较大，误差概率就不能太小：剩余不确定性必须体现在错误里。举一个数值例子，若 $X$ 均匀取值于 $|\mathcal{X}|=8$ 的集合，且 $H(X\mid Y)=1.5$ 比特，则

$$P_e\ge \frac{1.5-1}{\log 8}=\frac{0.5}{3}\approx 0.167$$

即至少 $16.7\mathrm{\%}$ 的样本无法被正确判断。这一结论与具体算法无关，是信息量本身的限制。

在机器学习语境下，Fano 不等式把特征与标签的互信息与可达的分类精度联系起来：互信息给定了误差的下界，增加模型容量无法突破这一界限，改进的方向只能是获取更多信息的特征。4.6 节会给出这一联系的更精细版本。

import numpy as np

def entropy(p):
    p = np.asarray(p, dtype=float)
    p = p[p > 0]
    return float(-(p * np.log2(p)).sum())

def fano_bound(H_x_given_y, n_classes):
    """由条件熵给出的误差下界"""
    return (H_x_given_y - 1) / np.log2(n_classes)

for h in [0.5, 1.5, 2.5]:
    print(f"H(X|Y) = {h:.1f} 比特（8 类）：误差下界 = {max(0.0, fano_bound(h, 8)):.4f}")
# 条件熵越小，误差下界越低；条件熵低于 1 比特时该下界不再有约束力（公式给出负值，取零）

4.1.6 熵率

随机过程的熵率

单个随机变量的熵描述一个位置的不确定性，序列的整体不确定性增长速度由熵率（entropy rate）描述。对随机过程 $\{X_i\}$，定义

$$H(\mathcal{X})=\underset{n\to \mathrm{\infty }}{lim}\frac{1}{n}H(X_1,X_2,\dots ,X_n)$$

极限的存在性由次可加性保证：令 $a_n=H(X_1,\dots ,X_n)$，由 $H(X_1,\dots ,X_{n+m})\le H(X_1,\dots ,X_n)+H(X_{n+1},\dots ,X_{n+m})$ 可知序列 $\{a_n\}$ 次可加，因此 $a_n/n$ 的极限存在（Fekete 引理）。熵率的单位是比特每符号，含义是每新增一个符号需要付出的信息量。

平稳过程的熵率

对平稳过程（2.8 节），熵率有更便于计算的表达：

$$H(\mathcal{X})=\underset{n\to \mathrm{\infty }}{lim}H(X_n\mid X_1,\dots ,X_{n-1})$$

极限同样存在，且条件是单调递减的（由条件作用减少熵可知 $H(X_n\mid X_1..X_{n-1})\le H(X_{n-1}\mid X_1..X_{n-2})$）。这一形式说明熵率等于在掌握全部历史之后，预测下一个符号还剩多少不确定性。平稳性保证这个量随 $n$ 收敛到常数。

独立序列与马尔可夫链

独立同分布序列：$H(\mathcal{X})=H(X_1)$，因为每个符号相对历史没有新增不确定性，熵率等于单符号熵。

一阶马尔可夫链：设转移矩阵为 $P$，平稳分布为 $\mathit{\pi }$（2.8 节），则

$$H(\mathcal{X})=H(X_2\mid X_1)=-\sum _i{\pi }_i\sum _j{P}_{ij}\log P_{ij}$$

这是各状态流出熵按平稳概率的加权平均。若链的某个状态确定性地转移到下一个状态（$P_{ij}=1$），该状态贡献零熵；若转移均匀分布，该状态贡献 $\log$(出度) 比特。熵率因而度量链的随机程度。

import numpy as np

def markov_entropy_rate(P):
    """一阶马尔可夫链的熵率（比特/符号），P 为转移矩阵"""
    P = np.asarray(P, dtype=float)
    # 平稳分布：解 pi = pi P
    eigvals, eigvecs = np.linalg.eig(P.T)
    idx = np.argmin(np.abs(eigvals - 1))
    pi = np.real(eigvecs[:, idx])
    pi = pi / pi.sum()
    row_ent = -np.sum(np.where(P > 0, P * np.log2(np.where(P > 0, P, 1)), 0), axis=1)
    return float(pi @ row_ent), pi

# 天气链：晴/雨，晴天有 90% 概率继续晴
P = np.array([[0.9, 0.1],
              [0.5, 0.5]])
rate, pi = markov_entropy_rate(P)
print(f"平稳分布 = {np.round(pi, 4)}")
print(f"熵率 = {rate:.4f} 比特/符号")
print(f"独立均匀序列的熵率（对照）= {np.log2(2):.4f} 比特/符号")

自然语言的熵率。香农在 1951 年的实验中让人逐字猜测英文文本，用猜对的次数估计熵率，得到的量级约为每个字符 $1$ 比特左右。后续实验与基于语言模型的估计给出更低的数值。熵率的实际用途是给出压缩的下界：文本压缩算法在最好情况下的平均码长不会低于熵率，实际压缩比与熵率的差距反映了算法的效率（4.4 节）。

4.1.7 渐近均分性质与典型性

渐近均分性质

设 $X_1,\dots ,X_n$ 独立同分布于 $p(x)$。对一条具体序列 $\mathbf{x}=(x_1,\dots ,x_n)$，其概率为 $p(\mathbf{x})=\prod _{i}p(x_i)$，而

$$-\frac{1}{n}\log p(\mathbf{x})=-\frac{1}{n}\sum _{i=1}^n\log p(x_i)$$

这是 $n$ 个独立同分布的随机变量 $-\log p(X_i)$ 的样本均值，其期望正是 $H(X)$。由大数定律（2.7 节），样本均值依概率收敛到期望，因此

$$-\frac{1}{n}\log p(X_1,\dots ,X_n)\stackrel{p}{\to }H(X)$$

这一结论称为渐近均分性质（asymptotic equipartition property，AEP）。它的含义是：几乎全部概率质量集中在那些概率接近 $2^{-nH(X)}$ 的序列上，这些序列被称为典型序列。序列的概率在指数尺度上是均分的，这正是均分一词的来源。

典型集

固定 $ϵ>0$，典型集（typical set）定义为

$$A_{ϵ}^{(n)}=\{\mathbf{x}:|-\frac{1}{n}\log p(\mathbf{x})-H(X)|\le ϵ\}$$

典型集有三条关键性质。

概率趋于一：当 $n\to \mathrm{\infty }$ 时 $P(A_{ϵ}^{(n)})\to 1$，由 AEP 直接得到。

大小有上界：$|A_{ϵ}^{(n)}|\le 2^{n(H(X)+ϵ)}$。证明利用每条典型序列的概率不小于 $2^{-n(H+ϵ)}$，全部概率之和不超过 $1$，故序列条数不超过 $2^{n(H+ϵ)}$。

大小有下界：对足够大的 $n$，$|A_{ϵ}^{(n)}|\ge (1-ϵ)2^{n(H(X)-ϵ)}$。

两条界合起来给出：典型序列的条数量级为 $2^{nH(X)}$，每条的概率量级为 $2^{-nH(X)}$。与全部序列的总数 $|\mathcal{X}{|}^n=2^{n\log |\mathcal{X}|}$ 相比，典型集可能远小于序列空间。举一个数值例子：$|\mathcal{X}|=4$、$H(X)=1$ 比特时，全部序列有 $4^n$ 条，而典型序列只有约 $2^n$ 条，占比为 $2^{-n}$，随 $n$ 指数下降。

这一结论是数据压缩的理论基础。需要区分的序列只有约 $2^{nH}$ 条，因此用 $nH$ 比特就可以编号，平均每个符号约 $H$ 比特，与熵率一致。压缩的具体构造（Huffman 编码、算术编码）在 4.4 节给出。

典型性的几种版本

弱典型与强典型的区别在于对序列概率的约束方式。弱典型（上面的定义）只约束经验熵接近真实熵；强典型要求序列的经验分布（每个符号出现的频率）接近真实分布，条件更强。强典型集合的自信息界与弱典型类似，但不依赖真实分布的尾部性质，在证明中更容易处理。

联合典型（jointly typical）把定义推广到序列对：$(\mathbf{x},\mathbf{y})$ 是联合典型的，若经验联合熵、边缘熵都接近各自的真实值。条件典型要求在给定 $\mathbf{x}$ 的条件下 $\mathbf{y}$ 的条件熵接近真实条件熵。联合典型性的主要用途是信道编码的典型性解码：接收端在全部候选码字中寻找与接收序列联合典型的那个，由联合典型集大小的估计可以证明错误概率趋于零，从而证明信道容量可达（4.5 节）。

需要说明的是，典型序列的性质是高概率性质，而不是对每条序列都成立。非典型序列依然可能出现，只是概率极小；在有限 $n$ 的情况下，典型集的性质与渐近结论之间存在明显差距，实际编码器的设计必须考虑这一差距。

import numpy as np

# 用伯努利序列验证 AEP：经验熵随 n 收敛到真实熵
def empirical_entropy(seq):
    """由序列的经验分布计算熵"""
    p1 = seq.mean()
    ps = np.array([p1, 1 - p1])
    ps = ps[ps > 0]
    return float(-(ps * np.log2(ps)).sum())

rng = np.random.default_rng(11)
p_true = 0.3
H_true = -(p_true * np.log2(p_true) + (1 - p_true) * np.log2(1 - p_true))
print(f"真实熵 H(X) = {H_true:.4f} 比特")

for n in [10, 100, 1000, 10_000, 100_000]:
    seq = rng.binomial(1, p_true, size=n)
    est = empirical_entropy(seq)
    print(f"  n = {n:>7,}：经验熵 = {est:.4f}，偏差 = {abs(est - H_true):.4f}")

# 典型集大小的估计：统计自信息落在 [H-0.1, H+0.1] 内的序列比例
n = 200
trials = 20_000
seqs = rng.binomial(1, p_true, size=(trials, n))
self_info = -(seqs * np.log2(p_true) + (1 - seqs) * np.log2(1 - p_true)).mean(axis=1)
in_typical = np.abs(self_info - H_true) <= 0.1
print(f"\n{trials} 次抽样中，典型序列（n = {n}）的比例 = {in_typical.mean():.4f}")
print(f"典型序列条数的对数尺度的上界 ≈ n(H + 0.1) = {n * (H_true + 0.1):.1f}")

4.1.8 本节小结

从自信息到典型性

本节从三条要求推出自信息必须取对数形式，取其期望得到熵。熵的三条基本性质（非负、上界为 $\log |\mathcal{X}|$、关于分布凹）来自 KL 散度的非负性与对数函数的凹性，这三条性质确定了后续所有优化与证明的边界条件。链式法则把联合熵展开为逐项条件熵之和，次可加性与条件作用减少熵由它推出，两条不等式的等号条件都指向独立。互信息定义为实际联合分布与独立假设下联合分布之间的 KL 散度，因此自动获得非负性与对称性，并有四种等价表达；条件互信息与互信息之间没有单调关系，依赖结构决定了条件化的方向。数据处理不等式说明任何处理都不增加信息，充分统计量正是等号成立的情形；Fano 不等式把条件熵转化为推断误差的下界，给出了任何算法都无法突破的精度限制。熵率把熵从单个变量推广到序列，独立同分布序列的熵率等于单符号熵，马尔可夫链的熵率等于按平稳分布加权的状态流出熵。渐近均分性质说明长序列的概率在指数尺度上均分，典型集的条数约为 $2^{nH}$，这一结论将在 4.4 节与 4.5 节分别导出压缩极限与信道容量。

熵度量的是单个分布的不确定性。许多问题关心的是两个分布之间的距离：用近似分布替代真实分布损失了多少信息、两个模型的预测分布相差多远、生成样本的分布与真实分布差多少。这类需求需要新的量，它们中的一些（KL 散度、交叉熵）正是本节互信息定义的构件。下一节系统整理这些散度与距离，说明各自的定义、性质与适用条件，并给出它们在优化与统计中的对应关系。

练习题

第 1 题 概念推导

设 $X$ 取值于大小为 $K$ 的有限集合，分布为 $p$。证明 $H(X)\le \log K$，并说明等号成立的条件。

参考答案

设 $u(x)=1/K$ 为均匀分布。考虑 $p$ 与 $u$ 之间的 KL 散度：

$$D_{\mathrm{KL}}(p\parallel u)=\sum _{x}p(x)\log \frac{p(x)}{u(x)}=\sum _{x}p(x)\log p(x)+\log K\sum _{x}p(x)$$

由 $\sum _{x}p(x)=1$，右边化简为 $-H(X)+\log K$。题目给出结论依赖 KL 散度的非负性（4.2 节将给出证明），在此可以先用另一条路径代替。

不用 KL 的证明：对数函数是凹函数，由 Jensen 不等式，

$$H(X)=\sum _{x}p(x)\log \frac{1}{p(x)}\le \log \sum _{x}p(x)\cdot \frac{1}{p(x)}=\log K$$

这里把 $H(X)$ 写成 $\sum _{x}p(x)g(x)$ 的形式（$g(x)=\log (1/p(x))$），对凹函数 $g$ 应用加权 Jensen 不等式即可。等号成立的条件是 Jensen 不等式中等号成立，即 $1/p(x)$ 对所有 $x$ 取相同值，也就是 $p(x)=1/K$ 对整个支撑集成立。因此等号当且仅当分布均匀。

两条路径的关系是：Jensen 不等式的差正好等于 KL 散度，所以上面的推导同时给出了 $D_{\mathrm{KL}}(p\parallel u)=\log K-H(X)\ge 0$，这说明均匀分布最大化熵与KL 散度非负是同一结论的两种表述。

第 2 题 计算推理

某推荐系统把用户分成两类（活跃、不活跃），把内容分成三类（新闻、娱乐、教程）。观测到的联合分布如下表。

	新闻	娱乐	教程
活跃	0.24	0.16	0.10
不活跃	0.06	0.14	0.30

请计算 $H(U)$、$H(C)$、$H(U,C)$、$H(C\mid U)$、$I(U;C)$，并说明哪个类别的条件熵更大，以及对推荐策略的含义。

参考答案

边缘分布：按行求和得 $p(\text{活跃})=0.50$，$p(\text{不活跃})=0.50$；按列求和得 $p(\text{新闻})=0.30$，$p(\text{娱乐})=0.30$，$p(\text{教程})=0.40$。

熵：

$$H(U)=-0.5\log 0.5-0.5\log 0.5=1.0000\text{ 比特}$$$$H(C)=-(0.3\log 0.3)\times 2-0.4\log 0.4=0.3\times 1.7370\times 2+0.4\times 1.3219=1.5710\text{ 比特}$$

联合熵：逐项计算 $p\log p$ 并求和，

$$H(U,C)=2.4535\text{ 比特}$$

条件熵：

$$H(C\mid U)=H(U,C)-H(U)=2.4535-1.0000=1.4535\text{ 比特}$$

互信息：

$$I(U;C)=H(C)-H(C\mid U)=1.5710-1.4535=0.1175\text{ 比特}$$

条件熵的分解：分别计算两类用户的条件熵。活跃用户的条件分布为 $(0.48,0.32,0.20)$，熵为 $1.4452$ 比特；不活跃用户的条件分布为 $(0.12,0.28,0.60)$，熵为 $1.2664$ 比特。活跃用户的条件熵更大，说明对活跃用户而言内容偏好更分散；不活跃用户的偏好更集中（明显偏向教程）。

策略含义：互信息 $0.1175$ 比特远小于 $H(C)$，说明用户类别对内容偏好的预测力有限，仅凭活跃状态无法有效区分偏好。更有价值的信息来自条件熵的分解：不活跃用户的条件熵更低，用一个针对性策略（推送教程类内容）就能覆盖大部分需求；活跃用户需要更细的画像。这一分析也提示：条件熵在分组上的差异比互信息总量更能指导具体策略。

第 3 题 代码验证

用模拟验证三条结论：其一，数据处理不等式，对含噪声的观测做量化处理后互信息不增；其二，渐近均分性质，经验熵随序列长度收敛到真实熵；其三，熵率，一阶马尔可夫链的熵率等于按平稳分布加权的状态流出熵。

参考答案

import numpy as np

def joint_mi(P):
    P = np.asarray(P, dtype=float)
    px = P.sum(axis=1, keepdims=True)
    py = P.sum(axis=0, keepdims=True)
    with np.errstate(divide="ignore", invalid="ignore"):
        ratio = np.where(P > 0, P / (px * py), 1.0)
        return float(np.where(P > 0, P * np.log2(ratio), 0.0).sum())

rng = np.random.default_rng(7)
n = 500_000

# 一条马尔可夫链 X -> Y -> Z
x = rng.binomial(1, 0.5, size=n)
y = rng.binomial(1, 0.85 * x + 0.15 * (1 - x))          # Y 含 X 的信息
z = rng.binomial(1, 0.65 * y + 0.35 * (1 - y))          # Z 只通过 Y 得到信息

def mi_from_samples(a, b, levels=2):
    P = np.zeros((levels, levels))
    for i, j in zip(a, b):
        P[i, j] += 1
    return joint_mi(P / P.sum())

print(f"I(X;Y) = {mi_from_samples(x, y):.4f}")
print(f"I(X;Z) = {mi_from_samples(x, z):.4f}")
print(f"I(Y;Z) = {mi_from_samples(y, z):.4f}")
# I(X;Z) 明显小于 I(X;Y)，验证数据处理不等式

# 量化处理：把连续观测分箱后互信息下降
u = rng.normal(size=n)
v = u + 0.5 * rng.normal(size=n)
for bins in [4, 16, 64]:
    qu = np.digitize(u, np.quantile(u, np.linspace(0, 1, bins + 1)[1:-1]))
    qv = np.digitize(v, np.quantile(v, np.linspace(0, 1, bins + 1)[1:-1]))
    P = np.zeros((bins, bins))
    np.add.at(P, (qu, qv), 1)
    print(f"分箱数 {bins:3d}：量化后的互信息 = {joint_mi(P / P.sum()):.4f}")
# 分箱越粗，互信息越小，量化损失的正是被抹平的细节

# 马尔可夫链熵率
P = np.array([[0.8, 0.1, 0.1],
              [0.2, 0.7, 0.1],
              [0.1, 0.2, 0.7]])
w, V = np.linalg.eig(P.T)
pi = np.real(V[:, np.argmin(np.abs(w - 1))])
pi = pi / pi.sum()
row_ent = -np.sum(np.where(P > 0, P * np.log2(np.where(P > 0, P, 1)), 0), axis=1)
print(f"\n平稳分布 = {np.round(pi, 4)}")
print(f"熵率（解析）= {pi @ row_ent:.4f} 比特/符号")

# 用长轨道估计熵率：条件熵 H(X_n | X_{n-1}) 的样本估计
states = np.empty(200_000, dtype=int)
states[0] = 0
for t in range(1, len(states)):
    states[t] = rng.choice(3, p=P[states[t - 1]])
P_hat = np.zeros((3, 3))
for a, b in zip(states[:-1], states[1:]):
    P_hat[a, b] += 1
P_hat = P_hat / P_hat.sum(axis=1, keepdims=True)
row_ent_hat = -np.sum(np.where(P_hat > 0, P_hat * np.log2(np.where(P_hat > 0, P_hat, 1)), 0), axis=1)
print(f"由轨道估计的转移熵（按平稳分布加权）= {pi @ row_ent_hat:.4f}")

三项验证的结果说明：数据处理不等式在具体数据上表现为观测链条越长信息越少；量化会单调地降低互信息，粗量化损失更大；马尔可夫链的熵率可以由解析公式算出，也可以由长轨道上的经验条件熵估计，两者一致。第三条的实践意义是熵率可以从数据估计，这使压缩比的理论下界可以直接计算。

第 4 题 综合应用

某团队研究一个文本分类任务，$X$ 为 20 类标签，标签近似均匀分布。他们测得当前特征集与标签的互信息为 $I(X;Y)=2.2$ 比特。请用 Fano 不等式给出分类误差的下界；说明若要把误差降到 $10\mathrm{\%}$ 以下，对特征的要求是什么；并结合数据处理不等式讨论增加特征变换环节的利弊。

参考答案

误差下界：由 $I(X;Y)=H(X)-H(X\mid Y)$ 得

$$H(X\mid Y)=H(X)-I(X;Y)={\log }_{2}20-2.2=4.3219-2.2=2.1219\text{ 比特}$$

代入 Fano 不等式：

$$P_e\ge \frac{H(X\mid Y)-1}{\log |\mathcal{X}|}=\frac{2.1219-1}{4.3219}\approx 0.260$$

即在当前特征下，无论用什么分类器，错误率都不可能低于约 $26\mathrm{\%}$。

把误差降到 10% 以下所需的互信息：要 $P_e\le 0.1$，需要

$$H(X\mid Y)\le 1+0.1\times 4.3219=1.4322\text{ 比特}$$

对应 $I(X;Y)\ge 4.3219-1.4322=2.8897$ 比特。也就是说互信息需要从 $2.2$ 提高到约 $2.89$ 比特以上，增幅约 $31\mathrm{\%}$。这一计算给出了特征工程的量化目标：需要寻找新的、与标签相关且与已有特征不冗余的信息来源。注意 Fano 给出的是必要条件而非充分条件，达到该互信息不保证能达到 $10\mathrm{\%}$ 的误差，但不达到就一定做不到。

特征变换的利弊：由数据处理不等式，任何确定性变换 $Y\to Z$ 都满足 $I(X;Z)\le I(X;Y)$。因此降维、离散化、特征选择都不会提高互信息，做的只是去掉冗余。变换的价值在于提高算法的效率与泛化：去掉与标签无关的噪声维度能减少估计误差，使分类器更接近利用已有信息的理论上限；代价是若变换设计不当（例如过度离散化、把有信息的非线性组合抹平），会真正损失信息，使可达误差上升。实践中的判据是看变换后验证集上的表现，而非变换本身的复杂度。

常见错误

错误 1 · 把熵当作随机变量自身的属性

原因：熵由分布决定，与取值的具体标签无关。把 $\{1,2,3\}$ 换成 $\{\text{晴},\text{雨},\text{阴}\}$ 得到的熵相同。若在分析中依据标签的语义相似性推断熵的大小或互信息的大小，结论会与计算不符。

解决：计算熵之前先写出分布，把标签视为等价的符号。需要利用取值之间的结构（例如有序类别、数值距离）时，改用能反映结构的度量，如 Wasserstein 距离或基于核的散度，见 4.2 节。

错误 2 · 认为增加条件总是减少熵

原因：条件作用减少熵 $H(Y\mid X)\le H(Y)$ 只比较无条件与以 $X$ 为条件两种情形。加入更多变量后，$H(Y\mid X,Z)$ 与 $H(Y\mid X)$ 之间没有固定的大小关系。把前者当作普遍规律，会在涉及多变量的推理中出错。

解决：区分两条结论：无条件熵大于等于任何单条件下的熵，这条成立；多个条件之间的关系需要具体分析依赖结构，对撞结构下条件化会增加关联，共因结构下条件化会减少关联。

错误 3 · 混淆比特与奈特

原因：同一分布的熵在不同底数下数值不同，换算因子约为 $1.4427$。报告中混用两个单位会使数值相差近一半，在与其他量（如码长、互信息界）比较时得到错误结论。

解决：在全文与代码中统一底数，代码里显式写出 ${\log }_2$ 或 $\log$（自然对数）并在注释中标注单位。涉及两个分布比值的量（KL 散度、互信息）在换底时等比缩放，可以按方便选择底数，但要与比较对象的底数保持一致。

错误 4 · 用有限样本的直方图估计互信息而不做偏差修正

原因：分箱估计互信息存在系统性上偏。即使两个变量独立，有限样本下估计值也大于零，因为每个箱内的样本都很少、经验分布必然偏离独立结构。样本量越小、分箱越细，偏差越大。这一偏差在特征选择中会导致大量无关特征被评为相关。

解决：控制分箱数量（每箱至少有几十个样本），或改用有偏差修正的估计方法（如 Miller-Madow 修正、基于 k 近邻的 Kozachenko-Leonenko 估计、神经网络互信息估计，见 4.7 节）。比较不同特征时使用相同的样本量与分箱方案，并用置换检验给出零分布作为基准。