Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.ic.2007.09.001
Title: Iterative learning from positive data and negative counterexamples
Authors: Jain, S. 
Kinber, E.
Issue Date: 2007
Source: Jain, S., Kinber, E. (2007). Iterative learning from positive data and negative counterexamples. Information and Computation 205 (12) : 1777-1805. ScholarBank@NUS Repository. https://doi.org/10.1016/j.ic.2007.09.001
Abstract: A model for learning in the limit is defined where a (so-called iterative) learner gets all positive examples from the target language, tests every new conjecture with a teacher (oracle) if it is a subset of the target language (and if it is not, then it receives a negative counterexample), and uses only limited long-term memory (incorporated in conjectures). Three variants of this model are compared: when alearner receives least negative counterexamples, the ones whose sizeis boundedbythe maximum size of input seen so far, and arbitrary ones. A surprising result is that sometimes absence of bounded counterexamples can help an iterative learner whereas arbitrary counterexamples are useless. We also compare our learnability model with other relevant models of learnability in the limit, study how our model works for indexed classes of recursive languages, and show that learners in our model can work in non-U-shaped way-never abandoning the first right conjecture. © 2007 Elsevier Inc. All rights reserved.
Source Title: Information and Computation
URI: http://scholarbank.nus.edu.sg/handle/10635/39429
ISSN: 08905401
DOI: 10.1016/j.ic.2007.09.001
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

7
checked on Dec 7, 2017

WEB OF SCIENCETM
Citations

7
checked on Nov 23, 2017

Page view(s)

41
checked on Dec 11, 2017

Google ScholarTM

Check

Altmetric


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