Nov, 2023

从置信太阳神启示学习确定的有限自动机

HTML
PDF
TL;DR从置信度预测器中学习确定有限自动机的问题，目标是学习一个保留置信度信息的确定有限自动机，使其与预测器在高度置信的情况下紧密匹配。
发现论文，激发创造
  • 表达形式语言：有限自动机与循环神经网络的比较

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

    Feb, 2019

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

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

    Oct, 2019

  • 在噪声存在的情况下分析Angluin的L*算法的鲁棒性

    通过利用随机性来降低噪音、生成 DFA，主要应用于有限状态机，可以通过学习算法来减少噪音并恢复原始 DFA，但在结构化噪音下表现不佳，并且随机性生成的系统几乎肯定具有非可递归枚举语言。

    Sep, 2022

  • 利用一种非常简单的属性有效地推断 NFA

    本文研究了基于有限状态机和重写规则的形式语法学习，提出了一种基于 SAT 求解器的NFA 自动机规模求解方法，并验证了该方法的高效性。

    Mar, 2023

  • $L^*LM$: 从示例中使用自然语言预测的学习自动机

    该研究介绍了一种从专家演示和自然语言中学习确定性有限自动机（DFA）的算法，利用自然语言的表达能力显著提高了从专家演示中学习DFAs的数据效率，通过结合大型语言模型和转化学习算法，实现了强大的少样本学习器。

    Feb, 2024

  • DFAMiner: 从标记样本中挖掘最小分离有限状态机

    DFAMiner是一种用于学习从一组标记样本中获取最小可分离确定有限自动机（DFA）的无主动学习工具。

    May, 2024

  • 基于字符串概率查询的PDFA蒸馏

    本研究提出了一种从神经网络中提取PDFA的算法，并展示了其在解释性机器学习领域的有效性。

    Jun, 2024

  • 学习最大加半环上的加权有限自动机及其终止性

    研究了基于L*风格学习算法针对max-plus半环上的加权自动机的主题，提出了一种理论修复并介绍了一种算法，该算法可以在一类max-plus半环上的加权语言中终止。

    Jul, 2024

  • 将大型语言模型作为确定性有限自动机学习的随机最小充分教师

    本研究针对大型语言模型在自动机学习中的应用空白，提出了一种概率最小充分教师(pMAT)的框架，利用概率性oracle逐步改进membership query的回答准确性。研究表明，借助特定的$\mathtt{Discrimination}$和$\mathtt{Verification}$提示及动态查询缓存优化算法，能够有效提高DFA学习的表现，从而为LLMs在自动机学习中的运用奠定理论基础。

    Aug, 2024

  • 深度DFA：通过神经概率松弛进行自动机学习

    本文提出了DeepDFA，一种通过跟踪识别确定性有限自动机（DFA）的新方法，采用可微但离散的模型。该方法结合了DFA的概率松弛和递归神经网络（RNN）的启发，提供了训练后的可解释性，并在复杂度和训练效率上优于传统RNN。实验验证表明，该方法在各种规模和复杂度的目标正规语言上表现准确、快速且对噪声具有强韧性，充分结合了逻辑语法诱导和深度学习的优势。

    Aug, 2024