Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Features
Decision trees are one of the most useful and popular methods in the machine
learning toolbox. In this paper, we consider the problem of learning optimal
decision trees, a combinatorial optimization problem that is challenging to
solve at scale. A common approach in the literature is to use greedy
heuristics, which may not be optimal. Recently there has been significant
interest in learning optimal decision trees using various approaches (e.g.,
based on integer programming, dynamic programming) -- to achieve computational
scalability, most of these approaches focus on classification tasks with binary
features. In this paper, we present a new discrete optimization method based on
branch-and-bound (BnB) to obtain optimal decision trees. Different from
existing customized approaches, we consider both regression and classification
tasks with continuous features. The basic idea underlying our approach is to
split the search space based on the quantiles of the feature distribution --
leading to upper and lower bounds for the underlying optimization problem along
the BnB iterations. Our proposed algorithm Quant-BnB shows significant speedups
compared to existing approaches for shallow optimal trees on various real
datasets.