Doing research about the xgboost algorithm I went through the documentation.

In this approach trees are regularized using the complexity definition $$ \Omega(f) = \gamma T + \frac12 \lambda \sum_{j=1}^T w_j^2 $$ where $\gamma$ and $\lambda$ are parameters, $T$ is the number of terminal leaves and $w_j$ is the score in each leaf.

I wonder: how does this define complexity? $T$, the number of terminal nodes, seems natural to me. But the sum of final scores squared?

Maybe overfitting is meant. Meaning that very large scores give too much confidence? Is it chosen to get a weak learner? What is a natural explanation for this choice of the complexity function?


1 Answer 1


This makes sense to me.

I'll focus on the Gaussian case. Here each tree $T_i$ is fit on the residuals of the current model, and the model update is $M_{i+1} = M_{i} + \alpha T_i$. The idea of a gradient booster is to carefully and slowly reduce the bias of the model by adding these trees one by one.

In this case, a large value of $w_i$ would correspond to a terminal (leaf) node giving a very large and significant update to the prior model. The idea of the regularization term is to minimize these incidents of large single tree updates (only allowing them if the decrease in the model loss function is large enough to offset the regularization penalty). If such an update is regularized away for a single tree, but turns out to be justified, it will be baked in over multiple model updates, in accordance with the philosophy of boosting.

This is in very close analogy to ridge regression.

  • $\begingroup$ Thanks, thus you think about it similarly as I do when I speak about a weak learner... Weak in the sense if not taking too large steps.. $\endgroup$
    – Richi W
    Oct 22, 2015 at 12:06
  • $\begingroup$ Could you be more specific for what is "Gaussian case"? fit a mixture of Gaussians? $\endgroup$
    – Haitao Du
    Aug 12, 2016 at 17:08
  • $\begingroup$ @hxd1011 I just mean that we are using sum of squared errors loss, aka the log-likelihood of the gaussian distribution. The main point is that here you can assume you're just fitting to the residuals. $\endgroup$ Aug 12, 2016 at 17:41
  • $\begingroup$ @MatthewDrury could you take a look at this related question? Thanks!! stats.stackexchange.com/questions/229599/… $\endgroup$
    – Haitao Du
    Aug 12, 2016 at 20:54

Your Answer

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

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