当前位置: 开发笔记 > 编程语言 > 正文

[EMNLP18]用序列标注来进行成分句法分析

作者：梦里的天真575 | 来源：互联网 | 2023-08-12 14:44

原文链接：ConstituentParsingasSequenceLabeling貌似已经有好几个月没怎么看过论文了，之前一直在写论文，一

原文链接&＃xff1a;

Constituent Parsing as Sequence Labeling

貌似已经有好几个月没怎么看过论文了&＃xff0c;之前一直在写论文&＃xff0c;一直没空更新博客&＃xff0c;最近闲下来把最后几篇没看完的论文看了。

论文地址&＃xff1a;

Constituent Parsing as Sequence Labeling

代码地址&＃xff1a;

aghie/tree2labels

介绍

本文定义了一种新的树的序列化方法&＃xff0c;将树结构预测问题转化为了序列预测问题。该序列用相邻两个结点的公共祖先&＃xff08;CA&＃xff09;数量和最近公共祖先&＃xff08;LCA&＃xff09;的label来表示一棵树&＃xff0c;并且证明了这个树到序列的映射是单射但不是满射的&＃xff0c;但是提出了一系列方法来解决这个问题。

相比于之前的序列方法&＃xff0c;比如Parsing as Language Modeling&＃xff0c;本文的序列化有所不同&＃xff0c;主要体现在之前的方法都是seq2seq的&＃xff0c;也就是输入句子&＃xff0c;直接输出树的括号表达式序列。但是这种方法输出不是定长的&＃xff0c;所以结果可能会比较差。本文的方法将输出长度固定在了句子长度减1上&＃xff08;只针对不存在一元产生式的句法树&＃xff0c;这种情况之后讨论&＃xff09;&＃xff0c;所以可以将每个预测分配到每个单词上&＃xff0c;然后用序列标注的方法来解决。

树的序列化

记号和基础知识

记输入句子为 $\textbf{w} &＃61; [w_1, w_2, \ldots, w_N]$ &＃xff0c;其中 $w_i \in V$ 。 T_N 为拥有个叶子结点的不含有一元产生式的句法树集合。句法分析的任务就是将输入句子 $\textbf{w}$ 映射到句法树 T_N 。

为了将句法分析转化为序列标注任务&＃xff0c;需要定义一个树的序列化方法&＃xff1a; $\Phi_N : T_N \to L^{N - 1}$ &＃xff0c;也就是将一棵有个叶子结点的句法树转化为长度为 N-1 的序列。并且该映射函数还得满足一定的条件&＃xff0c;首先它一定得是一个函数&＃xff08;也就是对于所有的句法树&＃xff0c;都得找到一个对应的序列&＃xff09;&＃xff0c;然后这个函数还得有单射性&＃xff08;也就是句法树和序列要一一对应&＃xff0c;不能存在两个句法树对应同一个序列&＃xff0c;否则的话预测出来一个序列可能解码出两棵句法树&＃xff0c;那就尴尬了&＃xff09;&＃xff0c;当然要是还满足满射性就最好了&＃xff08;也就是对于每一个序列&＃xff0c;最好都能找到一棵句法树与之对应&＃xff0c;不然预测出一个序列无法找到对应的句法树也很尴尬&＃xff09;&＃xff0c;当然找不到也没事&＃xff0c;后文有解决方法。

然后需要定义一个函数&＃xff0c;将句子映射为序列&＃xff1a; $F_{N, \theta} : V^N \to L^{N - 1}$ 。这个映射就通过序列标注的LSTM来实现了&＃xff0c; $\theta$ 就是LSTM的参数。

最后通过函数 $F_{N, \theta} \circ \Phi_N^{-1}$ 将输入句子转化为对应的句法树。那么 $F_{N, \theta}$ 没什么好说的&＃xff0c;就是一个序列标注模型&＃xff0c;下面重点就是介绍如何设计函数 $\Phi_N$ 。

编码

之前说到了将一棵有个叶子结点的句法树转化为长度为 N-1 的序列&＃xff0c;这个序列是这样生成的&＃xff1a;对于单词 w_i &＃xff0c;分配给它一个二元label l_i &＃61; (n_i, c_i) &＃xff0c;其中 n_i 为单词 w_i 和 $w_{i &＃43; 1}$ 的CA数量&＃xff0c; c_i 为它俩的LCA的label。

如上图所示&＃xff0c;这个序列的 n_i 有两种表示方法。一种就表示成CA的绝对数量&＃xff0c;如图中第一行所示。还有一种表示成后一个数与前一个数的差值&＃xff0c;这样能减少元组的数量&＃xff0c;但是会出现负数。当然在这个例子中貌似并不能看出数量减少了。。。

叉树编码&＃xff1a;如果句法树所有产生式全部是叉的&＃xff0c;那么还可以将编码进一步简化&＃xff0c;具体做法就是将所有的负数 n_i 统一为一个负数就行。为什么这里就不需要对负数进行区分了呢&＃xff1f;这还得从句法树的解码说起&＃xff0c;我们看一看是怎么从序列解码成句法树的。

当遇到一个负数 n_i 的时候&＃xff0c;说明 ${\rm LCA}(w_{i}, w_{i&＃43;1})$ 到根结点路径的长度比 ${\rm LCA}(w_{i-1}, w_i)$ 到根结点路径长度少 -n_i 个结点。大致结构如下图所示&＃xff08;图画的丑&＃xff0c;不要介意&＃xff09;&＃xff1a;

可以看出&＃xff0c; $w_{i&＃43;1}$ 这棵子树接在了从 $w_{i}$ 到根结点路径上的第 -n_i &＃43; 2 个结点上。但是 $w_{i&＃43;1}$ 具体在哪还无法确定&＃xff0c;只能确定它的子树根结点位置。另外需要解释的是&＃xff0c;为什么这里是常数2&＃xff1f;因为 w_i 到 $w_{i-1}$ 与 $w_{i}$ 的LCA的距离一定是2&＃xff0c;如果不是的话&＃xff0c;中间就一定会有其他结点&＃xff0c;那么就一定存在结点位于 $w_{i-1}$ 与 $w_{i}$ 之间&＃xff0c;这显然不可能。最后可以注意到&＃xff0c;这种情况下&＃xff0c;

如果 n_i 是正数的话&＃xff0c;说明 ${\rm LCA}(w_{i}, w_{i&＃43;1})$ 到根结点路径的长度比 ${\rm LCA}(w_{i-1}, w_i)$ 到根结点路径长度多 n_i 个结点。大致结构如下图所示&＃xff1a;

这种情况下&＃xff0c; $w_{i&＃43;1}$ 这棵子树接在了从 ${\rm LCA}(w_{i-1}, w_i)$ 到 w_i 路径上的第 n_i &＃43; 1 个结点处。同样也无法确定它的准确位置&＃xff0c;但是它所在的子树确定了从这分叉出去的。

回到正题&＃xff0c;之前说到了对于叉树&＃xff0c;所有负数都可以统一起来&＃xff0c;为什么呢&＃xff1f;继续看上面 n_i 负数那张图&＃xff0c;对于 $w_{i&＃43;1}$ 所在子树&＃xff0c;需要在从 w_i 到根结点这条路径上寻找一个分叉点&＃xff0c;也就是它俩的LCA。如果这是一个叉树&＃xff0c;那么这个分叉点就一定是第一个孩子数不满个的结点。因为如果再往下的话&＃xff0c;孩子数都满了&＃xff0c;再加子树孩子数一定大于。再往上的话&＃xff0c;就会导致这第一个结点孩子数小于 &＃xff0c;因为从左到右遍历的&＃xff0c;子树之间不会交叉&＃xff0c;以后都不会有子树插入到这个结点处了。

下图就是简化序列化后的二叉树例子&＃xff0c;第三行将所有的负数都用一个负号替代了&＃xff1a;

我尝试过了按照这个序列构建出一棵树的过程&＃xff0c;画了个草图给大家看看&＃xff0c;可能有点乱&＃xff08;参照的是上面那个非二叉树的图&＃xff09;&＃xff1a;

还有一个小trick就是对于有些直接连到根结点的叶子&＃xff0c;用 $({\rm ROOT}, c_i)$ 作为它们的label。

理论证明

主要证明两个性质&＃xff0c;一个就是充分性&＃xff08;即每个句法树都能映射为一个序列&＃xff09;&＃xff0c;另一个就是单射性&＃xff08;即每个序列只能唯一对应一个句法树&＃xff09;。

充分性&＃xff1a;这个显而易见&＃xff0c;对于每个句法树&＃xff0c;相邻两个单词一定存在唯一的LCA&＃xff0c;且它的label也是唯一的&＃xff0c;所以充分性肯定能保证的。

单射性&＃xff1a;为了简便&＃xff0c;首先证明不包含非终结符的树结构映射的单射性&＃xff0c;再证明加上非终结符也是单射的。

如果用 $(\bullet_i)$ 表示第个叶子结点&＃xff0c;那么句法树可以表示成如下的括号表达式&＃xff1a;

$\alpha_0 (\bullet_1) \alpha_1 (\bullet_2) \ldots \alpha_{\left| w \right| - 1} (\bullet_{\left| w \right|}) \alpha_{\left| w \right|}$

更进一步&＃xff0c;每个 $\alpha_i$ 形式肯定是 [)]^*[(X]^* &＃xff0c;因为如果存在一个闭合的括号对&＃xff0c;那么中间肯定还存在着一个叶子结点&＃xff0c;这显然不可能。所以我们可以用 $\alpha_{i)}$ 来替代 [)]^* &＃xff0c;用 $\alpha_{i(}$ 来替代 [(X]^* &＃xff0c;将 $\alpha_i$ 改写为 $\alpha_{i)} \alpha_{i(}$ &＃xff0c;括号表达式可以重写为&＃xff1a;

$\alpha_{0)} \alpha_{0(} (\bullet_1) \alpha_{1)} \alpha_{1(} (\bullet_2) \ldots (\bullet_{\left| w \right|}) \alpha_{\left| w \right|)} \alpha_{\left| w \right|(}$

注意到首尾两个元素一定是空的&＃xff0c;接下来用 $\beta_i$ 替换 $\alpha_{i-1(}(\bullet_i)\alpha_{i)}$ &＃xff0c;得到序列&＃xff1a;

$\beta_1 \beta_2 \ldots \beta_{\left| w \right|}$

更进一步&＃xff0c;可以证明 $\beta_i$ 一定只含有 $[(X]^*(\bullet_i)$ 和 $(\bullet_i)[)]^*$ 中的一个。因为如果两个都含有的话&＃xff0c;说明存在 $(X(\bullet_i))$ 这种一元产生式&＃xff0c;但是因为一元产生式都提前处理过了&＃xff0c;所以不可能存在。

接下来可以给每个 $\beta_i$ 分配一个值 $\delta(\beta_i)$ &＃xff0c;如果 $\beta_i$ 左右两边都没有括号&＃xff0c;那这个值就是0&＃xff0c;如果左边有个括号&＃xff0c;那值就是 &＃43;k &＃xff0c;如果右边有个括号&＃xff0c;那值就是。如果将这些值写成序列&＃xff1a;

$\delta(\beta_1)\delta(\beta_2)\ldots\delta(\beta_{\left|w\right| - 1})$

这个序列正好对应了之前的第二种编码&＃xff0c;也就是编码成LCA的个数之差。这是为什么呢&＃xff1f;可以看出&＃xff0c;一直到 $\beta_i$ 结束&＃xff0c;没有闭合的括号数量正好就是 w_i 和 $w_{i&＃43;1}$ 的LCA数量。所以 $\delta(\beta_i)$ 就是 w_i 和 $w_{i&＃43;1}$ 的LCA数量与 $w_{i-1}$ 和 $w_{i}$ 的LCA数量的差值。

最后这就验证了括号序列和之前的编码是一一对应的&＃xff0c;单射性得证。解码的时候只需要将数字直接转化成对应的括号序列就行了。

而加上了非终结符之后&＃xff0c;单射性不会受到影响。因为虽然两棵相同结构但是拥有不同非终结符的句法树&＃xff0c;转化成括号序列后是相同的。但是因为之前的定义中&＃xff0c;还有一个变量 c_i 来表示这个非终结符了&＃xff0c;所以还是能够唯一对应过去的。

限制

上面定义的序列化函数有两个缺点&＃xff1a;一是非满射&＃xff0c;二是不能处理一元产生式&＃xff0c;下面介绍一下解决方法。

对于一元产生式&＃xff1a; 有两种一元产生式&＃xff0c;一种是中间结点&＃xff0c;还有一种是叶子结点的label。

对于中间结点&＃xff0c;直接将一条链上的label合并成一个新的label就行了&＃xff0c;方法和之前文章介绍的一样。

而对于叶子结点的label&＃xff0c;一个方法是在解码之前先用一个函数预测一下每个叶子结点的label&＃xff0c;如果为空&＃xff0c;说明没有label&＃xff0c;否则就加上这个label&＃xff0c;然后再进行正常的解码。另一个方法是将之前的序列化的二元组扩展为三元组 (n_i, c_i, u_i) &＃xff0c;其中第三个元素就是每个叶子结点的label。

非满射&＃xff1a; 非满射会导致的问题就是产生出来的序列可能无法映射到某一棵句法树。根据文中所说&＃xff0c;一共有两种无法映射的情况。

一种情况是对于多叉树&＃xff0c;相邻两对叶子结点的LCA的label预测不同。比如在最上面一张图中&＃xff0c;“the red toy”如果预测为两个不同的label&＃xff0c;那么就会产生矛盾。这种情况很好解决&＃xff0c;只要在解码的时候只取第一个label&＃xff0c;忽略后一个就行了。

另一种情况是序列可能会产生一元产生式&＃xff0c;如下图所示&＃xff1a;

根据图中序列&＃xff0c;会产生下面那棵句法树&＃xff0c;一元结点X并没有预测到。但其实因为一元结点已经提前合并了&＃xff0c;所以如果预测到了一元结点&＃xff0c;直接删掉不要就行了。

序列标注

这里就不细讲了&＃xff0c;用的就是基本的BiLSTM &＃43; CRF序列标注模型&＃xff0c;具体可以看这篇论文&＃xff1a;

End-to-end Sequence Labeling via Bi-directional LSTM-CNNs-CRF

实验

这篇论文最大的卖点不是效果&＃xff0c;而是速度快&＃xff0c;下面是和其他模型的速度对比&＃xff0c;可以看出&＃xff0c;速度的确快了不少&＃xff0c;达到了大几百句每秒。但是还是存在序列标注模型的老毛病&＃xff0c;效果并不好&＃xff0c;虽然比之前的高了&＃xff0c;但是还是只有90%的F1。

结论与展望

这篇论文定义了一种新的句法树序列化方法&＃xff0c;将句法树序列化为长度减1的序列&＃xff0c;其中每个值就是相邻两个单词的CA个数和LCA的label。

看完这篇&＃xff0c;我仔细想了想&＃xff0c;其实之前的chart-based方法也都可以转化成序列&＃xff0c;只不过都得特别处理一下一元产生式和多叉树&＃xff0c;比较麻烦。以后可以考虑在这方面有所突破&＃xff0c;速度快还是很nice的。

推荐阅读

case
深入理解 Java 控制结构的全面指南

深入理解 Java 控制结构的全面指南 ... [详细]

蜡笔小新 2024-11-06 16:40:43
md5
PHP预处理常量详解：如何定义与使用常量

PHP预处理常量详解：如何定义与使用常量 ... [详细]

蜡笔小新 2024-11-09 11:31:23
java
深入解析 Android TextView 中 getImeActionLabel() 方法的使用与代码示例

深入解析 Android TextView 中 getImeActionLabel() 方法的使用与代码示例 ... [详细]

蜡笔小新 2024-11-04 19:48:30
main
如何高效启动大数据应用之旅？

在前一篇文章中，我探讨了大数据的定义及其与数据挖掘的区别。本文将重点介绍如何高效启动大数据应用项目，涵盖关键步骤和最佳实践，帮助读者快速踏上大数据之旅。 ... [详细]

蜡笔小新 2024-11-04 18:30:38
main
PTArchiver工作原理详解与应用分析

PTArchiver工作原理及其应用分析本文详细解析了PTArchiver的工作机制，探讨了其在数据归档和管理中的应用。PTArchiver通过高效的压缩算法和灵活的存储策略，实现了对大规模数据的高效管理和长期保存。文章还介绍了其在企业级数据备份、历史数据迁移等场景中的实际应用案例，为用户提供了实用的操作建议和技术支持。 ... [详细]

蜡笔小新 2024-11-11 13:40:49
js
C++ 异步编程中获取线程执行结果的方法与技巧及其在前端开发中的应用探讨

本文探讨了C++异步编程中获取线程执行结果的方法与技巧，并深入分析了这些技术在前端开发中的应用。通过对比不同的异步编程模型，本文详细介绍了如何高效地处理多线程任务，确保程序的稳定性和性能。同时，文章还结合实际案例，展示了这些方法在前端异步编程中的具体实现和优化策略。 ... [详细]

蜡笔小新 2024-11-09 15:14:28
main
FFMpeg学习进阶：音频处理基础理论与重采样技术详解

在Android平台中，播放音频的采样率通常固定为44.1kHz，而录音的采样率则固定为8kHz。为了确保音频设备的正常工作，底层驱动必须预先设定这些固定的采样率。当上层应用提供的采样率与这些预设值不匹配时，需要通过重采样（resample）技术来调整采样率，以保证音频数据的正确处理和传输。本文将详细探讨FFMpeg在音频处理中的基础理论及重采样技术的应用。 ... [详细]

蜡笔小新 2024-11-09 13:46:55
case
【BZOJ1012】[JSOI 2008] 最大数值问题：ST表优化解决方案

题目要求维护一个数列，并支持两种操作：一是查询操作，语法为QL，用于查询数列末尾L个数中的最大值；二是更新操作，用于修改数列中的某个元素。本文通过ST表（Sparse Table）优化查询效率，确保在O(1)时间内完成查询，同时保持较低的预处理时间复杂度。 ... [详细]

蜡笔小新 2024-11-09 12:14:17
main
全局变量与常量在内存中的布局分析及应用

本文详细探讨了全局变量与常量在内存中的存储布局及其应用。通过分析不同编译器和操作系统对全局变量与常量的处理方式，揭示了它们在内存中的具体分配机制。此外，文章还讨论了这些布局对程序性能和安全的影响，并提供了优化建议，帮助开发者更好地理解和利用全局变量与常量的内存管理。 ... [详细]

蜡笔小新 2024-11-09 10:50:48
main
如何撰写适应变化的高效代码：策略与实践

编写高质量且适应变化的代码是每位程序员的追求。优质代码的关键在于其可维护性和可扩展性。本文将从面向对象编程的角度出发，探讨实现这一目标的具体策略与实践方法，帮助开发者提升代码效率和灵活性。 ... [详细]

蜡笔小新 2024-11-09 10:20:32
java
使用Maven JAR插件将单个或多个文件及其依赖项合并为一个可引用的JAR包

本文介绍了如何利用Maven中的maven-assembly-plugin插件将单个或多个Java文件及其依赖项打包成一个可引用的JAR文件。首先，需要创建一个新的Maven项目，并将待打包的Java文件复制到该项目中。通过配置maven-assembly-plugin，可以实现将所有文件及其依赖项合并为一个独立的JAR包，方便在其他项目中引用和使用。此外，该方法还支持自定义装配描述符，以满足不同场景下的需求。 ... [详细]

蜡笔小新 2024-11-09 01:59:29
main
2018 HDU 多校联合第五场 G题：Glad You Game（线段树优化解法）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6356在《Glad You Game》中，Steve 面临一个复杂的区间操作问题。该题可以通过线段树进行高效优化。具体来说，线段树能够快速处理区间更新和查询操作，从而大大提高了算法的效率。本文详细介绍了线段树的构建和维护方法，并给出了具体的代码实现，帮助读者更好地理解和应用这一数据结构。 ... [详细]

蜡笔小新 2024-11-08 19:17:23
client
ESP8266 01S Web 服务器成功启动：详细解决方案与实践指南

本文详细介绍了一种利用 ESP8266 01S 模块构建 Web 服务器的成功实践方案。通过具体的代码示例和详细的步骤说明，帮助读者快速掌握该模块的使用方法。在疫情期间，作者重新审视并研究了这一未被充分利用的模块，最终成功实现了 Web 服务器的功能。本文不仅提供了完整的代码实现，还涵盖了调试过程中遇到的常见问题及其解决方法，为初学者提供了宝贵的参考。 ... [详细]

蜡笔小新 2024-11-08 19:12:49
client
MySQL与MariaDB数据库管理：约束与键操作详解

在关系型数据库中，数据约束是指在向数据表中插入数据时必须遵循的限制条件。在MySQL和MariaDB中，常见的数据约束包括主键约束、唯一键约束、外键约束以及非空约束等。这些约束确保了数据的完整性和一致性，是数据库管理中的重要组成部分。通过合理设置和使用这些约束，可以有效防止数据冗余和错误，提升数据库的可靠性和性能。 ... [详细]

蜡笔小新 2024-11-08 17:17:06
client
数据库多表联合查询：内连接与外连接详解

在数据库的多表查询中，内连接和外连接是两种常用的技术手段。内连接用于检索多个表中相互匹配的记录，即只有当两个表中的记录满足特定的连接条件时，这些记录才会被包含在查询结果中。相比之下，外连接则不仅返回匹配的记录，还可以选择性地返回不匹配的记录，具体取决于左外连接、右外连接或全外连接的选择。本文将详细解析这两种连接方式的使用场景及其语法结构，帮助读者更好地理解和应用多表查询技术。 ... [详细]

蜡笔小新 2024-11-07 17:11:30

梦里的天真575

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章