Show simple item record

Generalized and Scalable Optimal Sparse Decision Trees

dc.contributor.advisor Rudin, Cynthia
dc.contributor.author Zhong, Chudi
dc.date.accessioned 2020-06-09T17:45:23Z
dc.date.available 2020-12-01T09:17:12Z
dc.date.issued 2020
dc.identifier.uri https://hdl.handle.net/10161/20774
dc.description Master's thesis
dc.description.abstract <p>Decision tree optimization is notoriously difficult from a computational perspective but essential for the field of interpretable machine learning. Despite efforts over the past 40 years, only recently have optimization breakthroughs been made that have allowed practical algorithms to find \textit{optimal} decision trees. These new techniques have the potential to trigger a paradigm shift where it is possible to construct sparse decision trees to efficiently optimize a variety of objective functions without relying on greedy splitting and pruning heuristics that often lead to suboptimal solutions. The contribution in this work is to provide a general framework for decision tree optimization that addresses the two significant open problems in the area: treatment of imbalanced data and fully optimizing over continuous variables. We present techniques that produce optimal decision trees over a variety of objectives including F-score, AUC, and partial area under the ROC convex hull. We also introduce a scalable algorithm that produces provably optimal results in the presence of continuous variables and speeds up decision tree construction by several orders of magnitude relative to the state-of-the art.</p>
dc.subject Statistics
dc.subject Computer science
dc.subject Decision Trees
dc.subject Interpretable Model
dc.subject Operations Research
dc.subject Optimization
dc.title Generalized and Scalable Optimal Sparse Decision Trees
dc.type Master's thesis
dc.department Statistical Science
duke.embargo.months 5.7534246575342465


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record