On multivariate randomized classification trees: $l_0$-based sparsity, VC~dimension and decomposition methods
This work addresses the computational and interpretability challenges in optimal decision trees for classification, though it is incremental with improvements in sparsity and efficiency.
The authors tackled the problem of training sparse, optimal randomized classification trees by exploring concave approximations of the l0 norm for sparsity, deriving VC dimension bounds, and proposing a decomposition method for computational efficiency. They achieved promising results on 24 datasets with sparsity methods and significantly reduced training times on larger datasets without accuracy loss.
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 been devoted to optimal decision trees. We investigate the nonlinear continuous optimization formulation proposed in Blanquero et al. (EJOR, vol. 284, 2020; COR, vol. 132, 2021) for (sparse) optimal randomized classification trees. Sparsity is important not only for feature selection but also to improve interpretability. We first consider alternative methods to sparsify such trees based on concave approximations of the $l_{0}$ ``norm". Promising results are obtained on 24 datasets in comparison with $l_1$ and $l_{\infty}$ regularizations. Then, we derive bounds on the VC dimension of multivariate randomized classification trees. Finally, since training is computationally challenging for large datasets, we propose a general decomposition scheme and an efficient version of it. Experiments on larger datasets show that the proposed decomposition method is able to significantly reduce the training times without compromising the accuracy.