Browsing by Author "YE, Nan"

Now showing 1 - 2 of 2
  • No Thumbnail Available
    Item
    Prescribed Learning of Indexed Families
    (2007-09-21T01:27:00Z) JAIN, Sanjay; STEPHAN, Frank; YE, Nan
    This work extends studies of Angluin, Lange and Zeugmann on how learnability of a language class depends on the hypotheses space used by the learner. While previous studies mainly focused on the case where the learner chooses a particular hypotheses space, the goal of this work is to investigate the case where the learner has to cope with all possible hypotheses spaces. In that sense, the present work combines the approach of Angluin, Lange and Zeugmann with the question of how a learner can be synthesized. The investigation for the case of uniformly recursively enumerable classes has been presented by Jain, Stephan and Ye at the conference Algorithmic Learning Theory 2007. This paper investigates the case for indexed families and gives a special attention to the notions of conservative and non U-shaped learning.
  • No Thumbnail Available
    Item
    Prescribed Learning of R.E. Classes
    (2007-10-11) JAIN, Sanjay; STEPHAN, Frank; YE, Nan
    This work extends studies of Angluin, Lange and Zeugmann on the dependence of learning on the hypotheses space chosen for the class. In subsequent investigations, uniformly recursively enumerable hypotheses spaces have been considered. In the present work, the following four types of learning are distinguished: class-comprising (where the learner can choose a uniformly recursively enumerable superclass as hypotheses space), class-preserving (where the learner has to choose a uniformly recursively enumerable hypotheses space of the same class), prescribed (where there must be a learner for every uniformly recursively enumerable hypotheses space of the same class) and uniform (like prescribed, but the learner has to be synthesized effectively from an index of the hypothesis space). While for explanatory learning, these four types of learnability coincide, some or all are different for other learning criteria. For example, for conservative learning, all four types are different. Several results are obtained for vacillatory and behaviourally correct learning; three of the four types can be separated, however the relation between prescribed and uniform learning remains open. It is also shown that every (not necessarily uniformly recursively enumerable) behaviourally correct learnable class has a prudent learner, that is, a learner using a hypotheses space such that it learns every set in the hypotheses space. Moreover the prudent learner can be effectively built from any learner for the class.