Implementing Boosting Algorithms from Scratch

Hello! Welcome to your next lesson on ensemble learning.

Introduction

In our previous lessons, we delved into ensemble methods by exploring bagging and implementing a Random Forest from scratch. You learned that bagging reduces variance by training multiple models in parallel on bootstrapped data samples and averaging their predictions. This is a "divide and conquer" strategy where independent models collectively contribute to a more robust result.

Today, we pivot to the other major ensemble paradigm: boosting. Unlike the parallel nature of bagging, boosting is a sequential process where models are built one after another, each one learning from the mistakes of its predecessor. This iterative refinement process is exceptionally powerful for reducing model bias and often leads to state-of-the-art performance on tabular data.

Our learning goal for this lesson is to implement AdaBoost and Gradient Boosting Machines (GBMs) from first principles. By the end, you'll understand the core mechanics of how these two foundational boosting algorithms work and will have built them from the ground up.

1. AdaBoost: The First Successful Boosting Algorithm

AdaBoost, short for Adaptive Boosting, was one of the first and most influential boosting algorithms. Its core idea is elegant: it combines multiple "weak learners"—classifiers that are only slightly better than random guessing—into a single "strong learner."

The algorithm works by:

1. Training a sequence of weak learners (typically decision stumps, which are simple one-level decision trees).
2. Paying more attention to data points that were misclassified by previous learners. It does this by increasing their sample weights.
3. Giving a final, weighted vote where learners that performed better (had lower error) get a larger "say" in the final prediction.

Conceptual Overview

To build a strong intuition for AdaBoost, let's watch a video from StatQuest that clearly explains these three core ideas.

The AdaBoost Algorithm in Detail

Let's formalize the steps we saw in the video. For a binary classification problem with labels $y\in \{-1,1\}$:

1. Initialize Weights: Assign an equal weight $w_i=1/N$ to each of the $N$ training samples.

2. Iterate and Train Weak Learners: For $m=1,2,\dots ,M$ classifiers:
   a. Train a weak classifier $h_m(x)$ (a decision stump) that minimizes the weighted classification error:
   ${ϵ}_m=\frac{{\sum }_{i=1}^N{w}_i\cdot \mathbb{I}(y_i\ne h_m(x_i))}{{\sum }_{i=1}^N{w}_i}$
   where $\mathbb{I}(\cdot )$ is an indicator function that is 1 if the condition is true and 0 otherwise.

   b. Calculate the classifier's weight (its "say"), ${\alpha }_m$:
   ${\alpha }_m=\frac{1}{2}\ln \left(\frac{1-{ϵ}_m}{{ϵ}_m}\right)$
   Notice that if the error ${ϵ}_m$ is low (near 0), ${\alpha }_m$ is large and positive. If ${ϵ}_m$ is 0.5 (random guessing), ${\alpha }_m$ is 0. If ${ϵ}_m$ is high (near 1), ${\alpha }_m$ becomes a large negative number.

   c. Update Sample Weights: Increase the weights of misclassified samples and decrease the weights of correctly classified ones.
   $w_i\leftarrow w_i\cdot \exp (-{\alpha }_m{y}_i{h}_m(x_i))$
   The term $y_i{h}_m(x_i)$ is +1 for a correct classification and -1 for an incorrect one. This formula elegantly handles both cases: multiplying by $e^{{\alpha }_m}$ for incorrect samples and $e^{-{\alpha }_m}$ for correct ones.

   d. Normalize the weights so they sum to 1: $w_i\leftarrow w_i/{\sum }_{j=1}^N{w}_j$.

3. Final Prediction: The final classifier combines the votes of all weak learners, weighted by their $\alpha$ values. The final prediction is the sign of this weighted sum:
   $H(x)=\text{sign}\left({\sum }_{m=1}^M{\alpha }_m{h}_m(x)\right)$

Implementing AdaBoost from Scratch

Now, let's implement this. Your Python and software engineering skills will make this process straightforward. We will follow a from-scratch tutorial that builds both the DecisionStump weak learner and the main Adaboost class.

Here is the core structure of the code from the video, which you can use as a reference. You can also refer to the complete code in the accompanying article resource.

Test your understanding!

In the AdaBoost algorithm, if a weak learner (a stump) performs very poorly and has a weighted error ${ϵ}_m>0.5$, what happens during the training process? How does the algorithm handle this? (Hint: The implementation in the video includes a clever trick.)

Show answer

If a stump has an error greater than 0.5, it means it's performing worse than random guessing. AdaBoost handles this by "flipping" its predictions. This is done by changing the polarity of the stump. For example, if it was predicting +1 for values less than the threshold and -1 for values greater, it will now do the opposite.

This flip also changes the error. The new error becomes $1-{ϵ}_m$. Since the original ${ϵ}_m$ was > 0.5, the new error is < 0.5. This ensures the learner is now better than random, and its $\alpha$ value will be positive, allowing it to contribute meaningfully (albeit with opposite predictions) to the final ensemble.

2. Gradient Boosting Machines (GBMs)

While AdaBoost focuses on sample weights, Gradient Boosting takes a more generalized approach. It frames the boosting problem as an optimization problem where the goal is to minimize a loss function.

The core idea of Gradient Boosting is to sequentially add new models (typically decision trees) that predict the residuals (the errors) of the preceding model ensemble.

In essence:

1. Start with a simple initial prediction (e.g., the mean of the target values).
2. Calculate the errors (residuals) of this prediction.
3. Build a new model (a decision tree) that tries to predict these errors.
4. Add this new "error-correcting" model to the ensemble, scaled by a learning rate.
5. Repeat steps 2-4, with each new model trying to fix the remaining errors of the updated ensemble.

The "Gradient" in the name comes from the fact that this process is a form of gradient descent. The residuals are the negative gradient of the Mean Squared Error (MSE) loss function. This insight allows GBMs to be generalized to any differentiable loss function, making them applicable to a wide variety of regression and classification tasks.

From AdaBoost to GBM

Let's read a short article that introduces Gradient Boosting, explains its connection to AdaBoost, and outlines the algorithm.

Implementing a Simple GBM from Scratch

Implementing a full GBM from scratch requires a regression tree learner. Since we have built decision trees before, we will focus on the boosting logic that wraps around the tree learners. The article we just read provides a simplified Python implementation that demonstrates this core loop.

Let's break down the logic for a regression task:

1. Initialize Prediction: Start with an initial prediction for all samples. For a simple regression case, this is just the mean of the target variable y.
   predf = np.mean(y)

2. Iterative Correction Loop: For a set number of estimators (trees):
   a. Calculate Residuals: Find the difference between the true values y and the current ensemble prediction predf. These are the errors we want the next tree to correct.
   residuals = y - predf

   b. Fit a Tree to Residuals: Train a new decision tree (a weak learner, e.g., with max_depth=3) to predict these residuals, not the original y.
   tree.fit(X, residuals)

   c. Update Ensemble Prediction: Get the predictions from the new tree and add them to the overall prediction, scaled by a learning_rate ($\nu$).
   predf = predf + learning_rate * tree.predict(X)

   d. Repeat, storing each tree along the way.

3. Final Prediction: The final prediction for a new data point is the initial mean plus the sum of predictions from all the trees in the ensemble, each scaled by the learning rate.

The article "Gradient Boosting – A Concise Introduction from Scratch" contains a code block under the "Gradient Boosting from Scratch" section that implements this logic. Let's examine it.

This simplified process gives you the fundamental "first principles" understanding of how GBMs work: they are an additive model where each new term is a function trained to correct the errors of the existing model.

Test your understanding!

In Gradient Boosting, what is the role of the learning_rate (also called shrinkage)? What would be the potential consequence of setting a very high learning rate (e.g., 1.0) versus a very low one (e.g., 0.01)?

Show answer

The learning_rate controls the contribution of each new tree to the final ensemble. It "shrinks" the impact of each tree's prediction.

• High Learning Rate (e.g., 1.0): The model learns very quickly. Each new tree makes a large correction to the overall prediction. This can lead to overfitting, as the model may chase the noise in the residuals of the training data too aggressively.
• Low Learning Rate (e.g., 0.01): The model learns very slowly. Each tree makes a very small, incremental correction. This forces the model to find more general patterns and makes it more robust to noise, reducing the risk of overfitting. The trade-off is that you typically need more trees (n_estimators) to achieve good performance, which increases training time.

In practice, finding a good balance between learning_rate and n_estimators is key to building a high-performing GBM.

Conclusion

In this lesson, you have moved from the parallel world of bagging to the sequential world of boosting. You have implemented two of the most important algorithms in classical machine learning from first principles.

Key Takeaways:

• Boosting is an ensemble technique that builds models sequentially, where each new model corrects the errors of its predecessors.
• AdaBoost works by increasing the weights of misclassified samples, forcing subsequent weak learners (stumps) to focus on them. The final prediction is a weighted vote based on each learner's performance ($\alpha$).
• Gradient Boosting Machines (GBMs) generalize this idea. Each new weak learner (a shallow tree) is trained to predict the residuals (errors) of the current ensemble. This is equivalent to performing gradient descent on a loss function.
• The learning rate is a critical hyperparameter in GBMs that controls the contribution of each tree and helps prevent overfitting.

Preview of the next lesson:
Building AdaBoost and GBMs from scratch provides a deep understanding of their mechanics. However, in practice, we use highly optimized libraries that have made Gradient Boosting a dominant force in machine learning competitions and industry. In the next lesson, we will explore these high-performance libraries: XGBoost, LightGBM, and CatBoost, and learn how to apply them effectively.