学习最大加半环上的加权有限自动机及其终止性
该研究介绍了一种从黑盒语言模型中提取概率确定有限自动机(PDFA)的算法,并在应用于循环神经网络(RNN)时,通常比从同一网络中提取加权有限自动机(WFA)的谱提取法实现更好的单词错误率(WER)和标准化分布累计收益(NDCG)。
Oct, 2019
该论文提出了一种基于Astar搜索的算法,使用确定性自动机的后向最短距离作为启发式来找到非确定性有权自动机上的最短字符串,从而解决了在非幂等半环中单一最短路径算法未定义的问题。
Apr, 2022
基于Prime Decomposition定理,本文介绍自动机级联作为自动机复杂系统的一种结构化和模块化方式;并且证明了样本复杂度可以通过组件数量和单个组件的最大复杂度来描述,由此学习表示多组分相互作用的大型动态系统的自动机的数量可以呈指数级增长。
Nov, 2022
本文介绍了如何使用改进的backward算法处理带有failure transitions的weighted finite-state automata,方法非常高效,同时也给出了特殊情况下的算法复杂度分析。
Jan, 2023
我们使用转移半群建立一种有限状态自动机的即时确定化的抽象,并展示了如何应用它来界定渐近性。我们呈现了足够导致确定自动机的多项式状态复杂性的代数和组合特性。我们发现的一个特例是,具有许多非确定性转换的自动机几乎总是适用于多项式复杂性的确定化。此外,我们将我们的思想扩展到加权有限状态自动机。
Aug, 2023
在过去的文献中,非均匀的多项式大小有限自动机被用来解决非均匀的承诺决策问题。我们重点关注非确定性有限自动机的变体,它们具有至多一个(无歧义的)、多项式多个(少量的)接受计算路径,或者无歧义/少量计算路径导致每个固定配置。当这些机器仅能进行单向头移动时,可以证明在没有未经证明的困难假设的情况下,其中一些变体在计算能力上与其他变体不同。至于限制在多项式有界长度的实例上的两向机器,双向多项式大小的非确定性有限自动机和多项式大小的无歧义有限自动机在计算能力上是等效的。
Nov, 2023
该研究介绍了一种从专家演示和自然语言中学习确定性有限自动机(DFA)的算法,利用自然语言的表达能力显著提高了从专家演示中学习DFAs的数据效率,通过结合大型语言模型和转化学习算法,实现了强大的少样本学习器。
Feb, 2024
通过标准的基于梯度的训练,我们展示了transformers模型能够模拟加权有限自动机和加权树自动机的推理能力,并在理论上证明了这些结果以及所需的transformer模型大小与目标自动机状态数的关系。
Mar, 2024