Feasability of Learning Weighted Automata on a Semiring
Feasability of Learning Weighted Automata on a Semiring
复制标题
DOI：
10.48550/arxiv.2309.07806
复制
发表时间：
2023-09
期刊：
影响因子：
--
通讯作者：
Laure Daviaud;Marianne Johnson
中科院分区：
文献类型：
--
作者：
Laure Daviaud;Marianne Johnson
自从Angluin开创性的工作以来，通过成员资格和等价查询对自动机进行主动学习，已经被广泛研究，并且已经开发了几种概括来学习自动机的各种扩展。对于加权自动机，限制的情况下已经解决了文献中，在本文中，我们绘制的边界的Angluin方法（使用一类假设自动机构造的成员资格和等价查询）适用于学习加权自动机在一般半环。我们精确地展示了这种方法的理论局限性，并根据它们的可猜测性（对应于某些方程组的解的存在性和丰富性）对函数进行分类。我们提供了一个句法描述的边界条件的一个正确的假设存在的规定形式。当然，从算法的角度来看，知道（许多）解决方案存在并不需要转化为一个有效的算法来找到一个;我们最后讨论了一些已知的条件（及其变体），足以确保这一点，说明了几个熟悉的半环（包括自然数）的想法，并为未来的研究提出了一些开放的问题。
Since the seminal work by Angluin, active learning of automata, by membership and equivalence queries, has been extensively studied and several generalisations have been developed to learn various extensions of automata. For weighted automata, restricted cases have been tackled in the literature and in this paper we chart the boundaries of the Angluin approach (using a class of hypothesis automata constructed from membership and equivalence queries) applied to learning weighted automata over a general semiring. We show precisely the theoretical limitations of this approach and classify functions with respect to how guessable they are (corresponding to the existence and abundance of solutions of certain systems of equations). We provide a syntactic description of the boundary condition for a correct hypothesis of the prescribed form to exist. Of course, from an algorithmic standpoint, knowing that (many) solutions exist need not translate into an effective algorithm to find one; we conclude with a discussion of some known conditions (and variants thereof) that suffice to ensure this, illustrating the ideas over several familiar semirings (including the natural numbers) and pose some open questions for future research.