Mikhail Moshkov
King Abdullah University of Science and Technology (KAUST), Saudi Arabia
Title: Extensions of Dynamic Programming for Decision Tree Study
Biography
Biography: Mikhail Moshkov
Abstract
In the presentation, we consider extensions of dynamic programming approach to the study of decision trees as algorithms
for problem solving, as a way for knowledge extraction and representation and as classifi ers which, for a new object given
by values of conditional attributes, defi ne a value of the decision attribute. Th ese extensions allow us (1) to describe the set of
optimal decision trees, (2) to count the number of these trees, (3) to make sequential optimization of decision trees relative
to diff erent criteria, (4) to fi nd the set of Pareto optimal points for two criteria, and (5) to describe relationships between
two criteria. Th e results include the minimization of average depth for decision trees sorting eight elements (this question
was open since 1968), improvement of upper bounds on the depth of decision trees for diagnosis of 0-1-faults in read-once
combinatorial circuits, existence of totally optimal (with minimum depth and minimum number of nodes) decision trees for
Boolean functions, study of time-memory tradeoff for decision trees for corner point detection, study of relationships between
number and maximum length of decision rules derived from decision trees, study of accuracy-size tradeoff for decision trees
which allows us to construct enough small and accurate decision trees for knowledge representation and decision trees that as
classifi ers, outperform oft en decision trees constructed by CART. Th e end of the presentation is devoted to the introduction
to KAUST.