机器学习：理论基础（二）—— 信息论

惊奇度

惊奇度：某事件所携带的信息量可以被看做该事件发生时所给我们带来的惊讶程度。

我们希望能够将这种惊奇度/信息量进行量化，一个合理的假设是：事件的惊奇度/信息量只取决于事件发生的概率。用$S(p)$表示由概率为$p$的事件发生以后所产生的惊奇程度，假定$S(p)$对一切$0<p<=1$有定义。下面我们从$S(p)$应满足的条件出发确定$S(p)$的形式：

• 公理1：$S(1)=0$，当听到一个必然事件发生时，不会感到任何惊奇
• 公理2：$S(p)$是$p$的严格连续递减函数，事件发生的概率越大，惊奇度越小
• 公理3：$S(pq)=S(p)+S(q)$，对于独立事件E和F，假设E发生的惊奇度为$S(p)$，F发生的惊奇度为$S(q)$，则二者同时发生的惊奇度等于二者分别发生的惊奇度之和

容易验证，对数函数可同时满足这四个条件：

$$S(p) = -log p$$

当底数取2时，惊奇度/信息量的单位可用比特表示。

信息熵

信息熵：某随机变量x所带来的平均惊奇度(所携带的平均信息量)

离散随机变量的熵：

$$H(x)=-\sum_{x} p(x)logp(x)$$

• 规定$0log0=0$
• 当p(x)为均匀分布时，信息熵达到最大值，如$p(x)=\frac{1}{n}$，则$H(x)=lgn$
• 同等情况下x的取值越多，熵也越大

连续随机变量的熵(微分熵):

$$H(x)=-\int p(x)lnp(x)dx$$

• 当p(x)为高斯分布时，微分熵达到最大$H(x)=\frac{1}{2}(1+ln(2\pi \sigma ^2))$
• 微分熵随着分布宽度$\sigma ^2$的增加而增加；
• 微分熵可取负值；

我们可以从不同的视角来理解随机变量的熵:

1. 平均惊奇度：观察x时的平均惊讶程度；
2. 平均信息量：发送x时传输的平均信息量；
3. 不确定度：对x取值的不确定程度；
4. 最短编码长度：假设我们要对随机变量x的各种取值进行前缀编码，则随机变量x的熵等于最短平均编码长度；

联合熵与条件熵

随机变量$X,Y$的联合熵$H(X,Y)$描述了随机变量$X,Y$联合分布的不确定度：

$$H(X,Y)=-\sum_{x}\sum_{y}p(x,y)logp(x,y)$$

给定X的条件下，Y的条件熵(conditional entropy)为：

$$\begin{align*} H(Y\mid X)&=\sum_{x}H(Y|{X=x})\cdot p(X=x)\\ &=-\sum_{x}\sum_{y}p(y\mid x)logp(y\mid x)p(x)\\ &=-\sum_{x}\sum_{y}p(x,y)logp(y\mid x) \end{align*}$$

定理1:$X$和$Y$的联合熵可分解为$X$的熵加上给定$X$条件下$Y$的条件熵

$$H(X,Y)=H(X)+H(Y\mid X)$$

证明：

$$\begin{aligned} H(X,Y)&=-\sum_{i}\sum_{j}p(x_{i},y_{j})logp(x_{i},y_{j}) \\ & =-\sum_{i}\sum_{j}p(y_{i})p(x_{i}|y_{j})[logp(y_{i})+logp(x_{i}|y_{j})] \\ & = -\sum_{j}p(y_{j})logp(y_{j})\sum_{i}p(x_{i}|y_{i})-\sum_{j}p(y_{j})\sum_{i}p(x_{i}|y_{i})logp(x_{i}|y_{i})\\ & =H(Y)+H(X\mid Y) \end{aligned}$$

定理2：当另一个随机变量$X$被观测到后，$Y$的不确定度在平均意义下减少，当二者独立时等号成立：

$$H(Y\mid X) \leqslant H(Y)$$

交叉熵-相对熵-互信息

交叉熵(Cross-Entropy)：度量两个概率分布间的差异性信息。交叉熵等于我们用近似的分布$q(x)$来表示真实分布$p(x)$的平均编码长度，则：

$$C(p,q)=-\sum p(x)logq(x)$$

• $C(p,q)\geqslant H(p)$：交叉熵以真实熵为下界，熵代表了最短编码长度；
• 最小交叉熵等价于极大似然：我们用$q(x\mid \theta)$来作为真实分布$p(x)$的近似，关于p(x)的期望可以通过已观察到的服从分布$p(x)$的有限训练点$x_n$的加和作为近似，而后者正是极大似然的表达式；

$$C(p,q)=-\sum p(x)logq(x) = -\frac{1}{N}\sum_{n=1}^{N} logq(x_n\mid \theta )$$

相对熵(Relative Enrtopy)：交叉熵减去真实熵，表示近似概率分布$q(x)$对真实分布$p(x)$的相对熵；相对熵又称为KL散度(Kullback and Leibler,1951)，与交叉熵类似，同样可以度量两个随机分布的差异性；

$$\begin{align*} KL(p\parallel q)&=C(p,q)-H(p)\\ &=-\sum p(x)logq(x)-(-\sum p(x)logp(x))\\ &=-\sum p(x)log\frac{q(x)}{p(x)} \end{align*}$$

• $KL(p\parallel q)\geqslant 0$
• $KL(p\parallel q)\neq KL(q\parallel p)$

互信息(mutual information):用$p(x)p(y)$来作为$p(x,y)$的近似的KL散度，散度越大说明二者差异越大，x,y越不独立，互信息可以看做已知其中一个随机变量而造成的另一个随机变量的不确定性的减少。

$$\begin{align*} I(X,Y)&=KL(p(x,y)\parallel p(x)p(y))\\ &=-\sum_{x}\sum_{y} p(x,y)log\frac{p(x)p(y)}{p(x,y)}\\ &=-\sum_{x}\sum_{y}p(x,y)log\frac{p(x)}{p(x,y)}-\sum_{x}\sum_{y}p(x,y)logp(y)\\ &=\sum_{x}\sum_{y}p(x,y)logp(y\mid x)-\sum_{y}p(y)logp(y)\\ &=H(Y)-H(Y\mid X)\\ \end{align*}$$

• $I(X,Y)=I(Y,X)\geqslant 0$：当X,Y相互独立时等号成立

现在，我们可以总结上述所有和熵相关的公式:

$$\left\{\begin{matrix} \begin{align*} &S(p)=-lgp\\ &H(X)=-\sum_{x}p(x)lgp(x)\\ &H(Y\mid X)=\sum_{x}H(Y\mid X=x)p(X=x)=\sum_{x}\sum_{y}p(x,y)lgp(y\mid x)\\ &H(X,Y)=-\sum_{x}\sum_{y}p(x,y)lgp(x,y)\\ &C(p,q)=-\sum_{x}p(x)lgq(x)\\ &KL(p\parallel q)=C(p,q)-H(p)=-\sum_{x}p(x)lg\frac{q(x)}{p(x)}\\ &I(X,Y)=KL(p(x,y)\parallel p(x)p(y))=H(Y)-H(Y\mid X)=H(X)-H(X\mid Y)\\ &H(Y\mid X)=H(Y)-I(X,Y)\\ &H(X,Y)=H(X)+H(Y)-I(X,Y) \end{align*} \end{matrix}\right.$$

编码定理

通信中的编码问题（最小期望码长）：假设一个离散型随机变量X取值于
$\lbrace x{1}, \cdot \cdot \cdot ,x{N}\rbrace$，其相应概率为$\lbrace p(x{1}), \cdot \cdot \cdot ,p(x{N})\rbrace$，设计一个编码系统，将$x{i}$编成$n{i}$位的二进制序列，通过一个通信网络将从A处传送到B处，为避免混乱，要求编码后的序列不能出现一个序列是另一个序列的延伸。如何设计编码系统使得最终的期望码长最小。

引理1:为了将$X$的可能取值编码成0-1序列，且任何一个序列都不能是另一序列的延伸，其充要条件为：

$$\sum_{i=1}^{N}\left ( \frac{1}{2} \right )^{n_{i}}\leqslant 1$$

证明:

记$w{j}$为$x{i}$中编码长度为j的个数，$j=1,2,3…$，显然有：

$$w_{1}2^{n-1}+w_{2}2^{n-2}+\cdot \cdot \cdot +w_{n-1}2+w_{n}\leqslant 2^{n}$$

两边同除以$2^{n}$得：

$$\sum_{j=1}^{n}w_{j}\left ( \frac{1}{2}\right )^{j}=\sum_{i=1}^{N}\left ( \frac{1}{2} \right )^{n_{i}}\leqslant 1$$

无噪通道编码定理

无噪通道编码定理:假设每个信号单位从位置A到位置B的过程没有发生错误，则编码的期望码长不小于随机变量的信息熵:

$$\sum_{i=1}^{N}n_{i}p\left ( x_{i} \right )\geqslant H(X)=-\sum_{i=1}^{N}p\left ( x_{i} \right )\log p\left ( x_{i} \right )$$

证明：
记$p{i}=p(x{i})$，$q{i}=2^{-n{i}}/\sum{j=1}^{N}2^{-n{j}}$，则有$\sum{i=1}^{N}p{i}=\sum{i=1}^{N}q{i}=1$

$$\begin{aligned} -\sum_{i=1}^{N}p_{i}\log(\frac{p_{i}}{q_{i}})&=-\log e \sum_{i=1}^{N}p_{i}\ln (\frac{p_{i}}{q_{i}})\\ &=\log e \sum_{i=1}^{N}p_{i}\ln (\frac{q_{i}}{p_{i}})\\ &\leqslant \log e \sum_{i=1}^{N}p_{i}(\frac{q_{i}}{p_{i}}-1)\\ &=\log e (\sum_{i=1}^{N}p_{i}-\sum_{i=1}^{N}q_{i})=0 \end{aligned}$$

由此可得：

$$\begin{aligned} -\sum_{i=1}^{N}p\left ( x_{i} \right )\log p\left ( x_{i} \right )&\leqslant - \sum_{i=1}^{N}p_{i}\log q_{i}\\ &= \sum_{i=1}^{N}n_{i}p_{i}+\log(\sum_{j=1}^{N}2^{-n_{j}})\\ &\leqslant\sum_{i=1}^{N}n_{i}p_{i} \end{aligned}$$

定理:对于大部分随机变量$X$，不存在一组编码系统使得期望码长达到下界$H(X)$，但是总存在一个编码系统，使得期望码长与$H(X)$之间的误差小于1

证明:
取$n{i}=\left \lceil -\log p(x{i}) \right \rceil$，即：

$$-\log p(x_{i}) \leqslant n_{i}\leqslant -\log p(x_{i}) +1$$

代入期望码长公式$L=\sum{i=1}^{N}n{i}p(x_{i})$得：

$$-\sum_{i=1}^{N}p\left ( x_{i} \right )\log p\left ( x_{i} \right )\leqslant L\leqslant -\sum_{i=1}^{N}p\left ( x_{i} \right )\log p\left ( x_{i} \right )+1 H(X)\leqslant L< H(X)+1$$

有噪通道编码定理

假设每个信号单位的传送是独立的，且以概率p正确地从A处传送到B处，这样的通信系统称为二进制对称通道。若不经过处理直接传送便会发生误传，一种减少误传信号的方法是将信号重复多次，在译码时按多数原则进行翻译。

假设p=0.8，通过将信号重复3次进行编码译码。如000、001、010、100都代表0，111，110，101，011代表1。此时，传输一位错误的概率为：

$$0.2^{3}+3\times 0.2^{2}\times 0.8=0.104$$

错误率由0.2减小到0.104，事实上，只要重复足够多次可以将误传概率变得任意小，但是这种方法是以牺牲传输效率为代价的（降低到1/3）。但值得庆幸的是将传输错误概率减小到0的同时，传输效率并不会减小到0，这正是香农在信息论中提出的含噪声编码定理。

有噪通道编码定理:
: 只要信息传输效率小于通道容量，必存在一类编码使信息传输错误概率可以任意小。通道容量可由以下公式计算：

$$C^{*}=1+p\log p+(1-p)\log(1-p)$$

$C^{*}\leqslant 1$,当$p=1$或$p=0$时等号成立。有噪声编码定理又称香农第二定理，是编码存在定理。

最大熵原理

最大熵原理认为, 学习概率模型时, 在所有可能的概率模型(分布) 中, 熵最大的模型是最好的模型。直观地, 最大熵原理认为要选择的概率模型首先必须满足已有的事实, 即约束条件. 在没有更多信息的情况下, 那些不确定的部分都是等可能的. 最大熵原理通过熵的最大化来表示等可能性. 等可能不容易操作, 而熵则是一个可优化的数值指标。

引用

1. 概率论基础
2. PRML