论文标题
无限概念家庭的精确学习
Exact learning for infinite families of concepts
论文作者
论文摘要
在本文中，基于精确学习，测试理论和粗糙集理论的结果，我们研究了任意无限的概念家族，每个概念都由一组无限的元素和该集合的无限子集组成，称为概念。我们考虑了一个由有限数量的元素描述的概念家族的问题的概念：对于给定的概念，我们应该认识到所考虑的哪些元素属于此概念。作为解决问题的算法，我们考虑五种类型的决策树：（i）使用会员查询，（ii）使用等价查询，（iii）使用会员资格和等价查询，（iv）使用适当的等价查询，以及（v）使用会员资格和适当的等价质量。作为时间的复杂性，我们研究了决策树的深度。在最坏的情况下，随着问题描述中元素数量的增长，第一种类型的决策树的最小深度要么随着对数或线性线性增长，并且每种类型的决策树的最小深度都以上述为界，要么以常数为界，要么以对数或线性的方式成长。获得的结果使我们能够区分无限概念家族的七个复杂性类别。
In this paper, based on results of exact learning, test theory, and rough set theory, we study arbitrary infinite families of concepts each of which consists of an infinite set of elements and an infinite set of subsets of this set called concepts. We consider the notion of a problem over a family of concepts that is described by a finite number of elements: for a given concept, we should recognize which of the elements under consideration belong to this concept. As algorithms for problem solving, we consider decision trees of five types: (i) using membership queries, (ii) using equivalence queries, (iii) using both membership and equivalence queries, (iv) using proper equivalence queries, and (v) using both membership and proper equivalence queries. As time complexity, we study the depth of decision trees. In the worst case, with the growth of the number of elements in the problem description, the minimum depth of decision trees of the first type either grows as a logarithm or linearly, and the minimum depth of decision trees of each of the other types either is bounded from above by a constant or grows as a logarithm, or linearly. The obtained results allow us to distinguish seven complexity classes of infinite families of concepts.
