1
$\begingroup$

Before searching for split points LightGBM sorts categories withing categorical features by:

$\frac{\sum_{i=1}^{n} 1_{x_{i j}=x_{i k}} g_{i}}{\sum_{i=1}^{n} 1_{x_{i j}=x_{i k}} h_{i}}$

Where $g_i$ is gradient, and $h_i$ is hessian for instance $i$. $j$ denotes categorical feature and $k$ denotes category.

I understand that the gradient shows the change in the loss function for one unit change in the feature value. Similarly the hessian represents the change of change, or slope of the loss function for one unit change in the feature value.

What confuses me however is how to interpret unit change for categorical variables. It does not make sense to me since they are not ordinal.

$\endgroup$
1
$\begingroup$

I understand that the gradient shows the change in the loss function for one unit change in the feature value...

Here's the confusion: the gradient (and hessian) is not with respect to the features! GBMs treat the loss function as a function of the predictions (extremely high dimensional!), and the gradient and hessian are derivatives then with respect to the predictions. Wait, what? (blog post of Nicolas Hug of sklearn). I find it easiest to go back to the case with loss=MSE, so that the gradient is just the residual and the hessian is constant. The tree being built is now just an ordinary regression tree trying to fit the residual.

So, the question of what a GBM does with categorical features is really just the same as that question for decision trees. And (when supported), this usually uses the trick of ordering the levels according to the target (in context of GBM, the target is the ratio of gradient to hessian, maybe with regularization extra terms). And given that ordering, splits are performed in much the same way as for continuous features: split the ordering at some point (possibly using histograms to reduce the number of split points).

$\endgroup$
2
  • $\begingroup$ Thank you very much for the answer, i think it all makes sense now. I never really thought of it as we are treating the loss function as a fuction of predictors, but it makes sense since we are trying to minimize some difference of sorts between actual and predicted values at each iteration. I guess we can apply the same reasoning in the case of classification? Also, why do we divide by the hessian? $\endgroup$ – Polarni1 Dec 18 '20 at 4:27
  • 1
    $\begingroup$ Yes, classification works in basically the same way. For the last part, see en.wikipedia.org/wiki/… or section 2.2 from the xgboost paper. $\endgroup$ – Ben Reiniger Dec 18 '20 at 14:57

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.