=Paper=
{{Paper
|id=Vol-1492/Invited_01
|storemode=property
|title=Dynamic Programming Approach for Study of Decision Trees
|pdfUrl=https://ceur-ws.org/Vol-1492/Invited_01.pdf
|volume=Vol-1492
|dblpUrl=https://dblp.org/rec/conf/csp/Moshkov15
}}
==Dynamic Programming Approach for Study of Decision Trees==
<pdf width="1500px">https://ceur-ws.org/Vol-1492/Invited_01.pdf</pdf>
<pre>
Dynamic Programming Approach for Study of Decision
                     Trees

                                     Mikhail Moshkov

          Computer, Electrical, and Mathematical Sciences and Engineering Division
              King Abdullah University of Science and Technology (KAUST)
                                        Saudi Arabia
                          mikhail.moshkov@kaust.edu.sa

    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 classifiers which, for a new object given by values
of conditional attributes, define a value of the decision attribute. These extensions allow
us (i) to describe the set of optimal decision trees, (ii) to count the number of these
trees, (iii) to make sequential optimization of decision trees relative to different criteria,
(iv) to find the set of Pareto optimal points for two criteria, and (v) to describe relation-
ships between two criteria. The 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 monotone Boolean functions with at most six vari-
ables, 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 classifiers, outperform often decision trees constructed by CART.
The end of the presentation is devoted to the introduction to KAUST.

</pre>