文章基本信息

标题：Mind Change Speed-up for Learning Languages from Positive Data
本地全文：下载
作者：Sanjay Jain ; Efim Kinber
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2012
卷号：14
页码：350-361
DOI：10.4230/LIPIcs.STACS.2012.350
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Within the frameworks of learning in the limit of indexed classes of recursive languages from positive data and automatic learning in the limit of indexed classes of regular languages (with automatically computable sets of indices), we study the problem of minimizing the maximum number of mind changes F_M(n) by a learner M on all languages with indices not exceeding n. For inductive inference of recursive languages, we establish two conditions under which F_M(n) can be made smaller than any recursive unbounded non-decreasing function. We also establish how F_M(n) is affected if at least one of these two conditions does not hold. In the case of automatic learning, some partial results addressing speeding up the function F_M(n) are obtained.
关键词：Algorithmic and automatic learning; mind changes; speedup