Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.jcss.2012.03.002
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
Source: 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. https://doi.org/10.1016/j.jcss.2012.03.002
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
URI: http://scholarbank.nus.edu.sg/handle/10635/43255
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)

66
checked on Dec 16, 2017

Google ScholarTM

Check

Altmetric


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