信息熵

信息熵的定义

在信息论中，信息就是选择自由度的衡量，而信息熵就是数据随机性造成的信息（不确定度）平均值。基于这样的认识，我们很自然地对信息熵有了几个模糊的要求

信息熵是非负的： $H\left(p\right) \ge 0$
如果一个事件发生的概率为 $1$ ，我们不能从一个已经发生的事件上得到任何信息： $H\left(1\right) = 0$
如果发生了两个独立事件（联合概率等于各自概率的乘积），那么我们从这两事件中得到的信息熵应该是两个信息熵之和： $H\left(p_1\cdot p_2\right)=H\left(p_1\right)\cdot H\left(p_2\right)$
单个事件的信息量应该随概率的增加而减小，且应该是概率的连续函数，概率的微小变化也只能引起信息量的微小变化

注意：第四点的信息量不是信息熵，信息熵不可能单调

基于上述性质，我们构造出信息熵的可能形式：

$H\left(X\right)=-\sum_{x\in \mathcal{X}}p\left(x\right)\log p\left(x\right)$

在前面再乘以概率是为了不可能事件的熵为零： $H\left(0\right)\ =0$
底数是可选的，在量子计算中通常选 $2$ 作为底数

注意总体信息熵和单个信息量的区别，信息熵是所有概率信息熵的加和，类似于期望值计算

例：当随机变量取 $1$ 和 $0$ 的概率分别为 $p$ 和 $1-p$ ：

$X=\left\{ \begin{aligned} &1\quad \text{with probability} \quad p,\\ &0\quad \text{with probability} \quad 1-p \end{aligned} \right.$

$H\left(X\right)=-p\log p -\left(1-p\right)\log\left(1-p\right)=H\left(p\right)$

这里的 $H\left(p\right)$ 函数是一个固定函数，称为二进制熵函数，其随概率 $p$ 的变化如下图所示

当底数取 $2$ 且 $p=\frac{1}{2}$ 时，二元事件信息熵 $H\left(X\right)$ 取最大值 $H\left(X\right)=1$

$H\left(\frac{1}{2}\right)=\log_22=1 \;\left(\mathrm{bit}\right)$

表示一个二元事件的最大信息量是 $1 \;\mathrm{bit}$ ，与我们对存储单元的认识相符

信息熵的性质

均匀分布的随机变量具有最大熵

$H\left(X\right)=-\sum_{i=1}^n\frac{1}{n}\log\frac{1}{n}=\log n$

其他分布的信息熵都小于 $\log n$

信息熵是一个关于 $P$ 的凹函数（这里是英译过来的，在汉语中是“凸”的意思）

$H\left(P\right)\equiv H\left(X\right),\quad P=\left[p\left(x_1\right),p\left(x_2\right),\cdots p\left(x_n\right)\right]$

$H\left[\alpha P_1+\left(1-\alpha\right)P_2\right]\ge \alpha H \left(P_1\right)+\left(1-\alpha \right)H\left(P_2\right),0\le\alpha\le 1$

信息熵表示在最优策略下，平均确定一个随机变量取值所需的最小信息量

联合熵和条件熵

联合熵

如果一对离散的随机变量 $\left(X,Y\right)$ 的联合概率分布为 $p\left(x,y\right)$ ，那么我们分别定义联合熵和条件熵为：

$H\left(X,Y\right)=-\sum_{x\in\mathcal{X}}\sum_{y\in\mathcal{Y}}p\left(x,y\right)\log p\left(x,y\right)$

联合熵表示同时观测 $X$ 和 $Y$ 时，系统的总体不确定性，即确定一个 $\left(X,y\right)$ 所需的平均信息量。

条件熵

又定义一对离散的随机变量 $\left(X,Y\right)$ 的条件熵为

$\begin{align*} H\left(Y| X\right)&=\sum_{x\in\mathcal{X}}p\left(x\right)H\left(Y| X=x\right)\\ &=-\sum_{x\in\mathcal{X}}p\left(x\right)\sum_{y\in \mathcal{Y}}p\left(y| x\right)\log p\left(y | x\right)\\ &=-\sum_{x\in\mathcal{X}}\sum_{y\in\mathcal{Y}}p\left(x,y\right)\log p\left(y| x\right)\\ &=-E\left[\log p \left(Y|X\right)\right] \end{align*}$

上面推导过程利用了条件概率和联合概率的关系：

$p\left(x,y\right)=p\left(x\right)p\left(y|x\right)$

条件熵表示在知道一个变量后，系统仍具有的不确定性，即知道一个变量后，确定另一个变量所需的信息量。

链式法则： $H\left(X,Y\right)=H\left(X\right)+H\left(Y|X\right)$
$H\left(X|Y\right)\ne H\left(Y|X\right)$
$H\left(X|X\right)=0$

相对熵和互信息

相对熵

假设 $p\left(x\right)$ 是已经存在的真实概率分布，而我们需要设计一个 $q\left(x\right)$ 去接近真实分布，那么我们定义相对熵来描述分布 $q\left(x\right)$ 相对于真实分布 $p\left(x\right)$ 的额外信息量。 $p\left(x\right)$ 越接近于 $q\left(x\right)$ ，相对熵越小，直至降为零。

$D\left(p||q\right)=\sum _{x\in \mathcal{X}}p\left(x\right)\log \frac{p\left(x\right)}{q\left(x\right)}$

相对熵的两个变量不能交换位置，因为交换后，相对熵的权重发生了变化

$D(p||q) \ge 0;\quad D(p||q)=0\quad iff\quad p=q$
$D(p||q)\ne D(q||p)$

互信息

考虑 $X$ 和 $Y$ 两个随机变量，他们的联合概率质量函数为 $p\left(x,y\right)$ ，并具有边缘概率质量函数 $p\left(x\right)=\sum_{y\in \mathcal{Y}}p\left(x,y\right)$ 和 $p\left(y\right)=\sum_{x\in \mathcal{X}}p\left(x,y\right)$ ，我们把联合分布 $p\left(x,y\right)$ 和边缘分布之积 $p\left(x\right) p\left(y\right)$ 的相对熵称作互信息：

$\begin{aligned} I\left(X;Y\right) &=\sum_{x\in\mathcal{X}}\sum_{y\in\mathcal{Y}}p\left(x,y\right)\log \frac{p\left(x,y\right)}{p\left(x\right)p\left(y\right)}\\ &=D\left[p\left(x,y\right)\ || \ p\left(x\right)p\left(y\right) \right] \end{aligned}$

互信息表示两变量之间的互享信息量，等于知道一个变量后，另一个变量不确定性的减少量。

$I\left(X;Y\right) \ge 0;\quad I\left(X;Y\right)=0,\quad iff \quad p\left(x,y\right)=p\left(x\right)p\left(y\right)$
$I\left(X;Y\right)=I\left(Y;X\right)$

各个熵之间的关系

下图可直观地描述关于两个随机变量的各种熵之间的关系

$\begin{aligned} I\left(X;Y\right)&=I\left(Y;X\right)\\ &=H\left(X\right)-H\left(X|Y\right)\\ &=H\left(Y\right)-H\left(Y|X\right)\\ &=H\left(X\right)+H\left(Y\right)-H\left(X|Y\right)\\ \end{aligned}$

$I\left(X;X\right)=H\left(X\right)$

信息编码

Shannon 无噪声信源编码定理: 每个符号的平均比特数无法低于信源香农熵，熵 $H\left(X\right)$ 是理论上可以达到的最小平均码长。

这意味着信息不能被无限压缩， $H\left(X\right)$ 是信源的不可压缩极限。

经典通信模型

信道与噪声

信道由输入表 $\mathcal{X}$ , $\mathcal{Y}$ 和 $p\left(y|x\right)$ 组成，其中 $p\left(y|x\right)$ 表示输入信号为 $X$ 时接受到的信号会变为 $Y$ 的概率转移矩阵。

噪声是由于传输过程中的不可避免因素，接受方获得的信息中产生的不规则错误。

上图中信道的概率转移矩阵为 $p\left(y|x\right)$ ，干扰源为噪声。正是噪声使得信道具有了概率转移矩阵。

无记忆信道

无记忆信道的定义

输出的概率分布依赖于彼时的输入，而与之前的输入或输出无关，这样的信道称为无记忆信道。

上图所示的二元对称信道为一个典型的无记忆信道，此时的概率转移矩阵为

$p\left(y|x\right) = \begin{pmatrix} 1-p & p \\ p & 1-p \\ \end{pmatrix}$

但这个信道传输信息的正确率很依赖于噪声 $p$ ，而实际中正确率肯定是越高越好，噪声又是不可避免的，有没有什么不改变噪声 $p$ 也能提高信道抗噪性的办法呢？有的有的。

编码和纠错

如下图，一个 $0$ 被编码为 $000$ ，一个 $1$ 被编码为 $111$ 。如果接收器没有收到三个相等的数，那就采用多数规则。一共三位数编码一共有 $8$ 种情况，四种认定为 $0$ ，另外四种认定为 $1$ 。

这样接收方的信息错误率为：

$p\prime=p^3+3p^2\left(1-p\right)=p^2\left(3-2p\right)\le p,\quad 0\leq p\leq 1$

当 $p=0.2,\quad p\prime=0.104$

信道容量

我们定义一个离散的无记忆信道的信道容量为

$C=\max_{q\left(x\right)}I\left(X;Y\right)$

其中最大值取决于 $X$ 的概率分布函数 $q\left(x\right)$ 。

码率 $R$ 可定义为

$R= \frac{\text{有效信息比特}}{\text{编码比特}}$

例如，若一个 $0$ 被编码为 $000$ ，那么传输比特为 $3$ ，有效信息比特为 $1$ ，码率为 $1/3$ 。

信道容量表示一个信道在噪声干扰下，仍然能够保证误码率趋近 $0$ 的最大码率。若 $R$ 小于 $C$ ，可以优化编码策略，使误码率更趋近于 $0$ ；若 $R$ 大于 $C$ ，超过了理论极限码率，再好的编码策略也不会消除误码率。因此我们可以选择最优分布 $q\left(x\right)$ ，使得信道输入输出之间的互信息最大化，通过解除最高码率的限制间接提高有效信息传输速率。

Shannon 噪声无记忆信道编码定理

对于一个离散的无记忆信道，任何不超过信道容量 $C$ 的码率 $R$ （=信息比特或量子比特）都是可以达到的。例如，上文提到的提高抗噪性方法中，一个 $0$ 被编码为 $000$ ，一个 $1$ 被编码为 $111$ ，那么码率 $R=1/3$ ，而当 $p=0.2,C=0.278$ ， $R> C$ ，也就是说 $3$ bit编码方案还是会出错，需要采用 $4$ bit及以上方案编码。