信息论
信息论(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距离等价于欧氏距离.