1
$\begingroup$

I am going through the introduction to XGBoost page, and there is a section where they derive the optimal value of the leaf node, for a given tree structure.

To quote the specific section,

In this equation, $w_j$ are independent with respect to each other, the form $G_j w_j + \frac{1}{2} (H_j + \lambda) w_j^2$ is quadratic and the best $w_j$ for a given structure $q(x)$ and the best objective reduction we can get is: $$ w^*_j = -\frac{G_j}{H_j + \lambda}$$....

For context, $G_j w_j + \frac{1}{2} (H_j + \lambda) w_j^2$ is the summand of the objective, $G_j$ is the sum of sample gradients in leaf $j$ WRT leaf values evaluated at existing trees, $H_j$ is the sum of Hessian terms in leaf $j$, $w_j$ is the leaf value, and $\lambda$ is the L2-regularization constant.

Clearly $w^*_j$ is the stationary point of $w_j$ in the objective.

Now, the second derivative of the objective is $H_j + \lambda$. But a stationary point is only a minimum if the second derivative is positive. In this case, their equation for $w^*_j$ is only a minimizer of the objective if $H_j > 0$ (let's ignore $\lambda$ for simplicity here). If $H_j$ is negative, or zero, then $w^*_j$ may, in fact, be a maximizer or a saddle point.

I find that the second derivative of most typical objective functions is strictly positive. The common examples that come to mind are MSE ($1$), cross-entropy ($p (1 - p)$ where $p = \sigma(y)$), Poisson objective ($\frac{t}{y^2}$ where $t$ is the target). Which is a happy coincidence. But, as soon as we introduce a custom objective with a 2nd derivative that can be negative or zero, then XGBoost can no longer handle this. Is this true?

The reason I am asking this is because I am currently trying to train a model with a custom objective with Hessian that is sometimes $<0$. And I am getting the wrong behavior for very obvious cases. I even contrived a dataset where the leaf values should all be pushed to $-\infty$, and are instead being pushed to $+\infty$. One "hacky" solution I found, that actually worked, is to replace the Hessian with its absolute value. Though I can't theoretically justify why it works.

Is XGBoost unable to handle custom objectives with negative second derivatives? Or am I fundamentally misunderstanding something?

Improve this question
$\endgroup$
6
  • $\begingroup$ "I am currently trying to train a model with a custom objective with Hessian that is sometimes <0" - in those cases I guess you want to pick an end of the allowable interval (maybe $\pm\infty$ in the "raw" space?)? That might be complicated to get to work correctly inside an existing framework. Can you share this objective function? $\endgroup$
    – Ben Reiniger
    Mar 20 at 16:49
  • $\begingroup$ The MAE loss has a similar issue, where hessian is identically zero. That gets handled by most packages by just setting the hessian to 1 for split construction, which amounts to doing vanilla gradient descent (without the second derivative "enrichment"), although also then leaf values get set differently: github.com/microsoft/LightGBM/issues/… $\endgroup$
    – Ben Reiniger
    Mar 20 at 16:51
  • $\begingroup$ I think you’ve hit on the major problems with using a loss function that isn’t PSD with xgboost. As you’ve written, the software uses a quadratic approximation, which can be very poor for a non-convex loss. $\endgroup$
    – Sycorax ♦
    Mar 20 at 16:59
  • $\begingroup$ @BenReiniger The objective is basically $\sigma(y_i) * \alpha_i$ where $\alpha_i$ is some real number (+ve or -ve) associated with sample $i$. So the Hess is $\sigma(y_i) (1 - \sigma(y_i)) (1 - 2 \sigma(y_i)) \alpha_i$. Here, $\sigma(y) = (1 + e^{-y})^{-1}$. I don't understand what you mean by "pick an end of the allowable interval". Can you clarify please? I can't just subset on samples which have positive Hess, or I will get bad results. I have to include all of them. Currently, I got a good result by replacing Hess with its absolute value, but IDK why this worked $\endgroup$
    – Bridgeburners
    Mar 20 at 19:28
  • 1
    $\begingroup$ Newton's method also does not perform well when the Hessian is not PSD. The last sentence in your Comment seems like a good explanation for the behavior that you describe in your Question. It seems like you understand that choosing weights that maximize the loss would mean that the model does not make good predictions; doing this for several trees seems like this phenomenon would compound at each round of boosting. What requires more explanation? $\endgroup$
    – Sycorax ♦
    Mar 20 at 19:55

0

Reset to default

Your Answer

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