https://cemse.kaust.edu.sa/events/Pages/PhD-Defense--Decision-and-Inhibitory-Trees-for-Decision-Tables-with-Many-valued-Decisions-By-Mohammad-Mohiuddin-Aza-125204.aspx
PhD defense of our colleague Mohammad Azad.
Thesis title: Decision and Inhibitory Trees for Decision Tables with Many-valued Decisions.
Decision trees are one of the most commonly used tools in decision analysis, knowledge representation, machine learning, etc., for its simplicity and interpretability. We consider an extension of dynamic programming approach to process the whole set of decision trees for the given decision table which was previously only attainable by brute-force algorithms. We study decision tables with many-valued decisions (each row may contain multiple decisions) because they are more reasonable models of data in many cases. To address this problem in a broad sense, we consider not only decision trees but also inhibitory trees where terminal nodes are labeled with "≠ decision''. Inhibitory trees can sometimes describe more knowledge from datasets than decision trees. As for cost functions, we consider depth or average depth to minimize time complexity of trees, and the number of nodes or the number of terminal, or nonterminal nodes to minimize the space complexity of trees. We investigate the multi-stage optimization of trees relative to a number of cost functions, and also the possibility to describe the whole set of strictly optimal trees. Furthermore, we study the bi-criteria optimization cost vs. cost and cost vs. uncertainty for decision trees, and cost vs. cost and cost vs. completeness for inhibitory trees. The most interesting application of the developed technique is the creation of multi-pruning and restricted multi-pruning approaches which are useful for knowledge representation and prediction. The experimental results show that decision trees constructed by these approaches can often outperform the decision trees constructed by the CART algorithm. Another application includes the comparison of 12 greedy heuristics for single- and bi-criteria optimization (cost vs. cost) of trees. We also study the three approaches (decision tables with many-valued decisions, decision tables with most common decisions, and decision tables with generalized decisions) to handle inconsistency of decision tables. We also analyze the time complexity of decision and inhibitory trees over arbitrary sets of attributes represented by information systems in the frameworks of local (when we can use in trees only attributes from problem description) and global (when we can use in trees arbitrary attributes from the information system) approaches.
Biography: Mohammad Azad is a Ph.D. candidate in Computer Science at KAUST. His main research interest is in the discrete and combinatorial optimization of decision trees and its applications in machine learning. He worked in the extensions of dynamic programming for the optimization of different parameters of the decision and inhibitory trees, decision rules and tests which has resulted in several peer-reviewed publications in many conferences and journals. He gave a plenary speech as one of the authors of the best-contributed article “Restricted multi-pruning of decision trees” in Machine Learning and Data Analytics Symposium (MLDAS) 2016.