417 lines
16 KiB
Markdown
417 lines
16 KiB
Markdown
---
|
||
title: 1-信息论
|
||
tags:
|
||
- 信息论
|
||
- 数学基础
|
||
- 机器学习
|
||
---
|
||
|
||
# 信息论核心概念
|
||
|
||
> **前置知识假设**：读者已掌握微积分（极限、凸函数）、概率论（随机变量、期望、概率分布）以及基本的高等代数（对数运算）。本文档目标是为强化学习和非完全信息博弈中的信息论应用建立扎实的数学基础。
|
||
|
||
---
|
||
|
||
## 一、基本定义与核心量
|
||
|
||
### 1.1 自信息（Self-Information）
|
||
|
||
**定义**：单一事件 $X=x$ 发生所携带的信息量，定义为：
|
||
|
||
$$
|
||
I(x) \stackrel{\text{def}}{=} -\log P(x) = \log \frac{1}{P(x)}
|
||
$$
|
||
|
||
**直观理解**：
|
||
- 事件发生的概率越小，其自信息越大——"稀有事件才是大新闻"。
|
||
- 若 $P(x) = 1$（确定发生），则 $I(x) = 0$——不携带任何信息。
|
||
- 若 $P(x) = \frac{1}{2}$（抛硬币），则 $I(x) = 1$ bit。
|
||
|
||
**对数底数约定**：
|
||
|
||
| 底数 | 单位 | 应用场景 |
|
||
|------|------|----------|
|
||
| $\log_2$ | bit（比特） | 信息论、编码理论 |
|
||
| $\ln$ | nat（奈特） | 数学、机器学习 |
|
||
| $\log_{10}$ | Hart | 工程 |
|
||
|
||
本文优先使用 $\log_2$（bit）记号，数学结论对任意底数均成立（只差常数因子）。
|
||
|
||
### 1.2 信息熵（Entropy）
|
||
|
||
**定义**：随机变量 $X$ 的熵是其自信息的期望，即随机变量不确定性的度量：
|
||
|
||
$$
|
||
\boxed{H(X) \stackrel{\text{def}}{=} \mathbb{E}_{X \sim P}[I(X)] = \mathbb{E}_{X \sim P}\left[-\log P(X)\right] = -\sum_{x \in \mathcal{X}} P(x) \log P(x)}
|
||
$$
|
||
|
||
**直观理解**：熵描述了"编码 $X$ 的平均最小编码长度"（由 Shannon 源编码定理）。它同时度量了随机变量的不确定性——分布越均匀，熵越大；分布越尖锐，熵越小。
|
||
|
||
**熵的极值定理**：
|
||
|
||
> 对于在有限字母表 $\mathcal{X}$ 上定义的随机变量 $X$，有：
|
||
> $$
|
||
> H(X) \leq \log |\mathcal{X}|
|
||
> $$
|
||
> 等号成立当且仅当 $X$ 服从均匀分布。
|
||
|
||
**证明（利用 Jensen 不等式）**：设 $f(x) = \log x$ 为凹函数，则：
|
||
$$
|
||
H(X) = -\sum_x P(x) \log P(x) = \sum_x P(x) \log \frac{1}{P(x)} \leq \log \left(\sum_x P(x) \cdot \frac{1}{P(x)}\right) = \log |\mathcal{X}|
|
||
$$
|
||
等号成立当且仅当所有 $P(x)$ 相等（凹函数 Jensen 等号条件）。
|
||
|
||
### 1.3 联合熵（Joint Entropy）
|
||
|
||
**定义**：两个随机变量 $X$ 和 $Y$ 的联合熵：
|
||
|
||
$$
|
||
H(X, Y) \stackrel{\text{def}}{=} -\sum_{x \in \mathcal{X}} \sum_{y \in \mathcal{Y}} P(x, y) \log P(x, y) = \mathbb{E}_{P(x,y)}[-\log P(X, Y)]
|
||
$$
|
||
|
||
**直观理解**：描述同时描述 $(X, Y)$ 这两个随机变量所需的平均信息量。
|
||
|
||
### 1.4 条件熵（Conditional Entropy）
|
||
|
||
**定义**：给定 $Y=y$ 条件下 $X$ 的条件熵：
|
||
|
||
$$
|
||
H(X \mid Y=y) \stackrel{\text{def}}{=} -\sum_{x \in \mathcal{X}} P(x \mid y) \log P(x \mid y)
|
||
$$
|
||
|
||
全体条件熵的期望（对 $Y$ 求平均）：
|
||
|
||
$$
|
||
\boxed{H(X \mid Y) \stackrel{\text{def}}{=} \mathbb{E}_{Y \sim P}[H(X \mid Y)] = -\sum_{y \in \mathcal{Y}} \sum_{x \in \mathcal{X}} P(x, y) \log P(x \mid y)}
|
||
$$
|
||
|
||
**直观理解**：已知 $Y$ 之后，$X$ 还剩下多少不确定性？可以理解为"在 $Y$ 中包含的信息中，有多少是关于 $X$ 的"。
|
||
|
||
---
|
||
|
||
## 二、核心恒等式：链式法则（Chain Rule）
|
||
|
||
### 2.1 熵的链式法则
|
||
|
||
**定理（熵的链式法则）**：
|
||
|
||
> 对于任意两个随机变量 $X$ 和 $Y$：
|
||
> $$
|
||
> H(X, Y) = H(X) + H(Y \mid X)
|
||
> $$
|
||
> 或等价地：
|
||
> $$
|
||
> H(X, Y) = H(Y) + H(X \mid Y)
|
||
> $$
|
||
|
||
**推导**：
|
||
|
||
从联合概率的定义出发：
|
||
$$
|
||
P(x, y) = P(x) \cdot P(y \mid x)
|
||
$$
|
||
|
||
取负对数：
|
||
$$
|
||
-\log P(x, y) = -\log P(x) - \log P(y \mid x)
|
||
$$
|
||
|
||
对 $P(x, y)$ 取期望：
|
||
$$
|
||
\begin{aligned}
|
||
H(X, Y) &= -\sum_{x,y} P(x, y) \log P(x, y) \\
|
||
&= -\sum_{x,y} P(x, y) [\log P(x) + \log P(y \mid x)] \\
|
||
&= -\sum_x \left[\sum_y P(x, y)\right] \log P(x) - \sum_{x,y} P(x, y) \log P(y \mid x) \\
|
||
&= -\sum_x P(x) \log P(x) - \sum_{x,y} P(x, y) \log P(y \mid x) \\
|
||
&= H(X) + H(Y \mid X)
|
||
\end{aligned}
|
||
$$
|
||
|
||
$\square$
|
||
|
||
**物理直觉**：同时描述 $(X,Y)$ 的信息 = 先描述 $X$ 的信息 + 已知 $X$ 后再描述 $Y$ 的增量信息。
|
||
|
||
**推广（多元链式法则）**：
|
||
|
||
对 $n$ 个随机变量 $X_1, \ldots, X_n$：
|
||
$$
|
||
H(X_1, \ldots, X_n) = H(X_1) + H(X_2 \mid X_1) + H(X_3 \mid X_1, X_2) + \cdots + H(X_n \mid X_1, \ldots, X_{n-1})
|
||
$$
|
||
|
||
---
|
||
|
||
## 三、互信息（Mutual Information）
|
||
|
||
### 3.1 定义与直观理解
|
||
|
||
**定义**：两个随机变量 $X$ 和 $Y$ 之间的互信息，衡量 $Y$ 中包含的关于 $X$ 的信息量（或反之）：
|
||
|
||
$$
|
||
\boxed{I(X; Y) \stackrel{\text{def}}{=} \mathbb{E}_{P(x,y)}\left[\log \frac{P(x, y)}{P(x) P(y)}\right] = \sum_{x,y} P(x, y) \log \frac{P(x, y)}{P(x) P(y)}}
|
||
$$
|
||
|
||
**互信息的对称性**：$I(X; Y) = I(Y; X)$，从定义可直接看出。
|
||
|
||
**与熵的关系（三种等价表达）**：
|
||
|
||
1. **从熵角度**：
|
||
$$
|
||
I(X; Y) = H(X) - H(X \mid Y) = H(Y) - H(Y \mid X)
|
||
$$
|
||
|
||
2. **从联合熵角度**：
|
||
$$
|
||
I(X; Y) = H(X) + H(Y) - H(X, Y)
|
||
$$
|
||
|
||
3. **几何角度**：互信息是 $X$ 与 $Y$ 的联合分布与边缘分布乘积之间的"距离"（非对称，非度量）。
|
||
|
||
**直观理解**：互信息 $I(X; Y)$ 可以理解为——当我已知 $Y$ 后，$X$ 的不确定性的减少量；或者，等价地，$X$ 与 $Y$ 共享的信息量。
|
||
|
||
### 3.2 互信息与条件独立
|
||
|
||
> **定理**：$X \perp Y \mid Z$（即 $P(x, y \mid z) = P(x \mid z) P(y \mid z)$）当且仅当 $I(X; Y \mid Z) = 0$。
|
||
>
|
||
> 其中条件互信息 $I(X; Y \mid Z) = H(X \mid Z) - H(X \mid Y, Z)$。
|
||
|
||
这是理解 D-分离准则的数学基础：在贝叶斯网络中，条件独立的精确含义是条件互信息为零。
|
||
|
||
---
|
||
|
||
## 四、KL 散度（Kullback-Leibler Divergence）
|
||
|
||
### 4.1 定义
|
||
|
||
**定义（KL 散度 / 相对熵）**：给定两个概率分布 $P$ 和 $Q$（定义在同一概率空间上），$P$ 相对于 $Q$ 的 KL 散度定义为：
|
||
|
||
$$
|
||
\boxed{D_{\text{KL}}(P \| Q) \stackrel{\text{def}}{=} \mathbb{E}_{X \sim P}\left[\log \frac{P(X)}{Q(X)}\right] = \sum_x P(x) \log \frac{P(x)}{Q(x)}}
|
||
$$
|
||
|
||
**重要性质**：
|
||
- **非负性**：$D_{\text{KL}}(P \| Q) \geq 0$，当且仅当 $P = Q$ 时取等号。
|
||
- **非对称性**：$D_{\text{KL}}(P \| Q) \neq D_{\text{KL}}(Q \| P)$（一般不等），因此 KL 散度不是严格意义上的"距离"（metric）。
|
||
- **链式法则**：$D_{\text{KL}}(P \| Q) = H(P, Q) - H(P)$（注：此为代数恒等式，非 KL 散度的链式法则）
|
||
|
||
### 4.2 KL 散度非负性的严格证明（利用 Jensen 不等式）
|
||
|
||
**定理（KL 散度非负性）**：对于任意两个概率分布 $P$ 和 $Q$，有 $D_{\text{KL}}(P \| Q) \geq 0$。
|
||
|
||
**证明**：
|
||
|
||
考虑函数 $f(t) = -\log t$（凸函数，$f''(t) = 1/t^2 > 0$）。
|
||
|
||
对任意 $x$，令 $t_x = \frac{Q(x)}{P(x)}$，则 $f(t_x) = -\log \frac{Q(x)}{P(x)} = \log \frac{P(x)}{Q(x)}$。
|
||
|
||
由 **Jensen 不等式**（对于凸函数 $f$，$f\left(\mathbb{E}[Z]\right) \leq \mathbb{E}[f(Z)]$），令 $Z_x = \frac{Q(x)}{P(x)}$，权重为 $P(x)$：
|
||
|
||
$$
|
||
\begin{aligned}
|
||
D_{\text{KL}}(P \| Q) &= \sum_x P(x) \left(-\log \frac{Q(x)}{P(x)}\right) \\
|
||
&= \sum_x P(x) \cdot f\!\left(\frac{Q(x)}{P(x)}\right) \\
|
||
&\geq f\!\left(\sum_x P(x) \cdot \frac{Q(x)}{P(x)}\right) \quad \text{（Jensen 不等式）} \\
|
||
&= f\!\left(\sum_x Q(x)\right) \\
|
||
&= f(1) = -\log 1 = 0
|
||
\end{aligned}
|
||
$$
|
||
|
||
当 $f$ 为严格凸函数时，等号成立条件为：$Z_x$ 几乎处处为常数，即 $\frac{Q(x)}{P(x)} = c$（常数）对所有 $x$ 成立。由于 $\sum_x Q(x) = c \sum_x P(x) = c = 1$，故 $c=1$，即 $Q(x) = P(x)$。
|
||
|
||
$\square$
|
||
|
||
> **Jensen 不等式在此的角色**：它将加权的凸函数值与凸函数作用在加权和上关联起来。具体地，$\sum_x P(x) f(Q(x)/P(x)) \geq f\left(\sum_x Q(x)\right) = f(1)$，从而得到非负性。这是信息论中最重要的不等式之一，也是 EM 算法推导的理论基石。
|
||
|
||
### 4.3 交叉熵、熵与 KL 散度的关系
|
||
|
||
**三者关系恒等式**：
|
||
|
||
$$
|
||
\boxed{D_{\text{KL}}(P \| Q) = H(P, Q) - H(P)}
|
||
$$
|
||
|
||
其中 **交叉熵（Cross Entropy）** 定义为：
|
||
|
||
$$
|
||
H(P, Q) \stackrel{\text{def}}{=} -\sum_x P(x) \log Q(x) = \mathbb{E}_{X \sim P}[-\log Q(X)]
|
||
$$
|
||
|
||
**推导**：
|
||
|
||
$$
|
||
\begin{aligned}
|
||
D_{\text{KL}}(P \| Q) &= \sum_x P(x) \log \frac{P(x)}{Q(x)} \\
|
||
&= \sum_x P(x) [-\log Q(x)] - \sum_x P(x) [-\log P(x)] \\
|
||
&= H(P, Q) - H(P)
|
||
\end{aligned}
|
||
$$
|
||
|
||
**三者的几何关系**：
|
||
|
||
```
|
||
H(P, Q) (Cross Entropy)
|
||
┌────────────────────────────┐
|
||
│ │
|
||
│ D_KL(P||Q) │
|
||
│ ┌───────┐ │
|
||
│ │ H(P) │ │
|
||
│ └───────┘ │
|
||
└────────────────────────────┘
|
||
```
|
||
|
||
在机器学习中的实际应用：
|
||
- 当 $P$ 为真实数据分布（固定），$Q$ 为模型预测分布（可学习参数 $\theta$）时，
|
||
$$
|
||
H(P, Q) = H(P) + D_{\text{KL}}(P \| Q_\theta)
|
||
$$
|
||
第一项 $H(P)$ 为常数，与参数无关。因此**最小化交叉熵**等价于**最小化 KL 散度**（即最小化模型分布与真实分布的差距）。
|
||
|
||
---
|
||
|
||
## 五、算法直觉与应用
|
||
|
||
### 5.1 KL 散度在强化学习策略迭代中的作用
|
||
|
||
在 **PPO（Proximal Policy Optimization）** 和 **TRPO（Trust Region Policy Optimization）** 等策略优化算法中，KL 散度被用作策略更新的约束。
|
||
|
||
**为什么需要约束？**
|
||
|
||
无约束的策略梯度更新可能导致策略在单次迭代中变化过大，使得策略从"好"区域跳到"差"区域，导致训练不稳定甚至崩溃（尤其在 on-policy 场景下，一次崩溃可能使数据失效）。
|
||
|
||
**KL 约束的具体形式**：
|
||
|
||
TRPO 的优化目标：
|
||
$$
|
||
\max_\theta \quad \mathbb{E}_t\left[ \frac{\pi_\theta(a_t \mid s_t)}{\pi_{\theta_{\text{old}}}(a_t \mid s_t)} \hat{A}_t \right]
|
||
\quad \text{s.t.} \quad D_{\text{KL}}\left(\pi_\theta \| \pi_{\theta_{\text{old}}}\right) \leq \delta
|
||
$$
|
||
|
||
PPO 的等效形式（使用自适应 KL 惩罚）：
|
||
$$
|
||
\mathcal{L}^{\text{PPO}}(\theta) = \mathbb{E}_t\left[ \frac{\pi_\theta(a_t \mid s_t)}{\pi_{\theta_{\text{old}}}(a_t \mid s_t)} \hat{A}_t \right] - \beta \cdot D_{\text{KL}}\left(\pi_\theta \| \pi_{\theta_{\text{old}}}\right)
|
||
$$
|
||
|
||
**数学直觉**：
|
||
- $D_{\text{KL}}(\pi_{\theta} \| \pi_{\text{old}})$ 度量了"新策略相对于旧策略的差异"；
|
||
- 约束它小于 $\delta$，确保新策略不会偏离旧策略太远；
|
||
- 这本质上是在策略空间上进行**局部线性近似**，保证每次更新都在"信任域"内。
|
||
|
||
> **注意**：KL 散度是非对称的。在策略迭代中，通常使用 $D_{\text{KL}}(\pi_{\theta} \| \pi_{\text{old}})$（新策略在前）作为 TRPO 官方标准约束：前者衡量的是"从新策略视角看旧策略的差异"，而后者（$\pi_{\text{old}} \| \pi$）在极端情况下可能给出误导性的结果（比如新策略在某个区域给零概率，会导致 $D_{\text{KL}}(\pi_{\text{old}} \| \pi) = +\infty$）。
|
||
|
||
### 5.2 互信息与特征选择、信息瓶颈
|
||
|
||
#### 5.2.1 特征选择
|
||
|
||
在特征工程中，我们希望选择与目标变量 $Y$ 最相关的特征 $X$。互信息 $I(X; Y)$ 直接度量了这种相关性：
|
||
|
||
- $I(X; Y) = 0$：$X$ 与 $Y$ 完全独立，不含关于 $Y$ 的任何信息；
|
||
- $I(X; Y)$ 越大：$X$ 包含越多关于 $Y$ 的信息。
|
||
|
||
**条件互信息特征选择**：给定候选特征集 $\mathcal{F}$，选择使 $I(X_f; Y \mid X_{S})$ 最大的特征 $X_f$，其中 $X_S$ 为已选特征集。这确保选择的是"在已有特征基础上仍然带来新信息"的特征，而非冗余特征。
|
||
|
||
#### 5.2.2 信息瓶颈（Information Bottleneck, IB）
|
||
|
||
**IB 框架**（Tishby, Pereira, Bialek, 1999）提出：学习表示（representation）的目标是最小化输入 $X$ 与表示 $Z$ 之间的互信息 $I(X; Z)$（压缩），同时最大化 $Z$ 与标签 $Y$ 之间的互信息 $I(Z; Y)$（保留任务相关信息）。
|
||
|
||
优化目标：
|
||
$$
|
||
\min_{q(z \mid x)} \quad I(X; Z) - \beta \cdot I(Z; Y)
|
||
$$
|
||
|
||
其中 $\beta > 0$ 为 Lagrange 乘子，权衡压缩与信息保留。
|
||
|
||
**深度学习中的 IB**：
|
||
- 自编码器（AE）的重建项 $\mathbb{E}_{q}[\log P(x \mid z)]$ 本质上是 $I(X; Z)$ 的代理；
|
||
- 对比学习（Contrastive Learning）通过 InfoNCE 等目标最大化 $I(Z; Y)$；
|
||
- 瓶颈层（bottleneck layer）正是物理意义上的信息瓶颈。
|
||
|
||
### 5.3 熵在非完全信息博弈中的应用
|
||
|
||
#### 5.3.1 策略的混合程度
|
||
|
||
在非完全信息博弈（如扑克、桥牌）中，混合策略（mixed strategy）通过概率分布对多个纯策略进行加权。**熵**度量了一个混合策略的"不可预测程度"：
|
||
|
||
$$
|
||
H(\pi) = -\sum_{a \in \mathcal{A}} \pi(a) \log \pi(a)
|
||
$$
|
||
|
||
**直觉**：
|
||
- 若玩家使用纯策略（deterministic），$H(\pi) = 0$——对手可以完美预测你的行动；
|
||
- 若玩家均匀随机（uniform），$H(\pi) = \log |\mathcal{A}|$——行动完全不可预测。
|
||
|
||
**在 CFR（Counterfactual Regret Minimization）中的应用**：
|
||
|
||
CFR 算法中，每轮迭代的策略更新涉及**反事实后悔值（Counterfactual Regret）**的计算：
|
||
|
||
设累积正后悔 $R^+(a) = \max\left(\sum_{t} r^t(a),\ 0\right)$，则策略按后悔匹配更新：
|
||
|
||
$$
|
||
\sigma(a) = \frac{R^+(a)}{\sum_{a'} R^+(a')}
|
||
$$
|
||
|
||
其中 $r_i^t(a)$ 为动作 $a$ 的即时后悔值。**策略熵**是判断 CFR 收敛的重要监控指标：
|
||
|
||
- 收敛时，策略趋近**纳什均衡**（在零和博弈中对应低熵的确定策略）；
|
||
- 若熵在迭代中持续下降，说明策略正在稳定；若熵震荡，说明算法未收敛。
|
||
|
||
#### 5.3.2 熵正则化（Entropy Regularization）
|
||
|
||
在强化学习与博弈论中，**熵正则化**被广泛用于鼓励探索（exploration）：
|
||
|
||
$$
|
||
\mathcal{L}(\theta) = \mathbb{E}_{s,a \sim \pi_\theta}[r(s,a)] + \alpha \cdot H(\pi_\theta)
|
||
$$
|
||
|
||
其中 $\alpha > 0$ 控制熵项的权重。
|
||
|
||
- **在 RL 中**：高熵防止过早收敛到次优策略（避免 exploitation 过早）；
|
||
- **在博弈中**：熵正则化防止策略被对手轻易 exploit——你的行动越不可预测，对手越难找到针对性的对策。
|
||
|
||
> **直觉**：在博弈中，** exploitability**（被对手 best response 击败的程度）与策略熵负相关。最大熵均衡（Maximum Entropy Nash Equilibrium）是在所有均衡中最"保守"的一个，在信息安全要求高的场景（如网络安全、军事战略）中具有重要意义。
|
||
|
||
---
|
||
|
||
## 六、总结
|
||
|
||
### 核心公式速查
|
||
|
||
| 公式 | 名称 |
|
||
|------|------|
|
||
| $H(X) = -\sum_x P(x) \log P(x)$ | 信息熵 |
|
||
| $H(X \mid Y) = H(X, Y) - H(Y)$ | 条件熵 |
|
||
| $I(X; Y) = H(X) - H(X \mid Y)$ | 互信息 |
|
||
| $D_{\text{KL}}(P \| Q) = \sum_x P(x) \log \frac{P(x)}{Q(x)}$ | KL 散度 |
|
||
| $D_{\text{KL}}(P \| Q) = H(P, Q) - H(P)$ | KL 与交叉熵的关系 |
|
||
| $H(X, Y) = H(X) + H(Y \mid X)$ | 熵的链式法则 |
|
||
|
||
### 信息论的统一视角
|
||
|
||
```
|
||
┌──────────────┐
|
||
│ 联合熵 │
|
||
│ H(X, Y) │
|
||
└──────┬───────┘
|
||
│
|
||
┌────────────┼────────────┐
|
||
│ │ │
|
||
▼ ▼ ▼
|
||
┌──────────┐ ┌──────────┐ ┌──────────┐
|
||
│ H(X) │ │ H(Y) │ │I(X; Y) │
|
||
│ 边缘熵 │ │ 边缘熵 │ │ 互信息 │
|
||
└──────────┘ └──────────┘ └──────────┘
|
||
│ │ │
|
||
└────────────┼────────────┘
|
||
│
|
||
┌──────┴───────┐
|
||
│ 条件熵 │
|
||
│ H(X|Y), H(Y|X) │
|
||
└──────────────┘
|
||
```
|
||
|
||
理解这张图的关键：互信息 $I(X; Y)$ 是 $H(X)$ 与 $H(X \mid Y)$ 之间的差值——它量化了"依赖"的存在。
|
||
|
||
### 与后续内容的联系
|
||
|
||
- **KL 散度** → ELBO 的推导 → VAE 的理论基础 → 扩散模型的变分推断框架
|
||
- **互信息** → InfoNCE → 对比学习 → CLIP 等多模态模型
|
||
- **熵** → 策略梯度中的熵正则化 → PPO/SAC → 探索-利用权衡
|
||
- **链式法则** → 信用分配（credit assignment）→ 反向传播的信息流视角 |