2022/03/16 by Mohammad Azad, Igor Chikalov, Azad, Mohammad +7
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Neural Networks and Applications #Rough Sets and Fuzzy Logic #Statistical and Computational Modeling
paper · pdf · doi:10.48550/arxiv.2203.08894
openalex publication_date 2022/03/16 · openalex created_date 2022/05/05 · openalex updated_date 2026/07/28
In this paper, we consider decision trees that use both queries based on one\nattribute each and queries based on hypotheses about values of all attributes.\nSuch decision trees are similar to ones studied in exact learning, where not\nonly membership but also equivalence queries are allowed. We investigate the\nproblem of recognition of monotone Boolean functions with n variables, n=2,\n\…, 4, and the problem of sorting n pairwise different elements from\nlinearly ordered set, n=3, \…, 6. For each of these problems, we compare\nthe complexity of different types of optimal (relative to the depth or the\nnumber of realizable nodes) decision trees with hypotheses. We also study the\ncomplexity of decision trees constructed by entropy-based greedy algorithm and\nanalyze the length of decision rules derived from these trees.\n