I originally thought that the ordering trick would only really work for the LS loss. But now that I have read the Fisher paper more in details, it seems to me that we can always apply this trick because the trees are always least-squqres regression trees (regardless of the loss). Do you agree? Does lightGBM also uses this regardless of the loss?

@lorentzenchr @johannfaouzi should be intersted ;)

BTW I will come back to this after the feature freeze for the next release, which will be happening pretty soon.

lint failure ;)

@thomasjpfan @ogrisel in bbae955 I pushed an equivalence test w.r.t. OHE in different scenarios, let me know what you think?

Checking in: While debugging the differences between lightgbm and this PR, I found that for smallish trees ~ max_depth=3, that the splits are the same. The difference in performances comes from differences between the nodes' gain and value when compared to lightgbm. I'm still looking into it.

@thomasjpfan I made this comparison tool back then which may help you compare trees built with lightgbm: https://github.com/NicolasHug/plot_hgbdt

@thomasjpfan @ogrisel in bbae955 I pushed an equivalence test w.r.t. OHE in different scenarios, let me know what you think?

I think it's good test and it has value because it is simple enough, hence easier to debug if it starts failing because of a regression introduced in a future change.

However I wanted to also test that the decision function learned is the same for training set with 2 interacting categorical variables. In particular I wanted to to check that the learned decision function is also the same on datapoints with combinations of categorical variables not observed in the training set. WDYT?

Maybe it would interesting to write a similar test with many categorical variables with a large enough cardinality and a number of training samples that is significantly smaller that the number of possible combinations of the input variables. The target training gradients should not be optimally predictable from a single input variable, maybe random gradients would be enough to highlight the property I am interested in.

Hey guys,

Considering:

• the difficulties we have moving this forward
• the approaching next release
• the seemingly high complexity of the code
• @ogrisel's comment about keeping the nodes struct a structured array ENH Adds Categorical Support to Histogram Gradient Boosting #16909 (comment)
• the fact that these estimators are still experimental
• the fact that releasing an incomplete but useful solution is still better than never releasing a perfect solution

I would suggest to simplify this PR further, and expect categories to be encoded in [0, max_bins]. 256 categories will be enough for a lot of use-cases already. We can deal with higher cardinalities later, and at least at that point we would have a baseline against which we could compare performance. Also chances are, these future changes would all be backward-compatible.

This will allow to greatly simplify the code, and to rely on pure Cython + numpy instead of C++. I feel like this is our best chance to get this in for 0.24

I would be happy to make those changes, if that's OK with everyone.

I would suggest to simplify this PR further, and expect categories to be encoded in [0, max_bins]. 256 categories will be enough for a lot of use-cases already. We can deal with higher cardinalities later, and at least at that point we would have a baseline against which we could compare performance. Also chances are, these future changes would all be backward-compatible.

By restricting to 256, I am assuming we want to still handle unknown categories?

The native implementations of 256 categories that will increase the memory footprint of the predictor nodes. In this native implementation, the node_struct adds a static array to hold on to the categorical_bitset I would prefer node_struct to have a pointer to a memory space with the categorical_bitset. The nodes that use a numerical threshold would not need to allocate space for the categorical bitset. This means another object would hold on the memory for the categorical bitsets. Do you see

By restricting to 256, I am assuming we want to still handle unknown categories?

If you mean categories unknown during fit, yes we can treat as missing as currently done here

Re memory footprint: I agree that allocating a 256 bits array isn't absolutely ideal, but it's not so bad either: this would only add 32B to a struct that is already 47B. For an estimator that has 100 trees with 256 leaves (i.e. 512 nodes assuming they're balanced), this accounts for an extra 1.6MB (for a total of 2.4 + 1.6 = 4MB). This is order of magnitudes lower than what would be needed for fitting. So for a first version, this is quite reasonable IMHO.

I guess I'd be fine with having a pointer to something, as long as we can make it dead simple. It's unlikely that we can satisfy #16909 (comment) though.

As the alternative #18394 was merged but as several limitations, what is the future of this PR? Continue or close and still serve as a reference?

Let's close for now. (We can still reference it if we need to)

Is there anywhere the additional features of this vs. #18394 are being tracked?

So the difference between this PR and #18394 which was merged instead is that #18394 forces categories to be continuously encoded between [0, 254]. This PR (or more likely a variant thereof) would not restrict an upper bound on the category value. There's not issue tracking this ATM, as far as I know. Do you have use-cases with more than 254 unique category values @h-vetinari ?

Informally and from discussion we've had between core-devs, the focus seems to be more into: a) easier way to specify the categorical features #18894 and b) sparse matrix support #15336.

I have use cases with more than 254 categorical levels and would be very glad to see this extension. However, handling the passage of categoricals into the HGBT, e.g. in a pipeline, has priority in my opinion.