Please use this identifier to cite or link to this item:
Title: Variations on U-shaped learning
Authors: Carlucci, L.
Jain, S. 
Kinber, E.
Stephan, F. 
Issue Date: 2006
Citation: Carlucci, L., Jain, S., Kinber, E., Stephan, F. (2006). Variations on U-shaped learning. Information and Computation 204 (8) : 1264-1294. ScholarBank@NUS Repository.
Abstract: The paper deals with the following problem: is returning to wrong conjectures necessary to achieve full power of algorithmic learning? Returning to wrong conjectures complements the paradigm of U-shaped learning when a learner returns to old correct conjectures. We explore our problem for classical models of learning in the limit from positive data: explanatory learning (when a learner stabilizes in the limit on a correct grammar) and behaviourally correct learning (when a learner stabilizes in the limit on a sequence of correct grammars representing the target concept). In both cases we show that returning to wrong conjectures is necessary to achieve full learning power. In contrast, one can modify learners (without losing learning power) such that they never show inverted U-shaped learning behaviour, that is, never return to old wrong conjecture with a correct conjecture in-between. Furthermore, one can also modify a learner (without losing learning power) such that it does not return to old "overinclusive" conjectures containing non-elements of the target language. We also consider our problem in the context of vacillatory learning (when a learner stabilizes on a finite number of correct grammars) and show that each of the following four constraints is restrictive (that is, reduces learning power): the learner does not return to old wrong conjectures; the learner is not inverted U-shaped; the learner does not return to old overinclusive conjectures; the learner does not return to old overgeneralizing conjectures. We also show that learners that are consistent with the input seen so far can be made decisive: on any text, they do not return to any old conjectures-wrong or right. © 2006 Elsevier Inc. All rights reserved.
Source Title: Information and Computation
ISSN: 08905401
DOI: 10.1016/j.ic.2006.04.001
Appears in Collections:Staff Publications

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


checked on Oct 16, 2018


checked on Oct 16, 2018

Page view(s)

checked on Aug 3, 2018

Google ScholarTM



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