Learning probabilistic automata: A study in state distinguishability
Learning probabilistic automata: A study in state distinguishability
复制标题
学习概率自动机：状态可区分性的研究
DOI：
10.1016/j.tcs.2012.10.009
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Ricard Gavaldà
中科院分区：
文献类型：
--
作者：
Borja Balle;J. Castro;Ricard Gavaldà
用于学习PDFA的已知算法只能在目标机器的所谓可扩展性μ中以时间多项式运行，除了状态的数量和通常的精度和置信度参数之外。我们表明，μ的依赖是必要的，在最坏的情况下，每个算法的结构类似于现有的。作为一种技术工具，本文定义了一种新的统计查询算法L∞-查询.我们展示了如何模拟L∞-查询使用经典的统计学习，并表明，已知的PAC算法学习PDFA实际上是统计查询算法。我们的结果包括一个下界：每个学习PDFA的算法都必须对每个c>0进行Ω（1/μ1−c）查询。最后，一个自适应算法，PAC学习w.r.t.另一种复杂性的措施进行了说明。这在许多情况下会产生更好的效率，同时保留相同的不可避免的最坏情况行为。我们的算法需要更少的输入参数比以前现有的，并有一个更好的样本界。
Known algorithms for learning PDFA can only be shown to run in time polynomial in the so-called distinguishability μ of the target machine, besides the number of states and the usual accuracy and confidence parameters. We show that the dependence on μ is necessary in the worst case for every algorithm whose structure resembles existing ones. As a technical tool, a new variant of Statistical Queries termed L∞-queries is defined. We show how to simulate L∞-queries using classical Statistical Queries and show that known PAC algorithms for learning PDFA are in fact statistical query algorithms. Our results include a lower bound: every algorithm to learn PDFA with queries using a reasonable tolerance must make Ω(1/μ1−c) queries for every c>0. Finally, an adaptive algorithm that PAC-learns w.r.t. another measure of complexity is described. This yields better efficiency in many cases, while retaining the same inevitable worst-case behavior. Our algorithm requires fewer input parameters than previously existing ones, and has a better sample bound.