数据处理不等式 | Codeboy's Blog

形式陈述

设 $X,Y,Z$ 取值于标准 Borel 空间（包括有限、可数离散空间和通常的欧氏空间）。后处理由一个从 $Y$ 的取值空间到 $Z$ 的取值空间的概率核 $K$ 给出，联合律满足

P_{XYZ}(dx,dy,dz)=P_{XY}(dx,dy)K(y,dz).

记这种条件独立结构为 $X\to Y\to Z$ ，也称三变量的 Markov 链。此处不要求三个变量使用同一状态空间，也不额外要求时间齐次；同一状态空间上的Markov 过程是它的一个熟悉来源。上述空间假设保证相关正则条件分布存在，因而也可写为 $P_{Z\mid X,Y}=P_{Z\mid Y}$ （联合分布几乎处处），即 $X\perp Z\mid Y$ 。离散情形只需在正概率的 $(x,y)$ 上检查，并有 $p(x,y,z)=p(x,y)K(z\mid y)$ 。

数据处理不等式对互信息断言

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

确定后处理 $Z=g(Y)$ 对应 Dirac 核，是特殊情形。更一般地，在可测空间之间把同一个概率核 $K$ 分别作用于 $P,Q$ ，KL 散度收缩：

D(PK\|QK)\le D(P\|Q).

直觉

处理器只拿到 $Y$ ，无论它确定计算、随机化、量化还是丢弃数据，都不能恢复 $Y$ 已经没有的关于 $X$ 的信息。关键不在“处理是否复杂”，而在处理器是否还有另一条通往 $X$ 的信息路径。只要 $Z$ 偷看了 $X$ 、训练数据或旁路信号，所需 Markov 条件就可能失效。

公平消息比特经三次独立 BSC 观测后保留约 0.8624 bit 信息，压成多数判决后保留约 0.8157 bit — 多数判决保留消息估计，却丢失观测的置信程度

图中三条观测通路都读取同一个消息比特；汇集观测后才进行多数后处理。数值按下文的 $p=0.1$ 计算，全部以 bit 为单位。

互信息证明机制

在上述标准 Borel 范围内，以条件联合分布相对条件边缘乘积的 KL 散度取平均定义条件互信息。它非负，且链式法则可按两种顺序展开同一个量：

\begin{aligned} I(X;Y,Z)&=I(X;Y)+I(X;Z\mid Y),\\ I(X;Y,Z)&=I(X;Z)+I(X;Y\mid Z). \end{aligned}

Markov 条件令 $I(X;Z\mid Y)=0$ ，而条件互信息非负，所以

I(X;Y)=I(X;Z)+I(X;Y\mid Z)\ge I(X;Z).

这里始终是非负扩展实数的加法；即使互信息无穷，也没有使用 $\infty-\infty$ 。下文仅在互信息有限时讨论差值和等号的逆向条件。

离散 KL 收缩版本可由 log-sum 不等式证明：输出 $z$ 把多个输入 $x$ 的概率质量混合在一起，凸性保证这种合并不会增大散度。

例子与边界

可复算例：串联两个 BSC

令 $X$ 为公平比特， $Y=X\oplus N_1$ 、 $Z=Y\oplus N_2$ ，其中 $X,N_1,N_2$ 相互独立，且两个噪声都服从 $\operatorname{Bernoulli}(0.1)$ 。第二次翻转只使用 $Y$ 与新的独立噪声，故 $X\to Y\to Z$ 。第一段给出

I(X;Y)=1-h_2(0.1)\approx0.5310\ \text{bit}.

两次翻转恰有一次发生的概率为

q=2(0.1)(0.9)=0.18,

所以级联等效为 BSC $(0.18)$ ，并且

I(X;Z)=1-h_2(0.18)\approx0.3199\ \text{bit}<I(X;Y).

若后处理是可逆函数，则 $Y$ 可由 $Z$ 恢复，反向也有一条 Markov 链，因而取等；在互信息有限时，证明中的差值恰为 $I(X;Y\mid Z)$ ，所以等号当且仅当 $X\perp Y\mid Z$ ：给定 $Z$ 后，补看 $Y$ 不再帮助了解 $X$ 。

三次观测与多数判决：信息在哪一步丢失

令 $U$ 为公平消息比特，使用BSC$(0.1)$ 三重重复码，即 $Y_i=U\oplus N_i$ ，三份噪声相互独立且独立于 $U$ 。令 $\widehat U$ 为 $Y^3=(Y_1,Y_2,Y_3)$ 的多数值。消息到三次观测再到判决构成 $U\to Y^3\to\widehat U$ 。八种噪声事件已在 BSC 页列出，这里计算接收者看到每类观测后的不确定性。

例如 $y=000$ 时，两条消息产生它的概率分别是 $0.729$ 和 $0.001$ 。乘上均匀先验后，其边缘概率为 $(0.729+0.001)/2=0.365$ ，后验 $P(U=1\mid000)=1/730$ 。若 $y=001$ ，相应似然为 $0.081$ 和 $0.009$ ，故边缘概率为 $0.045$ ，后验 $P(U=1\mid001)=1/10$ 。其他串由交换坐标或补位得到：

完整观测 $Y^3=y$	串数	每串边缘概率	给定该观测的判决后验错误
000、111	2	$0.365$	$1/730$
001、010、100、011、101、110	6	$0.045$	$1/10$

表中最后一列是 $\Pr[U\ne\widehat U(y)\mid Y^3=y]$ ，仍以完整观测为条件。只保留多数输出时，这两种置信程度便无法区分；例如 $\Pr[U=1\mid\widehat U=0]=0.014/0.5=0.028$ ，而非 $1/730$ 或 $1/10$ 。

令 $h_2$ 为二元熵。两类完整观测的总概率分别为 $0.73$ 和 $0.27$ ，于是

\begin{aligned} H(U\mid Y^3)&=0.73h_2(1/730)+0.27h_2(1/10)\\ &\approx0.1375822694,\\ I(U;Y^3)&=1-H(U\mid Y^3)\approx0.8624177306. \end{aligned}

多数译码对两个消息的错误都为 $0.028$ ，所以从 $U$ 到 $\widehat U$ 恰好是 BSC $(0.028)$ ，且 $\widehat U$ 仍均匀。因此

I(U;\widehat U)=1-h_2(0.028)\approx0.8157394067,

I(U;Y^3\mid\widehat U) =I(U;Y^3)-I(U;\widehat U)\approx0.0466783240.

多数输出把 $000$ 和 $001$ 都压成 $0$ ，却抹去了“全票一致”与“二比一”两种置信程度。保留完整观测能区分这两种后验，故不等式在这里严格成立。

单次观测的互信息仅为 $I(U;Y_1)=1-h_2(0.1)\approx0.5310044064$ 。三次观测比一次多带来信息并不违反 DPI：新增的 $Y_2,Y_3$ 又访问了 $U$ ，它们不是只由 $Y_1$ 和独立随机币产生的后处理。三次使用的输入也不是三个独立消息比特，故不能把 $I(U;Y^3)$ 写成 $3C$ ；它既不超过 $3C$ ，也不超过 $H(U)=1$ 。

Markov 条件缺失时会失败

令 $X$ 为公平比特、 $Y$ 为常数，并让 $Z=X$ 。此时

I(X;Y)=0,\qquad I(X;Z)=1,

但这不是反例，因为 $P_{Z\mid X,Y}$ 仍依赖 $X$ ，所以 $X\to Y\to Z$ 根本不成立。给后处理额外侧信息也属于同一种模型改变。

后处理不可逆也可以取等。令 $Y=(X,N)$ ，其中 $N$ 是与 $X$ 独立的公平比特，并令 $Z=X$ 。处理丢弃了 $N$ ，不能恢复整个 $Y$ ，但只丢弃无关噪声，所以 $I(X;Y)=I(X;Z)=H(X)$ 。可逆性是充分条件，并非必要条件。

DPI 收缩的是互信息或分布的 KL，不是样本值的欧氏距离；确定映射完全可能拉大某些点对距离。

推论与应用

数据处理不等式给出级联信道的容量上界，并支撑充分统计量、隐私机制和信息瓶颈分析。在译码下界中，消息 $M$ 、信道输出 $Y^n$ 与估计 $\widehat M$ 形成 $M\to Y^n\to\widehat M$ ，于是估计器不可能比完整观测携带更多消息信息；再结合Fano 不等式即可把信息不足转成错误下界。

统计、学习和通信归约都必须逐项验证相应 Markov 链。算法输出是观测的函数这一事实只控制后处理阶段；若算法还访问独立数据、公共随机币以外的相关侧信息，联合分布和条件独立关系必须重新写出。

参考资料

Yury Polyanskiy and Yihong Wu, Information Theory: From Coding to Learning，2024-08-16 作者稿，Theorem 3.7(c)，印刷 pp. 51–52，DPI 与链式证明。
Thomas M. Cover and Joy A. Thomas, Elements of Information Theory, 2nd ed., Wiley, 2006, §2.8.
Imre Csiszár and János Körner, Information Theory: Coding Theorems for Discrete Memoryless Systems, 2nd ed., Cambridge University Press, 2011, §§2.1–2.2.
Robert G. Gallager, Information Theory and Reliable Communication, Wiley, 1968, §4.4.
Madhu Sudan（授课），6.441 Transmission of Information: Scribe Notes, MIT, 2006，Lectures 3–4，条件熵、数据处理、Fano 与 AEP。

形式陈述 ​

互信息证明机制 ​

可复算例：串联两个 BSC ​

三次观测与多数判决：信息在哪一步丢失 ​

Markov 条件缺失时会失败 ​

反向链接

形式陈述

互信息证明机制

可复算例：串联两个 BSC

三次观测与多数判决：信息在哪一步丢失

Markov 条件缺失时会失败