信息论
信息论（Information Theory）是数学、物理、统计、计算机科学等多个学科的交叉领域．信息论是由克劳德·香农最早提出的，主要研究信息的量化、存储和通信等方法．这里，“信息”是指一组消息的集合．假设在一个噪声通道上发送消息，我们需要考虑如何对每一个信息进行编码、传输以及解码，使得接收者可以尽可能准确地重构出消息．
在机器学习相关领域，信息论也有着大量的应用．比如特征抽取、统计推断、自然语言处理等．
1. 熵
熵（Entropy）最早是物理学的概念，用于表示一个热力学系统的无序程度．在信息论中，熵用来衡量一个随机事件的不确定性．
1.1 自信息和熵
自信息（Self Information）表示一个随机事件所包含的信息量．一个随机事件发生的概率越高，其自信息越低．如果一个事件必然发生，其自信息为0．
对于一个随机变量 𝑋（取值集合为 𝒳，概率分布为 𝑝(𝑥), 𝑥 ∈ 𝒳），当 𝑋 = 𝑥时的自信息𝐼(𝑥)定义为
在自信息的定义中，对数的底可以使用 2、自然常数 𝑒 或是 10．当底为 2 时，自信息的单位为bit；当底为𝑒时，自信息的单位为nat．对于分布为𝑝(𝑥)的随机变量𝑋，其自信息的数学期望，即熵𝐻(𝑋)定义为
其中当𝑝(𝑥𝑖 ) = 0时，我们定义0 log 0 = 0，这与极限一致，lim𝑝→0+ 𝑝 log 𝑝 = 0.
熵越高，则随机变量的信息越多；熵越低，则随机变量的信息越少．如果变量𝑋 当且仅当在 𝑥 时 𝑝(𝑥) = 1，则熵为 0．也就是说，对于一个确定的信息，其熵为0，信息量也为0．如果其概率分布为一个均匀分布，则熵最大．
假设一个随机变量𝑋 有三种可能值𝑥1 , 𝑥2, 𝑥3，不同概率分布对应的熵如下：
1.2 熵编码
信息论的研究目标之一是如何用最少的编码表示传递信息．假设我们要传递一段文本信息，这段文本中包含的符号都来自于一个字母表𝑨，我们就需要对字母表𝑨中的每个符号进行编码．以二进制编码为例，我们常用的ASCII码就是用固定的 8bits 来编码每个字母．但这种固定长度的编码方案不是最优的．一种高效的编码原则是字母的出现概率越高，其编码长度越短．比如对字母 𝑎, 𝑏, 𝑐 分别编码为0, 10, 110．
给定一串要传输的文本信息，其中字母 𝑥 的出现概率为 𝑝(𝑥)，其最佳编码长度为 − log2 𝑝(𝑥)，整段文本的平均编码长度为 − ∑𝑥 𝑝(𝑥)log2 𝑝(𝑥)，即底为 2的熵．
在对分布 𝑝(𝑥) 的符号进行编码时，熵 𝐻(𝑝) 也是理论上最优的平均编码长度，这种编码方式称为熵编码（Entropy Encoding）．
由于每个符号的自信息通常都不是整数，因此在实际编码中很难达到理论上的最优值．霍夫曼编码（Huffman Coding）和算术编码（Arithmetic Coding）是两种最常见的熵编码技术．
1.3 联合熵和条件熵
对于两个离散随机变量𝑋 和𝑌，假设𝑋 取值集合为𝒳；𝑌 取值集合为𝒴，其联合概率分布满足为𝑝(𝑥, 𝑦)，则
𝑋 和𝑌 的联合熵（Joint Entropy）为
𝑋 和𝑌 的条件熵（Conditional Entropy）为
根据其定义，条件熵也可以写为
2. 互信息
互信息（Mutual Information）是衡量已知一个变量时，另一个变量不确定性的减少程度．两个离散随机变量𝑋 和𝑌 的互信息定义为
互信息的一个性质为
如果变量𝑋 和𝑌 互相独立，它们的互信息为零．
3. 交叉熵和散度
3.1 交叉熵
对于分布为𝑝(𝑥)的随机变量，熵𝐻(𝑝)表示其最优编码长度．交叉熵（CrossEntropy）是按照概率分布𝑞的最优编码对真实分布为𝑝的信息进行编码的长度，定义为
在给定 𝑝 的情况下，如果 𝑞 和 𝑝 越接近，交叉熵越小；如果 𝑞 和 𝑝 越远，交叉熵就越大．
3.2 KL散度
KL 散度（Kullback-Leibler Divergence），也叫KL 距离或相对熵(Relative Entropy)，是用概率分布 𝑞 来近似 𝑝 时所造成的信息损失量．KL 散度是按照概率分布𝑞的最优编码对真实分布为𝑝的信息进行编码，其平均编码长度（即交叉熵）𝐻(𝑝, 𝑞) 和 𝑝 的最优平均编码长度（即熵）𝐻(𝑝) 之间的差异．对于离散概率分布𝑝和𝑞，从𝑞到𝑝的KL散度定义为
其中为了保证连续性，定义0 log 00 = 0, 0 log 0𝑞= 0．
KL散度总是非负的，KL(𝑝, 𝑞) ≥ 0，可以衡量两个概率分布之间的距离．KL散度只有当𝑝 = 𝑞时，KL(𝑝, 𝑞) = 0．如果两个分布越接近，KL散度越小；如果两个分布越远，KL散度就越大．但KL散度并不是一个真正的度量或距离，一是KL散度不满足距离的对称性，二是KL散度不满足距离的三角不等式性质．
3.3 JS 散度
JS散度（Jensen-Shannon Divergence）是一种对称的衡量两个分布相似度的度量方式，定义为
3.4 Wasserstein距离
Wasserstein 距离（Wasserstein Distance）也用于衡量两个分布之间的距离．对于两个分布𝑞1 , 𝑞2，𝑝 th-Wasserstein距离定义为
其中Γ(𝑞1 , 𝑞2)是边际分布为𝑞1 和𝑞2 的所有可能的联合分布集合，𝑑(𝑥, 𝑦)为𝑥 和 𝑦的距离，比如ℓ𝑝 距离等．
如果将两个分布看作两个土堆，联合分布 𝛾(𝑥, 𝑦) 看作从土堆 𝑞1 的位置 𝑥 到土堆𝑞2 的位置𝑦的搬运土的数量，并有
𝑞1 和𝑞2 为𝛾(𝑥, 𝑦)的两个边际分布．
𝔼(𝑥,𝑦)∼𝛾(𝑥,𝑦)[𝑑(𝑥, 𝑦)𝑝] 可以理解为在联合分布 𝛾(𝑥, 𝑦) 下把形状为 𝑞1 的土堆搬运到形状为𝑞2 的土堆所需的工作量，
其中从土堆𝑞1 中的点𝑥 到土堆𝑞2 中的点𝑦 的移动土的数量和距离分别为𝛾(𝑥, 𝑦)和 𝑑(𝑥, 𝑦)𝑝．因此，Wasserstein 距离可以理解为搬运土堆的最小工作量，也称为推土机距离（Earth-Mover’s Distance，EMD）．图E.1给出了两个离散变量分布的Wasserstein距离示例．图E.1c中同颜色方块表示在分布𝑞1 中为相同位置．
Wasserstein 距离相比 KL 散度和 JS 散度的优势在于：即使两个分布没有重叠或者重叠非常少，Wasserstein距离仍然能反映两个分布的远近．
对于 ℝ𝐷 空间中的两个高斯分布 𝑝 = 𝒩(𝝁1 , 𝚺1) 和 𝑞 = 𝒩(𝝁2 , 𝚺2)，它们的2 nd-Wasserstein距离为
当两个分布的方差为0时，2 nd-Wasserstein距离等价于欧氏距离.
