Dynamic programming extensions for decision and inhibitory tree study

---

Mikhail Moshkov

King Abdullah University of Science and Technology, Saudi Arabia

: J Comput Eng Inf Technol

Abstract

---

We discuss extensions of dynamic programming approach to the study of decision and inhibitory trees. Decision trees are used as algorithms for problem solving, as a way for knowledge representation, and as classifiers. Inhibitory trees, in which terminal nodes are labeled by expressions “≠ decision”, can for some decision tables represent more knowledge from these tables than decision trees. The created extensions of dynamic programming allow us, (i) to make multi-stage optimization of decision trees relative to different criteria, (ii) to describe the set of optimal trees and count the number of these trees, (iii) to find the set of Pareto optimal points for two criteria and describe relationships between these criteria. We show how the mentioned tools can be used for the study of inhibitory trees. The results include the minimization of average depth for decision trees sorting eight elements, finding of tight upper bounds on the depth of decision trees for diagnosis of constant faults in combinatorial circuits, existence of optimal relative to a number of criteria, simultaneously, decision trees for Boolean functions, investigation of time-memory tradeoff for decision trees for corner point detection, study of relationships between maximum length and number of decision rules induced from decision trees, study of accuracy-size tradeoff for decision trees which allows us to construct trees that, as classifiers, outperform often trees constructed by CART.

Biography

---

Mikhail Moshkov is a Professor in the CEMSE Division at King Abdullah University of Science and Technology, Saudi Arabia since October, 2008. He earned a Master’s Degree from Nizhni Novgorod State University, received his Doctorate from Saratov State University, and Habilitation from Moscow State University. From 1977 to 2004, he was with Nizhni Novgorod State University. Since 2003, he worked in Poland at the Institute of Computer Science, University of Silesia, and since 2006 also at the Katowice Institute of Information Technologies. His main areas of research are Complexity of Algorithms, Combinatorial Optimization and Machine Learning. He is the author or co-author of five research monographs published by Springer.

Email: mikhail.moshkov@kaust.edu.sa