[读书笔记] [PRML] 1.6 Information Theory

这一小节的知识点主要是信息论中的熵、相对熵（KL散度）、条件熵以及互信息。这几个信息论中的概念在机器学习中起到很大的作用，比如决策树上特征的选择，以及最近的一些工作利用互信息取得了不错的效果。

在熵之前，有一个信息量的概念，什么是信息量？当你被告知“有效抗癌药物研发成功”，你一定非常惊讶，觉得信息量很大；当你被告知"今天下午将停电"，你就不那么惊讶了；而当你被告知“明天太阳会升起”，你估计就直接忽视这条消息了。你对这三条消息表现出的惊讶程度（degree of surprise）是不一样的。对于第一条消息，你是表现的非常惊讶，那么意味着它的信息量很大，而对于第三条消息，你对它一点都不惊讶，它的信息量就近乎于0，那么信息量就可以被看做是在一条消息上你表现出的"惊讶程度"。

另外，这三条消息中的事件发生的概率是不一样的，第一条消息中的事件就目前来看概率是很低的，对应着信息量很大，而第三条消息发生的概率是100%，对应着信息量为0，从这就可以发现，消息量与事件发生的概率相关，事件概率越低，信息量越大，事件发生的概率越大，信息量越小。

从另外一个角度看，事件发生概率低，意味着消息的不确定性大，而概率越高，消息的不确定越低，那么信息量也度量了消息的不确定性。

Entropy and conditional entropy

上面只是对信息量比较直观的理解，下面是具体的数学定义。

考虑一个离散的随机变量 $x$，当观察到变量的一个具体值时，我们从中收到了多少信息，这就是信息量。上面也提到了，信息量就可以看成在学习 $x$ 值时的惊讶程度，它也与事件发生的概率相关，那么在计算信息量 $h$ 时就依赖于概率分布 $p(x)$。因此，我们寻找一个函数 $h(x)$，它是关于 $p(x)$ 的单调函数，以及它的计算结果表示着信息量 $h$。

值得注意的是，$h(?)$ 还需满足：存在两个不相关的事件 $x$ 和 $y$，即 $p(x,y)=p(x)p(y)$，那么从事件 $(x,y)$ 中获得的信息量应该等于单独从 $x$ 和 $y$ 事件中获得的信息量之和，即 $h(x,y)=h(x)+h(y)$。因此，$h(?)$ 一个可能的定义为：
$$h(x)=?\log p(x)$$
上式加了一个负号保证计算出的信息量为非负。有了单一的信息量定义，就可以考虑在传递一个随机变量的值时，它的平均信息量，就可以通过概率分布 $p(x)$ 求其期望，则随机变量 $x$ 的熵（entropy）定义如下：
$$H[x]=?\sum _{x}p(x)\log p(x)$$
上面提到，信息量也度量了消息的不确定性，那么熵刻画了随机变量的不确定性，熵越大，随机变量的不确定性就越大。当然，还有另外一种解释就是最短平均编码长度。如下图，随机变量的分布越均匀，对应的熵越大，而分布集中在少数取值上，对应的熵越小。不难发现，离散随机变量的熵取最小值时，即为有一个 $p(x_i)=1$，而其他取值的概率为0。

而对于求最大熵，可以通过Lagrange乘子法求解。Lagrange函数为：
$$\tilde{H}=?\sum _{i}p(x_i)\ln p(x_i)+\lambda \left(\sum _{i}p(x_i)?1\right)$$
最大化这个函数，通过令其偏导等于0，得到：
$$\frac{?\tilde{H}}{?p(x_i)}=?1?\ln p(x_i)+\lambda =0$$
得到最大熵应该满足一个均匀分布 $p(x_i)=p(x_j),?i,j$，若随机变量 $x$ 的取值有 $M$ 种情况，即 $p(x_i)=\frac{1}{M}$，其对应的熵值为 $H=\ln M$。考虑连续随机变量，其熵的计算如下：
$$H[x]=?\int p(x)\ln p(x)dx$$
连续随机变量的熵也被称为微分熵（differential entropy），其最大熵的情况是随机变量服从正态分布。

考虑随机变量 $(x,y)$， 其联合概率分布为 $p(x,y)$。如果随机变量 $x$ 的值已知，那么有条件概率 $p(y|x)$，另外确定 $y$ 的值需要的信息量应该由 $?\ln p(y|x)$ 来衡量，那么平均另外需要的信息量为
$$\begin{array}{rl}H[y|x]& =??p(y,x)\ln p(y|x)\mathrm{d}y\mathrm{d}x\\ & =??p(x)p(y|x)\ln p(y|x)\mathrm{d}x\mathrm{d}y\\ & =?\int p(x_i)H[y|x=x_i]\mathrm{d}x\end{array}$$
也可以称为给定 $x$ 的 $y$ 的条件熵（conditional entropy），也可以理解为 $x$ 给定条件下 $y$ 的条件概率分布的熵对 $x$ 的数学期望。可以看到条件熵满足以下公式：
$$H[x,y]=H[y|x]+H[x]$$
其证明可见下面 exercise 1.37的解答。 上式可以理解为描述 $x,y$ 所需要的信息量等于描述 $x$ 所需要的信息量与再给定 $x$ 的情况下另外所需要的信息量的和。

Relative entropy and mutual information

Relative entropy

考虑一个未知的概率分布 $p(x)$，假设采用 $q(x)$ 来近似原分布，那么采用 $q(x)$ 分布去计算确定 $x$ 的值所需要的平均信息量为 $\int p(x)\ln q(x)\mathrm{d}x$，这个便是交叉熵，则另外所需的信息量为：
$$\begin{array}{rl}\mathrm{K}\mathrm{L}(p\Vert q)& =?\int p(x)\ln q(x)\mathrm{d}x?(?\int p(x)\ln p(x)\mathrm{d}x)\\ & =?\int p(x)\ln \left\{\frac{q(x)}{p(x)}\right\}\mathrm{d}x\\ & =E\left(\ln p(x)?\ln q(x)\right)\end{array}$$
上式即是相对熵（Relative entropy）的定义，更多见的是称为 KL散度（Kullback-Leibler divergence, KL divergence）。KL散度描述了两个概率分布 $p(x)$ 和 $q(x)$ 相似度的一种度量，而KL散度是非对称的，也不满足三角不等式，不是严格意义上的距离度量。

可以将 Jensen 不等式应用于上式计算，得到：
$$KL(p||q)=?\int p(x)\ln \left\{\frac{q(x)}{p(x)}\right\}\mathrm{d}x\ge ?\ln \int q(x)\mathrm{d}x=0$$
上面的推导可以得到KL散度是大于等于0，而使得等于0成立的唯一情况是 $p(x)=q(x)$，可以看出KL散度所描述的是两个分布不相似的程度，即越相似，KL散度越低，反之亦然。

考虑用带参数的分布 $q(x|\theta )$ 去估计未知分布 $p(x)$，比如多元高斯分布。确定参数 $\theta$ 的一种方式即是最小化 $p(x)$ 与 $q(x|\theta )$ 的 KL散度。但一个问题是我们不知道 $p(x)$ 的真实分布，可以采用训练集中的训练样本去估计。在上面 KL 散度的定义中有一种定义是 $\ln p(x)?\ln q(x)$ 的期望，而期望 $E(f)$ 可以用训练样本得到 $\frac{1}{N}{\sum }_{n=1}^{N}f(x_n)$去做近似，那么KL散度近似为：
KL(p∥q)≈1N∑n=1N{?ln?q(xn∣θ)+ln?p(xn)}KL(p \| q) \approx \frac{1}{N}\sum_{n=1}^N \{-\ln q(x_n|\theta) + \ln p(x_n)\} KL(p∥q)≈N1?n=1∑N?{ ?lnq(xn?∣θ)+lnp(xn?)}
可以发现上式的第二项是与参数 $\theta$ 无关的，而第一项正是 negative log likelihood function，因此，最小化KL散度就相当于最大化似然函数。

Mutual information

考虑两个变量 $x,y$ 的联合分布 $p(x,y)$。如果两个变量相互独立，则有 $p(x,y)=p(x)p(y)$；如果它们不独立，则可以用 $p(x,y)$ 和 $p(x)p(y)$ 的KL散度来衡量它们接近独立的程度，而不同于普通的相似性度量方法，互信息可以捕捉到变量间非线性的统计相关性，因而可以认为其能度量真实的依赖性：
$$\begin{array}{rl}I(x,y)& \equiv KL(p(x,y)\Vert p(x)p(y))\\ & =??p(x,y)\ln \left(\frac{p(x)p(y)}{p(x,y)}\right)\mathrm{d}x\mathrm{d}y\end{array}$$
上式便是互信息（mutual information）的定义。通过 KL散度大于等于0的性质，可以得出 $I(x,y)\ge 0$，当 $x$ 和 $y$ 独立时等于0成立。不难得出其与条件熵之间的关系，即：
$$\begin{array}{r}I[x,y]=H[x]?H[x|y]=H[y]?H[y|x]\end{array}$$
*其证明可以见下面 exercise 1.41。*前面提到 $H[y]$ 可以看作是随机变量不确定性的度量，以及前面提到 $H[y|x]$ 可以看成是已知 $x$ 后另外所需的信息量（这部分信息量是不被 $x$ 所有的），那么从不确定性角度看， $H[y|x]$ 可以看成是 $x$ 没有涉及到的 $y$ 部分的不确定性的度量，那么互信息就可以看成 $y$ 的不确定度，减去在 $x$ 已知之后 $y$ 的剩余不确定度的量。这证实了互信息的直观意义为给定 $x$ 之后 $y$ 信息量的减少值。

其实通过下面的 Venn 图能比较直观的解读，比如上面那句"给定 $y$ 之后的 $x$ 信息量的减少值"，原本 $y$ 的信息量即下图的右边那个圆部分，而在给定 $x$ 之后，信息量只有右边 $H(y|x)$ 那部分，而减少的就是中间那部分，那部分就是互信息。

如果将上面的两个变量对应到训练集中的类与特征，那么类与特征的互信息是等价于决策树学习中的信息增益的。给定训练集$D$ 和 特征 $A$，$H(D)$ 表示对数据集 $D$ 进行分类的不确定性，而条件熵 $H(D|A)$表示在特征A给定的条件下对数据集进行分类的不确定性，而类与特征的互信息即 $H(D)?H(D|A)$，得到的便是信息增益，表示由于特征A而使得对数据集D的分类的不确定性减少的程度。

总结

这一节的内容是比较重要的，其中信息量的定义是一切的出发点。总结上面提到的几个概念：

• 熵：随机变量不确定性的度量；编码方案完美时，最短平均编码长度
• 条件熵：给定一个变量后，确定另外一个变量另外还需的信息量；
• 相对熵（KL散度）：描述了两个分布不相似的程度；
• 互信息：衡量两个变量接近独立的程度。

Exercise

1.37 Using the definition (1.111) together with the product rule of probability, prove the result (1.112).

$$\begin{array}{rl}H[y|x]+H[x]& =?\left(?p(y,x)\ln p(y|x)\mathrm{d}y\mathrm{d}x+\int p(x)\ln p(x)dx\right)\\ & =?\left(?p(y,x)\ln p(y|x)\mathrm{d}y\mathrm{d}x+?p(y,x)\ln p(x)\mathrm{d}y\mathrm{d}x\right)\\ & =??p(y,x)\ln p(y,x)\mathrm{d}y\mathrm{d}x=?H[x,y]\end{array}$$

1.41 Using the sum and product rules of probability, show that the mutual information $I(x,y)$ satisfies the relation.

$$\begin{array}{rl}I(x,y)& =??p(x,y)\ln \left(\frac{p(x)p(y)}{p(x,y)}\right)\mathrm{d}x\mathrm{d}y\\ & =??p(x,y)\left(\ln (p(y))?\ln (p(y|x))\right)\mathrm{d}x\mathrm{d}y\\ & =??p(x,y)\ln (p(y))\mathrm{d}x\mathrm{d}y+?p(x,y)\ln (p(y|x))\mathrm{d}x\mathrm{d}y\\ & =?\int p(y)\ln (p(y))\mathrm{d}y+?p(x,y)\ln (p(y|x))\mathrm{d}x\mathrm{d}y\\ & =H[y]?H[y|x]\end{array}$$

参考文献

[1] 如何理解K-L散度（相对熵）, https://www.jianshu.com/p/43318a3dc715
[2] 互信息（Mutual Information）, https://www.cnblogs.com/gatherstars/p/6004075.html
[3] 统计学习方法（第二版）, 李航
[4] 如何通俗的解释交叉熵与相对熵？, https://www.zhihu.com/question/41252833