On polynomial-time learnability in the limit of strictly deterministic automata
On polynomial-time learnability in the limit of strictly deterministic automata
复制标题
严格确定性自动机限制下的多项式时间可学习性
DOI：
10.1023/a:1022615325466
复制
发表时间：
1995
期刊：
影响因子：
7.5
通讯作者：
T. Yokomori
中科院分区：
文献类型：
--
作者：
T. Yokomori
本文研究了一类语言类在极限正态下的多项式时间可学习性，并在极限正态下学习的框架下讨论了确定性有限自动机的一个子类--严格确定性自动机的学习问题.我们首先讨论的困难，皮特的定义在学习框架中的限制，从积极的数据，表明任何一类的语言与无限下降链属性是不是多项式时间学习的限制，从积极的数据。然后，我们提出了新的定义多项式时间学习的限制从积极的数据。我们表明，在我们的新定义中，类的SDA是迭代的，一贯的多项式时间学习的限制，从积极的数据。特别地，我们提出了一种学习算法，该算法从正数据中学习极限内的任何SDAM，满足以下性质：（i）更新猜想的时间至多为O（m），（ii）隐式预测错误的数量至多为O（n），其中m是所有正数据的最大长度，m是M的字母大小，n是M的大小，（iii）每个猜想仅根据先前的猜想和当前的示例计算，以及（iv）在任何阶段，猜想与迄今为止看到的样本集一致。这与以下事实形成鲜明对比，即DFA类在极限中既不能从正数据学习，也不能在极限中多项式时间学习。
This paper deals with the polynomial-time learnability of a language class in the limit from positive data, and discusses the learning problem of a subclass of deterministic finite automata (DFAs), calledstrictly deterministic automata (SDAs), in the framework of learning in the limit from positive data. We first discuss the difficulty of Pitt's definition in the framework of learning in the limit from positive data, by showing that any class of languages with an infinite descending chain property is not polynomial-time learnable in the limit from positive data. We then propose new definitions for polynomial-time learnability in the limit from positive data. We show in our new definitions that the class of SDAs is iteratively, consistently polynomial-time learnable in the limit from positive data. In particular, we present a learning algorithm that learns any SDAM in the limit from positive data, satisfying the properties that (i) the time for updating a conjecture is at most O(ℓm), (ii) the number of implicit prediction errors is at most O(ℓn), where ℓ is the maximum length of all positive data provided,m is the alphabet size ofM andn is the size ofM, (iii) each conjecture is computed from only the previous conjecture and the current example, and (iv) at any stage the conjecture is consistent with the sample set seen so far. This is in marked contrast to the fact that the class of DFAs is neither learnable in the limit from positive data nor polynomial-time learnable in the limit.