Learning with ordinal-bounded memory from positive data

Abstract

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 kN, 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 Kleenes universal ordinal notation system O. To each ordinal notation in O 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 Kleenes system, then learners that extend their example memory at most b times can learn strictly more than learners that can extend their example memory at most a times. For notations for ordinals below ω2 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. © 2012 Elsevier Inc.