① 模型压缩:剪枝算法
过参数化主要是指在训练阶段,在数学上需要进行大量的微分求解,去捕抓数据中的微小变化信息,一旦完成迭代式的训练之后,网络模型推理的时候就不需要这么多参数。而剪枝算法正是基于过参数化的理论基础而提出的。
剪枝算法核心思想就是减少网络模型中参数量和计算量,同时尽量保证模型的性能不受影响。
那在AI框架中,实际上剪枝主要作用在右下角的端侧模型推理应用场景中,为的就是让端侧模型更小,无论是平板、手机、手表、耳机等小型IOT设备都可以轻松使用AI模型。而实际在训练过程更多体现在剪枝算法和框架提供的剪枝API上面。
实际上大部分刚接触剪枝算法的时候,都会从从宏观层面去划分剪枝技术,主要是分为Drop Out和Drop Connect两种经典的剪枝算法,如下图所示。
1)Drop Out:随机的将一些神经元的输出置零,称之为神经元剪枝。
2)Drop Connect:随机将部分神经元间的连接Connect置零,使得权重连接矩阵变得稀疏。
下面会把剪枝的更多种方式呈现出来,可能会稍微复杂哈。从剪枝的粒度来划分,可以分为结构化剪枝和非结构化剪枝,2个剪枝结构方法。下面来看看具体的剪枝方法有4种:
细粒度剪枝、向量剪枝、核剪枝在参数量与模型性能之间取得了一定的平衡,但是网络模型单层的神经元之间的组合结构发生了变化,需要专门的算法或者硬件结构来支持稀疏的运算,这种叫做 结构化剪枝(Unstructured Pruning) 。
其中,非结构化剪枝能够实现更高的压缩率,同时保持较高的模型性能,然而会带来网络模型稀疏化,其稀疏结构对于硬件加速计算并不友好,除非底层硬件和计算加速库对稀疏计算有比较好的支持,否则剪枝后很难获得实质的性能提升。
滤波器剪枝(Filter-level)主要改变网络中的滤波器组和特征通道数目,所获得的模型不需要专门的算法和硬件就能够运行,被称为 结构化剪枝(Structured Pruning) 。结构化剪枝又可进一步细分:可以是channel-wise,也可以是filter-wise,还可以是在shape-wise。
结构化剪枝与非结构化剪枝恰恰相反,可以方便改变网络模型的结构特征,从而达到压缩模型的效果,例如知识蒸馏中的student网络模型、NAS搜索或者如VGG19和VGG16这种裁剪模型,也可以看做变相的结构化剪枝行为。
虽然剪枝算法的分类看上去很多,但是核心思想还是对神经网络模型进行剪枝,目前剪枝算法的总体流程大同小异,可以归结为三种:标准剪枝、基于子模型采样的剪枝、以及基于搜索的剪枝,如下图所示。
标准剪枝是目前最流行的剪枝流程,在Tensorflow、Pytroch都有标准的接口。主要包含三个部分:训练、剪枝、以及微调。
1) 训练 :首先是对网络模型进行训练。在剪枝流程中,训练部分主要指预训练,训练的目的是为剪枝算法获得在特定基础SOTA任务上训练好的原始模型。
3) 微调 :微调是恢复被剪枝操作影响的模型表达能力的必要步骤。结构化模型剪枝会对原始模型结构进行调整,因此剪枝后的模型参数虽然保留了原始的模型参数,但是由于模型结构的改变,剪枝后模型的表达能力会受到一定程度的影响。实现上,微调网络模型,参数在计算的时候先乘以该Mask,Mask为1的参数值将继续训练通过BP调整梯度,而Mask为0的部分因为输出始终为0则不对后续部分产生影响。
4) 再剪枝 :再剪枝过程将微调之后的网络模型再送到剪枝模块中,再次进行模型结构评估和执行剪枝算法。目的是使得每次剪枝都在性能更优的模型上面进行,不断迭代式地进行优化剪枝模型,直到模型能够满足剪枝目标需求。
最后输出模型参数储存的时候,因为有大量的稀疏,所以可以重新定义储存的数据结构, 仅储存非零值以及其矩阵位置。重新读取模型参数的时候,就可以还原矩阵。
除标准剪枝之外,基于子模型采样的剪枝《EagleEye: Fast sub-net evaluation for efficient neural network pruning》最近也表现出比较好的剪枝效果。得到训练好的模型之后,进行子模型采样过程。一次子模型采样过程为:
1)对训练好的原模型中可修剪的网络结构,按照剪枝目标进行采样,采样过程可以是随机的,也可以按照网络结构的重要性或者通过KL散度计算进行概率采样。
2)对采样后的网络结构进行剪枝,得到采样子模型。子模型采样过程通常进行 次,得到 个子模型( ≥1), 之后对每一个子模型进行性能评估。子模型评估结束之后,选取最优的子模型进行微调以得倒最后的剪枝模型。
基于搜索的剪枝主要依靠强化学习等一系列无监督学习或者半监督学习算法,也可以是神经网络结构搜索相关理论。
给定剪枝目标之后,基于搜索的剪枝在网络结构中搜索较优的子结构,这个搜索过程往往伴随着网络参数的学习过程,因此一些基于搜索的剪枝算法在剪枝结束后不需要再进行微调。
这几年神经网络剪枝pruning作为模型压缩技术的四小龙之一,正在受到越来越多的关注。当然,各种更好的pruning参数选取方法一定还会层出不穷。另外,从趋势来看,以下几个方向值得关注:
打破固定假设 :挑战已有的固有的假设,例如ICLR2019会议的best paper彩票假说《The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks 》的出现。还有一开始提到的对于over-parameterization,与重用已有参数是否有有益的反思非常有意思。这样的工作会给剪枝算法非常大的启发,从而根本改变解决问题的思路。
自动化剪枝 :随着AutoML的大潮,越来越多的算法开始走向自动化。模型压缩能拉下吗?当然不能。经过前面的介绍我们知道,像ADC,RNP,N2N Learning这些工作都是试图将剪枝中部分工作自动化。如量化中的《HAQ: Hardware-Aware Automated Quantization》考虑网络中不同层信息的冗余程度不一样,所以自动化使用混合量化比特进行压缩。
与NAS融合 :如前面模型剪枝流程中提到,剪枝算法与神经网络搜索NAS的界限已经模糊了。NAS有针对结构化剪枝进行搜索方法,如One-Shot Architecture Search是先有一个大网络,然后做减法。NAS与模型压缩两个一开始看似关系不是那么大的分支,在近几年的发展过程中因为下游任务和部署场景的需求,最后似乎会走到一块去。这两个分支今天有了更多的交集,也必将擦出更多的火花。
与GAN融合 :这几年机器学习最火热的分支之一GAN,正在不断渗透到已有领域,在pruning中也开始有它的身影。如2019年《Towards Optimal Structured CNN Pruning via Generative Adversarial Learning》让generator生成裁剪后网络,discrimintor来判别是否属于原网络还是裁剪后网络,从而进行更有效的网络结构化裁剪。
硬件稀疏性支持 :剪枝会给神经网络模型带来稀疏性特征,参数稀疏性在计算中会有大量的索引,所以并不能加速。现在虽然有像cuSPARSE这样的计算库,但底层硬件AI芯片本身设计并不是专门为稀疏数据处理打造的。如果能将稀疏计算和处理能力做进芯片那必将极大提高计算效率。仅2021年中国就推出了10+款基于ASIC的AI加速芯片,相信针对稀疏性场景的支持在未来会有所突破。
模型压缩算法中针对已有的模型,有:张量分解,模型剪枝,模型量化。针对新构建的网络,有:知识蒸馏,紧凑网络设计等方法。
剪枝只是模型压缩方法中的一种,它与其它模型压缩方法并不冲突,因此会与量化、蒸馏、NAS、强化学习等方法慢慢融合,这些都是很值得研究的方向。另外在上面的发展来看,打破固有的假设定义,与NAS、GAN、AutoML、RL等技术进行相互的融合,可能到最后会模糊purning方式,出现新的范式或者压缩模式也是很吸引的。
② 知识蒸馏综述:网络结构搜索应用
【GiantPandaCV导语】知识蒸馏将教师网络中的知识迁移到学生网络,而NAS中天然的存在大量的网络,使用KD有助于提升超网整体性能。两者结合出现了许多工作,本文收集了部分代表性工作,并进行总结。
知识蒸馏可以看做教师网络通过提供soft label的方式将知识传递到学生网络中,可以被视为一种更高级的label smooth方法。soft label与hard label相比具有以下优点:
那么知识蒸馏在网络结构搜索中有什么作用呢?总结如下:
知识蒸馏在很多工作中作为训练技巧来使用,比如OFA中使用渐进收缩训练策略,使用最大的网络指导小网络的学习,采用inplace distillation进行蒸馏。BigNAS中则使用三明治法则,让最大的网络指导剩下网络的蒸馏。
目标:解决教师网络和学生网络的匹配问题(知识蒸馏中教师网络和学生网络匹配的情况下效果更好)。
在知识蒸馏中,选择不同的教师网络、不同的学生网络的情况下,最终学生网络的性能千差万别。如果学生网络和教师网络的容量相差过多,会导致学生难以学习的情况。Cream这篇文章就是为了解决两者匹配问题。
普通的SPOS方法如左图所示,通过采样单路径子网络进行训练。右图则是结合了知识蒸馏的方法,Cream提出了两个模块:
Cream中心思想是,子网络可以在整个训练过程中协作学习并相互教导,目的是提高单个模型的收敛性。
消融实验如下:
目标:通过教师引导各个block特征层的学习,根据loss大小评判各子网的性能。
这是一篇将NAS和KD融合的非常深的一个工作,被CVPR20接收。之前写过一篇文章进行讲解,这里简单回顾一下。
DNA是两阶段的one-shot NAS方法,因此其引入蒸馏也是为了取代普通的acc指标,提出了使用子网络与教师网络接近程度作为衡量子网性能的指标。
在训练的过程中,进行了分块蒸馏,学生网络某一层的输入来自教师网络上一层的输出,并强制学生网络这一层的输出与教师网络输出一致(使用MSELoss)。在搜索过程结束后,通过计算各子网络与教师网络的接近程度来衡量子网络。
目标:通过改进KL divergence防止学生over estimate或者under estimate教师网络。
上图展示了OFA,BigNAS等搜索算法中常用到的蒸馏方法,子网使用的是KL divergence进行衡量,文中分析了KL 散度存在的局限性:即避零性以及零强制性。如下公式所示,p是教师的逻辑层输出,q是学生逻辑层输出。
AlphaNet提出了一个新的散度衡量损失函数,防止出现过估计或者低估的问题。如下所示,引入了 。
其中 不为0或者1,这样如下图所示:
蓝色线对应example 2表示,当 为负值,如果q过估计了p中的不确定性, 的值会变大。
紫色线对应example 1表示,当 为正数,如果q低估了p中的不确定性, 的值会变大
同时考虑两种情况,取两者中最大值作为散度:
目标:提出了衡量学生网络和教师网络 内部激活相似度 衡量指标,通过表征匹配可以用来加速网络结构搜索。
这部分其实是属于知识蒸馏分类中基于关系的知识,构建的知识由不同样本之间的互作用构成。
具体的指标构成如上图所示,是一个bsxbs大小的矩阵,这个在文中被称为Representational Dissmilarity Matrix,其功能是构建了激活层内部的表征,可以通过评估RDM的相似度通过计算上三角矩阵的关系系数,比如皮尔逊系数。
该文章实际上也是构建了一个指标P+TG来衡量子网的性能,挑选出最优子网络。
如上图所示,RDM的计算是通过衡量教师网络的feature以及学生网络的feature的相似度,并选择选取其中最高的RDM相似度。通过构建了一组指标,随着epoch的进行,排序一致性很快就可以提高。
目标:固定教师网络,搜索最合适的学生网络。
对于相同的教师网络来说,不同的架构的学生网络,即便具有相同的flops或者参数,其泛化能力也有所区别。在这个工作中选择固定教师网络,通过网络搜索的方法找到最优的学生网络,使用L1 Norm优化基础上,选择出与教师网络KL散度差距最小的学生网络。
目标:在给定教师网络情况下,搜索最合适的学生网络。
神经网络中的知识不仅蕴含于参数,还受到网络结构影响。KD普遍方法是将教师网络知识提炼到学生网络中,本文提出了一种架构感知的知识蒸馏方法Architecture-Aware KD (AKD),能够找到最合适提炼给特定教师模型的学生网络。
Motivation: 先做了一组实验,发现不同的教师网络会倾向于不同的学生网络,因此在NAS中,使用不同的教师网络会导致模型倾向于选择不同的网络结构。
AKD做法是选择使用强化学习的方法指导搜索过程, 使用的是ENAS那种通过RNN采样的方法。
目标:从集成的教师网络中学习,并使用NAS调整学生网络模型的容量。NAS+KD+集成。
这篇文章之前也进行了讲解,是网络结构搜索,知识蒸馏,模型集成的大杂烩。
详见: https://blog.csdn.net/DD_PP_JJ/article/details/121268840
这篇文章比较有意思,使用上一步中得到的多个子网络进行集成,可以得到教师网络,然后使用知识蒸馏的方法来引导新的子网络的学习。关注重点在于:
AdaNAS受Born Again Network(BAN)启发, 提出Adaptive Knowledge Distillation(AKD)的方法以辅助子网络的训练。
集成模型选择 :
从左到右代表四次迭代,每个迭代中从搜索空间中选择三个模型。绿色线框出的模型代表每个迭代中最优的模型,AdaNAS选择将每个迭代中最优subnet作为集成的对象。
最终集成的时候还添加了额外的weight参数w1-w4:
最终输出逻辑层如下所示:(这个w权重也会被训练,此时各个集成网络的权重是固定的,只优化w)
Knowledge Distillation
目标:解决知识蒸馏的效率和有效性,通过使用特征聚合来引导教师网络与学生网络的学习,网络结构搜索则是体现在特征聚合的过程,使用了类似darts的方法进行自适应调整放缩系数。ECCV20
文章总结了几种蒸馏范式:
最后一种是本文提出的方法,普通的特征蒸馏都是每个block的最后feature map进行互相蒸馏,本文认为可以让教师网络的整个block都引导学生网络。
具体如何将教师网络整个block中所有feature map进行聚合,本文使用的是darts的方法进行动态聚合信息。(a) 图展示的是对group i进行的可微分搜索过程。(b)表示从教师到学生的路径loss构建,使用的是CE loss。(c)表示从学生到教师网络的路径loss构建,使用的是L2 Loss。其中connector实际上是一个1x1 卷积层。
(ps: connector让人想到VID这个工作)
③ 神经网络算法的局限性
神经网络算法的局限性是:可以使用均值函数但是这个函数将获取嵌入的平均值,并将其分配为新的嵌入。但是,很容易看出,对于某些不同的图,它们会给出相同的嵌入,所以,均值函数并不是单射的。
即使图不同,节点 v 和 v’ 的平均嵌入聚合(此处嵌入对应于不同的颜色)将给出相同的嵌入。
这里真正重要的是,你可以先用某个函数 f(x) 将每个嵌入映射到一个新的嵌入,然后进行求和,得到一个单射函数。在证明中,它们实际上显式地声明了这个函数 f,这需要两个额外条件,即 X 是可数的,且任何多重集都是有界的。
并且事实上,在训练中并没有任何东西可以保证这种单射性,而且可能还会有一些图是 GIN 无法区分的,但WL可以。所以这是对 GIN 的一个很强的假设,如果违反了这一假设,那么 GIN 的性能将受到限制。
神经网络算法的普适性是:
研究模型的局限性通常更容易获得对模型的洞察。毕竟,网络所不能学到的关于特定特征的知识在应用时独立于训练过程。
此外,通过帮助我们理解与模型相关的任务的难度,不可能性结果(impossibility result)有助于得出关于如何选择模型超参数的实用建议。
以图分类问题为例。训练一个图分类器需要识别是什么构成了一个类,即在同一个类而非其他类中找到图共享的属性,然后决定新的图是否遵守所学习到的属性。
然而,如果可以通过一定深度的图神经网络(且测试集足够多样化)证明上述决策问题是不可能的,那么我们可以确定,同一个网络将不会学习如何正确地对测试集进行分类,这与使用了什么学习算法无关。因此,在进行实验时,我们应该把重点放在比下限更深的网络上。
④ 超大规模图神经网络系统真的可以实现赋予机器常识吗
机器学习是人工智能的一个分支。
人工智能的研究历史有着一条从以“推理”为重点,到以“知识”为重点,再到以“学习”为重点的自然、清晰的脉络。
机器学习是实现人工智能的一个途径,即以机器学习为手段解决人工智能中的问题。
随着越来越多的这类技术变得成熟,机器将会在各种各样的任务上超越人类。
那么,机器是否可以理解自己呢?甚至机器是否可以设计和编码自己本身呢?
可以想象一下,一旦机器做到这一步,那将会带来什么样的颠覆。
Google Brain团队在探索这个领域,他们称之为“自动机器学习”方向。
顶尖的人工智能专家们发现,设计机器学习系统本身这样一个他们最困难的工作之一,也有可能通过AI系统自动完成。
甚至在一些场景下,AI系统自己开发的AI系统已经赶上甚至超过了人类专家。
国外著名科技记者 Steven Levy 在他刊于 BackChannel 的文章《谷歌如何将自己重塑为一家“机器学习为先”的公司》中提到,谷歌大脑负责人 Jeff Dean 表示,如果现在让他改写谷歌的基础设施,大部分代码都不会由人编码,而将由机器学习自动生成。
学术界也有相关研究,伯克利的 Ke Li 和 Jitendra Malik 在他们日前提交的论文《Learning to Optimize》中提出了让算法自我优化的方法。
他们在论文摘要中写道,“算法设计是一个费力的过程,通常需要许多迭代的思想和验证。 在本文中,我们探讨自动化算法设计,并提出了一种方法学习自动优化算法”。
从强化学习的角度入手,Ke Li 和 Jitendra Malik 使用指导性策略搜索来让 AI 学习优化算法,并且证明了他们所设计的算法在收敛速度和/或最终目标值方面优于现有的手工编程开发的算法。
⑤ 图神经网络是什么
图神经网络是一种直接作用于图结构上的神经网络。GNN的一个典型应用是节点分类。本质上,图中的每个节点都与一个标签相关联,我们希望预测未标记节点的标签。
⑥ 为什么有图卷积神经网络
本质上说,世界上所有的数据都是拓扑结构,也就是网络结构,如果能够把这些网络数据真正的收集、融合起来,这确实是实现了AI智能的第一步。所以,如何利用深度学习处理这些复杂的拓扑数据,如何开创新的处理图数据以及知识图谱的智能算法是AI的一个重要方向。
深度学习在多个领域的成功主要归功于计算资源的快速发展(如 GPU)、大量训练数据的收集,还有深度学习从欧几里得数据(如图像、文本和视频)中提取潜在表征的有效性。但是,尽管深度学习已经在欧几里得数据中取得了很大的成功,但从非欧几里得域生成的数据已经取得更广泛的应用,它们需要有效分析。如在电子商务领域,一个基于图的学习系统能够利用用户和产品之间的交互以实现高度精准的推荐。在化学领域,分子被建模为图,新药研发需要测定其生物活性。在论文引用网络中,论文之间通过引用关系互相连接,需要将它们分成不同的类别。自2012年以来,深度学习在计算机视觉以及自然语言处理两个领域取得了巨大的成功。假设有一张图,要做分类,传统方法需要手动提取一些特征,比如纹理,颜色,或者一些更高级的特征。然后再把这些特征放到像随机森林等分类器,给到一个输出标签,告诉它是哪个类别。而深度学习是输入一张图,经过神经网络,直接输出一个标签。特征提取和分类一步到位,避免了手工提取特征或者人工规则,从原始数据中自动化地去提取特征,是一种端到端(end-to-end)的学习。相较于传统的方法,深度学习能够学习到更高效的特征与模式。
图数据的复杂性对现有机器学习算法提出了重大挑战,因为图数据是不规则的。每张图大小不同、节点无序,一张图中的每个节点都有不同数目的邻近节点,使得一些在图像中容易计算的重要运算(如卷积)不能再直接应用于图。此外,现有机器学习算法的核心假设是实例彼此独立。然而,图数据中的每个实例都与周围的其它实例相关,含有一些复杂的连接信息,用于捕获数据之间的依赖关系,包括引用、朋友关系和相互作用。
最近,越来越多的研究开始将深度学习方法应用到图数据领域。受到深度学习领域进展的驱动,研究人员在设计图神经网络的架构时借鉴了卷积网络、循环网络和深度自编码器的思想。为了应对图数据的复杂性,重要运算的泛化和定义在过去几年中迅速发展。
⑦ 图神经网络是怎么炼成的:GNN基本原理简介
此文算是对Google Research这篇 A Gentle Introction to Graph Neural Networks 神作的阅读笔记.
十多年来,研究人员开发了一种称之为图神经网络(Graph Neural Networks,GNNs)的技术,旨在将如今在深度学习的诸多任务中摧枯拉朽的神经网络,应用到图结构之上,从而让神经网络捕捉到更错综复杂的交叉特征,以期待在一些任务上取得更佳的效果。鉴于操作图数据结构的复杂性,尽管已经发展了十几年,它在实际应用中却刚刚起步,即时是google也才开始研究将其被应用到药品研发、物理模拟、假新闻检测、交通预测和推荐系统等领域。
尽管GNN是一个新兴的研究领域,但图结构的数据其实在我们身边无处不在。那么什么是图呢?
这个理科生应该都清楚,图有点(Vertex)和边(Edge)两部分组成,一个图就代表了各个实体节点(node)之间的关系(edge):
每个节点或者边都可以包含它的一些属性信息,比如如果一个节点表示一个人,那么就可以包含这个人的姓名、性别、身高、体重之类的..我们研究需要的信息。
而这些信息,都可以用通用的向量的形式存入其中:
还有别忘了一点,边是可以有方向的,按此我们还能分为有向图或是无向图。边的方向代表了信息的传递方向,例如a是b的微信好友,那b也是a的微信好友,好友关系自然是没方向的,而比如a是b的爹,那显然b就不是a的爹,此时叫爹的关系就是有有方向的。
图结构的构建是非常灵活的,可以根据个人的设计构建出各种不一样的图。而作为开发者显然要结合实际解决的问题来构建合适的图。
正如前面所提到的,图无处不在。你可能已经熟悉例如知识图谱、社交网络之类的图数据。当时显然,图是一种极其强大的通用数据表示,传统神经网络中用到的欧式空间的数据,同样可以用图来表示,例如可以将图像和文本建模为图结构数据。
比如,我们可以将一张图片的每个像素作为图的节点,再将相邻的像素用边连接起来,就构造了一个该图像的图。
如上图展示了一个5*5的图片的邻接矩阵表示和图表示。
我们将每个单词作为节点,并将每个节点连接到下一个节点,就得到了一个文本的图:
当然,在实践中我们并不会这样来编码文本和图像,因为所有的图和文本都是非常规则的结构,表示成图就多此一举了。
我们再来看一些例子,这些数据的结构更加复杂,除了图之外很难用其他方式来表达。
分子是构成物质的基石,我们可以用节点来表示它的原子和电子,用边来表示共价键,这样便将一个分子表示成了一个图:
不同的图可以表示出不同的分子结构:
都说社会是一个大熔炉,身处其中的人和事物之间会发生极其复杂的关系。这种关系的表示用普通的表格数据是很难表示的,而图却能很好的展现。
下图是将莎士比亚歌剧《奥赛罗》中的任务关系表示成图:
怎么样,如果没看过歌剧能推测出那些是主角吗?
下面是将一个空手道竞标赛的对战关系构建为图:
类似的可以表示为图的数据还有很多很多,比如论文的引用之类统统都可以表示为图,下面是现实世界中不同规模的数据图表示的统计数据:
可见,各种各样规模的数据都可以轻松的用图来表示。
在上面我们列举了这么多的图,那么我们该对这些图数据执行什么任务呢?
图上的预测任务一般分为三类:
下面我们通过具体的示例来说明GNN怎么来解决上述的三个级别的预测问题。
在图级别的任务中,我们的目标是预测整个图的属性。例如我们通过分子图,来预测该分子的气味或是者它是否是与某些疾病有关的受体。
它的输入是完整的图:
输出是图的分类:
节点级任务一般就是预测每个节点的类型。
一个经典的例子就是Zach的空手道俱乐部。该数据集市一个单一的社交网络图,犹豫政治分歧,讲师Hi先生和管理员John之间不和导致空手道俱乐部分裂,其中的学员一部分效忠于Hi先生,一部分效忠于John。每个节点代表空手道联系着,边代表空手道之外这些成员的互动,预测问题就是判断这些节点是效忠于谁的。
边级任务其实就是预测每个边的属性.
在目标检测的语义分割任务中,我们也许不止要识别每个目标的类型,还需要预测各个目标之间的关系.我们可以将其描述为边级别的分类任务:给定表示图像中的对象的节点,我们希望预测哪些节点共享一条边,或者该边的值是多少。如果我们希望发现实体之间的连接,我们可以考虑图是完全连通的,并根据它们的预测值修剪边来得到一个稀疏图。
用图表示就是这样的过程:
那么我们要如何使用神经网络来处理上述各种类型的任务呢?
首先要考虑的是如何将图结构数据适配到神经网络.
回想一下啊,传统的神经网络输入的往往是矩阵形式的数据,那么要如何把图作为输入呢?
图表示有四种类型的信息:节点(nodes),边(edges),全局上下文(global-context),联通性(connectivity).对于前三种信息,有一个非常简单的方案,比如将节点排序,然后每个节点表示为一个向量,所有节点就得到了一个节点的矩阵,同理,边和上下文也可以这么搞.
但是要标识连通性就没有这么简单了,也许你会想到用临街矩阵来表示,但是这样表示会有明显的缺陷,因为节点数的规模往往是巨大的,对于一个数百万节点的图,那将耗费大量的空间,而且得到的矩阵往往也十分的稀疏,可以说空间利用率会很低.
当然,你也许会想,可以用稀疏矩阵来存储,这样就只需要存储连通的情况,空间利用率将大大提升,但是我们还要考虑到一点,就是稀疏矩阵的高性能计算一直是个艰难的,尤其是在用到GPU的情况.
并且,使用邻接矩阵还有一个问题就是各种不同的邻接矩阵可以标识相同的连通性,而这些矩阵并不能保证在神经网络中取的相同的效果.比如,同样的连通性,通过调换列的顺序,就能得到不同的邻接矩阵:
现在,我们成功的将图结构成功表示成了置换不变的矩阵格式,终于可以使用图形神经网络(GNN)来做图形预测任务了。
GNN是对保持图对称性(置换不变性)的图的所有属性(节点、边、全局上下文)的可优化变换。
我们将使用Gilmer等人提出的“消息传递神经网络”框架构建GNN,并使用Battaglia等人介绍的图网络网络架构示意图。GNNS采用“图输入,图输出”架构,这意味着这些模型类型接受图作为输入,其中包含节点,边和全局上下文的信息,并逐步地转换这些图嵌入,而不会更改输入的连接图结构。
我们使用最开始提到的那个图来构建一个最简单的GNN,输入的图是相应节点,边,全局信息的向量,我们针对每个向量使用一个MLP层来作变换,于是得到一个新的图.
针对上述构建的最简单的GNN,我们如何在上面描述的任何任务中进行预测呢?这里我们仅仅考虑二进制分类的情况,但这个框架可以很容易地扩展到多类或回归的情况。
如果是对节点分类,我们只要在最后一层接一个线性类器就可以了:
但是上面的预测过程有点过于简单了,完全没有用到图的结构信息,我们在此基础上增加一个pooling操作,以增加它的边缘信息:
具体操作是把待预测节点的邻居节点以及全局的信息进行聚合再做预测,即将这些embedding向量加到一起得到一个新的向量,再输入到最后的线性分类器.
同理,如果我们只有节点相应边的信息的话,也可以用类似的方式pooling,然后得到节点的向量表示再输入分类器:
反之,如果我们只有节点的信息,那么也可以用边所连接的两个节点来pooling出边的向量,然后将器输入到分类器预测边的类型:
显然,不管是哪种任务,整个GNN的推理过程都是一样的,可以表示为这样一个端到端的过程:
不过,显而易见的,这个简单的GNN在分类前只是对每个向量进行了一个变换,而没有用到图结构的任何信息,虽然在最后做预测的时候做了一些pooling的聚合,但也始终没有用到adjacency的信息,因此这个GNN的作用相当有限,但是它为我们提供了一个图结构层变换和堆叠的基本思路.
针对上面最简单GNN的不足,我们可以在其中根据连通性增加更加复杂的变换从而引入整个图结构的信息,我们将这个过程称之为信息传递.
信息传递包含三个步骤:
这个过程有点类似于卷积操作,每个节点汇聚了其邻居的节点,经过多个层的变换,它将涵盖全图的信息.
于是我们可以将这个节点信息传递应用到上述的图变换过程中:
然后,我们发现它并没用用上边的信息,于是可以把边信息也加上,变成这样:
既然把边的信息加上了,那怎么可以漏掉全局信息呢,于是完整的信息传递就可以表示成这样:
以上,我们梳理了最简单的GNNs是怎么完成的,你应该已经对GNN有了一个基本的了解,就像学会了传统神经网络中最简单的全连接网络类似,关于GNN还有更多不同种类的更复杂的图需要取了解和学习,但你只要掌握了以上的思想,学习起来也是十分容易的.