Please use this identifier to cite or link to this item:
Title: On learning of functions refutably
Authors: Jain, S. 
Kinber, E.
Wiehagen, R.
Zeugmann, T.
Issue Date: 4-Apr-2003
Citation: Jain, S., Kinber, E., Wiehagen, R., Zeugmann, T. (2003-04-04). On learning of functions refutably. Theoretical Computer Science 298 (1) : 111-143. ScholarBank@NUS Repository.
Abstract: Learning of recursive functions refutably informally means that for every recursive function, the learning machine has either to learn this function or to refute it, that is to signal that it is not able to learn it. Three modi of making precise the notion of refuting are considered. We show that the corresponding types of learning refutably are of strictly increasing power, where already the most stringent of them turns out to be of remarkable topological and algorithmical richness. Furthermore, all these types are closed under union, though in different strengths. Also, these types are shown to be different with respect to their intrinsic complexity; two of them do not contain function classes that are "most difficult" to learn, while the third one does. Moreover, we present several characterizations for these types of learning refutably. Some of these characterizations make clear where the refuting ability of the corresponding learning machines comes from and how it can be realized, in general. For learning with anomalies refutably, we show that several results from standard learning without refutation stand refutably. From this we derive some hierarchies for refutable learning. Finally, we prove that in general one cannot trade stricter refutability constraints for more liberal learning criteria. © 2002 Elsevier Science B.V. All rights reserved.
Source Title: Theoretical Computer Science
ISSN: 03043975
DOI: 10.1016/S0304-3975(02)00421-8
Appears in Collections:Staff Publications

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


checked on Dec 12, 2018


checked on Dec 12, 2018

Page view(s)

checked on Nov 23, 2018

Google ScholarTM



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