本文是对 ICLR 2020 oral 论文《基于计算约束下的有用信息的信息论 (A Theory of Usable Information Under Computational Constraint）》的解读。
Arxiv Link:
Openreview Link:
1 背景
香农互信息（Mutual Information）是一套影响深远的理论，并且在机器学习中的表示学习（Representation Learning）、信息最大化（Informax）、对比预测性编码（Contrastive Predictive Coding）与特征性选择；和结构学习（Structure Learning）中的贝叶斯网络的构建，均有广泛应用。但香农信息论没有考虑很重要的计算约束方面的问题，并假设了我们有无穷的计算能力。为了突出这个问题，我们考虑以下这个密码学中的例子。
为了更直观地理解其中的不合理性，我们用相应的图片分别表示明文和秘文，如下图所示，加密后的图片看起来就像随机采样产生的噪声图片。
但是对于人类（或机器学习算法）来说，根据明文去预测标注显然比根据秘文去预测更容易。因此我们认为，在人类看来，明文与标注有着更大的互信息，但这与香农互信息矛盾。这个矛盾背后的原因正是因为香农互信息假设了观测者有无穷的计算能力，从而忽视了什么是对于观测者来说的有用信息。
因此，香农互信息对无穷计算能力的假设与对基于观测者的有用信息的忽视带来了许多反直觉的例子。
除此之外，本文还证明了现有的对香农互信息的变分估计量（NWJ，MINE，CPC）或者有较大的方差，或者有较大的估计误差，比如 NJW 估计量的误差可以到互信息量的指数级别。
2 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，许多对不确定性的度量 （如方差、平均绝对离差、熵）是 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-信息是非对称的，它可以很自然地用到一些因果发现或者密码学（如 one-way function）的场景中。
3 对 V-信息的估计
不同于香农互信息，在对函数族 V 的一些假设下，本文证明了 V-信息在有限样本上的估计误差是有 PAC 界的：
这个 PAC 界启发我们将 V-信息用于一些使用香农互信息的结构学习的算法中。我们发现这些之前在有限样本上没有保证的算法，迁移到 V-信息下就有了保证。比如 Chow-Liu 算法就是一例：
4 更多的实验
我们也将 V-信息用到了其他结构学习的任务中，如基因网络重建（下左图）和因果推断（下右图）。
注意到与一些非参数化的估计量（如 KSG，Partitioning 等）相比，我们的方法在低维基因网络的重建中取得了更好的效果。同时我们的方法在因果推断的实验中正确地重建了时序序列。在确定性的时序轨迹 （deterministic dynamics）下，香农互信息是无法重建时序序列的。
最后，我们将 V-信息应用到公平表示（fairness）上。若VA，VB 是两个不同的函数族，我们发现实现 VA-信息最小化的公平表示不一定能泛化到 VB-信息最小化。这一发现挑战了许多现有文献的结果。
5 总结
ICLR 2020 系列论文解读
0、ICLR 2020 会议动态报道
疫情严重，ICLR2020 将举办虚拟会议，非洲首次 AI 国际顶会就此泡汤
疫情影响，ICLR 突然改为线上模式，2020年将成为顶会变革之年吗？
火爆的图机器学习，ICLR 2020上有哪些研究趋势？
1、直播
回放 | 华为诺亚方舟ICLR满分论文：基于强化学习的因果发现
2、Oral
01. Oral | 一种镜像生成式机器翻译模型：MGNMT
02. Oral | 额外高斯先验目标，缓解负多样性无知
03. Oral | 引入额外门控运算，LSTM稍做修改，性能便堪比Transformer-XL
04. Oral | 并行蒙卡树搜索，性能无损，线性加速，勇闯「消消乐」1000关！
05. Oral | 元强化学习迎来一盆冷水：不比元Q学习好多少
06. Oral | 用群卷积建立深度、等变的胶囊网络
07. Oral | 谷歌推出分布式强化学习框架SEED，性能“完爆”IMPALA，可扩展数千台机器，还很便宜
08. Oral | Reformer ，一种高效的Transformer
09. Oral | 基于值函数的规划和强化学习的控制架构（视频直播）
3、Spotlight
01. Spotlight | 模型参数这么多，泛化能力为什么还能这么强？
02. Spotlight | 公平与精确同样重要！CMU提出学习公平表征方法，实现算法公平
03. Spotlight | 组合泛化能力太差？用深度学习融合组合求解器试试
04. Spotlight | 加速NAS，仅用0.1秒完成搜索
05. Spotlight | 华盛顿大学：图像分类中对可实现攻击的防御（视频解读）
06. Spotlight | 超越传统，基于图神经网络的归纳矩阵补全
07. Spotlight | 受启诺奖研究，利用格网细胞学习多尺度表达（视频解读）
08. Spotlight | 告别死记硬背，元学习才能学会学习
4、Poster
01. Poster | 华为诺亚：巧妙思想，NAS与「对抗」结合，速率提高11倍
02. Poster | 抛开卷积，多头自注意力能够表达任何卷积操作
03. Poster | NAS 太难了，搜索结果堪比随机采样！华为给出 6 条建议
04. Poster | 清华提 NExT 框架，用「神经元执行树」学习可解释性
05. Poster | 谷歌最新研究：用“复合散度”量化模型合成泛化能力
06. Poster | 完胜 BERT，谷歌最佳 NLP 预训练模型开源，单卡训练仅需 4 天
07. Poster | FSNet：利用卷积核概要进行深度卷积神经网络的压缩
08. Poster | "同步平均教学"框架为无监督学习提供更鲁棒的伪标签
09. Poster | 快速神经网络自适应技术
