从信源熵到互信息

1. 信源熵

为了表征信源的信息量，所有符号信息量的期望为
H [ X ] = − ∑ k = 1 n P r { X = a k } log ⁡ P r { X = a k } = E [ − log ⁡ P r { X } ] H[X] = -\sum_{k=1}^{n} P_r \{X=a_k\} \log P_r \{X=a_k\} \\ = \mathbb{E} [ - \log P_r \{X \} ] H[X]=−k=1∑n​Pr​{X=ak​}logPr​{X=ak​}=E[−logPr​{X}]

这就是 $X$ 的熵。

符号 $\mathbb{E}$ 代表对于函数 − log ⁡ P r { X } - \log P_r \{X \} −logPr​{X} 在样本 $X$ 上遍历。

2. 条件熵

如果有 X = { a k } k = 1 n X=\{a_k\}_{k=1}^{n} X={ak​}k=1n​ 和 Y = { b k } k = 1 m Y=\{b_k\}_{k=1}^{m} Y={bk​}k=1m​
单独考虑 $X$ 及其分布为 P r { X = a k } P_r \{X=a_k\} Pr​{X=ak​} 的熵即为 $H[X]$。

固定 $Y=b_j$，考虑 $X$ 的条件分布 P r { X = a k ∣ Y = b j } P_r \{X=a_k \vert Y=b_j\} Pr​{X=ak​∣Y=bj​}:

• 若 $X$、 $Y$ 独立，则 P r { X = a k ∣ Y = b j } = P r { X = a k } P_r \{X=a_k \vert Y=b_j\} = P_r \{X=a_k \} Pr​{X=ak​∣Y=bj​}=Pr​{X=ak​}
• 若 $X$、 $Y$ 不独立，则为新的分布

给定 $Y=b_j$ 下 $X$ 的熵，即为 P r { X = a k ∣ Y = b j } P_r \{X=a_k \vert Y=b_j\} Pr​{X=ak​∣Y=bj​} 的期望：
H [ X ∣ Y = b j ] = − ∑ k = 1 n P r { X = a k ∣ Y = b j } log ⁡ P r { X = a k ∣ Y = b j } H[X \vert Y=b_j] = -\sum_{k=1}^{n} P_r \{X=a_k \vert Y=b_j\} \log P_r \{X=a_k \vert Y=b_j\} H[X∣Y=bj​]=−k=1∑n​Pr​{X=ak​∣Y=bj​}logPr​{X=ak​∣Y=bj​}

---

给定 $Y$ 下 $X$ 的熵，即为 H { X ∣ Y = b j } H \{X \vert Y=b_j\} H{X∣Y=bj​} 的期望：
H [ X ∣ Y ] = ∑ k = 1 n P r { Y = b j } H [ X ∣ Y = b j ] H[X \vert Y ] = \sum_{k=1}^{n} P_r \{ Y=b_j\} H[X \vert Y=b_j] H[X∣Y]=k=1∑n​Pr​{Y=bj​}H[X∣Y=bj​]

3. 条件熵的性质

条件熵 = 联合熵 - 条件自身的熵

$$H[X|Y]=H[X,Y]-H[Y],H[Y|X]=H[X,Y]-H[X]$$

proof:
first, we have
H [ X ∣ Y ] = E [ − log ⁡ P r { X ∣ Y } ] H[X|Y]= \mathbb{E} [ -\log P_r\{ X|Y \}] H[X∣Y]=E[−logPr​{X∣Y}]
H [ X , Y ] = E [ − log ⁡ P r { X , Y } ] H[X,Y]= \mathbb{E} [ -\log P_r\{ X,Y \}] H[X,Y]=E[−logPr​{X,Y}]

符号 $\mathbb{E}$ 代表对于函数 $f(X,Y)$ 在样本 { X , Y } \{X,Y \} {X,Y} 上遍历。

since
P r { X ∣ Y } = P r { X , Y } P r { Y } P_r\{ X|Y \} = \frac{ P_r\{ X,Y \} }{ P_r\{ Y \} } Pr​{X∣Y}=Pr​{Y}Pr​{X,Y}​
we have
log ⁡ P r { X ∣ Y } = log ⁡ P r { X , Y } − log ⁡ P r { Y } \log P_r\{ X|Y \} = \log P_r\{ X,Y \} - \log { P_r\{ Y \} } logPr​{X∣Y}=logPr​{X,Y}−logPr​{Y}
so
E [ − log ⁡ P r { X ∣ Y } ] = E [ − log ⁡ P r { X , Y } ] − E [ − log ⁡ P r { Y } ] \mathbb{E} [- \log P_r\{ X|Y \}] = \mathbb{E} [-\log P_r\{ X,Y \}] - \mathbb{E}[-\log { P_r\{ Y \} } ] E[−logPr​{X∣Y}]=E[−logPr​{X,Y}]−E[−logPr​{Y}]

条件熵 <= 无条件熵（通过做差利用Jesen不等式证明）
$$H[X|Y]\le H[X]$$

联合熵 <= 各自熵之和
$$H[X|Y]=H[X,Y]-H[Y]\le H[X]\to H[X,Y]\le H[X]+H[Y]$$

4. 互信息

互信息：无条件熵 - 条件熵
$$\begin{gathered} I(X;Y)=H[X]-H[X|Y] \\ I(Y;X)=H[Y]-H[Y|X] \end{gathered}$$

互信息 = 各自熵之和 - 联合熵
I ( X ; Y ) = H [ X ] − H [ X ∣ Y ] = H [ X ] − { H [ X , Y ] − H [ Y ] } = H [ X ] + H [ Y ] − H [ X , Y ] I(X;Y) = H[X] - H[X|Y] \\ = H[X] - \{H[X,Y]-H[Y] \} \\ = H[X] + H[Y] - H[X,Y] I(X;Y)=H[X]−H[X∣Y]=H[X]−{H[X,Y]−H[Y]}=H[X]+H[Y]−H[X,Y]
$$I(Y;X)=H[X]+H[Y]-H[X,Y]$$

互信息是对称的，即为
$$I(X;Y)=I(Y;X)$$