Rasmus Berg Palm、Ulrich Paquet、Ole Winther作者李诗萌、王淑婷编译arXiv选自

如何用循环关系网络机智地解决数独类关系推理任务?


本文引入循环关系网络来解决步骤相互依赖的关系推理任务,举个栗子,数独任务。以往的传统深度学习方法虽然也能解决,却总是会出现一些问题。本文提出的 RNN 模型解决了 96.6% 的最难数独,而且与其它方法相比结果最佳。

人类智能的核心组成部分是对目标及其相互作用进行抽象推理的能力 [Spelke 等人,1995,Spelke 和 Kinzler,2007]。举个例子,假设要解数独问题。数独盘面中有 81 个格,按 9*9 的方式排列,要用数字 1~9 填满这些格子,每个数字在每行、每列以及每一个 3*3 的非重叠格中都只能出现一次,有些数字已经给定为 1。要解数独,就得用方法推理出盘面上的格子以及它们在许多步骤中的相互作用关系。有人试着将数字放进格子中,并观察它会对其它格子产生怎样的影响,迭代地解决这一问题。

将这种方式与传统的深度学习方法(如多层感知(MLP)或多层卷积神经网络(CNN))进行对比来解决问题。上述架构将整个数独盘作为输入,在一次正向传递过程中输出了完整的解决方案,但在这个过程中它们忽视了目标之间存在的归纳偏置,以及它们是以一致的方式互相作用的。当面对需要推理基本关系的问题时,这些模型会出现问题也就不足为奇了 [Lake 等人,2016,Santoro 等人,2017]。

Santoro 等人的关系网络 [2017] 是用简单模块推理目标及其相互作用的重要第一步,但它的局限性在于只能进行单个关系运算,而在数据集上评估时最多需要三个推理步骤(令人惊讶的是,如文中所示,这一问题可通过单个关系推理步骤解决)。除了关系网络,在人工智能机器学习领域还有关于逻辑和推理方面的文献,我们将在第 5 节中讨论。

为了实现在多个步骤中有条理地推理目标及其相互作用的能力,本文引入了一个复合函数,循环关系网络。它是端到端可微分学习系统中多步关系推理的模块化组件。它将归纳偏置编码为:1)存在于这个世界的目标;2)可以通过属性充分描述;3)属性可以随时间的变化而改变;4)目标之间会互相影响;5)在给定属性的情况下,目标对彼此的影响不变。

从 Santoro 等人 [2017] 的研究中得出的重要见解是将关系推理函数分解成两个组件或「模块」:一个感知前端(其任务是识别原始输入中的目标,并将其表示为向量)和一个关系推理模块(使用这些表征来推理目标及其相互作用)。这两个模块都是用端到端的方法联合训练的。用计算机科学中的术语来说,关系推理模块实现了一个接口:它在有向边和节点的图上进行操作,其中节点由实值向量表示,并且是可微分的。本文主要开发该接口的关系推理方面。

我们评估的一些任务也可以通过在符号级别上操作的手工算法高效、完美地解决。例如,可以用约束传播和搜索 [Norvig,2006] 或舞蹈链 [Kuth,2000] 的方法在零点几秒内解决 9*9 的数独问题。从各个方面看这些符号算法都很优越,只有一点除外:它们不符合接口,因为它们不可微也不适用于实值向量描述。因此它们不能用于具有深度学习感知前端和端到端学习的组合模型中。

继 Santoro 等人 [2017] 后,我们用「关系推理」一词来表示以目标和交互为中心的问题解决方法。尽管「关系推理」与「关系逻辑」或「一阶逻辑」这种其他科学分支的术语相似,但这并不意味着直接的并行。

本文认为多步关系推理是深度学习架构中一项极具挑战的任务。我们开发了循环关系推理模块,它即这篇文章的主要贡献。我们在三个不同的数据集上进行多步关系推理,证实了这是一个强大的架构,它在 bAbI 和数独游戏上都实现了当前最佳的结果。

论文:Recurrent Relational Networks

论文链接:https://arxiv.org/pdf/1711.08028.pdf

摘要:本文关注的是学习解决需要一系列相互依赖步骤的关系推理任务,比如回答关于目标之间关系的复杂问题,或者是解决在解决方案中小元素相互约束的问题。我们引入了循环关系网络,这是一个在目标的图表征上运行的通用模块。正如 Santoro 等人 [2017] 所做的关于关系网络的概括,该网络可以增强任何能够进行多步关系推理的神经网络模型。我们用循环关系网络在 bAbI 文本问答数据集上实现了当前最佳结果,连续解决了 20/20 的任务。从关系推理的角度看,bAbI 并不是特别具有挑战性,因此我们引入了 Pretty-CLEVR 数据集,这是一个用于关系推理的新诊断数据集。在 Pretty-CLEVR 的建立过程中,我们可以通过改变问题来控制获得答案所需的关系推理步骤数量。最后,我们展示了循环关系网络是如何从监督训练数据中学会解决数独问题的,这是一项极具挑战的任务,需要 64 个以上的关系推理步骤。我们解决了 96.6% 最难的数独问题,而在所有可比较的方法中该方法实现了当前最佳的结果。

循环关系网络

我们以解决数独问题这种大家都很熟悉的事物为例来讨论循环关系网络。有一个简单的策略,如果在某个数独格子里填了「7」,那么在同一行、同一列以及对应的 3*3 格子中就可以安全地删去「7」这个选项。在信息传递框架中,这个格子需要向同一行、同一列以及对应 3*3 格子中的其它格子传递信息,告诉它们它的值是「7」,不要再接受「7」了。在一个迭代 t 中,这些信息是同时、并行地在所有格子之间发送的。然后每一个格子 i 就要思考所有的输入信息,并将其内部状态  更新为  i。更新状态后每一个格子都要向外发送新的信息,然后重复这个过程。

在图上传递信息:循环关系网络要学习在图上传递信息。就数独游戏而言,图有 i ∈ {1, 2, ..., 81} 个节点,每个节点表示数独盘中的一个格子。每个节点都有一个输入特征向量  和与数独盘中同一行、同一列以及同一 3*3 格子中所有节点相连的边。图是关系推理模块的输入,向量  一般是感知前端的输出,例如卷积神经网络。继续以数独游戏为例,每一个  都对初始的格子内容(空的或给定数字)以及格子中行和列的位置进行了编码。

在每个步骤 t 中,每个节点都有隐藏状态向量 ,将这个向量初始化为特征,使 。在每一步 t 中,每个节点会给它的相邻节点发送信息。我们通过以下方式定义在第 t 步时从节点 i 发送到节点 j 的信息 

其中信息函数 f 是多层感知机,它使得网络能够了解要发送的信息类型,我们在实验中使用了具有线性输出的 MLP。由于节点要考虑所有输入的信息,我们用以下方式对其进行求和:

式中 N(j)是所有和节点 j 相连的节点。就数独游戏而言,N(j)包含所有与 j 相同的行、列、3*3 格子的节点。在我们的实验中,因为在(1)中的信息是线性的,这有点类似于信念传播中如何对对数几率求和 [Murphy 等人,1999]。

循环节点更新:最后我们要通过以下方式更新节点隐藏状态,

式中的节点函数 g 是另一个学习过的神经网络。对先前节点隐藏状态  的依赖使得网络能够迭代地寻找解决方案,而不是每一步都从头开始。像这样在每一步都输入特征向量 ,就能将节点函数的注意力集中于来自其它节点的信息,而不是试图记住输入。

监督训练:上述用于发送信息和更新节点状态的等式定义了循环关系网络的核心。为了以有监督的方式训练一个求解数独的循环关系网络,我们在图中每个节点的数字 1~9 上引入了输出概率分布。节点 i 在第 t 步的输出概率  由下式给出:

式中 r 是将节点隐藏状态映射到输出概率的 MLP,例如用 softmax 非线性。在给定目标数字 y = {y_1, y_2, ..., y_81} 的情况下,第 t 步的损失是交叉熵项的和,每个节点的交叉熵项如下:,式中 是 o_i 的第 y_i 个组件。等式(1)到(4)在图 1 中阐释。

图 1:在全连接图上有 3 个节点的循环关系网络。绿色高亮表示的是节点的隐藏状态  ,红色高亮表示的是输入 ,蓝色高亮表示的是输出 。虚线表示循环连接。下标表示节点索引,上标表示 t 步。通过两步展开的同一图形请参阅补充材料。

收敛性信息的传递:本文提出模型的显著特征是我们在每一步都最小化了输出和目标分布之间的交叉熵

测试时我们只考虑了最后一步的输出概率,但训练时每一步都有损失是有益的。因为目标数字 y_i 是在步骤上是恒定的,所以它鼓励网络学习收敛信息传递算法。其次,它有助于解决梯度消失问题

Variation:如果边是未知的,可以将图视为全连接的。在这种情况中,网络需要学习哪些目标是彼此相互作用的。如果边有属性 ,等式 1 中的信息函数可以修改为

。如果想要整个图而不是每个节点的输出,可以将等式 4 中的输出修改为单个输出,即。也可以根据需要相应地修改损失。

实验

表 1:bAbI 的结果。用 10,000 个训练样本在所有 20 个任务上进行联合训练。用星号标记的条目是我们自己的实验,其它结果都来自于各自的论文。

图 2:2(a)是 Pretty-CLEVR 诊断数据集中的两个样本。每个样本都有 128 个相关问题,这表现出了不同等级的关系推理难度。对于最顶层的样本,用箭头表示的问题的解决方案是:「绿色,跳 3 次」,也就是「加号」。2(b)对应的是从 8 个可能的输出中随机挑选一个(形状和颜色取决于输入)。RRN 经过了四个步骤的训练,但因为它在每一步都进行了预测,因此我们可以评估每一步的表现。括号中标出了步数。

图 3:训练后的网络如何解决部分数独问题的示例。清晰起见,仅显示了完整 9*9 数独盘的最顶行。

表 2:求解数独的方法比较。只比较了可微的方法。用星号标记的条目是我们的实验,其它都来自于各自的论文。

理论循环神经网络NIPS 2018NIPS论文
1
相关数据
深度学习技术

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

交叉熵技术

交叉熵(Cross Entropy)是Loss函数的一种(也称为损失函数或代价函数),用于描述模型预测值与真实值的差距大小

机器学习技术

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

感知技术

知觉或感知是外界刺激作用于感官时,脑对外界的整体的看法和理解,为我们对外界的感官信息进行组织和解释。在认知科学中,也可看作一组程序,包括获取信息、理解信息、筛选信息、组织信息。与感觉不同,知觉反映的是由对象的各样属性及关系构成的整体。

迭代 技术

模型的权重在训练期间的一次更新。迭代包含计算参数在单个批量数据上的梯度损失。

多层感知机技术

感知机(Perceptron)一般只有一个输入层与一个输出层,导致了学习能力有限而只能解决线性可分问题。多层感知机(Multilayer Perceptron)是一类前馈(人工)神经网络及感知机的延伸,它至少由三层功能神经元(functional neuron)组成(输入层,隐层,输出层),每层神经元与下一层神经元全互连,神经元之间不存在同层连接或跨层连接,其中隐层或隐含层(hidden layer)介于输入层与输出层之间的,主要通过非线性的函数复合对信号进行逐步加工,特征提取以及表示学习。多层感知机的强大学习能力在于,虽然训练数据没有指明每层的功能,但网络的层数、每层的神经元的个数、神经元的激活函数均为可调且由模型选择预先决定,学习算法只需通过模型训练决定网络参数(连接权重与阈值),即可最好地实现对于目标函数的近似,故也被称为函数的泛逼近器(universal function approximator)。

人工智能技术

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

关系逻辑技术

研究事物间任意性质关系的逻辑推演规律的理论。关系是指若干事物之间的某种相互联系,它是逻辑学的重要概念之一。关系逻辑以具有任意性质的关系为其专门研究对象,特别是研究关系的和、关系的积、关系的逆、关系的否定等关系运算,以及各种复合关系的逻辑推演规律等等。

概率分布技术

概率分布(probability distribution)或简称分布,是概率论的一个概念。广义地,它指称随机变量的概率性质--当我们说概率空间中的两个随机变量具有同样的分布(或同分布)时,我们是无法用概率来区别它们的。

收敛技术

在数学,计算机科学和逻辑学中,收敛指的是不同的变换序列在有限的时间内达到一个结论(变换终止),并且得出的结论是独立于达到它的路径(他们是融合的)。 通俗来说,收敛通常是指在训练期间达到的一种状态,即经过一定次数的迭代之后,训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说,如果采用当前数据进行额外的训练将无法改进模型,模型即达到收敛状态。在深度学习中,损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变,暂时形成收敛的假象。

神经网络技术

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

卷积神经网络技术

卷积神经网路(Convolutional Neural Network, CNN)是一种前馈神经网络,它的人工神经元可以响应一部分覆盖范围内的周围单元,对于大型图像处理有出色表现。卷积神经网路由一个或多个卷积层和顶端的全连通层(对应经典的神经网路)组成,同时也包括关联权重和池化层(pooling layer)。这一结构使得卷积神经网路能够利用输入数据的二维结构。与其他深度学习结构相比,卷积神经网路在图像和语音识别方面能够给出更好的结果。这一模型也可以使用反向传播算法进行训练。相比较其他深度、前馈神经网路,卷积神经网路需要考量的参数更少,使之成为一种颇具吸引力的深度学习结构。 卷积网络是一种专门用于处理具有已知的、网格状拓扑的数据的神经网络。例如时间序列数据,它可以被认为是以一定时间间隔采样的一维网格,又如图像数据,其可以被认为是二维像素网格。

映射技术

映射指的是具有某种特殊结构的函数,或泛指类函数思想的范畴论中的态射。 逻辑和图论中也有一些不太常规的用法。其数学定义为:两个非空集合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)。同样的,在机器学习中,映射就是输入与输出之间的对应关系。

逻辑技术

人工智能领域用逻辑来理解智能推理问题;它可以提供用于分析编程语言的技术,也可用作分析、表征知识或编程的工具。目前人们常用的逻辑分支有命题逻辑(Propositional Logic )以及一阶逻辑(FOL)等谓词逻辑。

一阶逻辑技术

一阶逻辑是使用于数学、哲学、语言学及计算机科学中的一种形式系统。 过去一百多年,一阶逻辑出现过许多种名称,包括:一阶断言演算、低阶断言演算、量化理论或断言逻辑。一阶逻辑和命题逻辑的不同之处在于,一阶逻辑有使用量化变数。

梯度消失问题技术

梯度消失指的是随着网络深度增加,参数的梯度范数指数式减小的现象。梯度很小,意味着参数的变化很缓慢,从而使得学习过程停滞,直到梯度变得足够大,而这通常需要指数量级的时间。这种思想至少可以追溯到 Bengio 等人 1994 年的论文:「Learning long-term dependencies with gradient descent is difficult」,目前似乎仍然是人们对深度神经网络的训练困难的偏好解释。

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