After searching extensively I am unable to find a detail explanation and clear example of how exhaustive bipartition search is used by LightGBM (light gradient boosting) as an 'optimal' solution for handling categorical data.
Within the documentation (https://lightgbm.readthedocs.io/en/latest/Features.html#optimal-split-for-categorical-features) we have the following:
**Optimal Split for Categorical Features** It is common to represent categorical features with one-hot encoding, but this approach is suboptimal for tree learners. Particularly for high-cardinality categorical features, a tree built on one-hot features tends to be unbalanced and needs to grow very deep to achieve good accuracy. Instead of one-hot encoding, the optimal solution is to split on a categorical feature by partitioning its categories into 2 subsets. If the feature has k categories, there are 2^(k-1) - 1 possible partitions. But there is an efficient solution for regression trees. It needs about O(k * log(k)) to find the optimal partition. The basic idea is to sort the categories according to the training objective at each split. More specifically, LightGBM sorts the histogram (for a categorical feature) according to its accumulated values (sum_gradient / sum_hessian) and then finds the best split on the sorted histogram.
There are also discussions on Githut (e.g https://github.com/microsoft/LightGBM/issues/699) however none seem to present a clear and detailed example of how this work.
Is anyone please able to explain:
- By way of example how this bipartition search works in particular e.g. for a regression problem with a single categorical feature
- *why it is optimal**? The light gradient boosting material reference a paper*.
Many thanks -