Deriving The Discrete AdaBoost Update

One Rule, One Coefficient

At a boosting round, the current weights specify how strongly each training example contributes to the next update. For a candidate binary rule, its weighted error determines the coefficient that minimizes exponential loss along that rule. The derivation is a one-dimensional optimization, but it has an important qualification: if the rule is worse than chance under the current weights, the minimizing coefficient is negative. Thus, the claim that the update emphasizes errors applies to a rule with weighted error below one half, not to every binary rule.

Suppose the training data are \((x_i,y_i)\), \(i=1,\ldots,n\), with labels \(y_i\in\{-1,+1\}\). At the round under consideration, let \(D(i)\geq 0\) be the weight on example \(i\), with \(\sum_{i=1}^n D(i)=1\). A binary rule \(h\) takes values in \(\{-1,+1\}\). It classifies example \(i\) correctly when \(y_i h(x_i)=+1\), and incorrectly when \(y_i h(x_i)=-1\).

The weight distribution is normalized, so the weighted mass of correctly classified examples is \(1-\epsilon\), while the mass of incorrectly classified examples is \(\epsilon\). Since the signed prediction \(y_i h(x_i)\) is \(+1\) on correct examples and \(-1\) on incorrect ones, the loss reduces to

This reduction is why the coefficient depends on the rule through its weighted error alone. The individual weights still matter for the example-by-example update, but not for minimizing this one-dimensional loss.

Deriving the Minimizing Coefficient

Proof. For \(0<\epsilon<1\), differentiate:

Both terms in \(Z''(\alpha)\) are positive for every finite \(\alpha\), so \(Z''(\alpha)>0\) and \(Z\) is strictly convex. A stationary point therefore is the unique global minimizer. Setting the first derivative to zero gives

Substituting this value yields \(e^{\alpha^*}=\sqrt{(1-\epsilon)/\epsilon}\) and \(e^{-\alpha^*}=\sqrt{\epsilon/(1-\epsilon)}\). Consequently,

At \(\epsilon=0\), \(Z(\alpha)=e^{-\alpha}\), which is positive at every finite \(\alpha\) and tends to zero as \(\alpha\to+\infty\). At \(\epsilon=1\), \(Z(\alpha)=e^\alpha\), which tends to zero as \(\alpha\to-\infty\) and is positive for every finite \(\alpha\). These facts establish the two endpoint claims. \(\square\)

The minimizer is positive when \(0<\epsilon<1/2\), zero when \(\epsilon=1/2\), and negative when \(1/2<\epsilon<1\). If the weighted edge is written as \(\gamma=1-2\epsilon\), then, for \(-1<\gamma<1\), the same expression is \(\alpha^*=\frac12\log((1+\gamma)/(1-\gamma))\). The error form makes the endpoint and above-chance distinctions explicit.

The Normalized Example-Weight Update

For a finite minimizing coefficient with \(0<\epsilon<1\), substitute the optimal coefficient into the update definition. An incorrect example has \(y_i h(x_i)=-1\), so its multiplier is \(e^{\alpha^*}\). A correct example has \(y_i h(x_i)=+1\), so its multiplier is \(e^{-\alpha^*}\). The following result gives the normalized update in full.

Proof. Sum the updated weights over the incorrect examples. Their unnormalized total is \(\epsilon e^{\alpha^*}\). Using \(e^{\alpha^*}=\sqrt{(1-\epsilon)/\epsilon}\), this total is \(\sqrt{\epsilon(1-\epsilon)}\). Divide by \(Z(\alpha^*)=2\sqrt{\epsilon(1-\epsilon)}\) to obtain \(1/2\). For the correct examples, the unnormalized total is \((1-\epsilon)e^{-\alpha^*}=\sqrt{\epsilon(1-\epsilon)}\); division by the same normalizer also gives \(1/2\). The two totals sum to one, as required for a probability distribution. \(\square\)

When \(0<\epsilon<1/2\), the incorrect examples have a larger multiplier than the correct examples: \(e^{\alpha^*}>e^{-\alpha^*}\). Thus their relative weights rise, while correct examples’ relative weights fall, and the total mass of each group becomes one half. When \(1/2<\epsilon<1\), the coefficient is negative, so \(e^{\alpha^*}<e^{-\alpha^*}\): the correct examples receive the larger multiplier. The normalized group totals are still one half each. At \(\epsilon=1/2\), \(\alpha^*=0\), \(Z(\alpha^*)=1\), and the update leaves every weight unchanged.

Common Pitfall and Practical Meaning

A common mistake is to say that AdaBoost’s coefficient always increases the relative weight of misclassified examples. That conclusion silently assumes \(0<\epsilon<1/2\). With \(\epsilon=0.75\), for instance, the optimal error multiplier is \(1/\sqrt3\), smaller than the correct multiplier \(\sqrt3\); the coefficient is negative, not positive. The accurate statement is that a rule with weighted error below one half receives a positive coefficient and increases errors’ weights relative to correct examples. A rule above one half receives a negative coefficient and does the reverse. A tied rule receives coefficient zero.

The endpoint cases also require care. The logarithmic formula gives a finite minimizer only for \(0<\epsilon<1\). At either endpoint, the loss has no finite minimizer; it has an infimum approached as the coefficient diverges in the appropriate direction. Substituting \(\epsilon=0\) or \(1\) into the formula and treating the result as an ordinary finite update is therefore invalid.