AdaBoost Weight Update

mediumFREEEnsemble MethodsMachine Learning 1

Implement one step of the AdaBoost weight update algorithm.

Given sample weights $w$ , predictions $\hat{y}$ , and true labels $y$ :

Compute the weighted error: $\epsilon = \frac{\sum_{i: \hat{y}_i \neq y_i} w_i}{\sum w_i}$
Compute classifier weight: $\alpha = \frac{1}{2} \ln\frac{1 - \epsilon}{\epsilon}$
Update sample weights: $w_i' = w_i \cdot e^{-\alpha \cdot y_i \cdot \hat{y}_i}$
Normalize: $w_i'' = \frac{w_i'}{\sum w_j'}$

Labels are $\{-1, +1\}$ . If the classifier makes no mistakes ( $\epsilon = 0$ ), clamp $\epsilon$ to $10^{-10}$ before computing $\alpha$ so the logarithm stays finite. Return a tuple (alpha, new_weights) with alpha and each weight rounded to 4 decimal places.

Example

Input

weights = [0.25, 0.25, 0.25, 0.25]
y_true = [1, -1, 1, -1]
y_pred = [1, -1, -1, -1]

Output

(0.5493, [0.1667, 0.1667, 0.5, 0.1667])

Reasoning

Inputs: four samples, each with weight $0.25$ (total $1$ ). True labels are $+1, -1, +1, -1$ and the weak classifier predicted $+1, -1, -1, -1$ , so it agrees on samples 1, 2 and 4 and gets only sample 3 wrong.
Weighted error: only sample 3 counts, so $\epsilon = \frac{0.25}{1} = 0.25$ .
Classifier weight: $\alpha = \frac{1}{2}\ln\frac{1 - 0.25}{0.25} = \frac{1}{2}\ln 3 \approx 0.5493$ , the first value of the output.
Reweighting: a correct sample has $y_i \hat{y}_i = +1$ , so its weight shrinks to $0.25\,e^{-0.5493} = 0.25/\sqrt{3} \approx 0.1443$ . The wrong one has $y_i \hat{y}_i = -1$ and grows to $0.25\,e^{0.5493} = 0.25\sqrt{3} \approx 0.4330$ .
Normalising: the total is $3(0.1443) + 0.4330 \approx 0.8660$ , giving $0.1443/0.8660 \approx 0.1667$ for the correct samples and $0.4330/0.8660 = 0.5$ for sample 3: [0.1667, 0.1667, 0.5, 0.1667].
Notice that the misclassified sample now carries exactly half the total weight, so the next weak learner is pushed to focus on it.

Constraints

weights: list of current sample weights
y_true, y_pred: lists of labels in {-1, +1}
Return (alpha, new_weights) rounded to 4 decimal places
alpha is the classifier importance weight

Learn this in

Ensemble MethodsML Study Plan

More from Machine Learning 1

RBF Kernel Matrixhard Polynomial Kernelmedium Hinge Losseasy Linear Decision Boundaryeasy Gradient Boosting Residual Stephard

Concept primer

Background Knowledge

The AdaBoost algorithm is a popular ensemble method used in machine learning for classification problems. It works by combining multiple weak classifiers to create a strong classifier. The key idea behind AdaBoost is to assign weights to each sample in the dataset, with higher weights given to samples that are misclassified by the previous classifier. This process is repeated multiple times, with each new classifier attempting to correct the mistakes of the previous one.

In the context of the AdaBoost weight update algorithm, the goal is to update the sample weights based on the performance of the current classifier. This involves computing the weighted error, classifier weight, and updating the sample weights. The weighted error, denoted by $\epsilon$ , represents the proportion of misclassified samples, weighted by their respective sample weights. The classifier weight, denoted by $\alpha$ , is a measure of the classifier's performance, with higher values indicating better performance.

The AdaBoost weight update algorithm is based on the concept of exponential loss, which is a common loss function used in machine learning. The exponential loss function is defined as $L(y, \hat{y}) = e^{-y \cdot \hat{y}}$ , where $y$ is the true label and $\hat{y}$ is the predicted label. The algorithm uses this loss function to update the sample weights, with the goal of minimizing the overall loss.

Algorithm/Approach

The general approach to solving this problem involves implementing the AdaBoost weight update algorithm, which consists of four main steps: computing the weighted error, computing the classifier weight, updating the sample weights, and normalizing the updated weights. This algorithm is typically used in an iterative process, where multiple classifiers are trained and combined to create a strong classifier.

Step-by-Step Strategy

To implement the solution, follow these steps:

Compute the weighted error $\epsilon$ by summing the weights of misclassified samples and dividing by the total weight.
Compute the classifier weight $\alpha$ using the formula $\alpha = \frac{1}{2} \ln\frac{1 - \epsilon}{\epsilon}$ .
Update the sample weights $w_i'$ using the formula $w_i' = w_i \cdot e^{-\alpha \cdot y_i \cdot \hat{y}_i}$ .
Normalize the updated weights $w_i''$ by dividing by the sum of all updated weights.

Common Pitfalls

When implementing the solution, watch out for the following common pitfalls:

Make sure to handle the case where $\epsilon = 0$ or $\epsilon = 1$ , as these values will result in division by zero or undefined logarithm.
Use a stable method for computing the logarithm and exponential functions to avoid numerical instability.
Ensure that the updated weights are normalized correctly to avoid changing the overall scale of the weights.

Time & Space Complexity

The time complexity of the algorithm is $O(n)$ , where $n$ is the number of samples, since we need to iterate over all samples to compute the weighted error and update the sample weights. The space complexity is also $O(n)$ , since we need to store the updated weights for all samples. Note that these complexities assume that the input arrays w, y, and y_hat are already computed and available.

solution.py

Python 3.13

Test results