On the Depth of Decision Trees with Hypotheses

Area of Science:

• Computer Science
• Artificial Intelligence
• Machine Learning

Background:

• Decision trees are fundamental in machine learning for classification and prediction.
• Infinite binary information systems present unique challenges for decision tree construction.
• Rough set theory, test theory, and exact learning offer frameworks for analyzing complex data.

Purpose of the Study:

• To investigate decision tree complexity over infinite binary information systems.
• To define and analyze Shannon-type functions characterizing decision tree depth.
• To classify information systems based on decision tree construction complexity.

Main Methods:

• Utilizing concepts from rough set theory, test theory, and exact learning.
• Defining problems over information systems and analyzing worst-case minimum decision tree depth.
• Studying three Shannon-type functions representing attribute, hypothesis, and combined usage.

Main Results:

• Decision trees using only attributes exhibit logarithmic or linear behavior.
• Decision trees using hypotheses or both attributes and hypotheses show constant, logarithmic, or linear behavior.
• Infinite binary information systems were classified into four complexity classes based on function behavior.

Conclusions:

• The complexity of decision trees in infinite binary information systems is well-defined by Shannon-type functions.
• The classification into four complexity classes provides a structured understanding of computational requirements.
• This research contributes to the theoretical foundations of decision tree learning in complex data scenarios.