本页目录

信息论进阶 III · 率失真与大偏差

对标：Cover & Thomas §10、§11 ｜前置：it2-01/02、本科信息论 II、优化 III 收官页两个方向：率失真理论——有损压缩的极限（JPEG/MP3/神经压缩的理论天花板）；大偏差与 Sanov 定理——"稀有事件的概率按 KL 散度指数计价"：KL 的第三重身份（前两重：编码代价、统计距离），也是 hdp 线 Chernoff 界的完全体形态。

1. 率失真理论：有损压缩的极限

设定：失真度量 \(d(x, \hat x)\)（如平方误差/汉明距离），允许平均失真 \(\leq D\)，问最少码率。

定义与定理（率失真函数）

\[ R(D) = \min_{p(\hat x\mid x):\ E\,d(X,\hat X) \leq D}\ I(X; \hat X) \]

且此 \(R(D)\) 恰是可达的最小码率（正逆定理均成立【骨架：正向 = 随机码本 + 联合典型性（it2-02 的证明机器换个方向开——码字当"重建"用）；逆向 = Fano 链】）。

读法：压缩 = 用互信息买失真的市场，\(R(D)\) 是价目表：\(R(0) = H\)（无损极限，回收 it2-01）；\(D\) 大到一定程度 \(R = 0\)（均值重建即可）。凸性【一行：时间共享论证】保证价目表无套利。

两个闭式价目表【引用推导】：伯努利-汉明：\(R(D) = h(p) - h(D)\)；高斯-平方误差：

\[ R(D) = \frac12\log\frac{\sigma^2}{D} \]

——每多花 1 比特，失真减 4 倍（6dB/bit：音频工程的口诀出处）；多维高斯的反注水（reverse water-filling【引用】）：失真预算优先花在大方差分量——PCA 截断保大特征值的率失真论证（高代/统计的直觉获得信息论定价）。

🔗 现代对账：神经压缩/VAE 的 \(\beta\)-VAE 目标 \(\mathrm{rate} + \beta\,\mathrm{distortion}\) 就是 \(R(D)\) 的拉格朗日形式（comfy 课 VAE 的"压缩-保真"权衡在此有精确理论）；扩散模型的感知-失真权衡是它的当代延长线【引用 Blau–Michaeli】。

2. 类型方法与 Sanov 定理

类型（经验分布）：序列 \(x^n\) 的直方图 \(P_{x^n}\)。两个计数事实【骨架】：类型总数 \(\leq (n+1)^{|\mathcal{X}|}\)（多项式——与序列的指数形成落差）；给定类型 \(Q\) 的序列数 \(\approx 2^{nH(Q)}\)；真分布 \(P\) 下"类型 \(Q\) 的全部序列"的概率

\[ P^n(\text{type } Q) \;\doteq\; 2^{-n\,D_{\mathrm{KL}}(Q\,\|\,P)} \]

（\(\doteq\) = 指数阶相等；一行：单个 \(Q\)-型序列概率 \(= 2^{-n(H(Q) + D(Q\|P))}\) × 序列数。）

定理（Sanov） 对分布集合 \(E\)（正则性下）：

\[ P\big(\hat P_n \in E\big) \;\doteq\; 2^{-n\,\min_{Q\in E} D_{\mathrm{KL}}(Q\|P)} \]

【骨架】 上界：union bound 于多项式个类型，最大项主导；下界：单挑最优 \(Q^*\) 的类型贡献。\(\blacksquare\)

读法（KL 的第三重身份）：稀有事件的指数代价 = 到真相的 KL 距离；且事件发生时，经验分布长得像 \(Q^*\)（"条件极限定理"【引用】：稀有事件以最省 KL 的方式发生——"大自然走信息论的最短路"）。Chernoff/Cramér 界（hdp-01）是 Sanov 对半平面事件的投影（Cramér 速率函数 = KL 的 Legendre 共轭——cvx-01 的共轭变换在此第三次收租：大偏差速率函数与累积量母函数互为共轭）。

假设检验的极限（Stein 引理陈述）【引用】：固定第一类错误，第二类错误 \(\doteq 2^{-nD(P_0\|P_1)}\)——检验的指数效率由 KL 计价（统计 IV 的 N–P 引理在渐近尺度的续集；两分布越"KL-远"越好分辨——你的预测复盘里"命题区分度"的理论语言）。

3. 信息论进阶三页收官

页	定理	一句话
I	AEP/SMB	长序列塌缩进 \(2^{nH}\) 的典型集；压缩极限 = 熵率
II	信道编码	随机编码两指数赛跑；\(C\) 之上是物理不可能
III	\(R(D)\) / Sanov	失真按互信息计价；稀有按 KL 计价

熵/互信息/KL 三兄弟至此各就其位：熵管体积、互信息管分辨、KL 管代价——信息论的世界观完型。

4. 练习与要点

例 1（6dB 口诀验证） 16 位音频降到 8 位：率差 8 比特 ⇒ 失真比 \(4^8 = 65536\) 倍（48dB 信噪比损失）——高斯 \(R(D)\) 的一行应用；实际编解码器接近但不达此界（非高斯 + 感知度量——工程与理论的常规间隙）。

例 2（Sanov 手算） 公平硬币抛 \(n\) 次、正面比例 \(\geq 0.7\) 的概率指数：\(\min_{q\geq0.7}D(q\|0.5) = D(0.7\|0.5) \approx 0.119\) ⇒ \(P \doteq 2^{-0.119n}\)——对照 Hoeffding 的 \(e^{-2n(0.2)^2} = 2^{-0.115n}\)：Sanov 更紧且给出"事件如何发生"（经验分布 ≈ 0.7 那枚"假想硬币"）。

例 3（条件极限的直觉测试） 已知 100 次骰子总和 ≥ 450（均值 4.5）：各点数的条件频率长什么样？——指数倾斜分布（最省 KL 的 \(Q^*\)：\(q_i \propto e^{\lambda i}\)，\(\lambda\) 由均值约束定——最大熵/共轭的又一次会师）而非"全是 6"：稀有事件的最可能路径是"整体温和偏移"，不是"个别极端"。风险管理的深刻教训藏在这道题里。\(\blacksquare\)

下一门：最优传输——把"分布之间的距离"从 KL 换成"搬运成本"：Monge–Kantorovich、Wasserstein 几何与 Sinkhorn。