雷锋网AI科技评论按：本文转载自微信公众号 哈工大SCIR ，雷锋网获授权转载。
值得一提的是，本周五（11 月 24 日）晚上 8 点，第一作者王宇轩将在雷锋网旗下频道AI慕课学院（http://www.mooc.ai/）进行第 34 期的 GAIR 大讲堂直播，主题为《AAAI论文解读：基于转移的语义依存图分析》，扫描本文底部海报AI科技评论二维码，添加社长微信，备注「王宇轩」即可。
论文作者：王宇轩，车万翔，郭江，刘挺
本文介绍的工作来源于我实验室录用于 AAAI 2018 的论文《A Neural Transition-Based Approach for Semantic Dependency Graph Parsing》。
语义依存图是近年来提出的对树结构句法或语义表示的扩展，它与树结构的主要区别是允许一些词拥有多个父节点，从而使其成为有向无环图（direct edacyclic graph，DAG）。（我实验室在 SemEval-2012 上组织了世界上最早的语义依存（树）分析技术评测，并随后将其扩展到语义依存图，在 SemEval-2016 上组织了相关评测。图 1 和图 2 分别给出同一句话的句法依存树和语义依存图的例子，更多有关中文语义依存图的信息可以参考 http://mp.weixin.qq.com/s/bvm6sISUsUEhOpTOV-NxSg）
因此要获得句子的语义依存图，就需要对这种 DAG 进行分析。然而目前大多数工作集中于研究依存树结构，少有人研究如何对 DAG 进行分析。
本文提出一种基于转移的分析器，使用 list-based arc-eager 算法的变体对依存图进行分析，并提出了两种有效的神经网络模块，分别用于获得转移系统中缓存和子图更好的表示。该系统在中英数据集上都取得了很好的结果，并且还能通过简单的模型融合方法进一步提高性能。
图 1 句法依存树
图 2 语义依存图
目前依存树分析领域两大主流方法分别是基于转移（Transition-based）和基于图（Graph-based）的依存分析。基于图的算法将依存分析建模为在有向完全图中求解最大生成树的问题。基于转移的依存分析算法将句子的解码过程建模为一个有限自动机问题（类比编译器中的句法分析组件）。
本文中，我们选择了基于转移的依存分析方法。这种方法从起始转移状态开始，不断地执行转移动作从一个状态进入另一个状态，最终达到终结状态，并将终结状态对应的树（或图）作为分析结果。转移状态包括一个保存正在处理中的词的栈（Stack），一个保存待处理词的缓存（Buffer），和一个记录已经生成的依存弧的存储器。转移动作通常包括如移进、规约并生成依存弧等。数据驱动的基于转移依存句法分析的目标是训练一个分类器。这个分类器对给定转移状态预测下一步要执行的转移动作。
如图 2 所示，依存图与依存树有两种主要区别。
第一，依存图中存在交叉弧。传统转移算法需要通过添加缓存机制来解决交叉弧的问题。Choi 等人 2013 年提出的 List-based Arc-eager 算法 [1] 就是这样一思路的代表。List-based Arc-eager 算法在前文介绍的转移系统基础上，增加了一个双向队列（Deque）用于保存暂时跳过的词，来生成交叉弧。
第二，依存图中的词可能存在多个父节点。导致传统转移算法无法产生依存图的主要原因是：这些算法为了保证了最终生成的是一棵依存树，往往规定一旦找到了一个词的父节点，这个词就应立即被规约。为了使我们的转移算法能够产生依存图结构，我们在 Choi 等人的基础上修改了转移动作的执行条件，使得找到父节点的词缓存在双向队列中而不被规约，这为接下来的转移动作找到该词的其它父节点提供了可能，从而生成语义依存图。图 3 给出用修改后的算法生成语义依存图的具体流程。
图 3 修改后的 List-based Arc-eager 算法生成语义依存图的流程
解决了转移系统的问题，接下来就需要选择一个合适的分类器在每个转移状态下预测出下一步要执行的转移动作。我们选择了 Dyer 等人在 2015 年提出的 Stack-LSTM[2] 作为基础网络结构来学习转移系统中的栈、双向队列、缓存和历史转移动作序列中的信息。（关于 Stack LSTM 的具体介绍可以参考 http://mp.weixin.qq.com/s/QvHTUAicgf257wQwkRn3cQ）
为了更好地获得转移状态的表示，我们在上述结构的基础上提出了 2 个有效的神经网络模块——Bi-LSTM Subtraction 和 Incremental Tree-LSTM，分别对转移过程中的缓存和子图进行建模。图 4 给出了该模型的整体结构图。
图 4 依存图分析器模型整体结构图
Dyer 等人的模型中简单地使用从右向左的单向 LSTM 的最后一个隐层状态向量表示缓存中的所有信息。这种方法不但无法获取缓存之外的词（已被移入栈中或规约）的信息，也损失了从左向右的上下文信息。而且，我们认为只用一个隐层状态向量是无法很好地表示整个缓存中的信息的。因此，我们将缓存看作一个段，并用段头和段尾的表示的差来表示整个段。此外，为了获得缓存之外词的信息，我们首先将整个句子输入双向 LSTM 中，用每个词对应的隐层状态向量作为其表示 [3]。
图 5 Bi-LSTM Subtraction 结构图
例如图 5 中计算缓存的表示时，先用「吃饭」的正向 LSTM 表示减去「太」的正向 LSTM 表示，获得该段正向的表示，再用「太」的反向 LSTM 表示减去「吃饭」的反向 LSTM 表示，获得该段反向的表示。二者拼接起来作为此时缓存的表示。
Dyer 等人的模型中使用基于依存的递归神经网络（RecNN）来计算转移过程中的子结构，在处理较深的子结构时，这种方法可能会遇到梯度消失问题。为了解决该问题，我们利用 Tree-LSTM[4] 对这些子结构进行建模。图 6 显示了我们提出的 Incremental Tree-LSTM 与基于依存的 RecNN 的区别。RecNN 通过递归地组合一个个父节点-子节点对来构建子图，而 Tree-LSTM 则能同时合并一个节点及其所有子节点。
图 6 Incremental Tree-LSTM 与基于依存的递归神经网络对比
由于基于转移的依存图分析的特点，我们使用的 Tree-LSTM 与一般的 Tree-LSTM 有两点不同。首先，显然该任务中需要建模的子结构不一定是树。但好在我们处理的依存图不包括环，因此仍然能够使用 LSTM。更重要的是，与一般的 Tree-LSTM 能够同时获得一个节点的所有子节点不同，在基于转移的依存分析中，一个节点的子节点是逐个被找到的，因此我们需要不断利用 Tree-LSTM 更新父节点信息。具体来说，对于一个词，每当找到它的一个新子节点，就要将其所有已经找到的子节点和其本身的表示输入 Tree-LSTM 中计算它的新表示。例如图 7 中的子图构建流程如下：
（1）用 Tree-LSTM 合并 A 和 B 的表示并将结果作为 A 的新表示；
（2）合并 B 和 C 的表示并将结果作为 B 的新表示；
（3）合并 A、D 的表示和 B 当前的表示（b+c）并将结果作为 A 的新表示。
图 7 Incremental Tree-LSTM 中子图的递增式构建
我们的系统能通过一个简单的模型融合方法进一步提高性能。具体来说，就是在训练时使用不同随机初始化种子训练多个模型。在预测时，用这些模型算出的分数之和来选择接下来的转移动作。
我们的系统在中英文数据集上都获得了很好的实验结果，表 1 是 SemEval-2016 Task 9 中文数据集上的实验结果。该数据集分为两部分，分别是新闻集（NEWS）和小学课本集（TEXTBOOKS），前者句子较长、较复杂，后者句子较短、较简单。该评测的评价指标中最重要的两个分别是弧标签的 F 值（LF）和有多父节点的词的弧标签的 F 值（NLF）。
表中前 5 个是其他参赛系统，2-stage (Ding et al. 2014) 是我们重新实现的 Ding 等人在 2014 年提出的一个两步方法 [5]，先用传统依存树分析器生成树结构，再用 SVM 分类器从规则产生的候选弧集合中选出一些弧加入其中从而得到依存图结构。BS-IT 是我们的系统。实验结果表明我们的系统在两个数据集的各项评测指标中都明显超过其他系统。
表 2 中列出了测试 BS 和 IT 模块效果的实验，结果表明二者都能为基础系统带来性能提升。而二者同时使用时对系统性能提升更明显。
本文提出了一个基于转移的语义依存图分析方法，利用 List-based Arc-eager 算法的变体实现了有向无环图的生成。此外，本文还提出了两种有效的神经网络模块用于学习转移系统中重要部分的表示。在中英数据集上的实验结果证明了该方法的有效性。
[1] Choi J D, McCallum A. Transition-based Dependency Parsingwith Selectional Branching[C]. Proceedings of the 51thAnnual Meeting of the Association for Computational Linguistics. 2013: 1052-1062.
[2] Dyer C, Ballesteros M, Ling W, et al. Transition-based Dependency Parsingwith Stack Long Short-Term Memory[C]. Proceedingsof Annual Meeting on Association forComputational Linguistics. 2015: 334–343.
[3] Kiperwasser E, Goldberg Y. Simple and Accurate DependencyParsing Using Bidirectional LSTM Feature Representations [J]. Transactions ofthe Association for Computational Linguistics. 2016: 313-327.
[4] Tai K S,Socher R, Manning C D. Improved Semantic Representations from Tree-StructuredLong Short-Term Memory Networks[C]. Proceedings of the 53rd Annual Meeting ofthe Association for Computational Linguistics and the 7th International JointConference on Natural Language Processing. 2015: 1556-1566.
[5] Ding Y,Shao Y, Che W, et al. Dependency graph based Chinese semantic parsing [M]. ChineseComputational Linguistics and Natural Language Processing Based on NaturallyAnnotated Big Data. Springer, Cham, 2014: 58-69.
本周五（11月24日）晚上8点，第一作者王宇轩将在雷锋网旗下频道AI慕课学院（http://www.mooc.ai/）进行第34期的GAIR大讲堂直播，主题为《AAAI论文解读：基于转移的语义依存图分析》，扫描海报二维码添加社长微信，备注「王宇轩」即可。
正在生成分享图...
我在思考中