# Exhaustive Bipartition Search (Specific to light GBM or Catboost)

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 -