Confident and Consistent Partial Learning of Recursive Functions
No Thumbnail Available
Date
2014-07-10
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Partial learning is a criterion where the learner in nitely often outputs
one correct conjecture while every other hypothesis is issued only nitely often. This
paper addresses two variants of partial learning in the setting of inductive inference
of functions: rst, con dent partial learning requires that the learner also on those
functions which it does not learn, singles out exactly one hypothesis which is output
in nitely often; second, essentially class consistent partial learning is partial learning
with the additional constraint that on the functions to be learnt, almost all hypothe-
ses issued are consistent with all the data seen so far. The results of the present work
are that con dent partial learning is more general than explanatory learning, incom-
parable with behaviourally correct learning and closed under union; essentially class
consistent partial learning is more general than behaviourally correct learning and
incomparable with con dent partial learning. Furthermore, it is investigated which
oracles permit to learn all recursive functions under these criteria: for con dent par-
tial learning, some non-high oracles are omniscient; for essentially class consistent
partial learning, all PA-complete and all oracles of hyperimmune Turing degree are
omniscient.