Feb, 2019

表达形式语言：有限自动机与循环神经网络的比较

HTML
PDF
TL;DR通过训练循环神经网络（RNN）来学习识别正则形式语言时使用的内部表示，我们研究了一个简单的解码函数，其将该 RNN 的状态映射到该语言的最小确定性有限自动机（MDFA）的状态，进而探讨了RNN内部表示与有限状态自动机之间的强结构关系，解释了RNN识别正式语法结构的能力。
发现论文，激发创造
  • 子正则复杂度与深度学习

    本文通过对两种循环神经网络的实验研究，证明了正则正负推理算法是深度神经网络能否表示和学习时间序列中的长期依赖的可靠工具。此外，本文发现在同种实验中简单循环神经网络在最难的实验中表现出色，长短时记忆网络的表现总体上比简单循环神经网络差。

    May, 2017

  • 使用查询和反例从递归神经网络中提取自动机

    本文提出了一种新算法，利用精确学习和抽象来提取描述给定训练RNN状态动态的确定性有限自动机，使用Angluin的L*算法作为学习器和训练RNN作为oracle，即使状态向量较大且需要进行精细区分，该技术也可以高效地从训练RNN中提取准确的自动机。

    Nov, 2017

  • 递归神经网络规则提取的比较研究

    本研究旨在探讨不同复杂度的Tomita文法上，从常用的循环神经网络中提取确定有限状态自动机的性能表现。研究结果表明，随着底层文法复杂度的提高，大多数循环神经网络的提取性能逐渐降低。

    Jan, 2018

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

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

    Apr, 2019

  • 顺序神经网络作为自动机

    本研究试图从理论的角度解释神经网络的计算类型，通过将它们与自动机相关联，并使用定义“实时网络有界精度接受语言”的方法来解释网络内存度量，对可被各种循环网络、注意力和卷积网络接受的语言类别进行了表征。研究发现LSTM功能类似于计数器机，并将卷积网络与子正则层次结构相关联。这些理论洞察力有助于解释神经计算，以及神经网络与自然语言语法之间的关系。

    Jun, 2019

  • 从循环神经网络中提取加权有限状态自动机以处理自然语言

    本文提出了解决 RNN 的状态转移抽取中过稀疏问题的新方法，包括用经验方法补充缺失规则、调整转移矩阵以加强上下文感知、以及数据增强策略以跟踪目标 RNN 的更多动态行为。研究结果表明，我们的方法能够以更好的精度从 RNN 中提取加权有限自动机，特别适用于自然语言处理模型。

    Jun, 2022

  • 关于二阶递归神经网络的计算复杂性和形式层次的研究

    这项研究通过扩展第二阶循环神经网络的理论基础，证明存在一类有界时间的第二阶循环神经网络，具备图灵完备性，可以直接将转移表编码到其循环权重中，实现有界时间计算，并通过设计可解释。同时，该研究还展示了在有界权重和时间约束下，没有记忆的第二阶循环神经网络在识别正则语法方面优于传统的循环神经网络和门控循环单元等现代模型，并提供了识别任何一类正则语法所需的最大神经元数量的上界和稳定性分析。大量关于Tomita语法的实验证实了研究结果，并展示了采用第二阶循环神经网络进行解释和提取状态机时的成功率较一阶循环神经网络更高。这些结果拓展了循环神经网络的理论基础，并为未来可解释人工智能的研究提供了有希望的方向。

    Sep, 2023

  • 循环神经语言模型作为概率有限状态自动机

    本文研究了RNN语言模型对概率分布的表示能力，发现简单的RNN等效于概率有限状态自动机，能够表示有限状态模型可表达的概率分布的严格子集，同时研究了用RNN表示确定性有限状态语言模型的空间复杂度。这些结果对于了解RNN语言模型的能力和限制具有重要意义。

    Oct, 2023

  • 循环神经网络语言模型表达能力下界

    通过将递归神经网络语言模型连接到概率有限状态自动机，我们重新审视了递归神经网络语言模型的表征能力，并证明具有线性边界精度的递归神经网络语言模型可以表示任意的正则语言模型。

    May, 2024

  • 将神经网络训练为形式语言的识别器

    本研究解决了神经网络在形式语言理论中的应用差异问题，强调了机器应作为字符串的二元分类器进行训练。通过应用一种通用方法并扩展现有算法以控制字符串长度，研究表明RNN和LSTM在性能上通常优于变压器，这为未来语言识别理论的实证测试奠定了基础，并发布了名为FLaRe的数据集作为基准。

    Nov, 2024