2022/01/13 by Mikhail Moshkov, Moshkov, Mikhail
Computer Science · #Data Mining Algorithms and Applications #Machine Learning and Algorithms #Rough Sets and Fuzzy Logic #cs.AI #cs.CC #cs.LG
paper · pdf · doi:10.48550/arxiv.2201.08225
arXiv admin note: substantial text overlap with arXiv:2201.04506
arxiv created 2022/01/13 · arxiv updated 2022/01/21
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.