这一部分内容主要是PRML一书中1.6节的笔记。
信息论方面的一些知识在机器学习和模式识别上很有用，下面介绍一些基础，详细的信息论内容可以参考Viterbi and Omura，Cover and Thomas，Mackay。

1. 离散变量

1.1 信息量与信息熵

先考虑离散的情况，假设有一个离散随机变量 $x$，当我们观测到它的值时，我们想知道从这个观测值中获得了多少信息。可以用“惊讶程度”来描述我们从中获得了多少信息。举个例子：一件可能性很小的事件发生后，我们获得的信息量大于一件可能性很大的事件发生后我们获得的信息量。极端地说，如果一个必然事件发生，那我们获得的信息量为0，因为我们知道它一定会发生。
因此，刻画信息量需要依赖于概率分布 $p(x)$，我们希望用一个关于 $p(x)$ 单调的函数 $h(x)$ 来描述信息量，即 $p(x)$ 越大，$h(x)$ 越小。
另一方面，对于两个不相关的事件 $a$ 和 $b$，自然而然地，我们希望观察到它们同时发生所获得的信息量等于分别观察到它们发生所获得的信息量之和，即 $h(x,y)=h(x)+h(y)$；而同时，有 $p(x,y)=p(x)p(y)$。
从这两个式子，很容易想到 $p(x)$ 和$h(x)$ 满足对数关系：$$h(x) = -\log_2 p(x)\tag{1}$$ 其中，符号是为了保证 $h(x)\ge 0$。对数的底可以任意选取，目前先选择2，这时，$h(x)$ 的单位是比特。

接下来，假设发送者要传输一个随机变量的值给接收方，这个过程中平均信息传输量即为 $$\mathbb{E}[h(x)]=\mathrm{H}[x]=-\sum_x p(x)\log_2 p(x)\tag{2}$$ 将这个值称为随机变量 $x$ 的熵(entropy)。当 $p(x)=0$ 时，我们取 $p(x)\log p(x)=0$。

1.2 与编码的关系

考虑下面的例子：一个随机变量 $x$ 可能有8种不同的状态，每种状态等可能。为了传输 $x$ 的值，我们需要3个比特。$x$ 的熵为 $$\mathrm{H}[x]=-8\times \cfrac{1}{8}\log_2\cfrac{1}{8}=3 \text{ bits}$$ 再考虑另外一个例子：随机变量有八种状态{a,b,c,d,e,f,g,h}，每种状态不再是等概率出现，而是分别对应概率{$\frac{1}{2}$,$\frac{1}{4}$,$\frac{1}{8}$,$\frac{1}{16}$,$\frac{1}{64}$,$\frac{1}{64}$,$\frac{1}{64}$,$\frac{1}{64}$}。这时，信息熵为 $$\mathrm{H}[x]=-\cfrac{1}{2}\log_2\cfrac{1}{2}-\cfrac{1}{4}\log_2\cfrac{1}{4}-\cfrac{1}{8}\log_2\cfrac{1}{8}-\cfrac{1}{16}\log_2\cfrac{1}{16}-\cfrac{4}{64}\log_2\cfrac{1}{64}=2 \text{ bits}$$ 可以看出，非均匀分布随机变量的熵比均匀分布的熵小。回到编码，我们可以利用非均匀分布的特征，给可能性大的事件编码更短。一个可行的编码是：0，10，110，1110，111100，111101，111110，111111。这时，平均的编码长度为 $\frac{1}{2}\times 1+\frac{1}{4}\times 2+\frac{1}{8}\times 3+\frac{1}{16}\times 4+4\times\frac{1}{64}\times 4=2 \text{ bits}$

1.3 熵与无序性

从另外的角度来看，熵也可以看作是对无序程度的一种度量。
考虑这样一个例子：我们要将 $N$ 个相同的小球分到若干盒子中，第 $i$ 个盒子中有 $n_i$ 个小球，则不同的分配方式共有 $$W=\cfrac{N!}{\prod_i n_i!}\tag{3}$$ 这个值被称为多样性(multiplicity)。熵被定义为多样性的对数乘以一个常量，即 $$\mathrm{H}=\cfrac{1}{N}\ln W=\cfrac{1}{N}\ln N!-\cfrac{1}{N}\sum_i\ln n_i!\tag{4}$$ 考虑 $N\to\infty$ 时的情形，可以将 $\lim_{N\to\infty}(n_i/N)$ 看作是小球进入第 $i$ 个盒子的概率 $p_i$。应用斯特林公式 $\ln N!\simeq N\ln N-N$ 可以得到 $$\mathrm{H}=-\lim_{N\to\infty}\sum_i(\cfrac{n_i}{N})\ln(\cfrac{n_i}{N})=-\sum_i p_i\ln p_i\tag{5}$$

2. 连续变量

下面扩展到连续变量的情形。将 $x$ 取值范围分割成若干宽为 $\Delta$ 的小区间，假设 $p(x)$ 是连续的，由积分中值定理可知，在每个区间，一定存在一个 $x_i$满足 $$\int_{i\Delta}^{(i+1)\Delta}p(x)dx=p(x_i)\Delta\tag{6}$$ 对落在第 $i$ 个区间的 $x$，令它们都等于 $x_i$，则观察到 $x_i$ 的值的概率为 $p(x_i)\Delta$，对应的熵为$$\mathrm{H}=-\sum_i p(x_i)\Delta\ln(p(x_i)\Delta)=-\sum_i p(x_i)\Delta\ln p(x_i)-\ln\Delta\tag{7}$$ 省略掉(7)式中右端的第二项 $-\ln\Delta$，考虑极限情况 $\Delta\to 0$，则有 $$\lim_{\Delta\to 0}\left\{\sum_i p(x_i)\Delta\ln p(x_i)\right\}=-\int p(x)\ln p(x)\mathrm{d}x\tag{8}$$ 上式右端被称为微分熵(differential entropy)。
与离散的区别：我们发现连续和离散的熵的形式相差了一个量 $\ln\Delta$，它会在 $\Delta\to 0$ 时发散。这反映出：要极其精确地描述一个连续变量需要很大的信息量(比特数)。

2.1 最大熵

在离散的情形下，我们知道当不同状态的概率等大时，随机变量的熵最大。那么，在连续情形下，什么时候熵最大呢？

为了很好地定义这个最大值，我们限制了它的一阶和二阶矩（只限制一阶矩时，会得到不同的结果），同时保证概率的规范性，即在下面三条约束条件下最大化微分熵：$$\begin{array}{r,l}\int_{-\infty}^{\infty}p(x)\mathrm{d}x&=&1 \\ \int_{-\infty}^{\infty}xp(x)\mathrm{d}x&=&\mu \\ \int_{-\infty}^{\infty}(x-\mu)^2p(x)\mathrm{d}x&=&\sigma^2 \end{array}$$ 应用拉格朗日乘子法求解这个约束优化问题

关于约束优化问题可以参考这篇文章

由一阶必要条件（拉格朗日函数的导数为0）可以得到$$p(x)=\exp\left(-1+\lambda_1+\lambda_2 x+\lambda_3(x-\mu)^2\right)$$将$p(x)$代入到三个约束条件中，可以解出$\lambda_1$，$\lambda_1$ 和 $\lambda_1$。最终得到$$p(x)=\cfrac{1}{\sqrt{2\pi\sigma^2}}\exp\left\{-\cfrac{(x-\mu)^2}{2\sigma^2}\right\}\tag{9}$$最大化微分熵的分布其实是高斯分布。计算一下高斯分布下的微分熵可以得到 $\mathrm{H}[x]=\frac{1}{2}\{1+\ln(2\pi\sigma^2)\}$。可以看出，随 $\sigma$ 增大，分布变宽后，熵也会增大。注意到，不同于离散情况，微分熵可以取负值。

2.2 条件熵

假设有联合分布 $p(\mathbf{x},\mathbf{y})$，如果 $\mathbf{x}$ 的值已知，那么要确定 $\mathbf{y}$ 所需要的额外信息量为 $-\ln p(\mathbf{y}|\mathbf{x})$。因此，要确定 $\mathbf{y}$ 平均需要获取的额外信息量为 $$\mathrm{H}[\mathbf{y}|\mathbf{x}]=-\iint p(\mathbf{y},\mathbf{x})\ln p(\mathbf{y}|\mathbf{x})\mathrm{d}\mathbf{y}\mathrm{d}\mathbf{x}$$称为 $\mathbf{y}$ 在给定 $\mathbf{x}$ 下的条件熵。于是有$$\mathrm{H}[\mathbf{x},\mathbf{y}]=\mathrm{H}[\mathbf{y}|\mathbf{x}]+\mathrm{H}[\mathbf{x}]$$其中，$\mathrm{H}[\mathbf{x}]$ 是边际概率分布 $p(\mathbf{x})$ 的微分熵。上面的式子表示，确定 $\mathbf{x}$ 和 $\mathbf{y}$ 所需要的信息量为确定 $\mathbf{x}$ 需要的信息量加上给定 $\mathbf{x}$ 时确定 $\mathbf{y}$ 需要的信息量。

3. 相对熵（Relative Entropy）

考虑一个未知的分布 $p(\mathbf{x})$，我们用一个近似分布 $q(\mathbf{x})$。假设我们要利用 $q(\mathbf{x})$ 来构建一个编码模式，传输 $\mathbf{x}$ 给接受方。为确定 $\mathbf{x}$ 是由 $q(\mathbf{x})$ 而不是由 $p(\mathbf{x})$ 产生的所需要的额外信息量为$$\begin{array}{r,l}\mathrm{KL(p||q)}&=&-\displaystyle\int p(\mathbf{x})\ln q(\mathbf{x})\mathrm{d}\mathbf{x}-\left(\displaystyle\int p(\mathbf{x})\ln p(\mathbf{x})\mathrm{d}\mathbf{x}\right) \\ &=&-\displaystyle\int p(\mathbf{x})\ln\left\{\cfrac{q(\mathbf{x})}{p(\mathbf{x})}\right\}\mathrm{d}\mathbf{x}\end{array}\tag{10}$$
这个值称为相对熵，也称KL散度。注意到相对熵并不满足对称性，即 $\mathrm{KL(p||q)}\neq\mathrm{KL(q||p)}$
相对熵实际上描述了两个分布的差异性。我们想要让模型 $q(\mathbf{x}|\mathbf{\theta})$ 更好地近似真实分布 $p(\mathbf{x})$，实际上等价于最小化$p(\mathbf{x})$ 和 $q(\mathbf{x}|\mathbf{\theta})$ 之间的相对熵。
由于我们并不知道 $p(\mathbf{x})$ 是什么，所以并不能直接计算相对熵，只能通过从 $p(\mathbf{x})$ 中产生的样本点（即训练集）来估计$$KL(p||q)\simeq\sum_{n=1}^N\{-\ln q(\mathbf{x}_n|\mathbf{\theta})+\ln q(\mathbf{x}_n)\}\tag{11}$$上式右端的第二项与 $\mathbf{\theta}$ 是独立的，而第一项即为当前训练集下的对数似然函数。因此，最小化相对熵与最大化对数似然函数是等价的。

3.1 互信息（Mutual Information）

考虑联合分布 $p(\mathbf{x},\mathbf{y})$，当两个变量相互独立时，$p(\mathbf{x},\mathbf{y})=p(\mathbf{x})p(\mathbf{y})$。当它们不互相独立时，我们可以用联合分布与边际分布乘积之间的相对熵来衡量它们有多么“接近”独立$$\begin{array}{r,l}\mathrm{I}[\mathbf{x},\mathbf{y}]&\equiv&\mathrm{KL}(p(\mathbf{x},\mathbf{y})||p(\mathbf{x})p(\mathbf{y})) \\ &=&-\displaystyle\iint p(\mathbf{x},\mathbf{y})\ln\left(\cfrac{p(\mathbf{x})p(\mathbf{y})}{p(\mathbf{x},\mathbf{y})}\right)\mathrm{d}\mathbf{x}\mathrm{d}\mathbf{y}\end{array}$$这个值称为 $\mathbf{x}$ 与 $\mathbf{y}$ 之间的互信息。并有$$\mathrm{I}[\mathbf{x},\mathbf{y}]=\mathrm{H}[\mathbf{x}]-\mathrm{H}[\mathbf{x}|\mathbf{y}]=\mathrm{H}[\mathbf{y}]-\mathrm{H}[\mathbf{y}|\mathbf{x}]$$我们可以将互信息看作给定某个变量后，另一个变量的不确定性的减少。如果两个变量独立，那么这种减少即为0。

参考资料

Pattern Recognition and Machine Learning (PRML)