Consistent Partial Identification

Abstract

This study contrasts consistent partial identification with learning in the limit. Here partial identification means that the learner outputs an infinite sequence of conjectures in which one correct hypothesis occurs infinitely often and all other hypotheses occur only finitely often. Consistency means that every conjecture is correct on all the data seen so far. Learning in the limit means that the learner outputs from some time on always the same correct hypothesis. As the class of all total-recursive functions can be partially identified, the constraint of consistency has to be added to make a meaningful comparison to learning in the limit. For the version of consistency where the learner has to be defined and consistent on all inputs, it is shown that the power of the learning criterion depends on whether the function to be learnt is fed in canonical order or in arbitrary order. In the first case, consistent partial identification is incomparable to learning in the limit; in the second case, it is equivalent to consistent learning in the limit with arbitrarily fed input. Furthermore, the inference degrees of these criteria are investigated. For the case where the function is fed in canonical order, there are just two inference degrees: the trivial one which contains all oracles of hyperimmune free Turing degree and the omniscient one which contains all oracles of hyperimmune Turing degree. In the case that the function is fed in arbitrary order, the picture is more complicated and the omniscient inference degree contains exactly all oracles of high Turing degree.