Derive and apply the coefficient that minimizes AdaBoost’s weighted exponential loss for a binary weak learner.
Advanced
11 min read
What You'll Learn
Express the stagewise exponential-loss objective using current observation weights.
Derive the optimal coefficient for a binary learner from its weighted error.
Verify the minimizer using the second derivative and the minimized loss.
Distinguish normalized weights from unnormalized weights in calculations.
Handle learners with error equal to or greater than one-half.
Recognize why the factor of one-half in the coefficient matters.
Why a Weak Learner Gets a Coefficient
AdaBoost adds a weak classifier to a current score rather than replacing the score at each stage. The learner’s coefficient determines how much its prediction changes that score. A coefficient that is too small may fail to reduce the loss enough; one that is too large may overemphasize the learner’s mistakes. Minimizing the exponential loss gives a precise coefficient, determined by the learner’s error under the current observation weights.
The derivation below concerns binary classification with labels and learner predictions coded as \(-1\) or \(+1\). It assumes the current score is fixed while the coefficient of one candidate learner is chosen. It does not determine how the observation weights are updated after that choice.
Definition: Let \(y_i\in\{-1,+1\}\) be the class label for observation \(i\), and let \(h_i\in\{-1,+1\}\) be the prediction from a candidate weak learner. The prediction is correct when \(y_i h_i=+1\) and incorrect when \(y_i h_i=-1\). Let \(D_i\geq 0\) be the current observation weights, normalized so that \(\sum_i D_i=1\). The learner’s weighted classification error is
$$
\epsilon=\sum_{i:y_i\ne h_i}D_i.
$$
If the current score is \(F_{\mathrm{old}}(x_i)\), adding the learner with coefficient \(\alpha\) gives \(F_{\mathrm{new}}(x_i)=F_{\mathrm{old}}(x_i)+\alpha h_i\). The exponential loss for observation \(i\) is \(\exp[-y_iF(x_i)]\). The current weights are proportional to the loss contributions from the existing score, so the part of the total loss that depends on \(\alpha\) is proportional to
$$
L(\alpha)=\sum_i D_i\exp(-\alpha y_i h_i).
$$
Because \(y_i h_i\) is \(+1\) for a correct prediction and \(-1\) for an incorrect prediction, the objective separates into two terms:
This reduction is the key step: once the current weighted error is known, the individual observations no longer need to appear separately in the coefficient calculation.
Deriving the Minimizing Coefficient
Assume first that \(0<\epsilon<1\) and allow \(\alpha\) to be any real number. Differentiate the objective with respect to \(\alpha\):
At an interior minimum, the derivative is zero. Rearranging that equation gives \(\epsilon e^\alpha=(1-\epsilon)e^{-\alpha}\), so \(e^{2\alpha}=(1-\epsilon)/\epsilon\). Taking logarithms yields the optimal coefficient:
Theorem: For a binary learner with \(0<\epsilon<1\), minimizing the weighted exponential loss over real \(\alpha\) gives
$$
\alpha^*=\frac{1}{2}\log\left(\frac{1-\epsilon}{\epsilon}\right).
$$
The second derivative is \(L''(\alpha)=(1-\epsilon)e^{-\alpha}+\epsilon e^\alpha>0\), so this stationary point is the unique global minimum.
The factor \(1/2\) follows from the coding \(y_i,h_i\in\{-1,+1\}\): a correct prediction contributes \(e^{-\alpha}\), while an incorrect one contributes \(e^\alpha\). Equating the two weighted contributions involves \(e^{2\alpha}\), not \(e^\alpha\). A different score or label convention can change the expression, so the formula should not be transferred without checking how predictions enter the loss.
At the optimum, the two weighted contributions are equal. Substituting \(e^{-\alpha^*}=\sqrt{\epsilon/(1-\epsilon)}\) and \(e^{\alpha^*}=\sqrt{(1-\epsilon)/\epsilon}\) gives the minimized loss:
This expression is for normalized weights, so \(L(0)=1\). If the weights are not normalized, let \(W_C\) be their sum over correctly classified observations and \(W_E\) their sum over incorrectly classified observations. Then the objective is \(W_Ce^{-\alpha}+W_Ee^\alpha\), and, when both sums are positive, its minimizer and minimum are
The same coefficient results because multiplying every observation weight by the same positive constant does not change the minimizer. It does, however, multiply the objective’s minimum by that constant.
Worked Applications
Worked Example: Calculating the Coefficient From Normalized Weights
In a hypothetical classification of claim files for additional review, a candidate learner is evaluated on six files. Their current normalized weights are \(0.08, 0.12, 0.15, 0.20, 0.18,\) and \(0.27\). The learner misclassifies the files with weights \(0.12\) and \(0.18\). Find its weighted error, its optimal coefficient, and its minimized weighted exponential loss.
Method. Add the weights of the misclassified files to obtain the weighted error. Then use the normalized-weight formula. This avoids treating every file as equally important merely because there are six of them.
First check the total weight:
$$
0.08+0.12+0.15+0.20+0.18+0.27=1.00.
$$
The weights are normalized. The weighted error is
$$
\epsilon=0.12+0.18=0.30,
$$
so the correctly classified weight is \(1-0.30=0.70\).
The coefficient is
$$
\alpha^*=\frac{1}{2}\log\left(\frac{0.70}{0.30}\right)
=\frac{1}{2}\log\left(\frac{7}{3}\right)
\approx 0.4236.
$$
The exponential factors at this coefficient are
$$
e^{-\alpha^*}=\sqrt{\frac{3}{7}}\approx0.6546537,
\qquad
e^{\alpha^*}=\sqrt{\frac{7}{3}}\approx1.5275252.
$$
Thus, showing unrounded contributions before rounding the total,
$$
L(\alpha^*)=
0.70(0.6546537)+0.30(1.5275252)
\approx0.4582576+0.4582576
=0.9165152\approx0.9165.
$$
The formula for the minimum checks this result:
$$
2\sqrt{0.70(0.30)}=2\sqrt{0.21}\approx0.9165.
$$
To four decimal places, the coefficient is \(0.4236\) and the minimum is \(0.9165\). Since the initial loss is \(L(0)=1\), this learner reduces the weighted exponential loss.
Worked Example: Using Unnormalized Weights
For a different candidate classifier, the total current weight on correctly classified records is \(26\), and the total on misclassified records is \(14\). Find the optimal coefficient and the minimum unnormalized objective. Also check the result by comparing the two contributions at the optimum.
Method. Work directly with the correct and incorrect weight totals. This avoids rounding a normalized error before using it.
The objective is \(L(\alpha)=26e^{-\alpha}+14e^\alpha\), so
$$
\alpha^*=\frac{1}{2}\log\left(\frac{26}{14}\right)
=\frac{1}{2}\log\left(\frac{13}{7}\right)
\approx0.3095.
$$
At this coefficient,
$$
e^{-\alpha^*}=\sqrt{\frac{7}{13}},
\qquad
e^{\alpha^*}=\sqrt{\frac{13}{7}}.
$$
The correct and incorrect contributions are, retaining the unrounded factors,
$$
26\sqrt{\frac{7}{13}}\approx19.0788,
\qquad
14\sqrt{\frac{13}{7}}\approx19.0788.
$$
They are equal, as required by the derivative condition. The minimum is
$$
L(\alpha^*)=2\sqrt{26(14)}=2\sqrt{364}\approx38.1576.
$$
For a check, the loss at \(\alpha=0\) is \(26+14=40\), which exceeds \(38.1576\). The minimum formula and the equal-contribution check agree.
Worked Example: Comparing Two Candidate Learners
A hypothetical model has normalized current weights. Candidate A has weighted error \(0.18\), and candidate B has weighted error \(0.25\). For each learner, calculate the optimal coefficient and minimized loss. Which learner gives the smaller minimized loss?
Method. Apply the coefficient formula and the minimized-loss formula to each error separately. This comparison is based on the current weighted errors, not on unweighted counts.
For candidate A, the correct weight is \(1-0.18=0.82\). Therefore,
$$
\alpha_A^*=\frac{1}{2}\log\left(\frac{0.82}{0.18}\right)
=\frac{1}{2}\log\left(\frac{41}{9}\right)
\approx0.7582,
$$
and
$$
L_A(\alpha_A^*)=2\sqrt{0.18(0.82)}
=2\sqrt{0.1476}\approx0.7684.
$$
For candidate B, the correct weight is \(1-0.25=0.75\). Thus,
$$
\alpha_B^*=\frac{1}{2}\log\left(\frac{0.75}{0.25}\right)
=\frac{1}{2}\log(3)
\approx0.5493,
$$
and
$$
L_B(\alpha_B^*)=2\sqrt{0.25(0.75)}
=2\sqrt{0.1875}\approx0.8660.
$$
Both losses are below \(L(0)=1\), but candidate A has the smaller minimized loss. Its coefficient is also larger. The results check against the fact that, for errors below one-half, a smaller weighted error gives both a larger positive coefficient and a smaller minimized loss.
When the Usual Interpretation Needs Care
The coefficient formula has useful boundary and sign cases. For \(0<\epsilon<1/2\), \(\alpha^*>0\), so the learner receives a positive coefficient. At \(\epsilon=1/2\), the coefficient is zero and the minimized loss is \(1\): under the current weights, this learner does not improve the objective. For \(1/2<\epsilon<1\), the unrestricted minimizer is negative. Reversing all of the learner’s predictions changes its error from \(\epsilon\) to \(1-\epsilon<1/2\), producing the same fitted contribution when paired with the sign-reversed coefficient. In practice, whether to reverse or reject a learner depends on the fitting procedure’s conventions.
If \(\epsilon=0\), every positive-weight observation is classified correctly, and \(L(\alpha)=e^{-\alpha}\) tends to zero as \(\alpha\) tends to positive infinity. There is no finite minimizing coefficient. If \(\epsilon=1\), the corresponding infimum is approached as \(\alpha\) tends to negative infinity. These boundary cases are not covered by the finite logarithmic formula.
Common exam trap: Omitting the factor \(1/2\) gives the wrong coefficient under the \(-1,+1\) coding. For \(\epsilon=0.30\), the incorrect calculation \(\log(0.70/0.30)\approx0.8473\) is twice the correct coefficient. The derivative equation is \((1-\epsilon)e^{-\alpha}=\epsilon e^\alpha\), which gives \(e^{2\alpha}=(1-\epsilon)/\epsilon\), hence \(\alpha^*=\frac12\log((1-\epsilon)/\epsilon)\). Another frequent error is to calculate \(\epsilon\) from the number of mistakes rather than their current weights.
The derivation matters because it connects a learner’s weighted error to the size of its contribution: the coefficient is not an arbitrary tuning constant in this one-dimensional minimization. The result is specific to minimizing the exponential loss over the coefficient of a binary \(-1,+1\) learner, with the current weights held fixed. It does not by itself establish that the learner generalizes well to new observations.
Check Your Understanding
For each problem, use the stated current weights and the binary \(-1,+1\) convention. Give coefficients and losses to four decimal places when a decimal answer is requested.
A learner has normalized weighted error \(0.40\). Find its optimal coefficient and minimized weighted exponential loss. (Answer: \(\alpha^*\approx0.2027\), \(L(\alpha^*)\approx0.9798\).)
With unnormalized weights, the correct total is \(18\) and the incorrect total is \(2\). Find the coefficient and the minimum objective, and compare the minimum with the objective at zero. (Answer: \(\alpha^*=\log(3)\approx1.0986\), minimum \(12\), compared with \(20\) at zero.)
The total current weight is \(50\), of which \(18\) is on misclassified observations. Find the weighted error, the optimal coefficient, and the minimum unnormalized objective. (Answer: \(\epsilon=0.36\), \(\alpha^*=\frac12\log(16/9)\approx0.2877\), minimum \(48\).)
Two candidates have normalized errors \(0.20\) and \(0.10\). Find each optimal coefficient and minimized loss, then identify the better candidate by this objective. (Answer: for error \(0.20\), \(\alpha^*\approx0.6931\) and minimum \(0.8000\); for error \(0.10\), \(\alpha^*\approx1.0986\) and minimum \(0.6000\); the \(0.10\)-error candidate has the smaller minimum.)
A candidate has normalized error \(0.50\). State its optimal coefficient and minimum loss. If instead its error is \(0\), explain why the finite-coefficient formula does not apply. (Answer: at error \(0.50\), \(\alpha^*=0\) and the minimum is \(1\); at error \(0\), the loss approaches \(0\) as \(\alpha\to+\infty\), so no finite minimizer exists.)