信息论

信息熵的起源

信息熵的作用是来量化信息，若一件不可能发生的事情发生了，相对于可能或者大概率发生的事情发生了来说，我们收到的信息前者更多，必然事件对我们来说几乎没有信息。所以我们可以通过信息$x$的概率分布$p(x)$来表达信息量$h(x)$。通过以上的例子我们知道$h(\cdot)$具有如下的特点：

对于不相关的$x$和$y$，$h(x,y)=h(x)+h(y)$，而我们知道对于概率分布来说，若$x$和$y$相互独立，那么$p(x,y)=p(x) \cdot p(y)$，所以我们就想到了通过$-log_2p(x)$来表示$h(x)$，其中的负号是为了使信息量非负。这样概率低的事件就有了更高的信息量，为了方便$log$的底数取2，此时的$h(x)$单位为$bits$。我们将随机变量$x$的信息量称为熵

$$\text{H}(x) = -\sum_x{p(x) \cdot \log_2p(x)}$$

假设随机变量$X$有8种取值，每种的概率相等，则传输$X$需要$H(X) = -8 \cdot \frac{1}{8} \cdot \log_2{\frac{1}{8}} = 3\ bits$。现在假设8种取值$\{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}\}$，对这8中取值进行哈夫曼编码得到其对应的编码为：$\{0,10,110,1110,111100,111101,111110,111111\}$，其平均编码长度为2$bits$。我们可以看出熵是编码随机变量状态的最小比特量，且非均匀分布的熵值要小于均匀分布。

熵在统计力学的起源

考虑将$N$个相同的物品分配到一些盒子中，$n_i$表示在第$i$个盒子中分配到了$n_i$个物品，则一共有$N!$种分配的方式，若我们不考虑每个盒子中的分配顺序，则分配的方式一共有

$$W = \frac{N!}{\prod_i n_i! }$$

而熵则是对其取对数后归一化的结果，$\text{H}=\frac{1}{N}\cdot \ln W = \frac{1}{N} \cdot \ln N! - \frac{1}{N} \cdot \sum_i{\ln{n_i!}}$，而由于$\ln N! \simeq N \cdot \ln N - N,\ if\ N \rightarrow \infty $，则

$$\text{H} = -\lim_{N \rightarrow \infty} \sum{\frac{n_i}{N} \cdot \ln{\frac{n_i}{N}} = -\sum_i{p_i \cdot \ln p_i}}$$

在物理学术语中，盒子中的具体分配称为微观状态，而整体分配称为宏观状态。其中$W$也被称为宏观状态的权重。

均匀分布时熵最大

$$\text{H}(p) = -\sum_i{p(x_i) \cdot \ln p(x_i)}$$

根据拉格朗日乘数法得到：

$$\tilde{\text{H}} = -\sum_i{p(x_i) \cdot \ln p(x_i)} + \lambda \cdot (\sum_i{p(x_i)}-1)$$ $$\begin{cases} \frac{\partial \tilde{H}}{\partial p(x_i)} = -\ln p(x_i) - 1 + \lambda = 0\\ \\ \sum_i{p(x_i)} = 1 \end{cases}$$

所以$p(x_i) = \frac{1}{N}$，其中$N$为$X$的取值个数，所以这是一个均匀分布，至于是最大值还是最小值我们可以通过对$p(x_i)$求二阶偏导

$$\frac{\partial \tilde{H}}{\partial p(x_i) \partial p(x_j) } = -I_{ij} \cdot \frac{1}{p(x_i)}<0$$

其中$I_{ij}$是单位矩阵，所以最后得到的应该是最大值。

连续性随机变量的熵

将随机变量$X$的取值等量划分，假设每份为$\bigtriangleup$，则每份的概率为

$$\int _{i \cdot \bigtriangleup}^{(i+1) \cdot \bigtriangleup} p(x)dx = p(x_i) \cdot \bigtriangleup$$

熵便转化成了

$$\text{H}_\bigtriangleup = -\sum_i{p(x_i) \cdot \bigtriangleup \cdot \ln(p(x_i) \cdot \bigtriangleup )} = -\sum_i{p(x_i) \cdot \bigtriangleup \cdot \ln p(x_i)} - \ln\bigtriangleup$$

省略公式最右边的$\ln\bigtriangleup$，考虑极限$\bigtriangleup \rightarrow 0$，公式右边的第一项就变成了$p(x) \cdot \ln p(x)$的积分，即

$$\lim_{\bigtriangleup \rightarrow 0}\{-\sum{p(x_i) \bigtriangleup \ln p(x_i)}\} = -\int p(x) \ln p(x)dx$$

其中，右侧的量被称为微分熵，可以看到熵的离散形式与连续形式的差是$\ln\bigtriangleup$，而这在极限$\bigtriangleup \rightarrow 0$的情况下发散。这反映了一个事实：具体化一个连续变量需要大量的比特位。对于定义在多元连续变量$\mathbf{x}$上的概率密度，微分熵为

$$\text{H}[\mathbf{x}] = - \int p(\mathbf{x}) \ln p(\mathbf{x}) d\mathbf{x}$$

在离散分布的情况下，最大熵对应于均匀分布，而在连续分布下，最大熵对应着什么呢，我们可以先引入三个限制：

$$\int_{-\infty}^{\infty} p(x) dx = 1$$ $$\int_{-\infty}^{\infty} xp(x) dx = \mu$$ $$\int_{-\infty}^{\infty} (x - \mu)^2p(x) dx = \sigma ^2$$

根据拉格朗日乘数法

$$\tilde{\text{H}} = -\int_{-\infty}^{\infty}{p(x) \ln p(x) dx} + \lambda_1(\int_{-\infty}^{\infty} p(x) dx - 1) + \lambda_2(\int_{-\infty}^{\infty} xp(x) dx - \mu) + \lambda_3(\int_{-\infty}^{\infty} (x - \mu)^2p(x) dx - \sigma ^2)$$

通过变分法，令这个函数的导数等于0得到

$$p(x) = \exp\{-1 + \lambda_1 + \lambda_2x + \lambda_3(x - \mu)^2\}$$

将这个结果带入三个限制方程中，得到

$$p(x) = \frac{1}{\sqrt{2\pi\sigma^2}}\exp\{-\frac{(x - \mu)^2}{2\sigma^2}\}$$

所以连续分布最大微分熵的分布式高斯分布。在最大化熵的时候我们没有限制概率非负，但由于求出的概率分布确实非负，所以这种限制是不必要的。求高斯分布的微分熵，我们可以得到

$$\text{H}[x] = \frac{1}{2}\{1 + \ln(2\pi\sigma^2)\}$$

通过这个结果可以看到熵随着分布的宽度（$\sigma^2$）增加而增加，即越均匀熵越大；此外还表明了微分熵是可以为负的，当$\sigma^2 < \frac{1}{2\pi e}$时，$H[X]<0$

此外假设我们有一个联合概率分布$p(\mathbf{x}, \mathbf{y})$，若从该分布中抽取一对$\mathbf{x}$和$\mathbf{y}$，当$\mathbf{x}$的值已知时，需要确定对应的$\mathbf{y}$值所需的附加信息就是$-\ln p(\mathbf{y}|\mathbf{x})$。因此用来确定$\mathbf{y}$值的平均附加信息可以写成

$$\text{H}[\mathbf{y} | \mathbf{x}] = -\int{\int{p(\mathbf{y}, \mathbf{x} \ln p(\mathbf{y}|\mathbf{x})) d\mathbf{y}}d\mathbf{x}}$$

这被称为在$\mathbf{x}$给定的情况下，$\mathbf{y}$的条件熵，由乘积法则很容易看出

$$\text{H}[\mathbf{x} , \mathbf{y}] = \text{H}[\mathbf{y} | \mathbf{x}] + \text{H}[\mathbf{x}]$$

相对熵

考虑一个未知的分布$p(\mathbf{x})$，假设我们使用一个近似的分布$q(\mathbf{x})$对其建模，若要用$q(\mathbf{x})$编码$\mathbf{x}$发送给接收者，则由于$q(\mathbf{x})$不是真实分布，需要附加信息，而平均的附加信息可以表示为如下所示的公式，单位为$nats$

$$\text{KL}(p||q) = -\int p(\mathbf{x}) \ln q(\mathbf{x}) d\mathbf{x} - (-\int p(\mathbf{x}) \ln p(\mathbf{x})d\mathbf{x}) = -\int p(\mathbf{x}) \ln{\frac{q(\mathbf{x})}{p(\mathbf{x})}d\mathbf{x}}$$

上式称为分布$p(\mathbf{x})$和分布$q(\mathbf{x})$相对熵或者KL散度。下面证明$KL(p||q)\geqslant0$：

对于凸函数$f(x)$满足Jenson不等式，该等式可以通过归纳法证明

$$f(\sum_{i=1}^{M}\lambda_i x_i) \leqslant \sum_{i=1}^{M} \lambda_i f(x_i)$$

若将$\lambda_i$看成是取值为${x_i}$的离散变量$x$的概率分布，那么上式就可以表示为$f(\mathbf{E}[x]) \leqslant \mathbf{E}[f(x)]$，其中$\mathbf{E}[\cdot]$表示期望。对于连续变量，Jenson不等式的形式为

$$f(\int \mathbf{x} p(\mathbf{x}) d\mathbf{x}) \leqslant \int f(\mathbf{x}) p(\mathbf{x}) d\mathbf{x}$$

将其应用于KL散度，并利用$-\ln x$为凸函数，以及$\int q(\mathbf{x}) d\mathbf{x} = 1$可以得到

$$\text{KL}(p||q) =-\int p(\mathbf{x}) \ln{\frac{q(\mathbf{x})}{p(\mathbf{x})}d\mathbf{x}} \geqslant -\ln \int q(\mathbf{x}) d\mathbf{x} = 0$$

由于$-\ln x$为严格凸函数，因此只有当$q(\mathbf{x}) = p(\mathbf{x})$对于所有的$\mathbf{x}$都成立时，等号才成立，因此可以把KL散度看做两个分布$p(\mathbf{x})$和 $q(\mathbf{x})$之间不相似的程度。

为何我们会用最大似然函数来近似估计分布

假设数据通过未知分布$p(\mathbf{x})$生成，我们想要对其建模，我们可以试着用一些参数分布$q(\mathbf{x} | \mathbf{\theta})$来近似这个分布。确定$\mathbf{\theta}$的一种方法是最小化$p(\mathbf{x})$和$q(\mathbf{x} | \mathbf{\theta})$的KL散度，然而我们并不知道$p(\mathbf{x})$，但我们可以假设我们观测到了服从分布$p(\mathbf{x})$的一些点$\mathbf{x}_n$，其中$n=1,…,N$，则$p(\mathbf{x})$的期望就可以通过这些点来得到

$$\mathbf{E}[f] = \int p(x)f(x)dx \simeq \frac{1}{N}\sum_{n=1}^{N}f(x_n)$$ $$\text{KL}(p||q) \simeq \frac{1}{N} \sum_{n=1}^{N} \{-\ln q(\mathbf{x}_n|\mathbf{\theta}) + \ln p(\mathbf{x}_n)\}$$

从公式中我们可以看到第二项实际上与$\mathbf{\theta}$无关，而第一项是使用分布$q(\mathbf{x} | \mathbf{\theta})$估计训练集的负对数似然函数，所以最小化KL散度等价于最大化似然函数。

互信息

考虑由$p(\mathbf{x}, \mathbf{y})$给出的两个变量$\mathbf{x}$和$\mathbf{y}$组成的数据集，若变量相互独立，则$p(\mathbf{x}, \mathbf{y}) = p(\mathbf{x})p(\mathbf{y})$；若变量不是相互独立，那我们就可以通过其联合概率分布与边缘概率分布乘积之间的KL散度来判断其是否相互独立，而此时的KL散度为

$$\text{I} [\mathbf{x}, \mathbf{y}] \equiv \text{KL}(p(\mathbf{x}, \mathbf{y}) || p(\mathbf{x})p(\mathbf{y})) = -\int p(\mathbf{x}, \mathbf{y}) \ln \frac{p(\mathbf{x}, \mathbf{y})}{p(\mathbf{x}, \mathbf{y})} d\mathbf{x}d\mathbf{y}$$

而KL散度这种特殊的形式被称为互信息，而根据KL散度的性质$\text{I} [\mathbf{x}, \mathbf{y}] \geqslant 0$当且仅当$\mathbf{x}$和$\mathbf{y}$相互独立时成立。通过概率分布的$sum\ and\ product\ rules$可以看到互信息和条件熵之间的关系为

$$\text{I}[\mathbf{x}, \mathbf{y}] \equiv \text{H}[\mathbf{x}] - \text{H}[\mathbf{x}|\mathbf{y}] = \text{H}[\mathbf{y}] - \text{H}[\mathbf{y}|\mathbf{x}]$$

因此我们可以将互信息当成由于知道$\mathbf{y}$值而使得$\mathbf{x}$的不确定性减小，或者说知道$\mathbf{x}$的值而使得$\mathbf{y}$的不确定性减小。从贝叶斯角度来看，我们可以将$p(\mathbf{x})$看成是$\mathbf{x}$的先验概率，而$p(\mathbf{x} | \mathbf{y})$看做是观测到新数据$\mathbf{y}$的后验概率。因此互信息表示的是新的观测$\mathbf{y}$造成的$\mathbf{x}$的不确定性减小。