Classes with Easily Learnable Subclasses

Abstract

Let Ex denote the explanatory model of learning [ 3 ],[ 5 ]. Various more restrictive models have been studied in the literature, an example is finite identification [ 5 ]. The topic of the present paper are the natural variants (a) and (b) below of the classical question whether a given learning criteria is more restrictive than Ex-learning. (a) Does every infinite Ex-identifiable class have an infinite subclass which can be identified according to a given restrictive criterion? (b) If an infinite Exidentifiable 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.