Is there a theoretical basis for the shrinkage used in Boosted Regression Trees?

Question

In Gradient Boosted Regression Trees, a shrinkage $\nu$ is often applied as: $$ f_t(x) \leftarrow f_{t-1}(x) + \nu h(x)$$ where $h$ is the regression tree learned by fitting the tree to the gradient. I've tried implementing this and found that this shrinkage is indeed necessary to prevent overfitting. The shrinkage required may vary by application but I found that anything greater than $\nu=0.01$ led to overfitting.

Is there a theoretical justification for this kind of shrinkage? Are there more theoretically sound ways of regularizing GBRTs?

Answer 1

Is there ever a theoretical basis for any kind of regularization parameter? Usually, I see them introduced as convenient priors.

In addition to $\nu$, there are a lot of ways to regularize gradient boosted trees.

1. Tree depth,
2. Minimum sample size for splitting trees,
3. Minimum sample size for tree leaves,
4. Number of trees,
5. Randomly choosing small subsets of features for different trees.

I'm sure I forgot some. A good summary is made in this talk about Gradient Boosted Regression Trees (GBRT).

Answer 2

Yes, there is theoretical basis for the shrinkage $\nu$. It is not only a regularization parameter.

Remember that Gradient Boosting is equivalent to estimating the parameters of an additive model by minimizing a differentiable loss function (exponential loss in the case of Adaboost, multinomial deviance for classification, etc.) using Gradient Descent (see Friedman et al. 2000).

So $\nu$ controls the rate at which the loss function is minimized. Smaller values of $\nu$ result in greater accuracy because with smaller steps, the optimization is more precise (however, it takes more time because more steps are required).

With $\nu$ we have control on the rate at which the boosting algorithm descends the error surface (or ascends the likelihood surface).

Performance is best when $\nu$ is as small as possible with decreasing marginal utility for smaller and smaller $\nu$.

(Both citations are from Ridgeway 2007)