TY - CHAP

T1 - Infinite Families of Concepts

AU - Azad, Mohammad

AU - Chikalov, Igor

AU - Hussain, Shahid

AU - Moshkov, Mikhail

AU - Zielosko, Beata

N1 - KAUST Repository Item: Exported on 2022-12-02

PY - 2022/11/19

Y1 - 2022/11/19

N2 - In this chapter, 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: (1) using membership queries, (2) using equivalence queries, (3) using both membership and equivalence queries, (4) using proper equivalence queries, and (5) 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 type 1 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.

AB - In this chapter, 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: (1) using membership queries, (2) using equivalence queries, (3) using both membership and equivalence queries, (4) using proper equivalence queries, and (5) 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 type 1 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.

UR - http://hdl.handle.net/10754/686118

UR - https://link.springer.com/10.1007/978-3-031-08585-7_9

U2 - 10.1007/978-3-031-08585-7_9

DO - 10.1007/978-3-031-08585-7_9

M3 - Chapter

SN - 9783031085840

SP - 113

EP - 136

BT - Decision Trees with Hypotheses

PB - Springer International Publishing

ER -