PhD defense of our colleague Talha Amin.
Thesis title: Design and Analysis of Decision Rules Via Dynamic Programming
The areas of machine learning, data mining, and knowledge representation have many different formats used to represent information. Decision rules, amongst these formats, are the most expressive and easily-understood by humans. In this thesis, we use dynamic programming to design decision rules and analyze them. The use of dynamic programming allows us to work with decision rules in ways that were previously only possible for brute force methods. Our algorithms allow us to describe the set of all rules for a given decision table. Further, we can repeatedly reduce this set to only contain rules that are optimal with respect to selected criteria. We apply this study in order to generate small systems with short rules by simulating a greedy algorithm for the set cover problem. We also compare maximum path lengths of deterministic and non-deterministic decision trees (a non-deterministic decision tree is effectively a complete system of decision rules) with regards to boolean functions. Another area of advancement is the presentation of algorithms for constructing Pareto optimal points for rules and systems. This allows us to study the existence of ``totally optimal'' decision rules (rules that are simultaneously optimal with regards to multiple criteria). We also utilize Pareto optimal points to compare and rate greedy heuristics with regards to two criteria at once. Another application of Pareto optimal points is the study of trade-offs between cost and uncertainty allows us to find reasonable systems of decision rules that strike a balance between length and accuracy.
Biography: Talha Amin has been a student in the Computer, Electrical and Mathematical Sciences and Engineering (CEMSE) Division at KAUST since August 2009. He has completed a Master Degree and is now working towards a PhD with Dr. Mikhail Moshkov as his advisor. Prior to arriving at KAUST, Talha Amin received a BS Degree in Computer Science from the University of California, San Diego after attending from February 2007 to August 2009. His research interests encompass optimization, dynamic programming, and decision rules.
Congratulations dr. Talha Amin!
