Optimal all-subsets splits for categorical features in classification tree learning

Handling categorical features with many categories adequately in classification trees remains an unsolved problem. Most training algorithms approach a split over a categorical feature via either a one-hot encoding, a label embedding or a multiway split, all of which have significant disadvantages on the resulting tree. The ideal split would choose optimally among all possible category subsets, but this is exponentially costly on the number of categories. We provide a solution to this long-standing problem by 1) using as tree learning not greedy recursive partitioning (as in CART) but tree alternating optimization, and 2) showing that in the latter case the update of a categorical split can be done exactly in time linear on the number of categories. This results in trees that are far smaller (thus more interpretable) and with higher classification accuracy, as demonstrated in our experiments.