On 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 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.
