ACLJul, 2023

高效的半环加权 Earley 解析

PDF
TL;DR这篇论文通过退化系统的形式提供了 Earley (1970) 上下文无关解析算法的参考描述，其中包括了多种加速的方法。我们的展示包括从 Earley 的 $O (N^3|G||R|)$ 到 $O (N^3|G|)$ 的已知最坏情况运行时间改进，这在自然语言处理中出现的大型语法中是不可行的，它与语法 G 的二元化版本上的 CKY 算法的运行时间相匹配。在这里，N 是句子长度，|R | 是 G 中的产生式数目，|G | 是这些产生式的总长度。我们还提供了一个版本，在将语法简洁地表示为单个有限状态自动机 M 时实现了 O (N^3|M|) 的运行时间（这部分是新颖的）。我们细致地处理了到半环权重退化的概括，像 Stolcke (1995) 那样预处理语法以消除退化循环，并进一步推广 Stolcke 的方法以计算句子前缀的权重。我们还提供了高效执行的实现细节，在预处理语法上，我们方法的半环权重版本具有与无权重方法相同的渐近运行时间和空间要求，包括在某些语法上在次立方时间内的运行时间。
context-free parsing algorithmruntime improvementnatural language processingbinarized versionfinite-state automaton
发现论文，激发创造
  • 一种高效的概率上下文无关文法解析算法，用于计算前缀概率

    本文介绍了一种基于 Earley 解析法的扩展，可以给定随机上下文无关语法和输入字符串来计算被语法生成的前缀和子字符串的概率，以及字符串的最大可能 (Viterbi) 划分和每个语法生成的后验预期应用数量。

    Nov, 1994

  • 识别加权树相邻语言的高效算法

    提供了树连接语言、两级形式主义、半环加权版本、字符串求和算法和下推连接自动机的关键算法。

    Oct, 2023

  • 使用轻微上下文敏感文法进行非监督式不连续成分句法分析

    研究语法诱导，使用线性无上下文重写系统进行无监督不连续解析，将文法形式限制为二元 LFCRS 并使用张量分解与参数化规则概率得到大量非终端符号，从而能够诱导出具有连续和不连续结构的语言学意义的树。

    Dec, 2022

  • CCG 解析的复杂性

    本研究研究了 Vijay-Shanker 和 Weir（1994）形式主义下组合范畴语法（CCG）的解析复杂性。我们的主要结果是，在分析中，将语法的大小（而不仅仅是输入句子的长度）考虑进去时，该形式主义的任何解析算法最坏情况下需要指数时间。这与弱等价形式主义（如 Tree-Adjoining Grammar (TAG)）有所不同，对于这种形式主义，可以在与语法和输入句子的大小成多项式时间完成分析。我们的研究结果有助于更加深入地理解轻度上下文敏感语法的分类，并为寻找新的轻度上下文敏感版本的 CCG 提供信息。

    Feb, 2017

  • 广义 Earley 解析器：连接符号语法和序列数据以进行未来预测

    本研究旨在解决对未来序列数据的预测问题，提出将 Earley 解析器推广至未分段无标签序列数据，利用语言模型对最优的分段与标签进行预测，取得了显著的人类活动预测性能优于传统方法。

    Jun, 2018

  • 通过上下文敏感语法的高效左右商运算对编码语言模型进行约束解码

    本文介绍了一种增量解析器，该解析器能够早期拒绝语法错误的代码，并高效地检测符合填充中间任务的完整程序。我们开发了一种基于任意无上下文文法的左右商的 Earley 风格解析器，并将增量解析和商操作扩展到许多常见编程语言文法中的若干上下文敏感特性。这些方法的结果是一种高效、通用且可靠的左右商解析方法。为了验证我们的理论和特定设计决策的实际有效性，我们在 Python 3 的填充中间完成任务的特别困难情况下进行了方法评估。结果表明，受限生成可以极大地减少推荐代码中的语法错误的发生。

    Feb, 2024

  • 一种用于带权重写规则的高效编译器

    该研究介绍了一种新的算法，用于将上下文相关的重写规则编译成有限状态转换器（FSTs），能够更有效地进行自然语言和语音处理，并且扩展该算法以允许编译加权规则成加权的 FSTs。

    Jun, 1996

  • 神经符号推理及构成不确定性量化用于图形自回归解析的鲁棒性

    本文研究了面向神经符号推理的组合感知方法，涉及图预测的不确定性和推广性能，实现了在子图级别的细粒度神经符号推理，具有捕捉图形预测不同方面的神经和符号方法的独特优势，从而在领域间和尾部拥有良好的推广表现。

    Jan, 2023

  • 组合范畴语法的高效正常形式解析

    本文介绍了一种高效、正确且易于实现的规范化解析技术，用于处理类别语法，可以在语义等价类的每个可允许解析中完全消除虚假歧义。

    Jun, 1996

  • 复合概率上下文无关文法用于文法归纳

    我们研究了一个语法归纳问题的正式化，其将句子建模为由复合概率上下文无关文法生成。与传统的学习单一随机文法的方式不同，我们的文法的规则概率由每个句子的连续潜变量调制，这在传统上下文无关假设以外引出了边际依赖性。这种文法的推理通过折叠变分推理实现，在这种方法中，连续变量上放置平化的变分后验，并通过动态规划边际化潜在树。针对英语和中文的实验表明，与最近的最先进方法相比，我们的方法在无监督语法分析评估时非常有效。

    Jun, 2019