Learning with ordinal-bounded memory from positive data

详细信息	查看全文 | 推荐本文 |

• 作者：Lorenzo Carlucci^a ; ¹ ; ^{carlucci@di.uniroma1.it} ; Sanjay Jain^b ; ² ; ^{sanjay@comp.nus.edu.sg} ; Frank Stephan^c ; ³ ; ^{fstephan@comp.nus.edu.sg}
• 关键词：Inductive inference ; Bounded example memory ; Constructive ordinals ; Kolmogorov complexity
• 刊名：Journal of Computer and System Sciences
• 出版年：2012
• 期刊代码：186_00220000
• 类别：et
• 出版时间：September, 2012
• 卷：78
• 期：5
• 页码：1623-1636
• 文件大小：266 K

摘要

A bounded example memory learner operates incrementally and maintains a memory of finitely many data items. The paradigm is well-studied and known to coincide with set-driven learning. A hierarchy of stronger and stronger learning criteria had earlier been obtained when one considers, for each , iterative learners that can maintain a memory of at most k previously processed data items. We investigate an extension of the paradigm into the constructive transfinite. For this purpose we use Kleene始s universal ordinal notation system . To each ordinal notation in one can associate a learning criterion in which the number of times a learner can extend its example memory is bounded by an algorithmic count-down from the notation. We prove a general hierarchy result: if b is larger than a in Kleene始s system, then learners that extend their example memory 鈥渁t most b times鈥?can learn strictly more than learners that can extend their example memory 鈥渁t most a times鈥? For notations for ordinals below the result only depends on the ordinals and is notation-independent. For higher ordinals it is notation-dependent. In the setting of learners with ordinal-bounded memory, we also study the impact of requiring that a learner cannot discard an element from memory without replacing it with a new one. A learner satisfying this condition is called cumulative.