数据处理不等式

数据处理不等式可用来表明，任何巧妙的数据操作都无法改善从数据中得出的推论。

定义 如果随机变量 X、Y、Z 的条件分布仅取决于 Y，且与 X 条件无关，则称它们按该顺序形成马尔可夫链（表示为 \(X \rightarrow Y \rightarrow Z\)）。具体而言，如果联合概率质量函数可以写成如下形式，则 X、Y 和 Z 形成马尔可夫链 \(X \rightarrow Y \rightarrow Z\)

\[p(x,y,z) = p(x)p(y|x)p(z|y). \tag{2.117}\]

一些简单的结论如下：

• 当且仅当，给定Y，X和Z是条件独立的，\(X \rightarrow Y \rightarrow Z\)。马尔可夫性意味着条件独立，因为 \[p(x,z|y) = \frac{p(x,y,z)}{p(y)} = \frac{p(x,y)p(z|y)}{p(y)}= p(x|y)p(z|y).\tag{2.118}\]

  这是马尔可夫链的特征，可以扩展为定义马尔可夫场，马尔可夫场是n维随机过程，其中，给定边界上的值，内部和外部是独立的。

• \(X \rightarrow Y \rightarrow Z\)意味着\(Z \rightarrow Y \rightarrow X\)。因此，条件有时记为 \(X \leftrightarrow Y \leftrightarrow Z\)。

• 若\(Z=f(Y)\)，则\(X \rightarrow Y \rightarrow Z\)。

现在我们可以证明一个重要且有用的定理，该定理表明对 Y 的任何处理，无论是确定性的还是随机的，都不能增加 Y 包含的有关 X 的信息。

定理 2.8.1 （数据处理不等式） 若\(X \rightarrow Y \rightarrow Z\)，则\(I(X;Y) \ge I(X;Z)\)。

证明：通过链式法则，我们可以用两种不同方式展开互信息：

\begin{align} I(X;Y,Z) &= I(X;Z) + I(X;Y|Z) \tag{2.119}\\ &= I(X;Y) + I(X;Z|Y).\tag{2.120} \end{align}

由于给定Y，X和Z条件独立，有\(I(X;Z|Y) = 0\)。由于\(I(X;Y|Z)\ge 0\)，得到

\[I(X;Y) \ge I(X;Z).\tag{2.121}\] 当且仅当 \(I(X;Y|Z) = 0\)(即，\(X \rightarrow Y \rightarrow Z\)形成马尔科夫链)时，等号成立。类似的，可以证明\(I(Y;Z)\ge I(X;Z)\)。

引理 特别是，若 \(Z = g(Y)\)，有\(I(X;Y) \ge I(X;g(Y))\)。

证明： \(X \rightarrow Y \rightarrow g(Y)\)形成马尔科夫链。

因此，数据Y的函数不能增加关于X的信息。

引理 若\(X \rightarrow Y \rightarrow Z\)，那么\(I(X;Y|Z) \le I(X;Y)\)。

证明：根据马尔可夫性，我们注意到(2.119)和（2.120）中\(I(X;Z|Y) = 0\)，以及\(I(X;Z)\ge 0\)。因此， \[I(X;Y|Z) \le I(X;Y).\tag{2.122}\]

因此，通过对“下游”随机变量 Z 的观测，X 和 Y 的依赖性会降低（或保持不变）。注意，当 X、Y 和 Z 不构成马尔可夫链时，\(I(X;Y|Z) \le I(X;Y)\) 也是可能的。例如，设 X 和 Y 是独立的公平二进制随机变量，且 Z = X + Y。则 I (X; Y) = 0，但 \(I (X; Y|Z) = H(X|Z) − H(X|Y, Z) = H(X|Z) = P(Z = 1)H (X|Z = 1) = \frac{1}{2}\ bit\)。