Press "Enter" to skip to content

ICLR最高分论文揭秘模型泛化,GNN是潜力股

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

文 | Jerry Qiu

 

编 | 小轶

 

我们都知道,人类在很多任务上都可以很好地完成“ 外推 ”,例如:

 

啊不——我是说——例如,我们学会两位数的加减乘除后,就可以轻松将其推广至任意大整数的四则运算:

 

从数学的角度来讲,外推其实是与内插并列的一个概念。想必大家对多项式插值、样条插值等插值方法不陌生。通过已知的、离散的数据点,在 范围内 推求新数据点,即称为 内插(Interpolation) 。而如果我们在已知数据在 范围外 推求新数据点,则是 外推(Extrapolate) 。

 

在通用人工智能被广泛讨论的今天,我们不禁发问,神经网络能像人类一样完成外推吗?即神经网络在训练分布的支撑集 [1] 之外,会如何表现?前辈们对于这一问题已经进行了一定的探究。然而令人困惑的是,他们对神经网络的外推给出了截然不同的结论。

 

早期的工作表明, 多层感知机 (Multi-layer Perceptron,MLP)在学习简单的多项式函数时不能很好地外推 [2,3] 。然而近期的⼀些工作则表明,在部分具有挑战性的算法任务上(例如求解数学方程、预测物理系统的时间演化), 图神经网络 (Graph Neural Network,GNN)具有很好的泛化能力 ,能够将训练结果推广至比训练集更大的图上 [4,5,6] 。

 

多层感知机与图神经网络截然相反的表现引人深思: 什幺样的网络,在什幺样的条件下才会具有较强的外推能力呢?

 

今天给大家分享的这篇论文便研究了这一问题。该文在ICLR’21的review阶段获得了最高的平均得分。审稿人们纷纷赞其见解之深刻,在神经网络外推能力的分析上迈出了重要的一步。

 

论文题目:

 

How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks

 

论文链接:

 

https://arxiv.org/pdf/2009.11848.pdf

 

Arxiv访问慢的小伙伴也可以在 【 夕小瑶的卖萌屋 】订阅号后台回复关键词 【 1231 】 下载论文PDF~

 

论文概述

 

为了解释为何不同神经网络的外推能力不尽相同,论文作者详细探究了使用梯度下降训练的神经网络是如何外推的。直觉上来说,神经网络在训练分布之外的表现是任意的、不可预料的 [7] ,但事实上, 如果网络用梯度下降算法进行训练 ,则 它的外推能力是有规律可循的 。

 

在我们评价神经网络的外推能力前,我们需要先确定一个指标来衡量它。为此,论文作者定义了 外推误差 这一概念。一个模型的外推误差越小,则其外推能力越强。作者基于此讨论了MLP和GNN的具备外推能力的条件。

 

外推误差

 

在机器学习中,我们通常都希望在训练集上学习一个函数,训练目标是使满足。注意,这里是训练分布的支撑集,且只是的一个子集。

 

然而由于种种因素的限制,神经网络一般难以学到完美符合要求的函数,而只能得出一个与存在差距的函数,从而我们定义外推误差如下:

 

不难看出,外推误差就是函数在训练分布 支撑集之外的误差上界 。

 

MLP

 

多层感知机是结构最简单的神经网络,也是众多复杂网络架构(例如GNN)的组成部分。

 

收敛至线性

 

作者发现,使用 ReLU激活函数 、 过参数化 的MLP在训练分布外,总是 沿着从原点出发的各个方向都收敛为线性函数 ,如下图所示。

图中灰色部分是MLP需要学习的非线性函数,蓝色部分是MLP在训练分布内学得的结果, 黑色部分 是MLP在训练分布外的表现 。

 

作者也从理论上给出了双层ReLU MLP收敛速率的证明,发现这种 收敛常常出现在靠近训练数据的位置 ,这表明 ReLU MLPs在大多数 非线性任务 上的外推能力都较弱 。

 

MLPs外推误差小的条件

 

同时作者也发现, 当目标函数为 线性函数 时,MLPs的外推表现较好 。然而MLPs能否成功地进行外推,还取决于训练数据的 几何形状 。如果训练分布的支撑集 包括了各个方向 (例如包含原点的超立方体), 则MLPs的外推误差较小 。这一条件听起来可能无法理解,不妨一睹作者给出的数学定义:

 

Suppose the target function isfor some. Suppose the training datais sampled from a distribution whose supportcontains subset, where for any non-zero, there existsso that.

 

即MLPs 外推误差小的条件是:训练数据是从支撑集中采样得到的,它包含一个子集,满足:对于任意的维向量,存在正数使得属于,我们不难发现,显然这个需要包含原点。

 

作者给出了MLP学习线性目标函数的示例(灰色部分是MLP需要学习的线性函数,蓝色部分是训练分布,黑色部分是MLP在训练分布外的表现):

由于图上已经说得比较清楚,笔者尝试换个角度给出说明:假定数据分布定义在一个矩形区域内(蓝色部分),左一的原点在矩形区域内,此时训练数据自然是包含从原点出发的各个方向的,可以看出这时MLP外推效果较好;左二的原点在矩形的边上,那幺从原点出发的红色箭头的反方向就没有训练数据,MLP外推开始出现了一些偏差;右二的原点在矩形的角上,MLP外推的偏差也较大;右一中,数据分布定义在一条经过原点的线上,使得训练分布之外的部分有明显的外推误差。

 

GNN

 

图神经网络在多项非线性算法任务上表现出不错的外推能力,例如图算法、符号数学等。作者基于前文关于MLP的结论,继续探究GNN的外推效果。

 

作者猜想,如果 编码适当的非线性至GNN的架构和输入表示中 ,让MLP组件仅学习线性函数, 那幺GNN就能在 动态规划 任务中顺利外推 ,获得较小的外推误差。

编码非线性至架构

 

以最短路问题为例,着名的的Bellman-Ford算法中的更新式如下:

 

而使用最小值聚合(min-aggregation)的GNN架构的节点表示如下:

 

不难发现以上两式十分相似。因此, 如果我们让GNN中的MLP模块学习线性函数,则GNN就可以模拟Bellman-Ford算法。由于我们已知MLP在线性任务上外推能力较强,因此使用最小值聚合的GNN也可以在这个最短路问题上具备较强的外推能力。

 

编码非线性至输入表示

 

对于某些任务,改变输入表示,会更容易达到好的外推能力。在这种情况下,我们可以将目标函数 分解 成 嵌入(Embedding) 和一个模型 外推效果较好的目标函数 ,使得,就可以有助于外推。

 

作者在动态规划中的多体问题上验证了这一观点(多体问题:预测多个物体在引力作用下随时间的演化情况)。作者对输入表示进行了转换,使得MLP只需学习线性函数。与转换前MLP需要学习非线性函数相比,平均绝对百分比误差(Mean Average Percentage Error)大大下降。

 

总结

 

本论文是麻省理工CSAIL实验室研究生Keyulu Xu继ICLR 2020论文 What can Neural Networks Reason About? 之后的又一力作。论文兼具严谨的理论推导及有力的实验验证,甚至有一位审稿人直言40页的附录太长没看。

作为一篇数理性较强的研究,它的行文也做到了较高的流畅性和易读性。适逢GNN大红大紫之时,作者高屋建瓴,对GNN的外推能力提出了新的观点,对社区做出了可观的贡献,确实令人钦佩。

 

最后,愿大家都能在学术领域中勇闯无人之境!

 

Boldly go where no one has gone before. ——《Star Trek》

 

后台回复关键词【 入群 】

 

加入卖萌屋NLP/IR/Rec与求职讨论群

 

后台回复关键词【 顶会 】

 

获取ACL、CIKM等各大顶会论文集!

 

 

[1]Support (mathematics): https://en.wikipedia.org/wiki/Support_(mathematics)

 

[2]Barnard E, Wessels L F A. Extrapolation and interpolation in neural network classifiers[J]. IEEE Control Systems Magazine, 1992, 12(5): 50-53.

 

[3]Haley P J, Soloway D. Extrapolation limitations of multilayer feedforward neural networks[C]

 

[4]Battaglia P, Pascanu R, Lai M, et al. Interaction networks for learning about objects, relations and physics[C]

 

[5]Veličković P, Ying R, Padovano M, et al. Neural Execution of Graph Algorithms[C]

 

[6] Lample G, Charton F. Deep Learning For Symbolic Mathematics[C]

 

[7]Zhang C, Bengio S, Hardt M, et al. Understanding deep learning requires rethinking generalization[J]. arXiv preprint arXiv:1611.03530, 2016.

Be First to Comment

发表评论

邮箱地址不会被公开。 必填项已用*标注