PML Exercise 6 Solutions

Exercise 6.1 [Expressing mutual information in terms of entropies † ]

Prove the following identities:

$$I(X;Y) = H(X) - H(X|Y) = H(Y) - H(Y|X)$$

and

$$H(X,Y) = H(X|Y) + H(Y|X) + I(X;Y)$$

解答： 易知 $H(X)=-\mathbb{E}_{X}[\log p(X)], H(X\mid Y)=\mathbb{E}_{p(Y)}[H(p(X\mid Y))]=H(X,Y)-H(Y)$，因此 $H(X) - H(X\mid Y) = H(X) + H(Y)-H(X,Y)=H(Y)-H(Y\mid X)$，又有 $I(X;Y)=\sum_{X}\sum_{Y}p(X,Y)\log \frac{p(X,Y)}{p(X)p(Y)}$，所以

$$\begin{aligned} H(X)+H(Y)-H(X,Y)&=-\sum_{X}p(X)\log p(X)-\sum_{Y}p(Y)\log p(Y)+\sum_{X}\sum_{Y}p(X,Y)\log p(X,Y)\\ &=-\sum_{X}\sum_{Y}p(X,Y)\log p(X)-\sum_{Y}\sum_{X}p(Y,X)\log p(Y)+\sum_{X}\sum_{Y}p(X,Y)\log p(X,Y)\\ &=\sum_{X}\sum_{Y}p(X,Y)\log \frac{p(X,Y)}{p(X)p(Y)} \end{aligned}$$

Exercise 6.2 [Relationship between $D_{KL}(p||q)$ and $\chi^2$ statistic]

Show that, if $p(x) \approx q(x)$, then

$$D_{KL}(p \parallel q) \approx \frac{1}{2} \chi^2$$

where

$$\chi^2 = \sum_x \frac{(p(x) - q(x))^2}{q(x)}$$

Hint: write

$$p(x) = \Delta(x) + q(x)$$ $$\frac{p(x)}{q(x)} = 1 + \frac{\Delta(x)}{q(x)}$$

and use the Taylor series expansion for $\log(1 + x)$:

$$\log(1 + x) = x - \frac{x^2}{2} + \frac{x^3}{3} - \frac{x^4}{4} \dots$$

for $-1 < x \le 1$.

解答： 已知 $D_{KL}(p \parallel q)=\sum_{x} p(x)\log \frac{p(x)}{q(x)}$，设 $p(x) = \Delta(x) + q(x)$，则

$$\begin{aligned} D_{KL}(p\parallel q)&=\sum_x (\Delta(x) + q(x)) \log \frac{p(x)}{q(x)}\\ &=\sum_x (\Delta(x) + q(x))\log (1+\frac{\Delta(x)}{q(x)})\\ &=\sum_x (\Delta(x) + q(x))(\frac{\Delta(x)}{q(x)}-\frac{\Delta^2(x)}{2q^2(x)})\\ &=\sum_x \frac{\Delta^2(x)}{q(x)}+\Delta(x)-\frac{\Delta^3(x)}{2q^2(x)}-\frac{\Delta^2(x)}{2q(x)}\\ &=\sum_x \frac{\Delta^2(x)}{2q(x)}+\Delta(x)-\frac{\Delta^3(x)}{2q^2(x)} \end{aligned}$$

利用 $\sum_{x} \Delta(x)=\sum_{x}(p(x) -q(x))=0$ 的性质，以及 $\frac{\Delta^3(x)}{2q^2(x)}$ 是 $\frac{\Delta^2(x)}{2q(x)}$ 的更高阶无穷小项。

Exercise 6.3 [Fun with entropies † ]

Consider the joint distribution $p(X,Y)$:

$Y \backslash X$	1	2	3	4
1	1/8	1/16	1/32	1/32
2	1/16	1/8	1/32	1/32
3	1/16	1/16	1/16	1/16
4	1/4	0	0	0

• a. What is the joint entropy $H(X,Y)$?
• b. What are the marginal entropies $H(X)$ and $H(Y)$?
• c. The entropy of $X$ conditioned on a specific value of $y$ is defined as

$$H(X|Y = y) = - \sum_x p(x|y) \log p(x|y)$$

Compute $H(X|y)$ for each value of $y$. Does the posterior entropy on $X$ ever increase given an observation of $Y$?

• d. The conditional entropy is defined as

$$H(X|Y) = \sum_y p(y)H(X|Y = y)$$

Compute this. Does the posterior entropy on $X$ increase or decrease when averaged over the possible values of $Y$?

• e. What is the mutual information between $X$ and $Y$?

解答：

• a. 因为 $H(X,Y)=-\sum_{X}\sum_{Y} p(X,Y)\log_2 p(X,Y)$，因此计算可得 $-1*(1/4\log_2 1/4)-2*(1/8\log_2 1/8)-6*(1/16\log_2 1/16)-4*(1/32\log_2 1/32)=27/8$
• b. 因为 $H(X)=-\sum_Xp(X)\log_2p(X)$，因此计算可得 $H(X)=-1/2\log_2 1/2 -1/4\log_2 1/4-1/8\log_2 1/8-1/8\log_2 1/8=7/4$，$H(Y)=-1/4\log_2 1/4 - 1/4\log_2 1/4 - 1/4\log_2 1/4 - 1/4\log_2 1/4=2$
• c. 易知 $H(X\mid Y=1)=-1/8\log_2 1/8 - 1/16\log_2 1/16 - 2* 1/32 \log_2 1/32=15/16$，$H(X\mid Y=2)=15/16$，$H(X\mid Y=3)=1$，$H(X\mid Y=4)=1/2$，给定 $Y$ 并不会增加 $X$ 的熵
• d. 易得 $H(X\mid Y)=27/32$
• e. 易知 $I(X;Y)=H(X)-H(X\mid Y)=7/4 -27/32=29/32$

⚠️ 纠正：

• c. 应使用条件概率而不是联合概率，

$$H(X|Y=1) = -\frac{1}{2}\log_2\frac{1}{2} - \frac{1}{4}\log_2\frac{1}{4} - 2(\frac{1}{8}\log_2\frac{1}{8}) = \frac{7}{4}, H(X|Y=2) = \frac{7}{4}, H(X|Y=3) = -4(\frac{1}{4}\log_2\frac{1}{4}) = 2, H(X|Y=4) = -1\log_2 1 = 0$$

可知某些特定的观测结果会使熵增加。

• d. 易得 $H(X|Y) = \frac{1}{4}(\frac{7}{4}) + \frac{1}{4}(\frac{7}{4}) + \frac{1}{4}(2) + \frac{1}{4}(0) = \frac{1}{4}(\frac{22}{4}) = \frac{11}{8}$。平均来看，后验熵下降了（$11/8 < 7/4$）。
• e. 易得 $I(X;Y) = H(X) - H(X|Y) = \frac{7}{4} - \frac{11}{8} = \frac{14}{8} - \frac{11}{8} = \frac{3}{8}$

Exercise 6.4 [Forwards vs reverse KL divergence]

Consider a factored approximation $q(x, y) = q(x)q(y)$ to a joint distribution $p(x, y)$. Show that to minimize the forwards KL $D_{KL}(p \parallel q)$ we should set $q(x) = p(x)$ and $q(y) = p(y)$, i.e., the optimal approximation is a product of marginals.

Now consider the following joint distribution, where the rows represent $y$ and the columns $x$:

$Y \backslash X$	1	2	3	4
1	1/8	1/8	0	0
2	1/8	1/8	0	0
3	0	0	1/4	0
4	0	0	0	1/4

Show that the reverse KL $D_{KL}(q \parallel p)$ for this $p$ has three distinct minima. Identify those minima and evaluate $D_{KL}(q \parallel p)$ at each of them. What is the value of $D_{KL}(q \parallel p)$ if we set $q(x, y) = p(x)p(y)$?

解答： 将其展开

$$\begin{aligned} D_{KL}(p\mid \mid q)&=\sum_{x,y}p(x,y)\log \frac{p(x,y)}{q(x,y)}\\ &=\sum_{x,y}p(x,y)(\log p(x,y)-\log q(x)-\log q(y))\\ &=\sum_{x,y}p(x,y)\log p(x,y)-\sum_x p(x)\log q(x)-\sum_y p(y)\log q(y) \end{aligned}$$

又由 KL 散度性质可知 $\sum_x p(x)\log q(x) \leq \sum_x p(x)\log p(x)$，所以最小化时 $q(x)=p(x), q(y)=p(y)$。（因为 $D_{KL}(p \parallel q) = \sum p(x)\log p(x) - \sum p(x)\log q(x) \ge 0$，当且仅当 $p=q$ 时取等号，即 $-\sum p(x)\log q(x)$ 在 $q=p$ 时取得最小值）

$$\begin{aligned} D_{KL}(p \parallel q) &= \sum_{x,y}p(x,y)\log p(x,y) - \sum_x p(x)\log q(x) - \sum_y p(y)\log q(y) \\ &= -H(X,Y) \\ &\quad + H(X) + \sum_x p(x)\log \frac{p(x)}{q(x)} \\ &\quad + H(Y) + \sum_y p(y)\log \frac{p(y)}{q(y)} \\ &= \underbrace{-H(X,Y) + H(X) + H(Y)}_{\text{常数 } I(X;Y)} + \underbrace{D_{KL}(p_x \parallel q_x)}_{\ge 0} + \underbrace{D_{KL}(p_y \parallel q_y)}_{\ge 0} \end{aligned}$$

所以最小化时必须满足 $q(x)=p(x), q(y)=p(y)$。

反向 KL 散度的优化目标为

$$D_{KL}(q \parallel p) = \sum_{x,y} q(x)q(y) \log \frac{q(x)q(y)}{p(x,y)}$$

如果矩阵中某个位置 $p(x,y) = 0$，但近似分布在这个位置 $q(x)q(y) > 0$，那么散度就会直接变成 $\log(\frac{\text{正数}}{0}) \to +\infty$。为了避免出现无穷大的惩罚，反向 KL 散度要求：只要 $p(x,y)$ 是 0 的地方，$q(x)q(y)$ 必须也是 0。

因为 $q(x,y) = q(x)q(y)$ 必须是一个独立分布的乘积（在矩阵上表现为矩形区块），它绝不能跨越不同的“孤岛”（否则就会踩到 0 的雷区）。因此，$q$ 只能选择“依附”在这三个孤岛中的某一个上，这就是题目说的三个局部极小值（3 distinct minima）： 极小值 1：占据左上角 $2\times 2$ 区块，$q(x) = [1/2, 1/2, 0, 0]$, $q(y) = [1/2, 1/2, 0, 0]$，在这个区块内，$q(x,y) = 1/4$。$D_{KL} = 4 \times \left( \frac{1}{4} \log \frac{1/4}{1/8} \right) = \log 2$ 极小值 2：占据 $(3,3)$ 区块，$q(x) = [0, 0, 1, 0]$, $q(y) = [0, 0, 1, 0]$，这个点上 $q(3,3) = 1$，$p(3,3) = 1/4$。$D_{KL} = 1 \times \log \frac{1}{1/4} = \log 4 = 2\log 2$ 极小值 3：占据 $(4,4)$ 区块，跟极小值 2 类似，$D_{KL} = \log 4 = 2\log 2$

如果设置 $q(x, y) = p(x)p(y)$ 则 $q(x,y) = 1/16$，但会导致 $D_{KL}(q \parallel p) = \infty$。