Please use this identifier to cite or link to this item: https://scholarbank.nus.edu.sg/handle/10635/113931
Title: Consistent partial identification
Authors: Jain, S. 
Stephan, F. 
Issue Date: 2009
Citation: Jain, S.,Stephan, F. (2009). Consistent partial identification. COLT 2009 - The 22nd Conference on Learning Theory. ScholarBank@NUS Repository.
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.
Source Title: COLT 2009 - The 22nd Conference on Learning Theory
URI: http://scholarbank.nus.edu.sg/handle/10635/113931
Appears in Collections:Staff Publications

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

Page view(s)

66
checked on Jan 25, 2020

Google ScholarTM

Check


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