论文标题
精确的学习和测试理论
Exact learning and test theory
论文作者
论文摘要
在本文中，基于精确学习和测试理论的结果，我们研究了任意的无限二进制信息系统，每个信息系统由一组无限的元素和一组无限的元素组成，并在一组元素集中定义的一组无限的元素（属性）组成。我们考虑了信息系统上问题的概念，该概念由有限数量的属性描述：对于给定的元素，我们应该识别这些属性的值。作为解决问题的算法，我们考虑两种类型的决策树：（i）仅使用适当的假设（来自精确学习的适当等价查询的类似物），以及（ii）使用属性和适当的假设。作为时间的复杂性，我们研究了决策树的深度。在最坏的情况下，随着问题描述中属性数量的增长，两种类型的决策树的最小深度要么以上面的限制，要么以对数或线性形式增长。基于这些属性和任意假设获得的这些结果和结果，我们将所有无限二进制信息系统的集合分为七个复杂性类别。
In this paper, based on results of exact learning and test theory, we study arbitrary infinite binary information systems each of which consists of an infinite set of elements and an infinite set of two-valued functions (attributes) defined on the set of elements. We consider the notion of a problem over information system, which is described by a finite number of attributes: for a given element, we should recognize values of these attributes. As algorithms for problem solving, we consider decision trees of two types: (i) using only proper hypotheses (an analog of proper equivalence queries from exact learning), and (ii) using both attributes and proper hypotheses. As time complexity, we study the depth of decision trees. In the worst case, with the growth of the number of attributes in the problem description, the minimum depth of decision trees of both types either is bounded from above by a constant or grows as a logarithm, or linearly. Based on these results and results obtained earlier for attributes and arbitrary hypotheses, we divide the set of all infinite binary information systems into seven complexity classes.
