目录七、相关研究八、讨论GG-NN模型学到了什么逻辑推理与模型学习的对比任务编码与背景知识实验结果与局限性动态推理优化未来应用展望A 收缩映射示例限制更新以定义欧几里得度量下的收缩映射GNN模型中的节点标签与信息传播信息衰减与长程依赖限制A.1 非线性情况分析B RNN和LSTM在序列预测任务中表现不佳的原因节点ID说明长序列依赖挑战非顺序性数据挑战C 嵌套预测细节说明上一篇文章图神经网络分享系列-GGNN(GATED GRAPH SEQUENCE NEURAL NETWORKS)(二)七、相关研究最密切相关的成果是图神经网络GNNs前文已详细讨论。Micheli2009提出了另一紧密相关模型其与GNNs的主要差异在于输出模块。GNNs已在多个领域应用Gori等2005Di Massa等2006Scarselli等2009Uwents等2011但未在ICLR社区广泛使用。本文部分目标是将GNNs推广为一种实用且有趣的神经网络变体。从GNNs到门控图序列神经网络GG-NNs的改进可与Domke2011和Stoyanov等2011在结构化预测中的工作类比。他们将需收敛至稳定状态的信念传播替换为截断式信念传播更新并通过训练使固定次数的迭代产生有效结果。类似地递归神经网络Goller Kuchler1996Socher等2011扩展为树结构LSTMTai等2015与GG-NNs采用GRU更新而非标准GNN循环机制的目的一致均旨在提升信息在图结构中的长期传播效率。本文提出的“通过组合学习组件构建问题定制化神经网络”的核心思想可追溯至Hinton1988通过族谱结构组装神经网络以预测人际关系的早期研究。Hammer Jain2004和Bottou2014也体现了类似理念。图核方法Shervashidze等2011Kashima等2003可用于基于核的图结构输入学习任务但未见其同时学习核函数并生成序列的研究。Perozzi等2014通过随机游走将图转化为序列再利用序列方法学习节点嵌入。Sperduti Starita1997将图映射为向量后通过神经网络分类。多项研究涉及图结构中节点表征的传播机制。Bruna等2013将卷积推广至图结构其与GNNs的差异类似于卷积网络与循环网络的差异。Duvenaud等2015设计了可微分的图特征学习操作。Lusci等2013将无向图转为多组有向无环图DAGs并向各根节点内聚传播节点表征训练集成模型。上述研究均聚焦单步问题。GNNs及其扩展具备指针网络Vinyals等2015的多数优势当使用节点选择输出层时可直接选取输入节点作为输出。主要区别在于其一GNNs显式利用图结构虽降低通用性但可能增强泛化能力其二指针网络要求节点具备属性如空间位置而GNNs可仅通过图中位置定义节点从而在另一维度上更具通用性。门控图序列神经网络GGS-NNs与软对齐及注意力模型如Bahdanau等2014Kumar等2015Sukhbaatar等2015存在两点关联其一公式7中的图表示利用上下文聚焦关键节点其二程序验证案例中的节点标注跟踪已解释节点确保输出序列生成时覆盖所有输入节点。八、讨论GG-NN模型学到了什么通过类比逻辑推理方法来分析GG-NN模型的学习机制具有启发性。以bAbI任务为例考察右侧示例所需的子集文本行。逻辑推理与模型学习的对比传统逻辑推理需要两个核心组件故事中事实的逻辑编码以及以推理规则形式编码的背景世界知识。例如任务编码与背景知识当前的任务编码方式简化了故事到图结构的解析过程但并未提供任何背景知识。GG-NN图门控神经网络模型可视为通过学习神经网络权重来隐式掌握这些知识。实验结果与局限性论文结果表明GGS-NN图门控序列神经网络在具有内在图结构的问题上展现出良好的归纳偏置其适用场景可能更为广泛。但若要进一步扩展应用范围仍需克服以下限制输入时序与高阶关系现有bAbI任务转换未考虑输入的时间顺序或三元及以上关系。改进方向可能包括串联多个GG-NN每个边对应一个子网络或将高阶关系表示为因子图。非结构化输入处理当前bAbI任务依赖符号化输入理想情况应支持非结构化输入。潜在解决方案是将非结构化输入与隐向量融入GGS-NN框架但需实验验证最佳实现方式。动态推理优化当前GGS-NN要求在接收全部事实后再处理问题迫使网络预先推导所有事实后果并将相关信息存储于节点表征中。更优方案是让问题作为初始输入动态推导回答问题所需的事实。未来应用展望GGS-NN的后续应用潜力广阔重点方向包括端到端可学习系统开发能学习程序语义属性或复杂图算法的系统。知识库与数据库推理应用于需基于知识库和数据库进行推理的问题。结构化与深度学习的融合结合结构化表征与深度学习算法在利用已知结构的同时学习推理与扩展表征的方法。该技术代表了向结构化表征与深度学习高效结合的重要一步。A 收缩映射示例考虑一个具有N个节点{1, ..., N}的线性单隐藏单元循环结构GNN。为简化问题忽略所有边标签和节点标签等价于一个简单示例。在每一步时间隐藏状态的更新规则如下对于每个i其中mi和bi是传播模型的参数。采用约定当j ≤ 0时hj循环指向h。定义h(t) [h(t), ..., h(t)]⊤。给定向量b [b₁, ..., b_N]ᵀ可以表示为所有I的联合更新。限制更新以定义欧几里得度量下的收缩映射这意味着存在某个 ρ 1使得对于任意 h 和 h′满足以下条件或者换种说法可以立即看出这意味着对于每个 ( i ) 都有 ( |m_i| )只需令 ( h ) 为单位向量除第 ( i-1 ) 位为 1 外其余全零并令 ( h ) 为零向量。展开公式 10 可得GNN模型中的节点标签与信息传播在GNN模型中节点标签控制传播过程中使用的和的取值。信息衰减与长程依赖限制通过分析展开式并注意到所有满足可以观察到距离为的节点标签信息会以速率衰减。因此在这种简单情况下要求为压缩映射的约束意味着模型无法维持长程依赖关系。A.1 非线性情况分析同样的分析方法适用于非线性更新情况。设σ为任意非线性函数定义变换T(h) σ(Mh b)。将T(h)表示为[T₁(h), ..., T_N(h)]ᵀ其中T_i(h^(t−1)) h^(t)。根据收缩映射的定义式13T的雅可比矩阵的每个元素的绝对值均以ρ为界。为理解这一点考虑两个向量h和h′其中h_k h′_k对于所有k ≠ j且h_j ∆ h′_j。根据等式13的定义对于所有I因此左侧表达式在∆趋近于0时定义为∂Ti/∂hj当j i-1时由于特殊的循环图结构对于所有其他 j我们得到 ∂Ti/∂hj 0。将该结论应用于时间步 t 的更新时可得通过链式法则和特殊的图结构可以分析h(1)的变化如何影响h(t)。当 ρ 1 时该导数会随着 t 的增长以指数级速度趋近于 0。直观上这意味着一个节点对远处另一个节点的影响会呈指数级衰减因此难以建模长距离依赖关系。B RNN和LSTM在序列预测任务中表现不佳的原因RNN循环神经网络和LSTM长短期记忆网络在序列预测任务如bAbI任务19、最短路径和欧拉回路上的表现明显逊色于单输出任务。其中欧拉回路任务是RNN和LSTM表现最差的任务之一。以下是可能的原因该描述定义了一个包含两个环路的图主目标环路3-7-5-8-6和干扰子图1-2-4-0。所有边均以双向形式呈现两次以保证对称性。任务要求根据给定的起始两个节点及方向从第一个节点指向第二个节点找到对应的环路。干扰子图的加入提高了任务难度导致输出环路并非严格意义上的“欧拉环”。对于RNN和LSTM模型上述训练样例会被进一步转换为令牌序列。节点ID说明此处节点ID与原始符号数据中的ID不同。RNN和LSTM会读取整个序列并在读到ans标记时开始预测第一个输出。每个预测步骤中模型将ans标记作为输入并期望输出目标节点ID视为类别标签。当前设置中每个预测步骤的输出不会作为下一步的输入。GGS-NN模型采用相同设置仅将预测的节点标注传递至下一步因此与RNN和LSTM的比较仍保持公平。如何利用历史预测改进基线模型和GGS-NN是未来研究方向。长序列依赖挑战本例中RNN和LSTM需处理的序列较长接近80个标记后才开始预测。部分预测严重依赖长程记忆例如第三个预测步骤原始符号数据中的节点3RNN数据中的节点4需要参考序列开头的边(3-7)和前几个标记(n4 e1 n8)。RNN难以保持长程记忆LSTM表现更优但仍无法完全解决该问题。非顺序性数据挑战该任务的另一难点在于输出序列顺序与输入序列无关。即使边的排列顺序随机变化目标输出序列也应保持不变。bAbI任务19和最短路径任务同理。GGS-NN擅长处理此类“静态”数据而RNN和LSTM则不然。但GGS-NN如何适应RNN和LSTM擅长的时序序列数据仍需未来探索这是第8节讨论的GGS-NN模型局限性之一。C 嵌套预测细节说明列表的列表等数据结构属于嵌套数据结构其中每个节点的val指针指向另一个数据结构。这类数据结构可通过允许谓词嵌套的方式在分离逻辑中表示。例如列表的列表可表示为ls(x, y, λt → ls(t, NULL))其中λt → ls(t, NULL)是一个Lambda表达式表示对于从x到y的列表中每个节点其val指针t满足ls(t, NULL)。因此存在一个从x到y的列表其中每个节点指向另一个列表。非嵌套的简单列表可表示为ls(x, y, ⊤)其中⊤表示空谓词。与非嵌套情形不同此时val指针总指向NULL此处必须考虑val指针以描述和处理嵌套数据结构。为使GGS-NN能够预测嵌套公式将算法1调整为算法2。外层循环遍历每个命名变量一次并生成以该变量关联节点为活动节点的嵌套谓词。嵌套预测过程与算法1类似。在递归调用嵌套预测过程前第32行的节点标注更新不仅将当前结构中的节点标注为“已解释”还会将所有通过当前结构中节点val指针链接的节点标注为“活动”。以列表的列表为例预测ls(x, y,后标注步骤将x到y列表中的所有节点标注为“已解释”并将这些节点val指针指向的所有节点标注为“活动”。该行为并非硬编码到算法中标注模型可从数据中学习此模式。