On Approximately Identifying Concept Classes in the Limit
On Approximately Identifying Concept Classes in the Limit
复制标题
关于极限内概念类的近似识别
DOI：
10.1007/3-540-60454-5_47
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
T. Yokomori
中科院分区：
文献类型：
--
作者：
Satoshi Kobayashi;T. Yokomori
在本文中，我们介绍了概念的各种近似，并提出了一个近似学习框架，以防目标概念可能在假设空间之外。给出了近似可辨识性的几个表征定理。特别地，我们展示了一个显著的结果，即完整数据的上最佳近似可辨识性被分解为正数据的上最佳近似可辨识性。在此基础上，给出了正数据近似可辨识性的其他一些性质，建立了近似可辨识性与准序理论和拓扑理论中一些重要概念之间的关系。本文所得到的结果实质上是关于概念类在无穷交集下的闭包性。我们还证明了存在一些有趣的示例概念类，它们具有这样的性质（包括专门的EFS），通过它们可以从正数据的极限中识别任何概念的上最佳近似。
In this paper, we introduce various kinds of approximations of a concept and propose a framework of approximate learning in case that a target concept could be outside the hypothesis space. We present some characterization theorems for approximately identifiability. In particular, we show a remarkable result that the upper-best approximate identifiability fromcompletedata is collapsed into the upper-best approximate identifiability frompositivedata. Further, some other characterizations for approximate identifiability from positive data are presented, where we establish a relationship between approximate identifiability and some important notions in quasi-order theory and topology theory. The results obtained in this paper are essentially related to the closure property of concept classes underinfiniteintersections (orinfiniteunions). We also show that there exist some interesting example concept classes with such properties (including specialized EFS's) by which an upper-best approximation ofanyconcept can be identifiable in the limit from positive data.