Learning with ordinal-bounded memory from positive data
The paper generalises the paradigm of `learning in the limit with bounded example memory'. Learning in the limit models the scenario of a learner (a computable device) receiving one by one the members of a recursively enumerable (r.e.) set \(L\) of natural numbers (in any order, possibly with repetitions, each member of \(L\) being presented at least once), outputting every time a new number appears a description of an r.e.\ set, and having to eventually keep outputting a correct, fixed description of \(L\). In the paradigm of bounded example memory, the learner can only base its conjecture on the previous conjecture, the new datum \(x\) it receives, and a set \(D\) of data which have been previously received and memorised, while updating its memory to some subset of \(D\cup\{x\}\) (so the new datum can be memorised or not, and any memorised datum can still be memorised or not). The size of the memory set can be bound by an integer \(k\), and the paradigm becomes more and more stringent as \(k\) decreases; it is equivalent to the paradigm of `iterative learning' when \(k=0\) (every conjecture is then based on the last conjecture and the new datum). In the proposed generalisation, the learner has to also output representations of smaller and smaller ordinals every time the memory becomes larger than it ever was (as data can be forgotten, memory can shrink, and an ordinal representation is output not when memory increases, but when it increases beyond the largest size it ever reached).NEWLINENEWLINEThe first ordinal representation to start with is fixed to some element \(a\), giving rise to the paradigm of `\(a\)-bounded example memory' learning. The ordinal representations are determined by Kleene's system of notation \(\mathcal O\) of all constructive ordinals (a notation is the index of a program which allows one to describe -- not in a unique way -- an ordinal from a notation of its predecessor or in the case of a limit ordinal \(\alpha\), from a sequence of notations of ordinals whose limit is \(\alpha\)). For a representation \(\underline{k}\) of a natural number \(k\), \(\underline{k}\)-bounded example memory learning is equivalent to bounded example memory learning with a memory bound of \(k\). The first main result of the paper is that for any ordinal notation \(a\), \(a\)-bounded example memory learning is weaker than learning in the limit with no bound on the set of memorised data (which is equivalent to remembering all data presented, but not the order of presentation).NEWLINENEWLINEThe second main result of the paper is that given two ordinal notations \(a\) and \(b\) with \(a<_{\mathcal O}b\), then \(a\)-bounded example memory learning is weaker than \(b\)-bounded example memory learning (\(<_{\mathcal O}\) is an r.e. relation on ordinal notations that is consistent with the order relation on ordinals, that is, if \(a<_{\mathcal O}b\) then the ordinal represented by \(a\) is smaller than the ordinal represented by \(b\)). Then the authors show that if \(a\) and \(b\) are two notations for a given ordinal smaller than \(\omega^2\), then \(a\)-bounded example memory learning and \(b\)-bounded example memory learning are equivalent, reflecting the fact that notations below \(\omega^2\) are essentially unique. In contrast, for ordinals above \(\omega^2\), the concepts are notation dependent, as it is shown that for all notations \(a\), there exists a class of languages which cannot be learned by any learner using an \(a\)-bounded example memory, but which can be learnt using a \(b\)-bounded example memory where \(b\) is a notation for \(\omega^2\). The paper ends with a result on cumulative learners, which can only remove a (unique) memorised datum by letting the new datum replace it, hence memory can remain of the same size or increase by one, but it can never decrease. This is shown using techniques from Kolmogorov complexity, to be a restriction on the paradigm of bounded example memory learning for a memory bound as small as 2.
- Incremental Learning with Ordinal Bounded Example Memory
- Learning with bounded memory in stochastic models
- On Learning With Finite Memory
- Learning with Finite Memory
- Learning with partially ordered representations
- Incremental learning from positive data
- Incremental learning of approximations from positive data
- scientific article; zbMATH DE number 1670720
- Towards a map for incremental learning in the limit from positive and negative information
- Feasible Iteration of Feasible Learning Functionals
- scientific article; zbMATH DE number 3539202 (Why is no real title available?)
- scientific article; zbMATH DE number 1010621 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- Incremental concept learning for bounded data mining.
- Incremental learning from positive data
- Incremental Learning with Ordinal Bounded Example Memory
- Language identification in the limit
- Language learning from texts: Mindchanges, limited memory and monotonicity
- Learning with Temporary Memory
- On the Forms of the Predicates in the Theory of Constructive Ordinals
- On the Forms of the Predicates in the Theory of Constructive Ordinals (Second Paper)
- On the role of procrastination in machine learning
- Ordinal mind change complexity of language identification
- Toward a mathematical theory of inductive inference
This page was built for publication: Learning with ordinal-bounded memory from positive data
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q440010)
