EMNLPOct, 2022

带权下推自动机算法

PDF
TL;DR本研究通过改进 Lang 算法，开发了直接处理加权下推自动机的新算法，可以更有效地运用于自然语言处理中，并能够在空间和时间效率上取得优化。
weighted pushdown automatanatural language processingdynamic programmingpda-to-cfg conversionlang's algorithm
发现论文，激发创造
  • 识别加权树相邻语言的高效算法

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

    Oct, 2023

  • 使用查询和反例学习确定性加权自动机

    该研究介绍了一种从黑盒语言模型中提取概率确定有限自动机（PDFA）的算法，并在应用于循环神经网络（RNN）时，通常比从同一网络中提取加权有限自动机（WFA）的谱提取法实现更好的单词错误率（WER）和标准化分布累计收益（NDCG）。

    Oct, 2019

  • 神经网络下推自动机：模型、栈和学习模拟

    本研究讨论了一种利用外部栈内存扩展循环神经网络处理能力的方法，即神经网络下推自动机（NNPDA），并详细介绍了它的构建、训练和从训练网络中提取象征信息的能力。通过样本字符串的训练，可以提取出离散下推自动机（PDA），能够准确地识别未知来源语法的任意长度的字符串，并且与原始语法的 PDA 相同或等价。

    Nov, 2017

  • 使用推下自动机的基于序列的代码生成

    本文提出了一种基于 PDA 的代码生成方法，将 PDA 机构建成模块并设计算法对序列模型生成进行限制，最终构建了一种名为 CodePAD 的代码生成框架，它可以利用 PDA 的状态传递信息辅助本来基于序列的深度学习模型进行更好的学习，实验显示 CodePAD 在四个数据集上均可以达到 100% 的文法正确率，并且相较于基础模型在三个数据集上有着 15% 至 17% 的 BLEU 分数提升。

    Nov, 2022

  • 具有失败弧的无环加权有限状态自动机算法

    本文介绍了如何使用改进的 backward 算法处理带有 failure transitions 的 weighted finite-state automata，方法非常高效，同时也给出了特殊情况下的算法复杂度分析。

    Jan, 2023

  • 在 GPU 上使用有限状态转导进行解码

    通过 GPU 实现 Viterbi 算法和前向 - 后向算法对加权有限状态自动机进行加速，取得了至多 5.2 倍于串行实现输出速度，并对 OpenFST 实现达到 6093 倍的加速效果。

    Jan, 2017

  • 通过状态空间回归从循环神经网络中提取加权自动机

    使用回归方法进行等价查询的加权有限状态自动机（WFA）从循环神经网络（RNN）中提取的新算法实现了最近 Weiss、Goldberg 和 Yahav 的 DFA 提取方法的定量 / 加权扩展。

    Apr, 2019

  • 概率有向无环图自动机用于语义图的问题

    研究了 DAG 自动机作为概率模型的可行性，结果表明，通过赋予转换权重，一些单根，多根和无界的 DAG 自动机不能作为有用的概率模型，并且这种问题似乎是普遍存在的，但平面变体不受此影响，但这些变体有其他问题。

    Oct, 2018

  • 可微分加权有限状态转换器

    该论文提出了一种使用加权有限状态转录器（WFSTs）进行自动微分的框架，使它们可以在训练期间动态使用，该框架可以探索新的结构化损失函数并结合各种序列级损失函数使用剪枝和回退等方法，在字短语的潜在分解学习方面具有很大的优势，同时提出了一种卷积 WFST 层，可用作传统卷积层的替代，用于手写识别和语音识别的实验中表现良好。

    Oct, 2020

  • 控制层次中的收敛与多样性

    本研究通过控制机制，定义了四种文法形式：PDAs 控制 PDAs 生成的语言，PDAs 控制 CFGs 生成的语言，CFGs 控制 PDAs 生成的语言和 CFG 控制 CFG 生成的语言，进一步精确定义了它们之间的等价关系，此外，提出了一种称为 PAA 的新型自动机形式，它从 CFG 控制 PDA 的角度出发生成语言。

    Jun, 2023