Shrinkage parameter in Adaboost?

Question

I'm unclear how the shrinkage parameter works in Adaboost.

I understand the concept of shrinkage in the theoretical sense related to ordinary least squares, but I'm not sure how to interpret this parameter in relation to Adaboost.

Answer 1

Basically the idea is to slow down learning, allowing to dramatically reduce overfitting. That is, if thinking about it in terms of gradient descent (which Adaboost just is, being a particular case of Gradient Boosting), using no shrinkage performs descent in the direction & amplitude given by the training set. In many cases, this may not be the optimal direction and will cause early overfitting.

Slowing down learning is also the idea behind boosting itself, as using weak predictors manages to reach lower generalisation error by not overfitting early, as happen with simple decision trees for instance.

Answer 2

A visual explanation of the trade-off between learning rate and iterations

This post is based on the assumption that the AdaBoost algorithm is similar to the M1 or SAMME implementations which can be sumarized as follows:

Let $G_m(x) \ m = 1,2,...,M$ be the sequence of weak classifiers, our objective is:

$$G(x) = \text{sign} \left( \alpha_1 G_1(x) + \alpha_2 G_2(x) + ... \alpha_M G_M(x)\right) = \text{sign} \left( \sum_{m = 1}^M \alpha_m G_m(x)\right)$$

AdaBoost.M1

1. Initialize the obervation weights $w_i = 1/N$

2. For $m = 1,2,...,M$

   • Compute the weighted error $ Err_m = \frac{\sum_{i-1}^N w_i \mathcal{I}(y^{(i)} \neq G_m(x^{(i)}) )}{\sum_{i=1}^N w_i}$
   • Compute the estimator coefficient $\alpha_m = L \log \left( \frac{1 - err_m}{err_m}\right)$ where $L \leq 1$ is the learning rate
   • Set data weights $w_i \leftarrow w_i \exp[ \alpha_m \ \mathcal{I}(y^{(i)} \neq G_m(x^{(i)}))]$
   • To avoid numerical instability, normalize the weights at each step $w_i \leftarrow \frac{w_1}{\sum_{i=1}^N w_i}$

3. Output $G(x) = \text{sign} \left[ \sum_{m=1}^M \alpha_m G_m(x)\right]$

The impact of Learning Rate L and the number of weak classifiers M

From the above algorithm we can understand intuitively that

• Decreasing the learning rate $L$makes the coefficients $\alpha_m$ smaller, which reduces the amplitude of the sample_weights at each step (since $w_i \leftarrow w_i e^{ \alpha_m \mathcal{I}...} $ ). This translates into smaller variations of the weighted data points and therefore fewer differences between the weak classifier decision boundaries
• Increasing the number of weak classifiers M increases the number of iterations, and allows the sample weights to gain greater amplitude. This translates into 1) more weak classifiers to combine at the end, and 2) more variations in the decision boundaries of these classifiers. Put together these effects tend to lead to more complex overall decision boundaries.

From this intuition, it would make sense to see a trade-off between the parameters $L$ and $M$. Increasing one and decreasing the other will tend to cancel the effect.

An example on a toy dataset

Here is a toy dataset used on a different question. Plotting the final decision boundary for different values of L and M shows there is some intuitive relation between the two.

• Too small $L$ or $M$ leads to an overly simplistic boundary. Left hand side plots
• Making one large and the other small tends to cancel the effect Plots in the middle
• Making both large gives a good result but may overfit Right hand side plot

Sources:

• You can find the code and figures on my blog
• Sklearn implementation here - line 479
• Elements of Statistical Learning - page 339