编码
信息论研究目标: 用最少的编码表示传递信息.
举一个例子来感性认识一下:
假设两地互相通信，两地之间一直在传递A，B，C，D四类消息，那应该要选择什么样的编码方式才能尽可能少的使用资源呢？
等长编码
如果这四类消息的出现是等概率的，都为$\frac{1}{4}$，那么肯定应该采用等编码方式，也就是
| 信息 | A | B | C | D |
|---|---|---|---|---|
| 编码 | 00 | 01 | 10 | 11 |
这样就能达到最优的编码方式，平均编码长度为$2\times\frac{1}{4}\times4=2$
但是，如果四类消息出现的概率不同呢？例如, A消息出现的概率是$\frac{1}{2}$，B是$\frac{1}{4}$，C是$\frac{1}{8}$，D是$\frac{1}{8}$，那应该怎样编码呢？
不等长编码
直觉告诉我们，为了使平均编码长度尽可能小，出现概率高的A消息应该使用短编码，出现概率低的C，D消息应该使用长编码。与等长编码相比，这样的编码方式叫做变长编码，它的效果更好. 这实际上是哈夫曼编码.
哈夫曼编码的原则:
- 对出现概率大的符号分配短字长的二进制码，
- 对出现概率小的符号分配长字长二进制码，得到符号平均码长最短的码。
- 将信息符号按其出现概率从大到小排列；
- 将两个最小概率组成一组，划成2个分支域，并标以0 和1；再把2 个分支域合并成1个支域，标以两个概率之和；
- 依次类推，直到概率之和等于1.0；
- 找出概率和1.0 到各信息符号的路径，记下各路径从右到左各分支域的0 和1，即得到信息符号相应的码字。（反向编码）
哈夫曼编码过程举例:
从右往左, 以此给ABCD反向编码如下:
| 信息 | A | B | C | D |
|---|---|---|---|---|
| 编码 | 0 | 10 | 110 | 111 |
| 概率 | $1/2$ | $1/4$ | $1/8$ | $1/8$ |
平均编码长度为$1\times\frac{1}{2}+2\times\frac{1}{4}+3\times\frac{1}{8}+3\times\frac{1}{8}=1.75$，显然要优于等长编码, 这也是最优编码.
编码空间
在对消息进行变长编码时，可以看到对A消息编码后，后面的三类消息编码都不是以0开头。这是因为在编码时必须保证该编码是唯一可解码的。例如若A消息编码为0，B消息编码为01，那么0101的编码就会产生歧义，即不知道在何位置对接收到的编码消息进行划分。因此在进行变长编码时，就必须保证任何编码都不是其他编码的前缀。符合这种特性的编码称为前缀码（Prefix Codes）。
从上面的叙述可以看出，每当在某位置选取一个编码以后，我们都要损耗一部分编码空间，如图
当我们在第2个bit选择了编码1，那为了满足前缀码的特性，就会导致有$\frac{1}{4}$的编码空间不能继续使用了。事实上，长度为L的编码会使得$\frac{1}{2^L}$的编码空间不能继续使用。
因此，为了达到对信息进行最优编码的目标，我们要在使用尽可能短的编码与短编码可能会导致编码空间不可用的两种情况中进行权衡。
我们可以把使用短编码需要消耗的编码空间称为编码代价。事实上，为了达到理论上的最优编码，我们只需要根据不同消息X出现的概率P(X)给每类消息分配相应的编码代价即可以达到最优编码，假设X的编码长度为L(X)，那么
$$ \begin{align*} &\frac{1}{2^{L(X)}} =P(X)\\ &L(X) = log_2{\frac{1}{P(X)}}\\ \end{align*} $$
这样，对于p分布，我们的平均编码长度就是:
$$ H(p)=\sum_{x}p(x)log_2(\frac{1}{p(x)}) $$
在信息论中，H(p)被称为熵，熵代表了理论上对符合p分布的消息进行编码的最优编码的平均长度。
若现在还有一种消息序列的概率分布满足q分布，但是它仍然使用p分布的最优编码方式，那么它的平均编码长度即为
$$ H(q||p)=H_p(q)=\sum_{x}q(x)log_2(\frac{1}{p(x)})$$
其中$H_p(q)$被称为q分布相对于p分布的交叉熵（Cross Entropy），它衡量了q分布使用p分布的最优编码方式时的平均编码长度。
交叉熵不是对称的，即$H_p(q)\neq H_q(p)$。交叉熵的意义在于它给我们提供了一种衡量两个分布的不同程度的方式。两个分布p和q的差异越大，交叉熵$H_p(q)$就比$H(p)$大的越多，如图
它们的不同的大小为$D_p(q)$，这在信息论中被称为KL散度（Kullback-Leibler Divergence），它满足
$$D_p(q)=H_p(q)-H(q)$$
KL散度可以看作为两个分布之间的距离，也可以说是可以衡量两个分布的不同程度。
和单变量相同，如果有两个变量X，Y，我们可以计算它们的联合熵（Joint Entropy）
$$H(X,Y)=\sum_{x,y}p(x,y)log_2(\frac{1}{p(x,y)})$$
当我们事先已经知道Y的分布，我们可以计算条件熵（Conditional Entropy）
$$ H(X|Y)=\sum_{y}p(y)\sum_{x}p(x|y)log_2(\frac{1}{p(x|y)})=\sum_{x,y}p(x,y)log_2(\frac{1}{p(x|y)}) $$
X与Y变量之间可能共享某些信息，我们可以把信息熵想象成一个信息条，如下图
从中可以看出，单变量的信息熵H(X)(或H(Y))一般比多变量信息熵H(X,Y)要小。如果把条件熵也放进来，那么可以从信息条更清晰的看出它们之间的关系
可以看出
$$H(X,Y)=H(X)+H(Y|X)=H(Y)+H(X|Y)$$
更细一点，我们把H(X)与H(Y)重叠的部分定义为X与Y的互信息（Mutual Entropy），记作$I(X,Y)$，则
$$I(X,Y)=H(X)+H(Y)-H(X,Y)$$
互信息代表了X中包含的有关于Y的信息（或相反）。
将X与Y不重叠的信息定义为差异信息（Variation of Information），记为$V(X,Y)$，则
$$V(X,Y)=H(X,Y)-I(X,Y)$$
差异信息可以衡量变量X与Y的差距，若V(X,Y)为0，就意味着只要知道一个变量，就知道另一个变量的所有信息。随着V(X,Y)的增大，也就意味着X与Y更不相关。形象化的表示可以从下图看出
自信息（self-information)
- 非常可能发生的事件, 信息量少
- 较不可能发生的事件, 信息量更多
- 独立事件, 应该具有增量的信息, 例如连续两次硬币正面朝上的信息量，应该是一次硬币正面朝上的信息量的两倍。
信息量公式: $$ I(x) = -log(P(x)) $$
香农熵（Shannon entropy）
自信息量处理单个输出，香农熵对整个概率分布中的不确定性总量进行量化。
香农熵公式:
$$ H(x) = E_{x \sim P}[I(x)] = -E_{x \sim P}[logP(x)] $$
KL散度（Kullback-Leibler (KL) divergence）
对于同一个随机变量x，有两个单独的概率分布P(x)和 Q(x)，使用KL散度来描述这两个分布的差异。因为KL散度是非负的，如果KL散度为0.表示P和Q在离散变量上相同分布，或者连续变量上几乎处处相同。
KL散度公式:
$$ D_{KL} = E_{x \sim P}[log\frac{P(x)}{Q(x)}] = E_{x \sim P}[logP(x) - logQ(x)] $$
交叉熵（cross-entropy)
用于度量两个概率分布间的差异性信息
交叉熵公式:
$$ H(P,Q) = -E_{x \sim P}logQ(x) $$
三者间的关系
$$ H(P,Q) = H(P) + D_{KL})(P\parallel Q) $$
交叉熵和KL散度在机器学习中的应用
信息论中有很多理论可以应用在机器学习中，其中交叉熵和KL散度在各类模型中出现的频率非常高。
在分类任务中，我们想要的结果是使预测的分布和真实的分布尽量接近，交叉熵提供了一种非常好的衡量方式，在LR分类，SVM多分类等问题中经常用到，将交叉熵定义为损失函数
$$L=H_p(q)=\sum_xp(x)log(\frac{1}{q(x)})$$
其中$p(x)$代表真实分布，$q(x)$代表预测分布，优化目标为$min_{q(x)}L$。
在概率推断中，经常使用变分推断来近似隐变量Z真实的后验分布P(Z|X)。利用如下公式
$$lnP(X)=L(q)+KL(q||p)$$
其中
$$ L(q)=\int q(Z)ln\{\frac{p(X,Z)}{q(Z)}\}dZ KL(q||p)=-\int q(Z)ln\{\frac{p(Z|X)}{q(Z)}\}dZ $$
上式中的$L(q)$称为证据下界（Evidence Lower Bound）。
这里KL散度$KL(q||p)$描述了估计分布$q(Z)$与真实分布$P(Z|X)$的差别，当$KL(q||p)=0$时两分布就是相同的。我们知道$KL(q||p)\geq0$，但因为我们不知道真实的后验分布$P(Z|X)$是什么，因此无法直接最小化$KL(q||p)$，但是我们可以通过最大化$L(q)$来达到这个目的。而在求解最大化$L(q)$的过程中，可以利用平均场方法（Mean Field）将最终目标可以转化成最小化另外的一个KL散度.