Learning Optimal Decision Trees

All currently known algorithms for learning decision trees are based on the paradigm of heuristic top-down induction. Although the results of these algorithms are usually good, there is no guarantee that the resulting trees are really as small, accurate or shallow as possible. In this paper, we introduce an algorithm for inducing the smallest most accurate decision tree on training data. This algorithm allows us to find out how well heuristic algorithms approximate truly optimal decision trees. 1