📘

AdaBoost Weight Update

MediumEnsemble Methods 📚 Machine 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\}$ . 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:

First, we calculate the weighted error $\epsilon = \frac{\sum_{i: \hat{y}_i \neq y_i} w_i}{\sum w_i}$ . For the given input, $\hat{y}_i \neq y_i$ for $i = 2, 3$ , so $\epsilon = \frac{0.25 + 0.25}{1} = 0.5$ .
Then, we compute the classifier weight: $\alpha = \frac{1}{2} \ln\frac{1 - \epsilon}{\epsilon} = \frac{1}{2} \ln\frac{1 - 0.5}{0.5} = \frac{1}{2} \ln\frac{0.5}{0.5} = \frac{1}{2} \ln(1) = 0$ is incorrect due to the properties of $\ln(1)$ , we should instead get $\alpha = \frac{1}{2} \ln\frac{0.5}{0.5} = 0$ is a special case. However, given $\epsilon = 0.5$ , $\alpha = \frac{1}{2} \ln\frac{1 - 0.5}{0.5} = \frac{1}{2} \ln(1) = 0$ is not the case here, we actually calculate $\alpha$ using $\epsilon$ in the formula which results in $\alpha = \frac{1}{2} \ln\frac{0.5}{0.5}$ . But since $\frac{1 - \epsilon}{\epsilon} = \frac{0.5}{0.5} = 1$ , $\alpha = \frac{1}{2} \ln(1) = 0$ would be the case if $\epsilon$ was not exactly $0.5$ , for $\epsilon = 0.5$ , $\alpha = 0$ would not be the correct calculation. Let's correct that: given $\epsilon = 0.5$ , $\alpha$ should actually be calculated with the given $\epsilon$ which leads to $\alpha = \frac{1}{2} \ln\frac{1-0.5}{0.5}$ . The issue here is that $\frac{1-0.5}{0.5} = 1$ , and $\

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

More from Machine Learning 1

RBF Kernel MatrixHard Polynomial KernelMedium Hinge LossEasy Linear Decision BoundaryEasy Gradient Boosting Residual StepHard

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

0/0

Run code to see test results.