Learning classes of approximations to non-recursive functions
Learning classes of approximations to non-recursive functions
复制标题
DOI：
10.1016/s0304-3975(01)00405-4
复制
发表时间：
2002-10-16
影响因子：
1.1
通讯作者：
Zeugmann, T
中科院分区：
文献类型：
--
作者：
Stephan, F;Zeugmann, T
Blum and Blum(通知。和控制28(1975)125-155)表明，停顿问题K的一类适当的递归逼近是可靠的可学习的，但无论2是否在NUM中，它都是开放的。通过证明B不在NUM中，我们解决了这个老问题，并且研究了通过逼近任意给定的递归可枚举集A而不是停顿问题K而得到的该问题的变种.所有相应的函数类U(A)仍然是可外推的，但可能不能可靠地外推学习，例如，如果A是非高的和超单纯的。Blum和Blum(1975)只考虑了由单调复杂性函数定义的K的近似。我们证明了这一条件是使可学习性独立于潜在复杂性度量的必要条件。证明了对于一类自然复杂性度量，由所有总复杂性函数生成的对K的所有递归逼近的(B)类甚至不是行为上正确的可学习的。另一方面，有一些复杂性度量使得(B)过多的波浪号是可学习的。对于所有的类(U)都得到了类似的结果，对于自然复杂性度量，B被证明是不可鲁棒学习的，但是同样存在复杂性度量使得B，更一般地，每个类U(A)都是鲁棒可学习的。这一结果扩大了对Jain等人的批评。J·康普特。系统科学。62(L)(2001)178-212)，因为由人工复杂性度量定义的类被证明是鲁棒可学的，而由自然复杂性度量定义的类是不可鲁棒学习的。(C)2002年，爱思唯尔科学公司出版。
Blum and Blum (Inform. and Control 28 (1975) 125-155) showed that a class a of suitable recursive approximations to the halting problem K is reliably EX-learnable but left it open whether or not 2 is in NUM. By showing B to be not in NUM we resolve this old problem.Moreover, variants of this problem obtained by approximating any given recursively enumerable set A instead of the halting problem K are studied. All corresponding function classes U(A) are still EX-inferable but may fail to be reliably EX-learnable, for example if A is non-high and hypersimple.Blum and Blum (1975) considered only approximations to K defined by monotone complexity functions. We prove this condition to be necessary for making learnability independent of the underlying complexity measure. The class (B) over tilde of all recursive approximations to K generated by all total complexity functions is shown to be not even behaviorally correct learnable for a class of natural complexity measures. On the other hand, there are complexity measures such that (B) over tilde is EX-learnable. A similar result is obtained for all classes (U) over tilde (A).For natural complexity measures, B is shown to be not robustly learnable, but again there are complexity measures such that B and, more generally, every class U(A) is robustly EX-learnable. This result extends the criticism of Jain et al. (J. Comput. System Sci. 62(l) (2001) 178-212), since the classes defined by artificial complexity measures turn out to be robustly learnable while those defined by natural complexity measures are not robustly learnable. (C) 2002 Published by Elsevier Science B.V.