3
$\begingroup$

As I know, EFB can help you to decrease features which are sparse. They put two features together and add offset every feature in feature bundles. They combine features into same histogram.

After creating histogram, how can it works when finding the best split point?

There is a question, and I can't find answer in the paper. https://dl.acm.org/doi/pdf/10.5555/3294996.3295074

$\endgroup$
1
  • $\begingroup$ Nice question (+1) and welcome to CV.SE. $\endgroup$
    – usεr11852
    Dec 16, 2021 at 23:14

1 Answer 1

1
$\begingroup$

Given a new feature $Z$ created by merging features $A$, $B$ and $C$ together, feature $Z$ is treated like any other feature. Note that features $A$, $B$ and $C$ can be either categorical or continuous and ideally, all the sparse features will be combined into fully dense features.

More details: LightGBM does not actually work with the raw values directly but with the discretized version of feature values (the histogram bins). EFB (Exclusive Feature Bundling) merges together mutually exclusive (sparse) features; in that way it performs indirect feature elimination and engineering without hurting (at face value) the performance of the learner. Non-zero values of each of the constituent features are "almost never" taken simultaneously. To ensure that "almost never" we use an offset value; that offset all but guarantees that the histogram-based algorithm is able to "construct a feature bundle by letting exclusive features reside in different bins" (direct quote from Sect. 4 from the paper LightGBM: A Highly Efficient Gradient Boosting Decision Tree (2017) by Ke et al.) Note that EFB is an NP-hard problem (i.e. takes long to solve fully) so LightGBM allows a small number of non-mutually exclusive points (~0.01% of the total number of points). To re-iterate though: EBF is done once before training (either GOSS or anything else); see this Github issue on How does EBF sort features for bundling? too, I found it very helpful for my understanding of EBF.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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