Название: Decision Trees with Hypotheses
Автор: Mohammad Azad, Igor Chikalov
Издательство: Springer
Серия: Synthesis Lectures on Intelligent Technologies
Год: 2022
Страниц: 148
Язык: английский
Формат: pdf (true), epub
Размер: 13.9 MB

Decision trees are widely used in many areas of Computer Science and related fields as classifiers, as a means for knowledge representation, and as algorithms to solve various problems. They are studied, in particular, in test theory, rough set theory, and exact learning. These theories are closely related: attributes from rough set theory and test theory correspond to membership queries from exact learning. Exact learning studies additionally the so-called equivalence queries. In this book, we added to the model considered in test theory and rough set theory the notion of a hypothesis that allowed us to use an analog of equivalence queries and studied decision trees using various combinations of attributes, hypotheses, and proper hypotheses (an analog of proper equivalence queries).

The two main goals of this book are (i) to create tools for the experimental and theoretical study of decision trees with hypotheses and (ii) to compare these decision trees with conventional decision trees that use only queries, each of which is based on one attribute.
We got both experimental and theoretical results showing that the decision trees with hypotheses can have less complexity than the conventional decision trees. These results open up some prospects for using decision trees with hypotheses as a means for knowledge representation and as algorithms for computation of the Boolean functions.

The obtained theoretical results and tools designed for the study of decision trees with hypotheses can be helpful for researchers who use decision trees and rules in data analysis. This book can also be used for the creation of courses for graduate students.

Contents:
1. Introduction
Part I. Decision Tables
2. Main Notions
3. Dynamic Programming Algorithms for Minimization of Decision Tree Complexity
4. Construction of Optimal Decision Trees and Deriving Decision Rules from Them
5. Greedy Algorithms for Construction of Decision Trees with Hypotheses
6. Decision Trees with Hypotheses for Recognition of Monotone Boolean Functions and for Sorting
Part II. Binary Information Systems and Infinite Families of Concepts
7. Infinite Binary Information Systems. Decision Trees of Types 1, 2, and 3
8. Infinite Binary Information Systems. Decision Trees of Types 4 and 5
9. Infinite Families of Concepts