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 -

It is not easy to track down this information. In the case of regression and binary classification, it can be shown that after ordering the data, the binary splits will occur between contiguous blocks. Let us consider the case of binary classification. Say you have 5 categories with proportion of 1's given by

• A: 0.3
• B: 0.1
• C: 0.8
• D: 0.9
• E: 0.5

Normally, you would have to check every possible partition into 2 subsets (exponential). However, the theorem tells you that you can first order according to proportion of 1's

B, A, E, C, D

and then only consider splits in this particular ordering, so

• {B}, {A,E,C,D}
• {B,A}, {E,C,D}
• {B,A,E}, {C,D}

etc...

That is what is meant by contiguous, and it has to do with an information theoretic argument related to the centroid (the value minimizing the expected loss for a leaf in the tree).

The following paper has been quite helpful: