ICLR 2020 | 北大图灵班满分论文：基于计算约束下有用信息的信息论

AI科技评论今天

以下文章来源于北京大学前沿计算研究中心，作者许逸伦

北京大学前沿计算研究中心

北京大学前沿计算研究中心（Center on Frontiers of Computing Studies, PKU）官方公众号

作者 | 许逸伦

编辑 | 丛末

本文是对 ICLR 2020 oral 论文《基于计算约束下的有用信息的信息论 (A Theory of Usable Information Under Computational Constraint）》的解读。

该论文由北京大学2016级图灵班本科生许逸伦，斯坦福博士生Shengjia Zhao, Jiaming Song, Russell Stewart，和斯坦福大学助理教授Stefano Ermon合作完成。在审稿阶段中，该论文获“满分”接收。

Arxiv Link: https://arxiv.org/abs/2002.10689

Openreview Link: https://openreview.net/forum?id=r1eBeyHFDH

背景

香农互信息（Mutual Information）是一套影响深远的理论，并且在机器学习中的表示学习（Representation Learning）、信息最大化（Informax）、对比预测性编码（Contrastive Predictive Coding）与特征性选择；和结构学习（Structure Learning）中的贝叶斯网络的构建，均有广泛应用。但香农信息论没有考虑很重要的计算约束方面的问题，并假设了我们有无穷的计算能力。为了突出这个问题，我们考虑以下这个密码学中的例子。

在我们的例子中，有一个带标注的明文数据集，同时有一个相对应的 RSA 加密后的秘文数据集。如果 RSA 的公钥已知，那么由于 RSA 是双射的，根据互信息在双射下的不变性，明文与秘文应该与其标注有着相同的互信息，如下图所示：

为了更直观地理解其中的不合理性，我们用相应的图片分别表示明文和秘文，如下图所示，加密后的图片看起来就像随机采样产生的噪声图片。

但是对于人类（或机器学习算法）来说，根据明文去预测标注显然比根据秘文去预测更容易。因此我们认为，在人类看来，明文与标注有着更大的互信息，但这与香农互信息矛盾。这个矛盾背后的原因正是因为香农互信息假设了观测者有无穷的计算能力，从而忽视了什么是对于观测者来说的有用信息。

另一个例子是，由香农互信息的数据处理不等式（data processing inequality）我们知道，神经网络的深层表示（CNN feature）与标注的互信息应少于原始输入与标注的互信息。但是在简单的分类器看来，深层表示与标注的互信息更大。

因此，香农互信息对无穷计算能力的假设与对基于观测者的有用信息的忽视带来了许多反直觉的例子。

除此之外，本文还证明了现有的对香农互信息的变分估计量（NWJ, MINE, CPC）或者有较大的方差，或者有较大的估计误差，比如 NJW 估计量的误差可以到互信息量的指数级别。

V-信息：一种新的信息论框架

基于以上提到的香农信息论的缺点，本文利用变分（variational）的思想提出了一种显示地考虑计算约束的信息量，并称之为 V(ariational)-information。

首先，我们定义一个大集合

这个集合包含所有把一个随机变量 X 的具体取值映射到另一个随机变量的取值域上的概率测度 P(Y)。

什么是计算约束呢？首先见下面我们对条件 V-熵（conditional V-entropy）的定义（其中我们省去了不重要的预测族（predictive family）的定义，它本质上是加了些正则条件，感兴趣的小伙伴可以看下原 paper）：

定义（条件 V-熵）：X, Y 是两个取值在 X, Y 的随机变量，V ⊆ Ω 是一个预测族，则条件 V-熵的定义为：

计算约束体现在观测者被限制为 V ⊆ Ω，即取全集 Ω 的一个子集合 V。由于 V ⊆ Ω，因此定义中的 f[x] 是一个概率测度，f[x](y) 是该概率测度（如概率密度函数）在 y 处的取值。

直观地来看，条件 V-熵是在观测到额外信息 X 的情况下，仅利用函数族 V 中的函数，去预测 Y 可以取到的期望下最小的负对数似然（negative log-likelihood）。同理定义 V-熵，也就是没有观测到额外信息（用 ∅ 表示）的情况下，利用 V 中的函数去预测 Y 可以取到的期望下最小的负对数似然。

下面我们展示，通过取不同的函数族 V，许多对不确定性的度量（如方差、平均绝对离差、熵）是 V-熵的特例：

接着类似于香农互信息的定义，我们利用 V-熵来定义 V-信息：

定义（V-信息）：X, Y 是两个取值在 X, Y 的随机变量，V ⊆ Ω 是一个预测族，则 V-信息的定义为：

即从 X 到 Y 的 V-信息是 Y 的 V-熵在有考虑额外信息 X 的情况下的减少量。我们也证明了决定系数、香农互信息均为 V-信息在取不同函数族 V 下的特例。我们还证明了 V-信息的一些性质，比如单调性（取更大的函数族 V，V-信息也随之增大），非负性与独立性（X, Y 独立则 V-信息为0）。

此外我们展示，通过显示地考虑计算约束，在 V-信息的框架下，计算可以增加 V-信息，即增加对观测者而言的有用信息：