信息论进阶 III · 率失真、反注水与稀有事件

1. 三种失真目标，以及一个容易遗漏的零点

编码器把 \(X^n\) 映射为标签 \(J\in\{0,\ldots,M-1\}\)，译码器从标签重构 \(\widehat X^n\)。固定长度码率为 \(r_n=\log_2M/n\)。对非负单字母失真 \(d\)，令

平均准则约束 \(\mathbb E d_n\leq D\)；超额失真准则约束 \(P(d_n>D)\)；逐条准则要求源支持中的每条序列都满足 \(d_n\leq D\)。三者的有限最优码本通常不同。基本定义与有限信息下界见 MIT 6.441 第23.2节。

本课的单字母信息率失真函数定义为

先考虑有限字母表、IID源、有界失真。用允许 \(\limsup_n\mathbb E d_n\leq D\) 的渐近准则时，适当的编码定理把它接到最小渐近码率。这与先对每个有限 \(n\) 强制精确零失真再取极限不同。

例如 \(0\lt p\lt 1\) 的 Bernoulli 源，在 Hamming 失真下，每个二元词都有正概率。若有限平均失真严格等于零，就必须恢复全部 \(2^n\) 个词，故 \(M\geq2^n\)，码率至少为 1。另一方面，允许失真随 \(n\) 趋零，可以使用几乎无损信源码，渐近率为 \(H_2(p)\)。所以

不等于“每个有限码都严格零失真”的最小率。确定性源只需一个代表词，另作零率处理。

2. 偏置二元源：最优的是反向对称信道

设 \(X\sim\operatorname{Bernoulli}(p)\)，重构也是二元，\(d=\mathbf1_{\{X\ne\widehat X\}}\)。记 \(D_0=\min(p,1-p)\)。完整公式为

负预算不可行。零率平台由重构为最常见符号达到。对 \(D\leq D_0\leq1/2\)，误差位 \(E=X\oplus\widehat X\) 给出

最后一步使用二元熵在 \([0,1/2]\) 单调递增，不能把这个推导延长到所有预算。

为了取等，先独立生成 \(\widehat X\sim\operatorname{Bernoulli}(q)\) 与 \(Z\sim\operatorname{Bernoulli}(D)\)，再令 \(X=\widehat X\oplus Z\)。满足源边缘的条件是

在正码率段这个 \(q\) 合法，且 \(H(X\mid\widehat X)=H_2(D)\)。这是从重构到原信源的反向 BSC；实际前向 \(W(\hat x\mid x)\) 应由 Bayes 公式算出，一般不对称。公平源才使两方向同时对称。\(p=D=1/2\) 的零率点直接选常数重构，避免使用 \(0/0\)。这种构造见 MIT 第25.1.1节。

实验同时保留 \(P_{X\widehat X}\)、两个边缘与两个方向的条件概率。边缘为零时，相应条件分布没有唯一含义，记为不适用。

3. 一份具体有限码本怎样记账

固定重构词 \(c_0,\ldots,c_{M-1}\)。对每个源词 \(x^n\)，选择 Hamming 距离最近者；平局按标签顺序选第一个。若重复词出现两次，标签仍保留，但不会凭空增加可重构的信息。

设实际映射为 \(j(x^n)\)，则

实验逐词累加，不抽样估计；最大失真只对正概率源支持取最大。它还把各重构区域的质量相加，得到 \(P(J=j)\)。确定性映射满足 \(H(J\mid X^n)=0\)，所以 \(I(X^n;J)=H(J)\)。

编码信息通过 \(X^n\to J\to\widehat X^n\)。若重复标签从未被使用，它们不增加标签熵。一般有限码都有

对 IID 源，写 \(D_i=\mathbb E d(X_i,\widehat X_i)\)，则

最后一步是凸性。由此 \(r_n\geq R_{\rm info}(\bar D)\)，但不保证某个有限码恰好达到边界。实验并列显示实际码率、每符号标签熵和实际失真对应的信息下界。

4. 从测试信道到长码：覆盖概率不可省略

互信息关于固定源边缘下的测试信道为凸函数。混合两个测试信道使失真线性混合、互信息不超过加权平均，因而 \(R_{\rm info}\) 凸且不增。这也解释了为何可以在有余量的预算间连续逼近。

取一个测试联合分布 \(P_{X\widehat X}\)，令其平均失真为 \(D'\lt D\)、互信息为 \(I\)。独立抽取 \(M\) 个重构词，每个服从 \(P_{\widehat X}^n\)。对每个原词，寻找一条同时失真小、信息密度不过大的候选。

记可接受集合 \(F_n\) 满足

在真实测试联合分布下，IID大数定律使 \(P(F_n^c)=\eta_n\to0\)。除概率至多 \(\sqrt{\eta_n}\) 的坏原词外，条件接受率至少为 \(1-\sqrt{\eta_n}\)。对这样的好原词，由似然比换测度，独立候选的命中率至少为

独立造码本使全部候选都失败的条件概率为 \((1-q_x)^M\leq e^{-Mq_x}\)。所以平均覆盖失败率至多

取 \(M=\lceil2^{nR}\rceil\) 且 \(R>I+\epsilon\)，两项都趋零。有界失真下，失败事件的期望成本也趋零；再选择 \(D'+\epsilon\lt D\)，便得到达标的长码。存在性来自对码本取平均，不承诺所有随机码本都好。

这段证明明确用了有限字母表与有界失真。高斯平方误差是无界情形，还需尾部可积性处理。一般可达性和边界条件见 MIT 第24章。

5. BA迭代：边缘不动，并不足以保证最优

采用自然对数单位，固定 \(\beta\geq0\)，最小化

若互信息以 bit 计算，则同一目标中的系数为 \(\beta/\ln2\)；不能把数值相同的两个乘子直接互换。

BA从重构边缘 \(q^{(t)}\) 出发，交替执行

它交替最小化 \(\sum_xp_xD_{\rm KL}(W_x\|q)+\beta\mathbb E d\)。固定 \(W\) 时最优 \(q\) 是其输出边缘；固定 \(q\) 时用归一化指数公式得到最优 \(W\)。

如果某个 \(q_y^{(0)}=0\)，其后每一步该分量都为零。于是一个坏的边界起点可能原地不动：例如 \(p=0.1,\beta=3,q^{(0)}=(1,0)\)，重构永远为 0，边缘变化量为 0，失真仍是 0.1。这不能当作全局最优。

实验保留固定步数的全部轨迹，以 log-sum-exp 计算；很小但非零的内部概率保留对数，不靠人为添加最小正数改变支持。最后的微小负互信息或负对偶差若由舍入产生，也保留原始值并标为浮点诊断。

6. 给BA一个可复算的上下界

对当前 \(q\)，记

设 \(A=\max_yc_y\)。因为 \(\sum_yq_yc_y=1\)，有 \(A\geq1\)。取 \(a_x=(AZ_x)^{-1}\)，则每个 \(y\) 都满足

为什么这给下界？对任意联合分布，把 \(p_xa_xe^{-\beta d(x,y)}\) 看成总质量不超过 1 的候选反向分布。KL非负给出

对 \(y\) 平均，得到所有测试信道共同遵守的下界

当前实际 \(W\) 的 \(U=I_{\rm nat}(W)+\beta D(W)\) 是上界。于是 \(U-L\) 比边缘变化量更直接反映最优性余量；它同时检查未被当前 \(q\) 使用的输出列，能发现支持锁死。

在二元 Hamming 模型中，还能独立核对最优失真

然后代入第2节公式得到最优目标。此处算法用固定乘子，并不是“输入一个预算就自动求出相应乘子”。面板把预算下的解析最优信道与乘子下的BA轨迹分别列明。

7. 高斯反注水：保留方向也要付精度成本

设独立实高斯坐标 \(X_i\sim N(0,\lambda_i)\)，总平方误差预算为 \(D_{\rm tot}\)。这里先按每个向量计率，不除以坐标数。单坐标 \(\lambda_i>0\) 时，\(0\lt D_i\lt \lambda_i\) 的信息率为 \(\tfrac12\log_2(\lambda_i/D_i)\)；\(D_i\geq\lambda_i\) 时零率；\(D_i=0\) 时无穷率。

高斯的可达联合分布可以反向写成

下界来自 \(h(X_i\mid\widehat X_i)=h(X_i-\widehat X_i\mid\widehat X_i)\leq h(X_i-\widehat X_i)\) 与给定方差的高斯最大熵性质。精确模型并不要求前向误差独立于原信号。

最小化各坐标码率之和，并约束 \(\sum_iD_i\leq D_{\rm tot}\)。对活动坐标求导，

因此活动坐标获得相同绝对失真水位 \(\theta\)，被丢弃的坐标最多花掉自身方差：

（预算小于总方差时），且

零方差坐标不承载信息；总预算超过总方差时，全部重构为零即可，剩余预算不必用尽。实验用精确分数确定活动集合和水位，再计算对数码率。若需每坐标率，将总率除以维数。

相关高斯向量可以正交对角化协方差，平方误差在正交变换下不变，再对特征值反注水。小方差方向可能被舍弃，大方差方向却仍有有限精度成本；这比“只保留几个PCA分量”多了一步。参阅 Stanford EE274 变换编码讲义。

8. 类型概率：先保留有限前因子

对二元 IID 源，\(K\) 为 1 的个数，\(q=k/n\)。给定类型有 \(\binom nk\) 个词，每个词的概率为 \(p^k(1-p)^{n-k}\)。因此

当 \(0\lt p\lt 1\) 时，单词概率可写为

二元类型基数满足一个够用的多项式界

下界也可取更紧的 \((n+1)^{-1}\)：在 Bernoulli\((q=k/n)\) 下，\(k\) 是二项分布的众数，其质量至少为 \(1/(n+1)\)。乘回每词概率便得到所需类型基数下界。上界来自该类型在同一分布下的总概率不超过 1。

所以 \(2^{-nD_2(q\|p)}\) 表示指数部分，不等于有限类型的精确质量。若 \(p\) 为端点而类型使用了源中不可能的符号，则质量为零、KL为无穷，不能用截到某个小正数的曲线替代。

对于任意已选择的类型集合，实验精确计算其总概率 \(P_E\)、其中最大的类型质量 \(m_*\) 和正概率类型数 \(N_E\)。可直接核对

这个有限分数界与依赖对数的KL诊断并列显示；空事件时各质量为零，没有条件分布。

9. Sanov：开集、闭集与格点各做什么

设有限字母表上的 IID 真分布为 \(P\)，经验分布为 \(\widehat P_n\)。以整个概率单纯形的相对拓扑取事件 \(E\) 的内部和闭包，Sanov给出

约定空集上的下确界为 \(+\infty\)，不满足绝对连续的 \(Q\) 的KL也为 \(+\infty\)。只有内外两侧的最小代价一致时，这份夹逼才给出一个共同指数。该表述的更一般形式见 Chafaï：From Boltzmann to random matrices and beyond，第648页。

有限字母表上的证明可以直接接第8节：类型数至多为多项式，上界对各类型求和；下界在事件内部选一个分布，用越来越细的整数类型逼近它。内部条件确保近似类型最终仍在事件里。

例如“恰好 \(K/n=0.7\)”是一个单点事件。若 \(n\) 不是 10 的倍数，根本没有对应整数类型，概率为零；若 \(n\) 是 10 的倍数，又有正概率。不能把某个有限KL值当成所有长度都适用的概率等式。实验的单点模式用分数精确判断格点，不借浮点容差把相邻比例算作相等。

相比之下，公平硬币事件 \(K/n\geq0.7\) 的极限速率是 \(D_2(0.7\|0.5)\approx0.118709100769\)。在 \(n=100\) 时，实际概率约 \(3.9250698228\times10^{-5}\)，实际负对数除以100约为 \(0.146369221562\)；有限前因子仍看得见。

10. 条件分布与指数倾斜：有限平均不等于极限点

二元事件的完整条件分布为

公平硬币在 \(n=100,K/n\geq0.7\) 条件下，平均正面比例约为 \(0.706613947501\)，并非精确的 0.7。在这一闭尾事件中，KL在 \(q\geq0.7\) 上唯一最小于 0.7；更远区域有严格更大代价，因此条件质量随长度增长集中到边界附近。

一般有限字母表、正的真分布 \(p_i\)、线性均值约束下，KL最小化的驻点满足

令 \(\psi(\lambda)=\ln\sum_i p_i e^{\lambda f_i}\)，则 \(\psi'(\lambda)=\mathbb E_{q_\lambda}f\)。在可行的内部均值 \(a\) 上选择 \(\psi'(\lambda)=a\)，有

所以 Cramér 速率函数是对数矩母函数的 Legendre 变换；KL最小化给出同一个代价。不能把两种对象的名字交换。对一般集合，还需核对唯一投影和事件正则性，才有条件集中到某个单一分布的结论。信息投影的推导见 MIT 第12章。

11. 四道完整练习：从有限记录走回证明

练习一：偏置源的前向信道究竟长什么样？

令 \(p=0.1,D=0.05\)，构造最优测试联合分布，并求两个前向错误概率。

练习二：平均达标为什么仍有四分之一以上的坏块？

三位独立 Bernoulli\((0.1)\)，重构词为000和111，最近邻编码。求平均每位失真、最大支持失真与超过0.1的概率。

练习三：三维高斯的预算怎样分配？

独立坐标方差为 \(9,4,1\)，总平方失真预算为3。求反注水水位、逐坐标码率和前向重构条件分布。

练习四：同样写0.7，为何有时概率恰好为零？

比较公平硬币在 \(n=100\) 与 \(n=101\) 时“正面比例恰好0.7”，再说明“至少0.7”为何不同。

12. 怎样把这些结论带到真实压缩问题

高斯正码率段满足 \(D=\sigma^2 2^{-2R}\)，所以在同一理想模型中增加一比特，最优平方失真预算除以4，对应约6.02dB。这个等式不自动说明某份音频从16位改成8位就损失48dB：真实源分布、削波、量化方法、感知度量和编解码器的有限性能都需要另测。第23.1节的高码率标量量化近似也有自己的假设。

神经压缩的训练目标同样需要清楚的账本。例如对编码分布 \(q(z\mid x)\) 与候选先验 \(p(z)\)，在KL有定义时，

右端第二项是边缘模型失配代价，因此一个训练中的KL项不自动等于互信息，更不自动等于最终文件字节数。用率失真思想分析工程系统时，应明确源、失真函数、码率口径、模型限制及实际编码方式。

进入最优传输前，可以复述四个机制：反向测试信道怎样构造边界，有限码本怎样付出真实失真，反注水怎样分配精度，类型计数怎样留下KL指数。它们共享优化与概率工具，但各自约束和可观测量必须完整保留。