Related Experiment Video
Updated: Jul 12, 2025
07:05
Operant Protocols for Assessing the Cost-benefit Analysis During Reinforced Decision Making by Rodents
Published on: September 10, 2018
6.0K
On Complexity of Deterministic and Nondeterministic Decision Trees for Conventional Decision Tables from Closed
Azimkhon Ostonov1, Mikhail Moshkov1
1Computer, Electrical and Mathematical Sciences & Engineering Division and Computational Bioscience Research Center, King Abdullah University of Science and Technology (KAUST), Thuwal 23955-6900, Saudi Arabia.
Entropy (Basel, Switzerland)
|October 28, 2023
Summary
This study examines decision trees derived from decision tables. We analyze how attribute complexity impacts the minimum complexity of deterministic and nondeterministic decision trees.
Area of Science:
- Computer Science
- Decision Theory
- Algorithmic Complexity
Background:
- Decision tables are fundamental in representing complex decision-making processes.
- Understanding the complexity of decision trees is crucial for efficient algorithms.
- Previous research has explored decision tree optimization, but the impact of closed classes of decision tables requires further investigation.
Purpose of the Study:
- To analyze the relationship between attribute complexity and the minimum complexity of deterministic and nondeterministic decision trees.
- To investigate the correlation between the minimum complexity of deterministic and nondeterministic decision trees.
- To extend the understanding of decision table properties within closed classes.
Main Methods:
- Consideration of conventional decision tables belonging to classes closed under attribute removal and decision modification.
- Analysis of the dependence of decision tree complexity on attribute set complexity.
- Comparative study of the minimum complexity of deterministic versus nondeterministic decision trees.
Main Results:
- Established dependencies between the complexity of attribute sets and the minimum complexity of both deterministic and nondeterministic decision trees.
- Quantified the relationship between the minimum complexity of deterministic decision trees and their nondeterministic counterparts.
- Demonstrated that nondeterministic decision trees can represent sets of true decision rules covering all table rows.
Conclusions:
- The complexity of decision trees is significantly influenced by the complexity of the underlying attribute sets within closed classes of decision tables.
- The study provides insights into the trade-offs between deterministic and nondeterministic decision tree representations.
- Findings contribute to a deeper theoretical understanding of decision table analysis and decision tree construction.
Keywords:
closed classes of decision tablesdeterministic decision treesnondeterministic decision treesMore Related Videos
12:18A Machine Learning Approach to Design an Efficient Selective Screening of Mild Cognitive Impairment
Published on: January 11, 2020
7.6K
07:42An Automated T-maze Based Apparatus and Protocol for Analyzing Delay- and Effort-based Decision Making in Free Moving Rodents
Published on: August 2, 2018
13.7K
Related Concept Videos
01:14Decision Making: Traditional Method
4.0K
The process of hypothesis testing based on the traditional method includes calculating the critical value, testing the value of the test statistic using the sample data, and interpreting these values.
First, a specific claim about the population parameter is decided based on the research question and is stated in a simple form. Further, an opposing statement to this claim is also stated. These statements can act as null and alternative hypotheses, out of which a null hypothesis would be a...
First, a specific claim about the population parameter is decided based on the research question and is stated in a simple form. Further, an opposing statement to this claim is also stated. These statements can act as null and alternative hypotheses, out of which a null hypothesis would be a...
4.0K
01:29Contingency Table
2.5K
A contingency table provides a way of portraying data that can facilitate calculating probabilities. It is a method of displaying a frequency distribution as a table with rows and columns to show how two variables may be dependent (contingent) upon each other; The table helps determine conditional probabilities quite quickly and can help systematically organize, analyze and quantify data. The table displays sample values concerning two variables that may be dependent or contingent on one...
2.5K
01:20Decision Making
119
Decision-making is a fundamental cognitive process that involves evaluating alternatives and selecting among them. This process can range from simple choices, such as deciding what to wear, to complex decisions, like choosing a major in college or a career path. The complexity of the decision often dictates the approach we use, which can be broadly categorized into two types: automatic and controlled decision-making.
Automatic decision-making is fast, intuitive, and relies on gut feelings...
Automatic decision-making is fast, intuitive, and relies on gut feelings...
119
01:26Constraints and Statical Determinacy
616
In structural engineering, the equilibrium of a system is not only determined by its equations of equilibrium but also with the help of constraints. Constraints refer to restrictions on the motion of a system. The proper combinations of constraints can minimize the total number of constraints needed to maintain a system in mechanical equilibrium. When this happens, the system is said to be statically determinate. For such systems, the unknown reaction supports can be estimated using equilibrium...
616
01:19Survival Tree
88
Survival trees are a non-parametric method used in survival analysis to model the relationship between a set of covariates and the time until an event of interest occurs, often referred to as the "time-to-event" or "survival time." This method is particularly useful when dealing with censored data, where the event has not occurred for some individuals by the end of the study period, or when the exact time of the event is unknown.
Building a Survival Tree
Constructing a...
Building a Survival Tree
Constructing a...
88
01:34Woodward–Hoffmann Selection Rules and Microscopic Reversibility
3.1K
Electrocyclic reactions, cycloadditions, and sigmatropic rearrangements are concerted pericyclic reactions that proceed via a cyclic transition state. These reactions are stereospecific and regioselective. The stereochemistry of the products depends on the symmetry characteristics of the interacting orbitals and the reaction conditions. Accordingly, pericyclic reactions are classified as either symmetry-allowed or symmetry-forbidden. Woodward and Hoffmann presented the selection criteria for...
3.1K