INFOTH Note 4: Cond. MI & Cond. KL, Data Processing Ineq.
4.1 Conditional Mutual Information and Cond. KL Divergence
Def: Cond. MI
\[ I(X;Y|Z):=H(X|Z)-H(X|Y,Z)=H(Y|Z)-H(Y|X,Z) \]展开式子可以发现，在互信息中定义的 给定 Z 也是 将 Z 求和的：
\[ \begin{aligned} I(X;Y|Z)&=H(X|Z)-H(X|Y,Z) \\&=\sum_z p(z)\sum_x p(x|z)\log \frac1{p(x|z)} \\&+\sum_{z}p(z)\sum_y p(y|z)\sum_x p(x|y,z)\log p(x|y,z)\quad\text{(Def)} \\&=\sum_{x,z}p(x,z)\log \frac1{p(x|z)}+ \sum_{x,y,z}p(x,y,z)\log{p(x|y,z)} \\&=\sum_{x,y,z}p(x,y,z)\log \frac1{p(x|z)}+ \sum_{x,y,z}p(x,y,z)\log{p(x|y,z)} \\&=\sum_{x,y,z}p(x,y,z)\log {p(x|y,z)\over p(x|z)} \\&=\sum_{x,y,z}p(x,y,z)\log {p(x,y|z)\over p(x|z)p(y|z)} \\&=E_{X,Y,Z}\left[\log {p(x,y|z)\over p(x|z)p(y|z)}\right] \end{aligned} \]We can also write the expectation as
\[ D(p(x,y|z)||p(x|z)p(y|z)) \]which is the conditional relative entropy (KL divergence).
Yes, \(I(X;Y|Z)\) is the conditional relative entropy \(D(\cdot||\cdot|Z)\) as defined in the unconditional MI; and it’s also in the expected form as defined.
Def: Cond. KL
\[ D(p(x|z)||q(x|z)|\sigma(z)):=\sum_z \sigma(z)\sum_xp(x|z)\log {p(x|z)\over q(x|z)} \]Fact: 条件可能不小于等于非条件
\[ I(X;Y|Z) ~?~I(X;Y) \]but we have a firmly guaranteed \(H(X,Y|Z)\le H(X,Y)\).
4.2 Chain Rules
Theorem: KL Divergence Chain Rule
- Analogy: \(p(u,z)=p(z)p(u|z)\)
Chain Rule for Relative Entropy:
\[ D(p(u,z)||q(u,z))=D(p(z)||q(z))+D(p(u|z)||q(u|z)) \]Theorem: General MI Chain Rule
\[ I(X;Y_1,\dots,Y_n)=I(X;Y_1)+I(X;Y_2|Y_1)+\dots+ I(X;Y_n|Y_1\dots Y_{n-1}) \]- 右半部分在进行chain rule
- 当然左半部分的chain也成立
Proof Sketches (2 methods)
- Using Successive Addition
- Using Expectation Linearity
4.3 Data Processing Inequality
Def: Markov Chain (1st order)
We say 3 random variables form a (1st order) Markov Chain written as \(X\to Y\to Z\) if
\[ p(z|x,y)=p(z|y)p(y|x) \]Theorem
If \(X\to Y\to Z\), then
\[ I(X;Z)\le I(X;Y). \]-
A variable processed from another variable cannot contain more information.
- Information will not increase after being processed.
-
Equality Condition: \(I(X;Y|Z)=0\). the amount of information that \(Y\) provides about \(X\) that is not available in \(Z\).
- \(Z\) must contain all the information that \(Y\) has about \(X\)
- \(Z\) 是 \(Y\) 的充分统计量 sufficient statistics \(I(X;Z)=I(X;Y)\)
-
Also: because \(I(X;Z)=H(X)-H(X|Z)\), \(I(X;Y)=H(X)-H(X|Y)\), hence
\(H(X|Z)\ge H(X|Y)\) – the farther one in the chain has more entropy; processing adds entropy.
Proof
First, from the chain rule of MI,
\[ I(X;Y,Z)=I(X;Z)+I(X;Y|Z)=I(X;Y)+I(X;Z|Y) \]Because \(X\perp\!\!\!\perp Z|Y\), \(I(X;Z|Y)=0\).
So
\[ I(X;Z)+I(X;Y|Z)=I(X;Y) \]and \(I(\cdot;\cdot)\ge 0\), which means
\[ I(X;Z)\le I(X;Y)\qquad\square \]and the equality holds iff
\[ I(X;Y|Z)=0 \](or given \(Z\), \(X\perp\!\!\!\perp Y|Z\)).