Please use this identifier to cite or link to this item:
Title: Learning languages from positive data and negative counterexamples
Authors: Jain, S. 
Kinber, E.
Keywords: Computational learning theory
Inductive inference
Learning in the limit
Negative counterexamples
Issue Date: 2008
Citation: Jain, S., Kinber, E. (2008). Learning languages from positive data and negative counterexamples. Journal of Computer and System Sciences 74 (4) : 431-456. ScholarBank@NUS Repository.
Abstract: In this paper we introduce a paradigm for learning in the limit of potentially infinite languages from all positive data and negative counterexamples provided in response to the conjectures made by the learner. Several variants of this paradigm are considered that reflect different conditions/constraints on the type and size of negative counterexamples and on the time for obtaining them. In particular, we consider the models where (1) a learner gets the least negative counterexample; (2) the size of a negative counterexample must be bounded by the size of the positive data seen so far; (3) a counterexample can be delayed. Learning power, limitations of these models, relationships between them, as well as their relationships with classical paradigms for learning languages in the limit (without negative counterexamples) are explored. Several surprising results are obtained. In particular, for Gold's model of learning requiring a learner to syntactically stabilize on correct conjectures, learners getting negative counterexamples immediately turn out to be as powerful as the ones that do not get them for indefinitely (but finitely) long time (or are only told that their latest conjecture is not a subset of the target language, without any specific negative counterexample). Another result shows that for behaviorally correct learning (where semantic convergence is required from a learner) with negative counterexamples, a learner making just one error in almost all its conjectures has the "ultimate power": it can learn the class of all recursively enumerable languages. Yet another result demonstrates that sometimes positive data and negative counterexamples provided by a teacher are not enough to compensate for full positive and negative data. © 2007 Elsevier Inc. All rights reserved.
Source Title: Journal of Computer and System Sciences
ISSN: 00220000
DOI: 10.1016/j.jcss.2007.06.012
Appears in Collections:Staff Publications

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


checked on Oct 22, 2018


checked on Oct 22, 2018

Page view(s)

checked on Oct 20, 2018

Google ScholarTM



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