信息熵与编码定理
[toc]
惊奇度与信息量
定性描述
- 惊奇度：一个事件的惊奇度是指该事件发生时我们所感到的惊奇程度
- 信息量：一条信息的信息量是指该信息所含信息的多少。一条信息越是让我们感到惊奇，它所含信息量就越大
对于一个掷骰子的试验，假设E代表掷出点数为偶数（概率为1/2），我们对于事件E发生的惊奇程度并不大，但是当E代表掷出点数为6（概率为1/6），我们的惊奇程度就会很大。同样的我们会认为，“明天太阳会从东边升起”这句话没有任何信息量，而“国足将在世界杯夺冠”，这句话信息量太大了。
定量描述
我们希望能够将这种惊奇度/信息量进行量化，一个合理的假设是：
事件的惊奇度/信息量只取决于事件发生的概率。
用$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_{1},x_{2},...,x_{n}$的随机变量X，且相应概率分别为$p_{1},...,p_{n}$,当观察到随机变量X的值，所引起的平均惊奇度为：
H(x)=-\sum_{i=1}^{n}p_{i}logp_{i}
规定$0log0=0$。可以证明当$p_{i}$相同时，$H(x)$达到最大值，所以$H(x)$也可认为是随机变量$X$的不确定程度。在信息论中，$H(x)$称为随机变量的熵，即观测到随机变量$X$的值以后所接收的平均信息量。
信息熵的理解
熵、不确定度、惊奇度、信息量是从不同角度来看待X的同一特性：
随机变量$X$的熵$H(X)$=随机变量$X$的不确定度=观测到随机变量$X$的值后的平均惊奇度=观测到随机变量$X$的值后的平均信息量
我们可以从以下不同角度来理解它们之间的关系：
- 随机变量X的熵H(X)代表了X取值的“混乱”程度，即我们对X取值的不确定程度，我们越是不确定X的取值，当我们观测到它的值时所产生的平均惊奇度就越大；
- 信息熵代表了信息内容的“混乱”程度，即我们对信息内容的不确定程度，我们越是不确定信息的内容，当我们获取该信息的内容时，它所带给我们的信息量就越大；
- 对于获取到的一条信息，我们越是感到惊奇说明它所包含的信息量越大；
随机向量的熵
- 随机向量
$(X,Y)$的联合不确定度为：
H(X,Y)=-\sum_{i}\sum_{j}p(x_{i},y_{j})logp(x_{i},y_{j})
- 当
$Y=y_{j}$已观测到，$X$在$Y=y_{j}$条件下的剩余不确定度为：
$$
H_{Y=y_{j}}(X)=-\sum_{i}p(x_{i}|y_{j})logp(x_{i}|y_{j})
$$ - 当
$Y$被观测到后，$X$的平均不确定度为：
$$
H_{Y}(X)=\sum_{j}H_{Y=y_{j}}(X)\cdot p(y_{j})
$$
定理1:
: 随机变量$X$和$Y$的联合不确定度可分解为$Y$的不确定度与$Y$被到测到后$X$的平均不确定度之和:
H(X,Y)=H(Y)+H_{Y}(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_{Y}(X)
\end{aligned}
引理:
: 当$x>0$时，下式恒成立，当且仅当$x=1$时等号成立
\ln x\leqslant x-1
定理2：当另一个随机变量$Y$被观测到后，$X$的不确定度在平均意义下减少，当二者独立时等号成立：
H_{Y}(X) \leqslant H(X)
编码定理
通信中的编码问题（最小期望码长）：假设一个离散型随机变量X取值于
$\left \{x_{1}, \cdot \cdot \cdot ,x_{N}\right \}$，其相应概率为$\left \{p(x_{1}), \cdot \cdot \cdot ,p(x_{N})\right \}$，设计一个编码系统，将$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，事实上，只要重复足够多次可以将误传概率变得任意小，但是这种方法是以牺牲传输效率为代价的。但值得庆幸的是将传输错误概率减小到0的同时，传输效率并不会减小到0，这正是香农在信息论中提出的含噪声编码定理。
有噪声编码定理:
: 对于二进制对称系统，为使传送一比特的误差概率变得任意小，传输平均速率存在一个上限$C^{*}$，称为通道容量。
C^{*}=1+p\log p+(1-p)\log(1-p)
