Jarvis' Blog 成功的路上并不拥挤, 因为坚持的人不多

机器学习(一): 信息论初步

2018-09-18
Jarvis
Post

Update: 2019-04-08

我们通常提到信息论(information theorey)时一般在谈论如何以更紧凑的方式表示数据(比如数据压缩源编码), 或者在数据传输和存储时减少误差. 乍一看和机器学习及概率论并无关系, 但他们有着密切的联系. 比如在压缩数据时, 往往使用短的编码词编码高频词汇, 长的编码词编码低频词汇; 反之解码时需要一个好的概率模型来确定哪种原始组合的概率更高.

Claude Shannon 1916-2001. Picture source

1. 信息量和熵

定义: 分布为 的随机变量 取值为 信息量(information content)定义为

因此概率越小的事件, 信息量越大. 进而, 熵可以定义为随机变量 的平均信息量(即信息量的期望).

定义: 分布为 的随机变量 的熵是不确定性的一种度量, 记为 . 特别的, 对一个有着 个取值的离散随机变量, 熵(entropy)可以定义为

定理: , 当且仅当 是离散均匀分布时等号成立.

该定理可以作为下面信息不等式的推论得出. 从定理中容易知道离散分布的最大熵为 . 特别地, 时得到二值熵 , 其中 为成功概率(相应的 为失败概率).

定义: 给定随机变量 , 随机变量 条件熵(conditional entropy)定义为

进一步, 给定随机变量 , 随机变量 的条件熵定义为

2. KL 散度

一个通常用于度量两个概率分布 的差异大小的指标就是 KL 散度(Kullback-Leibler divergence) 或称为相对熵.

定义: 离散形式

连续形式

注意, KL 散度不是对称的, 所以并不是一种距离度量. 把 KL 散度展开为两项

其中我们把 称为交叉熵. 交叉熵是使用模型 编码来自于分布 的数据所需要的平均位数, 从而”正规”熵 即是使用正确模型编码所需要的位数, 所以 KL 散度可以理解为使用模型 编码来自于分布 的数据所额外需要的位数.

定理(信息不等式): , 当且仅当 时等号成立.

可利用 Jensen 不等式

证明上述定理, 证明略.

3. 互信息

考虑随机变量 , 如果我们想知道这两者之间的关联性有多强, 一个直接的方法是计算他们的相关系数. 但是相关系数所反应的随机变量的相关性存在局限性, 如下图所示

Correlation Examples

相关性相同的随机变量可以有着千奇百怪且截然不同的分布. 因此我们引入互信息(mutual information, MI)

定义: 对随机变量 ,

显然 , 当且仅当 时取等号.

这意味着 当且仅当 独立. 进一步我们有

其中 称为条件熵, 利用贝叶斯公式上式容易证明. 有了条件熵, 我们就能对互信息做出直观的解释: 观测到随机变量 $$ Y $$ 后随机变量 $$ X $$ 的熵减, 反之亦然. 与互信息相关的另一概念是点互信息(pointwise mutual information, PMI)

定义: 对随机事件 ,

衡量了两个事件同时发生的概率.

显然 的 MI 是 PMI 的期望(从定义式中可以看出).

连续随机变量的互信息

计算连续随机变量的互信息通常先对其进行离散, 然后得到区间的统计值后再采用离散 MI 的计算公式. 然而离散的步长对结果有显著的影响. 另一种方法是最大化信息系数(maximal information coefficient, MIC) , 即尝试多种区间大小, 然后取最大值

定义:

其中 是一族大小为 的网格点, 表示网格上离散了的随机变量, 是采样的区间数, 一个典型的值为 .

可以证明 MIC 的范围是 . 下面图 A 给出了 63566 个随机变量的相关系数 CC 和 MIC 的关系图, 图 B 给出了 CC 和 MI 的关系图.

MI-MIC-CC

  • 点 C 表示一组低 CC, 低 MIC 的随机变量, 可以看出他们是不相关的.
  • 点 D 和 H 表示两组高 CC(取绝对值), 高 MIC 的随机变量, 可以看出他们几乎存在线性相关性.
  • 点 E, F 和 G 表示三组低 CC, 高 MIC 的随机变量, 显然他们存在非线性的相关性, 但是此时 CC 无法反映出这种相关性, 而 MIC 仍然能较好的体现出来.
  • 图 I 中左侧的两幅图的噪声比右侧的两幅图更小

参考

[1] Machine Learning: A Probabilistic Perspective, Kevin P. Murphy, Chapter 2, Probability

[2] https://en.wikipedia.org/wiki/File:Correlation_examples.png

[3] Reshef D N, Reshef Y A, Finucane H K, et al. Detecting novel associations in large data sets[J]. science, 2011, 334(6062): 1518-1524.


Content