0
$\begingroup$

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 -

*http://www.csiss.org/SPACE/workshops/2004/SAC/files/fisher.pdf)

$\endgroup$
1
$\begingroup$

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:

https://cs.nyu.edu/~roweis/csc2515-2006/readings/chou_pami.pdf

The paper provides a necessary condition, but for particular cases (like l2 norm regression and binary classification), it leads to the above result.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.