Optimal Trees

9/15/16 | 4:15pm | E51-315 
Reception to follow.

Abstract: Classification and Regression Trees (CART) were introduced by Breiman et al. in 1984 and is one of the most widely used methods in Machine Learning. As an indication of impact CART has attracted approximately 30,000 citations in Google Scholar. The method constructs a decision tree using a greedy algorithm. Leo Breiman commented in 1984: "Finally, another problem frequently mentioned (by others, not by us) is that the tree procedure is only one-step optimal and not overall optimal. ... If one could search all possible partitions ... the two results might be quite different. This issue is analogous to the familiar question in linear regression of how well the stepwise procedures do as compared with `best subsets' procedures. We do not address this problem. At this stage of computer technology, an overall optimal tree growing procedure does not appear feasible for any reasonably sized dataset." Motivated by the astonishing speedups in Mixed-Integer Optimization solvers over the past 25 years, we present Optimal Classification Trees, a novel formulation of the decision tree problem using modern MIO techniques that yields the optimal decision tree for axes-aligned splits. We also show the richness of this MIO formulation by adapting it to give Optimal Classification Trees with Hyperplanes that generates optimal decision trees with multivariate splits. We develop high-performance heuristics for these formulations that offer significant improvements over traditional greedy approaches and run in comparable times. We show in a large and diverse collection of instances that our optimal trees improve substantially over CART and related methods such as Random Forests.





Jack Dunn

ORC Doctoral Student

Bio: Jack Dunn is a PhD candidate in the Operations Research Center at MIT. Before joining MIT, he earned a B.Eng. in Engineering Science with First Class Honours from the University of Auckland in New Zealand. His research focuses on the intersection of Optimization with Machine Learning & Statistics, with particular emphasis on the application of modern optimization techniques to classical statistical problems.

Event Time: 

2016 - 16:15