信息论

文章参考自：Visual Information Theory

Codes

假设有一个朋友Bob，他只说4个单词：dog、cat、fish、bird，并且交流时使用2进制码表示信息。使用定长的2位二进制码可表示4个单词，此时的平均码长为2。单词和二进制编码的对应关系如下

可将此编码方式画图显示如下，方块的面积之和越大，表示平均码长越长

上述编码方式没有考虑每个单词出现的概率。现在已知Bob特别喜欢dog，他说的4个单词的频率分布如下

为了缩小平均码长，考虑如下变长编码

变长编码可视化图如下所示，方块的面积之和为1.75，即平均码长为1.75。对于这个概率分布，这种编码方式已经达到最优。

The Space of Codewords

每定义一个编码，都需要牺牲掉以此编码为前缀的所有编码空间。如下图所示，假设我们定义了一个编码01，为了使解码无歧义，必须舍弃任何以01为前缀的编码，如010、011010110等。此时，牺牲的比例为$\frac{1}{2^L}=\frac{1}{4}$2L1​=41​，如黑色部分所示，$L=2$L=2是定义编码01的长度

如果定义编码的长度为$L$L，那么牺牲的编码空间（可以理解为代价）$\text{Cost}=\frac{1}{2^L}$Cost=2L1​

一个很直观的理解是，定义的编码长度越小，所牺牲掉的编码空间也越大。因此，虽然对出现概率高的单词定义长度小的编码，缩短了平均码长，获得了好处，但是牺牲了较大的编码空间，即产生了坏处。于是，我们需要在上述好处和坏处之间做权衡。

Optimal Encodings

一个最优的编码策略是根据单词的出现频率作为比例来分配代价（证明略）。对于出现频率高的单词，我们甘愿为之付出更大的代价，来达到缩短平均码长的目的。

例如一个单词的出现频$p(x)=0.5$p(x)=0.5，我们付出的代价的数值也为0.5，于是有$\text{Cost}=\frac{1}{2^L}=p(x)=0.5$Cost=2L1​=p(x)=0.5，从而算出$L=1$L=1

Entropy

总结上一节的最优编码策略，对于一个单词，其出现的概率为$p(x)$p(x)，分配的编码长度为$L(x)$L(x)，付出的代价$\text{Cost}=\frac{1}{2^{L(x)}}$Cost=2L(x)1​，令代价等于概率$\frac{1}{2^{L(x)}}=p(x)$2L(x)1​=p(x)，解得$L(x)=\log_2\frac{1}{p(x)}$L(x)=log2​p(x)1​，为概率对应的最优编码的长度，这个长度$L(x)$L(x)可以是小数

于是可以求出离散概率分布$p(x)$p(x)的最优编码的平均码长，称为熵，记作$H(p)$H(p)。
$H(p)=\sum_{x}p(x)\log\frac{1}{p(x)}=-\sum_{x}p(x)\log p(x)$H(p)=x∑​p(x)logp(x)1​=−x∑​p(x)logp(x)

对于连续型变量的概率分布，熵的定义为积分形式
$H(p)=\int_{x}p(x)\log\frac{1}{p(x)}dx=-\int_{x}p(x)\log p(x)dx$H(p)=∫x​p(x)logp(x)1​dx=−∫x​p(x)logp(x)dx

熵有3种意义

1. 数据压缩的程度，即上述的平均码长的理解
2. 事件或信息的不确定性
   例如太阳从东方/西方升起，熵为0；投掷硬币出现正/反面，熵为1
3. 数据集的混杂程度
   例如全是大米，看上去一片“纯净”；大米掺入一点绿豆，看上去还算比较“纯净”；一半大米一半绿豆，看上去就是“混杂”的；等量的大米、绿豆、黄豆、黑豆，看上去就及其“混杂”

Cross-Entropy

假设我们还有一位朋友Alice，同样只会说4个单词：dog、cat、fish、bird。但Alice喜欢猫，她和Bob的单词频率分布有所不同（cat的频率最大），如下所示

Bob的编码方式对他自己是最优的，平均码长为1.75。
而Alice采用了Bob的编码方式，此时平均码长为2.25，显然对Alice来说，因为她的概率分布不同于Bob，因此Bob的编码方式对她不是最优的

于是就有了交叉熵的定义：对于一个概率分布$q(x)$q(x)，使用另一个概率分布$p(x)$p(x)的最优编码，得到的平均码长，记作$H_p(q)$Hp​(q)，称为$q$q对$p$p的交叉熵，下标$p$p表示使用$p$p的最优编码
注：wikipedia中记作$H(q,p)$H(q,p)，第2个变量表示使用的最优编码系统

$H_p(q)=\sum_{x}q(x)\log\frac{1}{p(x)}=-\sum_{x}q(x)\log p(x)$Hp​(q)=x∑​q(x)logp(x)1​=−x∑​q(x)logp(x)
连续形式为
$H_p(q)=\int_{x}q(x)\log\frac{1}{p(x)}dx=-\int_{x}q(x)\log p(x)dx$Hp​(q)=∫x​q(x)logp(x)1​dx=−∫x​q(x)logp(x)dx

对于Alice和Bob，存在以下4种情况：

• Bob使用自己的最优编码，$H(p)=1.75$H(p)=1.75
• Alice使用Bob的最优编码，$H_p(q)=2.25$Hp​(q)=2.25
• Alice使用自己的最优编码，$H(q)=1.75$H(q)=1.75
• Bob使用Alice的最优编码，$H_q(p)=2.375$Hq​(p)=2.375
  
  可以看出$H_p(q)\neq H_p(q)$Hp​(q)​=Hp​(q)，即交叉熵是不对称的。

KL Divergence（相对熵）

只要$p(x)$p(x)与$q(x)$q(x)不相等，那么$H_q(p)\gt H(p)$Hq​(p)>H(p)，差值表示了$p(x)$p(x)使用了另一个概率$q(x)$q(x)的编码时，相对于自己的最优编码长度增加了多少，称为$p$p相对于$q$q的相对熵，记为$D_q(p)$Dq​(p)

$\begin{aligned} D_q(p)&=H_q(p)-H(p)\\ &=\sum_{x}p(x)\log\frac{1}{q(x)}-\sum_{x}p(x)\log\frac{1}{p(x)}\\ &=\sum_{x}p(x)\frac{\log p(x)}{\log q(x)} \end{aligned}$Dq​(p)​=Hq​(p)−H(p)=x∑​p(x)logq(x)1​−x∑​p(x)logp(x)1​=x∑​p(x)logq(x)logp(x)​​
注：wikipedia中记作$D_{KL}(p\parallel q)$DKL​(p∥q)，表示$p$p相对于$q$q

连续形式
$D_q(p)=\int_{x}p(x)\frac{\log p(x)}{\log q(x)}dx$Dq​(p)=∫x​p(x)logq(x)logp(x)​dx

同样的，KL Divergence也是非对称的，$D_q(p)\neq D_p(q)$Dq​(p)​=Dp​(q)

KL Divergence可以理解为两个概率分布之间的距离