【机器之心】北大图灵班本科生满分论文：计算约束下有用信息的信息论
机器之心转载
来源： 北京大学前沿计算研究中心
作者：许逸伦
本文是第八届国际表征学习会议 (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) 。
推荐阅读
- 机器人：青岛造运输机器人打败五家外企 成功进驻世界最大中转枢纽港
- 「时间」iPhone se2这机器放在现在这个时间，真的有点奇怪
- #科技如梦#iPhone se2这机器放在现在这个时间，真的有点奇怪
- [机器人]从昆虫身上找灵感，研发人员用3D打印批量制造机器人群 | 硬科技
- 公司：AT＆T将提供云平台为XENEX公司的消毒机器人提供物品清洁服务
- 机器之心：几行代码搞定ML模型，低代码机器学习Python库正式开源
- 【机器之心】工作流一目了然，看小姐姐用动图展示10大Git命令
- 「机器人」科学家使用集成神经网络改变机器人步态
- #3DMGAME#索尼申请陪玩机器人专利 能感知玩家情感并做出反馈
- 「」2.5D视觉系统“Eyes”实现机器人应用的极致简易操作