Please use this identifier to cite or link to this item:
Title: Learning with ordinal-bounded memory from positive data
Authors: Carlucci, L.
Jain, S. 
Stephan, F. 
Keywords: Bounded example memory
Constructive ordinals
Inductive inference
Kolmogorov complexity
Issue Date: 2012
Citation: Carlucci, L., Jain, S., Stephan, F. (2012). Learning with ordinal-bounded memory from positive data. Journal of Computer and System Sciences 78 (5) : 1623-1636. ScholarBank@NUS Repository.
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.
Source Title: Journal of Computer and System Sciences
ISSN: 00220000
DOI: 10.1016/j.jcss.2012.03.002
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

checked on Jun 29, 2020

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.