On learning of functions refutably
On learning of functions refutably
复制标题
DOI：
10.1016/s0304-3975(02)00421-8
复制
发表时间：
2003-04-04
影响因子：
1.1
通讯作者：
Zeugmann, T
中科院分区：
文献类型：
--
作者：
Jain, S;Kinber, E;Zeugmann, T
递归函数的可反驳非正式学习意味着对于每个递归函数，学习机要么学习这个函数，要么反驳它，即发出信号表明它不能学习它。我们发现，相应类型的学习反驳是严格增加的权力，其中最严格的原来是显着的拓扑和算法的丰富性。此外，所有这些类型都在工会下关闭，尽管强度不同。此外，这些类型被证明是不同的，就其内在的复杂性;其中两个不包含函数类是“最难”学习，而第三个。此外，我们提出了这些类型的学习可反驳的几个特征。其中一些特征明确了相应的学习机的反驳能力从何而来以及如何实现。对于具有可反驳异常的学习，我们证明了几个来自标准学习的结果是可反驳的。由此，我们推导出一些可反驳学习的层次结构。最后，我们证明，在一般情况下，不能贸易更严格的可反驳性限制更自由的学习标准。(C)2002 Elsevier Science B. V.保留所有权利。
Learning of recursive functions refutably informally means that for every recursive function, the learning machine has either to learn this function or to refute it, that is to signal that it is not able to learn it. Three modi of making precise the notion of refuting are considered. We show that the corresponding types of learning refutably are of strictly increasing power, where already the most stringent of them turns out to be of remarkable topological and algorithmical richness. Furthermore, all these types are closed under union, though in different strengths. Also, these types are shown to be different with respect to their intrinsic complexity; two of them do not contain function classes that are "most difficult" to learn, while the third one does. Moreover, we present several characterizations for these types of learning refutably. Some of these characterizations make clear where the refuting ability of the corresponding learning machines comes from and how it can be realized, in general.For learning with anomalies refutably, we show that several results from standard learning without refutation stand refutably. From this we derive some hierarchies for refutable learning. Finally, we prove that in general one cannot trade stricter refutability constraints for more liberal learning criteria. (C) 2002 Elsevier Science B.V. All rights reserved.