ICLRFeb, 2019

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

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

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

    Oct, 2023

  • 状态规则化递归神经网络

    通过使用一种被称为状态规范化的机制来处理以前递归神经网络（RNNs）的不足，从而提高 RNNs 的状态转移动态分析和解释性，并将其应用于自动机抽取，自然语言处理和计算机视觉中。

    Jan, 2019

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

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

    Jan, 2018

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

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

    Nov, 2017

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

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

    May, 2024

  • 从 Transformer 中提取有限状态机

    我们提出了一种专门为 Transformer 模型设计的自动机提取算法，通过对 Transformer 模型的内部潜在表示进行转换过程的跟踪并使用经典的教学方法来将其解释为确定有限状态自动机（DFA），揭示了 Transformer 模型如何理解形式语言的结构，从而增强了 Transformer 模型的可解释性并深入了解了机器学习系统如何处理形式语言。

    Jun, 2024

  • 使用门控循环神经网络从可解释结构中学习

    本文研究从深度学习模型中学习可解释结构的方法，针对门控循环神经网络内部机制不明确的问题，发现有限状态自动机具有更可解释的内部机制并提出了基于不同聚类方法的两种学习有限状态自动机的方法，在人类生命和危险领域的应用中，有限状态自动机在一定程度上可替代循环神经网络。

    Oct, 2018

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

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

    Jun, 2022

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

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

    Jun, 2019

  • 循环网络识别具有低维振荡的模式

    通过对一个受 SET 卡牌游戏启发的简单任务上训练的循环神经网络（RNN）进行解读，本研究提出了一种新颖的动力学机制用于模式识别。我们将训练后的 RNN 解释为通过低维极限环中的相位转移以类似于有限状态自动机（FSA）中的状态转换来识别模式。我们通过手工创建一个简单的振荡模型来验证这一解释，该模型能够复现训练后的 RNN 的动力学。我们的发现不仅暗示了一种潜在的能够进行模式识别的动力学机制，还暗示了一种潜在的 FSA 的神经实现。最重要的是，这项工作为深度学习模型解释性的讨论做出了贡献。

    Oct, 2023