Decision and Inhibitory Trees and Rules for Decision Tables with Many-valued Decisions

Please note the non-standard date and location of this presentation.

This will be a presentation of joint work by Mikhail Moshkov, Fawaz Alsolami, Mohammad Azad, and Igor Chikalov.

Abstract. We consider examples of problems and decision tables with many-valued decisions and discuss the difference between decision and inhibitory trees and rules for decision tables with many-valued decisions. We mention some relatively simple results obtained earlier for decision trees, tests, rules, and rule systems for binary decision tables with many-valued decisions, and generalize them to the inhibitory trees, tests, rules, and rule systems. We extend the multi-stage and bi-criteria optimization approaches to the case of decision trees and rules for decision tables with many-valued decisions and then generalize them to the case of inhibitory trees and rules. The applications of these techniques include the study of totally optimal (optimal relative to a number of criteria simultaneously) decision and inhibitory trees and rules, the comparison of greedy heuristics for tree and rule construction as single-criterion and bi-criteria optimization algorithms, the development of the restricted multi-pruning approach used in classification and knowledge representation, etc. We also study the time complexity of decision and inhibitory trees and rule systems over arbitrary sets of attributes represented by information systems.

Bio. Mikhail Moshkov is professor in the Computer, Electrical, and Mathematical Sciences and Engineering Division at King Abdullah University of Science and Technology, Thuwal, Saudi Arabia since October 1, 2008. He earned master’s degree from Nizhny Novgorod State University, received his doctorate from Saratov State University, and habilitation from Moscow State University. From 1977 to 2004, Dr. Moshkov worked in Nizhny Novgorod State University. In 2003 the Ministry of Higher Education of Russia granted him the title of Professor. Since 2003 he worked in Poland in the Institute of Computer Science, University of Silesia, and since 2006 also in the Katowice Institute of Information Technologies. His main research interests are connected with (i) study of time complexity of algorithms in such computational models as decision trees, decision rule systems and acyclic programs with applications to combinatorial optimization, fault diagnosis, pattern recognition, machine learning, data mining, and analysis of Bayesian networks, (ii) analysis and design of classifiers based on decision trees, reducts, decision rule systems, inhibitory rule systems, and lazy learning algorithms, and (iii) extensions of dynamic programming to the problems with exponential number of subproblems, to sequential optimization relative to different criteria, and to analysis of relationships among different criteria with applications to machine learning, data mining and combinatorial optimization. Dr. Moshkov is author or coauthor of seven research monographs published by Springer, over 200 journal and conference papers, and book chapters. He has directed more than 20 funded research projects (including joint projects with Intel Corporation). Dr. Moshkov was member of editorial board of Fundamenta Informaticae (IOS Press) in 1991-2009 and he is member of editorial board of LNCS Transactions on Rough Sets (Springer) since 2003. He served as a program, organizing or steering committee member in over 70 conferences, workshops and schools. Ten students received their Ph.D. under his supervision.