Making sense of the Gain term in Gradient tree boosting

Question

In the XGBoost Documentation they specify the Gain term as \begin{equation} Gain=\frac{1}{2} \left[ \frac{G_L^2}{H_L+\lambda} + \frac{G_R^2}{H_R+\lambda}- \frac{(G_L+G_R)^2}{H_L+H_R+\lambda}\right]-\gamma \end{equation} Furthermore, it is stated that

if the gain is smaller than $\gamma$, we would do better not to add that branch

But why is that true? Also, how do I pick which feature/node to split? (In CART, for example, you simply scan through all features and all thresholds)

EDIT: perhaps they mean that the term is smaller than zero, and not $\gamma$, which makes things clearer

Answer 1

I would re-express the terminology:

\begin{equation} \text{gain}=\frac{1}{2} \left[ \frac{G_L^2}{H_L+\lambda} + \frac{G_R^2}{H_R+\lambda}- \frac{(G_L+G_R)^2}{H_L+H_R+\lambda}\right] \\ \text{pruned gain}=\frac{1}{2} \left[ \frac{G_L^2}{H_L+\lambda} + \frac{G_R^2}{H_R+\lambda}- \frac{(G_L+G_R)^2}{H_L+H_R+\lambda}\right]-\gamma \end{equation}

The purpose of $\gamma$ is to determine when the gain from a split is too small to be meaningful. It's one hyper-parameter that can help combat overfitting, or simply to encourage shallower trees. If $\text{gain} < \gamma$, equivalent to $\text{pruned gain} < 0$, then the improvement from the split is too small, and the proposed split is discarded.