Mikhail Moshkov
King Abdullah University of Science and Technology, Saudi Arabia
Title: Multi-stage optimization of decision trees: two applications
Biography
Biography: Mikhail Moshkov
Abstract
Multi-stage optimization of decision trees is one of the extensions of dynamic programming. It allows us to optimize decision trees sequentially relative to a number of cost functions. We will discuss two applications of this technique: finding of minimum average depth of a decision tree for sorting eight elements and creation of an algorithm for reduct minimization. The question about minimum average depth of a decision tree for sorting of eight elements was open since 1968 and was considered by D Knuth in his famous book The Art of Computer Programming, Volume 3, Sorting and Searching. Reduct is a minimal set of conditional attributes in a decision table which gives the same information about decision attribute as the whole set of conditional attributes. The problem of reduct minimization is closely connected with the feature selection. The end of the presentation is devoted to the introduction to KAUST