DFAMiner: 从标记样本中挖掘最小分离有限状态机
提出并评估了一种新技术,通过观察动态系统的运行时行为自动学习混合自动机。该技术利用信息论度量作为数据分段和模型选择的成本函数,以惩罚过拟合,并确定每个转换的可能原因。通过实验验证,能够成功发现角色的真实行为并与近期自动学习概率定时自动机的工作进行比较,表现出优异的结果。
Jul, 2017
通过训练循环神经网络(RNN)来学习识别正则形式语言时使用的内部表示,我们研究了一个简单的解码函数,其将该 RNN 的状态映射到该语言的最小确定性有限自动机(MDFA)的状态,进而探讨了RNN内部表示与有限状态自动机之间的强结构关系,解释了RNN识别正式语法结构的能力。
Feb, 2019
基于Prime Decomposition定理,本文介绍自动机级联作为自动机复杂系统的一种结构化和模块化方式;并且证明了样本复杂度可以通过组件数量和单个组件的最大复杂度来描述,由此学习表示多组分相互作用的大型动态系统的自动机的数量可以呈指数级增长。
Nov, 2022
我们提出了一种计数奖励自动机——一种能够模拟任何能以形式语言表示的奖励函数的有限状态机变体。与以前的方法不同,这些方法仅能表达任务为正则语言,而我们的框架允许通过无限制语法来描述任务。我们证明了一个配备这样抽象机器的代理能够解决比使用当前方法更多的任务。我们展示了这种表达能力的增加并不需要增加自动机的复杂性。我们提出了一系列利用自动机结构来提高样本效率的学习算法。我们展示了我们的方法在样本效率、自动机复杂性和任务完成方面优于竞争方法的实证结果。
Dec, 2023
该研究介绍了一种从专家演示和自然语言中学习确定性有限自动机(DFA)的算法,利用自然语言的表达能力显著提高了从专家演示中学习DFAs的数据效率,通过结合大型语言模型和转化学习算法,实现了强大的少样本学习器。
Feb, 2024
本研究针对大型语言模型在自动机学习中的应用空白,提出了一种概率最小充分教师(pMAT)的框架,利用概率性oracle逐步改进membership query的回答准确性。研究表明,借助特定的$\mathtt{Discrimination}$和$\mathtt{Verification}$提示及动态查询缓存优化算法,能够有效提高DFA学习的表现,从而为LLMs在自动机学习中的运用奠定理论基础。
Aug, 2024
本文提出了DeepDFA,一种通过跟踪识别确定性有限自动机(DFA)的新方法,采用可微但离散的模型。该方法结合了DFA的概率松弛和递归神经网络(RNN)的启发,提供了训练后的可解释性,并在复杂度和训练效率上优于传统RNN。实验验证表明,该方法在各种规模和复杂度的目标正规语言上表现准确、快速且对噪声具有强韧性,充分结合了逻辑语法诱导和深度学习的优势。
Aug, 2024
本研究解决了现有机器学习架构在表示图形算法决策时的局限性,提出了一个新的框架:GraphFSA。该框架能够在给定图的每个节点上学习有限状态自动机,并通过各种合成问题进行了全面的实证评估。结果表明,GraphFSA在推广和外推能力上表现出色,为图形算法的表示提供了替代方法。
Aug, 2024