On Optimal Learning Algorithms for Multiplicity Automata
On Optimal Learning Algorithms for Multiplicity Automata
复制标题
多重自动机的最优学习算法
DOI：
10.1007/11776420_16
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Hanna Mazzawi
中科院分区：
文献类型：
--
作者：
Laurence Bisht;N. Bshouty;Hanna Mazzawi
我们研究多项式时间学习算法的多重自动机（MA）和多重自动机功能（MAF），最大限度地减少访问一个或多个以下资源：等价查询，成员查询或算术运算领域。这是特别有趣的，当访问上述资源中的一个或多个是显着更昂贵的比others.We应用新的代数方法的基础上矩阵Theory简化算法和证明其正确性。我们提高了问题的算法复杂性，并认为它几乎是最优的。然后我们证明了最小等价查询数的紧界和成员查询数的几乎（上拓扑因子）紧界。
We study polynomial time learning algorithms for Multiplicity Automata (MA) and Multiplicity Automata Function (MAF) that minimize the access to one or more of the following resources: Equivalence queries, Membership queries or Arithmetic operations in the field. This is in particular interesting when access to one or more of the above resources is significantly more expensive than the others.We apply new algebraic approach based on Matrix Theory to simplify the algorithms and the proofs of their correctness. We improve the arithmetic complexity of the problem and argue that it is almost optimal. Then we prove tight bound for the minimal number of equivalence queries and almost (up tologfactor) tight bound for the number of membership queries.