许逸伦作者

ICLR 2020 Oral | 基于计算约束下的有用信息的信息论

导读

本文是第八届国际表征学习会议 (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

01 背景

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

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

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

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

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

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

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

02 V-信息:一种新的信息论框架

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

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

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

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

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

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

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

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

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

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

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

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

同时,注意到 V-信息是非对称的,它可以很自然地用到一些因果发现或者密码学(如 one-way function)的场景中。

03 V-信息的估计

不同于香农互信息,在对函数族 V 的一些假设下,本文证明了 V-信息在有限样本上的估计误差是有 PAC 界的:

这个 PAC 界启发我们将 V-信息用于一些使用香农互信息的结构学习的算法中。我们发现这些之前在有限样本上没有保证的算法,迁移到 V-信息下就有了保证。比如 Chow-Liu 算法就是一例:

本文通过实验验证了新的基于 V-信息的算法构建 Chow-Liu Tree 的效果,优于利用现存最好的互信息估计量的 Chow-Liu 算法。

04  更多的实验

我们也将 V-信息用到了其他结构学习的任务中,如基因网络重建(下左图)和因果推断(下右图)。

注意到与一些非参数化的估计量(如 KSG, Partitioning 等)相比,我们的方法在低维基因网络的重建中取得了更好的效果。同时我们的方法在因果推断的实验中正确地重建了时序序列。在确定性的时序轨迹 (deterministic dynamics)下,香农互信息是无法重建时序序列的。

最后,我们将 V-信息应用到公平表示(fairness)上。若VA, VB 是两个不同的函数族,我们发现实现 VA-信息最小化的公平表示不一定能泛化到 VB-信息最小化。这一发现挑战了许多现有文献的结果。

05  总结

本文提出并探索了一种新的信息框架 V-信息。V-信息包含了许多现有的概念,并且有许多机器学习领域喜欢的性质,比如对信息处理不等式的违背与非对称性。V-信息可以被有保证地估计好,且在结构学习中有着优异的表现。

ICLR

国际表征学习会议(The International Conference on Learning Representations, ICLR)深度学习领域的顶级会议,也是国际发展最快的人工智能专业会议之一,由深度学习三大巨头之二的 Yoshua Bengio 和Yann LeCun 牵头创办。会议采取公开评审的审稿制度,因其在深度学习领域各方面(如人工智能、统计学和数据科学),以及计算机视觉、计算生物学等重要应用领域发表和展示前沿研究成果而享誉全球。ICLR 2020原定2020年4月26日至5月1日在埃塞俄比亚举行,现因疫情缘故改为线上举行。

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

北京大学前沿计算研究中心主导/参与的相关科研成果发布。

理论机器学习信息论ICLR 2020
相关数据
深度学习技术

深度学习(deep learning)是机器学习的分支,是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。 深度学习是机器学习中一种基于对数据进行表征学习的算法,至今已有数种深度学习框架,如卷积神经网络和深度置信网络和递归神经网络等已被应用在计算机视觉、语音识别、自然语言处理、音频识别与生物信息学等领域并获取了极好的效果。

结构学习技术

结构化预测是监督学习,分类和回归的标准范式的一种推广。 所有这些可以被认为是找到一个能最大限度减少训练集损失的函数。

机器学习技术

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

人工智能技术

在学术研究领域,人工智能通常指能够感知周围环境并采取行动以实现最优的可能结果的智能体(intelligent agent)

参数技术

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

数据科学技术

数据科学,又称资料科学,是一门利用数据学习知识的学科,其目标是通过从数据中提取出有价值的部分来生产数据产品。它结合了诸多领域中的理论和技术,包括应用数学、统计、模式识别、机器学习、数据可视化、数据仓库以及高性能计算。数据科学通过运用各种相关的数据来帮助非专业人士理解问题。

表征学习技术

在机器学习领域,表征学习(或特征学习)是一种将原始数据转换成为能够被机器学习有效开发的一种技术的集合。在特征学习算法出现之前,机器学习研究人员需要利用手动特征工程(manual feature learning)等技术从原始数据的领域知识(domain knowledge)建立特征,然后再部署相关的机器学习算法。虽然手动特征工程对于应用机器学习很有效,但它同时也是很困难、很昂贵、很耗时、并依赖于强大专业知识。特征学习弥补了这一点,它使得机器不仅能学习到数据的特征,并能利用这些特征来完成一个具体的任务。

计算机视觉技术

计算机视觉(CV)是指机器感知环境的能力。这一技术类别中的经典任务有图像形成、图像处理、图像提取和图像的三维推理。目标识别和面部识别也是很重要的研究领域。

神经网络技术

(人工)神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型,那时候研究者构想了「感知器(perceptron)」的想法。这一领域的研究者通常被称为「联结主义者(Connectionist)」,因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型,它们都是前馈神经网络:卷积神经网络(CNN)和循环神经网络(RNN),其中 RNN 又包含长短期记忆(LSTM)、门控循环单元(GRU)等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习,但也有一些为无监督学习设计的变体,比如自动编码器和生成对抗网络(GAN)。

映射技术

映射指的是具有某种特殊结构的函数,或泛指类函数思想的范畴论中的态射。 逻辑和图论中也有一些不太常规的用法。其数学定义为:两个非空集合A与B间存在着对应关系f,而且对于A中的每一个元素x,B中总有有唯一的一个元素y与它对应,就这种对应为从A到B的映射,记作f:A→B。其中,y称为元素x在映射f下的象,记作:y=f(x)。x称为y关于映射f的原象*。*集合A中所有元素的象的集合称为映射f的值域,记作f(A)。同样的,在机器学习中,映射就是输入与输出之间的对应关系。

贝叶斯网络技术

贝叶斯网络(Bayesian network),又称信念网络或是有向无环图模型,是一种概率图型模型。例如,贝叶斯网络可以代表疾病和症状之间的概率关系。 鉴于症状,网络可用于计算各种疾病存在的概率。

信息论技术

信息论是在信息可以量度的基础上,研究有效地和可靠地传递信息的科学,它涉及信息量度、信息特性、信息传输速率、信道容量、干扰对信息传输的影响等方面的知识。通常把上述范围的信息论称为狭义的信息论,又因为它的创始人是香农,故又称为香农信息论。

因果推断技术

因果推断是基于效应发生的条件得出关于因果关系的结论的过程。因果推理和关联推理之间的主要区别在于,前者分析了原因发生变化时效应变量的反应。事情发生的科学被称为原因学。Causal Inference是Causal reasoning一个例子。

推荐文章
暂无评论
暂无评论~