Please use this identifier to cite or link to this item:
Title: Classes with easily learnable subclasses
Authors: Jain, S. 
Menzel, W.
Stephan, F.
Issue Date: 2004
Citation: Jain, S., Menzel, W., Stephan, F. (2004). Classes with easily learnable subclasses. Information and Computation 190 (1) : 81-99. ScholarBank@NUS Repository.
Abstract: In this paper we study the question of whether identifiable classes have subclasses which are identifiable under a more restrictive criterion. The chosen framework is inductive inference, in particular the criterion of explanatory learning (Ex) of recursive functions as introduced by Gold [Inform. Comput. 10 (1967) 447]. Among the more restrictive criteria is finite learning where the learner outputs, on every function to be learned, exactly one hypothesis (which has to be correct). The topic of the present paper are the natural variants (a) and (b) below of the classical question whether a given learning criterion like finite learning is more restrictive than Ex-learning, (a) Does every infinite Ex-identifiable class have an infinite finitely identifiable subclass? (b) If an infinite Ex-identifiable class S has an infinite finitely identifiable subclass, does it necessarily follow that some appropriate learner Ex-identifies S as well as finitely identifies an infinite subclass of S? These questions are also treated in the context of ordinal mind change bounds. © 2004 Elsevier Inc. All rights reserved.
Source Title: Information and Computation
ISSN: 08905401
DOI: 10.1016/j.ic.2003.12.004
Appears in Collections:Staff Publications

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

Google ScholarTM



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