This thesis is devoted to the development of extensions of dynamic programming to the study of decision trees. The considered extensions allow us to make multi-stage optimization of decision trees relative to a sequence of cost functions, to count the number of optimal trees, and to study relationships: cost vs cost and cost vs uncertainty for decision trees by construction of the set of Pareto-optimal points for the corresponding bi-criteria optimization problem. The applications include study of totally optimal (simultaneously optimal relative to a number of cost functions) decision trees for Boolean functions, improvement of bounds on complexity of decision trees for diagnosis of circuits, study of time and memory trade-off for corner point detection, study of decision rules derived from decision trees, creation of new procedure (multi-pruning) for construction of classifiers, and comparison of heuristics for decision tree construction. Part of these extensions (multi-stage optimization) was generalized to well-known combinatorial optimization problems: matrix chain multiplication, binary search trees, global sequence alignment, and optimal paths in directed graphs.
| Date of Award | Jul 10 2016 |
|---|
| Original language | English (US) |
|---|
| Awarding Institution | - Computer, Electrical and Mathematical Sciences and Engineering
|
|---|
| Supervisor | Mikhail Moshkov (Supervisor) |
|---|
- dynamic programming
- Decision Trees
- cost functions
- bi-criteria optimization
- multi-stage optimization
- Data Mining