Learning with ordinal-bounded memory from positive data

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 k∈Nk∈N, 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 OO. To each ordinal notation in OO 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 “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ω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.

► We study iterative learners with a constructive ordinal bound on their finite memory.
► The larger the ordinal the stronger the learning power.
► For ordinals larger than ω2ω2 the learning criteria depend on the choice of notation.
► Erasing elements from memory without replacing them can increase learning power.