# Definition of complexity of a tree in xgboost

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

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.

• 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.. – Ric Oct 22 '15 at 12:06
• Could you be more specific for what is "Gaussian case"? fit a mixture of Gaussians? – Haitao Du Aug 12 '16 at 17:08
• @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. – Matthew Drury Aug 12 '16 at 17:41
• @MatthewDrury could you take a look at this related question? Thanks!! stats.stackexchange.com/questions/229599/… – Haitao Du Aug 12 '16 at 20:54