Observation-Weight Updates In AdaBoost

Why AdaBoost Changes Observation Weights

AdaBoost fits a sequence of weak classifiers. After one classifier is fitted, the algorithm changes the relative importance of the training observations before fitting the next one. Observations classified incorrectly receive increased relative weight; correctly classified observations receive decreased relative weight. The update does not change the observations or their labels. It changes how much each observation contributes to the next learner’s weighted classification error.

Let the training data consist of \(n\) pairs \((x_i,y_i)\), where \(y_i\in\{-1,+1\}\), and let \(h_t(x_i)\in\{-1,+1\}\) be the prediction of the learner at round \(t\). The current weights \(D_t(i)\) are nonnegative and sum to one. Thus, they form a probability distribution over the training observations, but they are algorithmic weights—not probabilities that the labels are correct.

The weighted error, rather than the fraction of observations misclassified, determines the update. If the weights are unequal, a learner that gets many low-weight observations wrong can have a smaller weighted error than one that gets fewer high-weight observations wrong.

Deriving the Observation-Weight Update

The update follows from AdaBoost’s exponential loss. Write the ensemble score before round \(t\) as \(F_{t-1}(x)\), with \(F_t(x)=F_{t-1}(x)+\alpha_t h_t(x)\). The contribution of observation \(i\) to the exponential loss is \(\exp[-y_iF_t(x_i)]\). The current weights are proportional to the corresponding loss contributions before the new learner is added.

Since \(y_i h_t(x_i)=+1\) for a correct classification and \(-1\) for an incorrect classification, the multiplier is \(\exp(-\alpha_t)\) for a correct classification and \(\exp(\alpha_t)\) for an incorrect one. The resulting update is

For the standard AdaBoost coefficient, assuming \(0<\epsilon_t<1/2\),

This coefficient makes the total updated weight on the current learner’s incorrect observations equal to the total updated weight on its correct observations. To see why, the unnormalized total for correct observations is \((1-\epsilon_t)\exp(-\alpha_t)\), while the total for incorrect observations is \(\epsilon_t\exp(\alpha_t)\). Substituting the coefficient gives

Therefore \(Z_t=2\sqrt{\epsilon_t(1-\epsilon_t)}\), and normalization assigns total weight \(1/2\) to each group. Within either group, relative proportions are unchanged: observations in the same group all receive the same multiplier. In particular, this update does not make every misclassified observation equally weighted; it preserves the ratios of their current weights.

Applying the Update When the Error Is Weighted

A reliable calculation separates three quantities: the current weights, the weighted error, and the updated weights. First sum the weights on the misclassified observations. Then use that error to find \(\alpha_t\), if it is requested. Finally, allocate half of the normalized total to each prediction group while preserving the weights’ relative proportions within each group. The group-allocation method is equivalent to the multiplicative formula when the standard coefficient is used.

Weights Carry Forward to the Next Round

The new weights are the starting weights for fitting the next learner. They do not reset to equal weights after each round. Consequently, an observation that has been misclassified may become relatively influential, but its weight is still determined by its current weight and the result of the latest learner. Correct classification in a later round can reduce its relative weight again.

Important Conditions and Common Traps

The usual coefficient formula assumes a binary classifier with labels coded as \(-1\) and \(+1\), and a learner whose weighted error is less than \(1/2\). If \(\epsilon_t=1/2\), then \(\alpha_t=0\), so the update makes no change. If \(\epsilon_t>1/2\), the coefficient from the formula is negative; when reversing the learner’s predictions is permissible, reverse them and use error \(1-\epsilon_t<1/2\). If \(\epsilon_t=0\), the formula has no finite coefficient. A perfectly accurate learner is a boundary case, typically handled by stopping or by an explicitly specified implementation rule, rather than by substituting zero into the formula.

A frequent sign error is to give the larger multiplier to correct classifications. For example, in the first worked example, reversing the multipliers would leave the correct group with unnormalized total \(0.70\exp(\alpha_t)\) and the incorrect group with \(0.30\exp(-\alpha_t)\). Since \(\exp(\alpha_t)=\sqrt{7/3}\) and \(\exp(-\alpha_t)=\sqrt{3/7}\), these totals are about \(1.0693\) and \(0.1964\), respectively—not equal. After normalization, this mistaken update would assign about \(0.8448\) to the correct group and \(0.1552\) to the incorrect group, the opposite of the intended emphasis.

• Do not use the raw fraction misclassified unless the current weights are equal. Compute the weighted error from the weights on the incorrect observations.
• Do not reverse the update direction. Incorrect classifications use the factor \(\exp(\alpha_t)\); correct classifications use \(\exp(-\alpha_t)\).
• Do not skip normalization. The unnormalized products are not the next weights, because they need not sum to one.
• Do not equalize individual weights. The standard update equalizes the total weight of the two groups, not the weight of each observation.