Building AdaBoost with Weighted Decision Stumps

The AdaBoost Algorithm: An Overview

The core idea of AdaBoost is to combine many weak learners into a single, strong classifier. It does this iteratively. In each iteration, AdaBoost identifies the mistakes of the current ensemble and "boosts" the importance of the misclassified samples. The next weak learner in the sequence is then trained to focus on these difficult examples.

The process can be visualized as a series of steps:

This process involves two kinds of weights:

1. Sample Weights ($w$): Each data point in the training set has a weight. Initially, all points are weighted equally. After a weak learner is trained, the weights of misclassified points are increased. This tells the next weak learner: "Pay more attention to these points!"
2. Classifier Weights ($\alpha$): Each weak learner gets a "say" in the final prediction, determined by its performance. A weak learner with lower error gets a higher $\alpha$ value, giving it more influence in the final vote.

The result is a sequence of stumps, each one an expert on the mistakes of its predecessors.

The Mathematical Steps of AdaBoost

Let's formalize the algorithm. For a set of $M$ classifiers and $N$ data points, the process is as follows. You can follow along with a detailed explanation of the theory and formulas in the following video.

Here is a summary of the steps discussed in the video:

1. Initialize Sample Weights: For each sample $i$, set the initial weight $w_i=1/N$.

2. For $m=1\text{ to }M$: (Iterate through each weak learner)
   a. Train a Weak Learner ($h_m$): Find the best decision stump by performing the greedy search we discussed in the last lesson. The "best" stump is the one that minimizes the weighted error.
   b. Calculate Weighted Error (${ϵ}_m$): The error is the sum of the weights of the misclassified samples.
   ${ϵ}_m={\sum }_{i=1}^N{w}_i\cdot I(y_i\ne h_m(x_i))$
   Where $I(\cdot )$ is the indicator function (1 if true, 0 if false).
   c. Calculate Classifier Weight (${\alpha }_m$): This value represents the "say" of the $m$-th classifier.
   ${\alpha }_m=\frac{1}{2}\ln \left(\frac{1-{ϵ}_m}{{ϵ}_m}\right)$
   A lower error ${ϵ}_m$ results in a higher ${\alpha }_m$.
   d. Update Sample Weights ($w_i$): 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))$
   After updating, the weights are normalized so they sum to 1. Notice that if a sample is misclassified, $y_i{h}_m(x_i)=-1$, making the exponent positive and increasing the weight.

3. Final Prediction: The final prediction is the sign of the weighted sum of all weak learners' predictions.
   $F(x)=\text{sign}\left({\sum }_{m=1}^M{\alpha }_m{h}_m(x)\right)$

Implementing the AdaBoost Class

Now, let's translate these steps into code. We will create an AdaBoost class that uses our DecisionStump from the previous lesson. The implementation will closely follow the structure presented in the resources from Patrick Loeber and Python Engineer.

Your DecisionStump class from the last lesson should look like this. We will use it directly.

# From previous lesson
class DecisionStump:
    def __init__(self):
        self.polarity = 1
        self.feature_idx = None
        self.threshold = None
        self.alpha = None # We will set this in the AdaBoost class

    def predict(self, X):
        n_samples = X.shape[0]
        X_column = X[:, self.feature_idx]
        predictions = np.ones(n_samples)
        if self.polarity == 1:
            predictions[X_column < self.threshold] = -1
        else:
            predictions[X_column > self.threshold] = -1
        return predictions

Now, let's build the main AdaBoost class.

1. The __init__ and fit Methods

The fit method is where the main algorithm lives. It will contain the loop that sequentially creates, trains, and weights our decision stumps.

import numpy as np

class AdaBoost:
    def __init__(self, n_clf=5):
        self.n_clf = n_clf  # The number of weak learners (M)
        self.clfs = []      # List to store the trained stumps

    def fit(self, X, y):
        n_samples, n_features = X.shape

        # Step 1: Initialize weights
        w = np.full(n_samples, (1 / n_samples))
        self.clfs = []

        # Step 2: Iterate through classifiers
        for _ in range(self.n_clf):
            clf = DecisionStump()
            min_error = float('inf')

            # --- Greedy search for the best stump (Step 2a) ---
            # This is the "training" part from our previous lesson
            for feature_i in range(n_features):
                X_column = X[:, feature_i]
                thresholds = np.unique(X_column)
                for threshold in thresholds:
                    p = 1
                    predictions = np.ones(n_samples)
                    predictions[X_column < threshold] = -1
                    
                    # Step 2b: Calculate weighted error
                    misclassified = w[y != predictions]
                    error = sum(misclassified)

                    # A stump better than random guessing has error < 0.5
                    # If error > 0.5, we flip the polarity
                    if error > 0.5:
                        error = 1 - error
                        p = -1

                    if error < min_error:
                        min_error = error
                        clf.polarity = p
                        clf.threshold = threshold
                        clf.feature_idx = feature_i
            # --- End of greedy search ---
            
            # Step 2c: Calculate classifier weight (alpha)
            EPS = 1e-10  # Avoid division by zero
            clf.alpha = 0.5 * np.log((1.0 - min_error + EPS) / (min_error + EPS))

            # Step 2d: Update sample weights
            predictions = clf.predict(X)
            w *= np.exp(-clf.alpha * y * predictions)
            w /= np.sum(w)  # Normalize weights

            # Save the trained classifier
            self.clfs.append(clf)

The video below walks through this exact implementation logic. Watching it will help connect the formulas to the code you see above.

2. The predict Method

Once the model is fitted, making a prediction involves getting a weighted vote from every stump in our ensemble and taking the sign of the sum.

    def predict(self, X):
        # Get predictions from all classifiers, weighted by their alpha
        clf_preds = [clf.alpha * clf.predict(X) for clf in self.clfs]
        
        # Sum the weighted predictions
        y_pred = np.sum(clf_preds, axis=0)
        
        # Return the sign of the sum
        y_pred = np.sign(y_pred)
        
        return y_pred

This implementation is a direct translation of the final prediction formula. The following short segment shows its implementation.

You can also review the complete, clean code in the accompanying article to consolidate your understanding.

Conclusion

Congratulations! You have now implemented the AdaBoost algorithm from scratch. By combining your DecisionStump weak learner with a clever weighting scheme, you've built a powerful classifier.

Key Takeaways:

• AdaBoost is an adaptive boosting algorithm that trains weak learners sequentially.
• Sample weights are used to make the algorithm focus on data points that were previously misclassified.
• The classifier weight ($\alpha$) is calculated based on the weak learner's weighted error and determines its influence on the final prediction.
• The fit method involves an outer loop for the number of classifiers and an inner set of loops to find the best stump for the current sample weights.
• The predict method computes a weighted sum of the predictions from all stored weak learners and returns the sign.

Preview of the Next Lesson:
AdaBoost is a brilliant algorithm, but its derivation is tied to a specific loss function (the exponential loss). What if we wanted to use this "boosting" idea for other problems, like regression with Mean Squared Error?

In the next lesson, we will take the first step towards a more general boosting framework called Gradient Boosting. You will learn to calculate pseudo-residuals for a regression loss function. These residuals represent the "errors" that the next weak learner should try to fit, and you'll see that they are directly related to the gradient of the loss function—connecting back to the central theme of our course.