Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound
Computing an optimal classification tree that provably maximizes training performance within a given size limit, is NP-hard, and in practice, most state-of-the-art methods do not scale beyond computing optimal trees of depth three. Therefore, most methods rely on a coarse binarization of continuous features to maintain scalability. We propose a novel algorithm that optimizes trees directly on the continuous feature data using dynamic programming with branch-and-bound. We develop new pruning techniques that eliminate many sub-optimal splits in the search when similar to previously computed splits and we provide an efficient subroutine for computing optimal depth-two trees. Our experiments demonstrate that these techniques improve runtime by one or more orders of magnitude over state-of-the-art optimal methods and improve test accuracy by 5% over greedy heuristics.
Code (2)
Tasks
BinarizationMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
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 chall…
Combinatorial OptimizationA GPU-Accelerated Moving-Horizon Algorithm for Training Deep Classification Trees on Large Datasets
Decision trees are essential yet NP-complete to train, prompting the widespread use of heuristic methods such as CART, which suffers from sub-optimal performance due to its greedy nature. Recently, breakthroughs in findi…
GPUOn multivariate randomized classification trees: $l_0$-based sparsity, VC~dimension and decomposition methods
Decision trees are widely-used classification and regression models because of their interpretability and good accuracy. Classical methods such as CART are based on greedy approaches but a growing attention has recently …
Classificationfeature selectionSparsity in Optimal Randomized Classification Trees
Decision trees are popular Classification and Regression tools and, when small-sized, easy to interpret. Traditionally, a greedy approach has been used to build the trees, yielding a very fast training process; however, …
ClassificationGeneral ClassificationRS-ORT: A Reduced-Space Branch-and-Bound Algorithm for Optimal Regression Trees
Mixed-integer programming (MIP) has emerged as a powerful framework for learning optimal decision trees. Yet, existing MIP approaches for regression tasks are either limited to purely binary features or become computatio…