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[8]. 
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:

  1. By way of example how this bipartition search works in particular e.g. for a regression problem with a single categorical feature
  2. *why it is optimal**? The light gradient boosting material reference a paper*.

Many thanks -



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.