Following AdaBoost Through Several Rounds
AdaBoost builds a classifier in stages. At each stage, a weak learner is fit using the current observation weights, so mistakes on heavily weighted observations matter more than mistakes on lightly weighted ones. The next set of weights then emphasizes observations the learner classified incorrectly. A worked calculation must keep these two ideas separate: the weighted error determines the learner’s coefficient, and that coefficient determines the weight update.
Use binary class labels \(y_i\in\{-1,+1\}\) and a weak classifier \(h_t(x_i)\in\{-1,+1\}\). At round \(t\), let \(D_t(i)\) be the nonnegative weight of observation \(i\), with \(\sum_i D_t(i)=1\). An observation is misclassified when \(y_i\ne h_t(x_i)\).
Because \(y_i h_t(x_i)=+1\) for a correct prediction and \(-1\) for an incorrect prediction, correct observations are multiplied by \(e^{-\alpha_t}\), while misclassified observations are multiplied by \(e^{\alpha_t}\), before normalization. When \(0<\epsilon_t<1/2\), the two groups have a useful simplification: after the update, the total weight on each group is one-half. Individual weights within a group remain proportional to their weights before the update.
Why the Learner Coefficient Has This Form
The coefficient balances the contribution of correct and incorrect predictions at the current round. Given weighted error \(\epsilon_t\), the sum of the unnormalized updated weights is \(Z_t=(1-\epsilon_t)e^{-\alpha_t}+\epsilon_t e^{\alpha_t}\). The correct group contributes the first term; the misclassified group contributes the second.
Differentiate \(Z_t\) with respect to \(\alpha_t\): \(- (1-\epsilon_t)e^{-\alpha_t}+\epsilon_t e^{\alpha_t}=0\) at the minimum.
Moving one term to the other side and multiplying by \(e^{\alpha_t}\) gives \(\epsilon_t e^{2\alpha_t}=1-\epsilon_t\).
Taking logarithms gives \(\alpha_t=\frac12\ln((1-\epsilon_t)/\epsilon_t)\), as stated above.
This coefficient is positive when the learner is better than chance, \(\epsilon_t<1/2\), and is zero when \(\epsilon_t=1/2\). If a candidate learner has error greater than one-half, reversing all its predictions gives error less than one-half. An error of zero makes the displayed coefficient unbounded; in a finite calculation, a perfectly classifying learner is ordinarily a stopping case rather than a round with a finite coefficient.
Worked Rounds With Equal Starting Weights
Worked Example: Three Learners and Four Observations
A hypothetical binary screening task has four observations, with labels \(y=(+1,+1,-1,-1)\). Start with equal weights \(D_1(i)=1/4\). Three candidate weak learners have predictions \(h_1=(+1,+1,-1,+1)\), \(h_2=(+1,-1,-1,-1)\), and \(h_3=(+1,+1,+1,-1)\). Carry out three rounds and give the final class predictions.
Round 1: weighted error and coefficient. Learner \(h_1\) is wrong only on observation 4. Its weighted error is \(\epsilon_1=1/4\), so \(\alpha_1=\frac12\ln((3/4)/(1/4))=\frac12\ln 3\), approximately \(0.5493\). The single misclassified observation receives total updated weight \(1/2\); the three correctly classified observations share the other \(1/2\) in their original proportions. Thus \(D_2=(1/6,1/6,1/6,1/2)\). These weights sum to \(1\).
Round 2: use the current weights. Learner \(h_2\) is wrong only on observation 2. Its error is therefore \(\epsilon_2=D_2(2)=1/6\), not the fraction \(1/4\) of observations it misclassifies. The coefficient is \(\alpha_2=\frac12\ln((5/6)/(1/6))=\frac12\ln 5\), approximately \(0.8047\). Observation 2 receives updated weight \(1/2\). The correctly classified observations, 1, 3, and 4, divide the other half proportionally to their previous weights: \(D_3(1)=D_3(3)=\frac12( (1/6)/(5/6))=1/10\), and \(D_3(4)=\frac12( (1/2)/(5/6))=3/10\). Hence \(D_3=(1/10,1/2,1/10,3/10)\), which sums to \(1\).
Round 3: update again. Learner \(h_3\) is wrong only on observation 3, so \(\epsilon_3=1/10\), and \(\alpha_3=\frac12\ln(9)=\ln 3\), approximately \(1.0986\). Observation 3 receives weight \(1/2\). The correct observations 1, 2, and 4 share the other half proportionally to their weights in \(D_3\): their new weights are \(\frac12( (1/10)/(9/10))=1/18\), \(\frac12( (1/2)/(9/10))=5/18\), and \(\frac12( (3/10)/(9/10))=1/6\). Thus \(D_4=(1/18,5/18,1/2,1/6)\); the entries sum to \(1\).
Final weighted vote. For observation \(i\), calculate \(F(x_i)=\sum_{t=1}^3\alpha_t h_t(x_i)\) and predict \(+1\) if \(F(x_i)>0\), or \(-1\) if \(F(x_i)<0\). Observation 1 has score \(\alpha_1+\alpha_2+\alpha_3\), which is positive. Observation 2 has score \(\alpha_1-\alpha_2+\alpha_3\approx0.8432\), which is positive. Observation 3 has score \(-\alpha_1-\alpha_2+\alpha_3\approx-0.2554\), which is negative. Observation 4 has score \(\alpha_1-\alpha_2-\alpha_3\approx-1.3540\), which is negative. The final predictions are \((+1,+1,-1,-1)\), matching all four labels. The check is consistent with the prediction vectors and with the sign rule for the vote.
Method and mistake avoided. At each round, sum the current weights on the learner’s mistakes; do not count the mistakes as though all observations still had equal weight. In round 2, counting one mistake out of four would incorrectly give error \(1/4\), rather than the correct weighted error \(1/6\).
Unequal Starting Weights and a Vote That Still Makes Mistakes
A weighted vote is not a promise that every training observation will be classified correctly. It combines learners according to their coefficients; a later learner can influence the vote, but an observation’s label is not automatically guaranteed to win.
Worked Example: Unequal Weights, Two Rounds, and the Final Vote
A hypothetical claims-triage dataset has five observations with labels \(y=(+1,+1,-1,-1,+1)\) and initial weights \(D_1=(0.10,0.20,0.30,0.15,0.25)\). Learner \(h_1=(+1,-1,-1,+1,+1)\) is followed by learner \(h_2=(+1,+1,+1,-1,-1)\). Calculate both rounds, the updated weights after each, and the final predictions.
Round 1. Learner \(h_1\) makes mistakes on observations 2 and 4, so \(\epsilon_1=0.20+0.15=0.35=7/20\). Its coefficient is \(\alpha_1=\frac12\ln((13/20)/(7/20))=\frac12\ln(13/7)\), approximately \(0.3095\). The two mistaken observations together receive updated weight \(1/2\); their shares are \(0.20/0.35\) and \(0.15/0.35\), giving weights \(2/7\) and \(3/14\). The correctly classified observations 1, 3, and 5 share the other half in proportion to \(0.10,0.30,0.25\). Their updated weights are \(1/13,3/13,5/26\), respectively. Thus \(D_2=(1/13,2/7,3/13,3/14,5/26)\), approximately \((0.0769,0.2857,0.2308,0.2143,0.1923)\); these weights sum to \(1\).
Round 2. Learner \(h_2\) is wrong on observations 3 and 5. The weighted error is \(\epsilon_2=3/13+5/26=11/26\), approximately \(0.4231\). Therefore \(\alpha_2=\frac12\ln((15/26)/(11/26))=\frac12\ln(15/11)\), approximately \(0.1551\). After the update, observations 3 and 5 share total weight \(1/2\) in the ratio \(3/13:5/26=6:5\), giving weights \(3/11\) and \(5/22\). The correct observations 1, 2, and 4 share the other half in the ratio \(1/13:2/7:3/14\); their weights are \(1/15,26/105,13/70\). Thus \(D_3=(1/15,26/105,3/11,13/70,5/22)\). The correct group sums to \(1/2\), the mistaken group sums to \(1/2\), and all five weights sum to \(1\).
Final vote. The learner coefficients are positive, but \(\alpha_2<\alpha_1\). Observations 1 has positive votes from both learners, so its score is \(\alpha_1+\alpha_2>0\). Observation 2 has votes \((-1,+1)\), so its score is \(-\alpha_1+\alpha_2\approx-0.1544\); it is predicted negative and is wrong. Observation 3 has votes \((-1,+1)\), so its score is also approximately \(-0.1544\); it is predicted negative and is correct. Observation 4 has votes \((+1,-1)\), also giving approximately \(-0.1544\); it is predicted negative and is correct. Observation 5 has votes \((+1,-1)\), likewise giving approximately \(-0.1544\); it is predicted negative and is wrong. The final predictions are \((+1,-1,-1,-1,-1)\), with three of five labels correct.
Method and mistake avoided. Compare coefficients before deciding which vote dominates when learners disagree. The final vote is not determined by the most recent learner alone, nor does the fact that weights were updated guarantee that every observation is classified correctly by the ensemble.
A Close Vote After Two Updates
Worked Example: Tracking a Nearly Tied Final Score
In a hypothetical two-class audit, three observations have labels \(y=(+1,-1,+1)\) and initial weights \(D_1=(0.20,0.30,0.50)\). The first learner predicts \(h_1=(-1,-1,+1)\), and the second predicts \(h_2=(+1,+1,+1)\). Find both coefficients, the weight distributions, and the final prediction for each observation.
Round 1. Learner \(h_1\) is wrong on observation 1 only, so \(\epsilon_1=0.20=1/5\) and \(\alpha_1=\frac12\ln(4)=\ln 2\), approximately \(0.6931\). The mistaken observation receives updated weight \(1/2\). The correctly classified observations 2 and 3 divide the other half in the ratio \(0.30:0.50=3:5\), giving weights \(3/16\) and \(5/16\). Thus \(D_2=(1/2,3/16,5/16)\), and the entries sum to \(1\).
Round 2. Learner \(h_2\) is wrong on observation 2 only. Its weighted error is \(\epsilon_2=3/16\), so \(\alpha_2=\frac12\ln((13/16)/(3/16))=\frac12\ln(13/3)\), approximately \(0.7332\). Observation 2 receives weight \(1/2\). Observations 1 and 3 share the remaining half in the ratio \(1/2:5/16=8:5\), giving weights \(4/13\) and \(5/26\). Therefore \(D_3=(4/13,1/2,5/26)\), which sums to \(1\).
Final vote. Observation 1 receives votes \((-1,+1)\), giving \(F(x_1)=-\ln 2+\frac12\ln(13/3)\approx0.0400\), so it is predicted positive and is correct. Observation 2 receives the same votes and the same positive score, so it is predicted positive and is wrong. Observation 3 receives two positive votes, giving score \(\alpha_1+\alpha_2>0\), so it is predicted positive and is correct. The predictions are \((+1,+1,+1)\), with two of three labels correct. The small score difference for observations 1 and 2 is a useful check: the second coefficient only slightly exceeds the first.
Method and mistake avoided. Preserve the half factor in the coefficient. Using \(\ln((1-\epsilon)/\epsilon)\) without the factor \(1/2\) would double both coefficients and misstate the scale of every vote.
Common Checks Before Accepting a Calculation
- Check the current distribution. Each round’s weighted error uses that round’s weights, not the initial weights. Confirm that the weights sum to one before using them.
- Check which observations are wrong. Compare each prediction to its label. A reversed sign changes the error and all subsequent calculations.
- Check the error range. For a useful weak learner, \(0<\epsilon_t<1/2\), so \(\alpha_t>0\). An error of \(1/2\) gives zero coefficient; an error above \(1/2\) calls for reversing predictions or rejecting that learner.
- Check normalization. For an error strictly between zero and one-half, the updated total weight on mistakes is \(1/2\), as is the total on correct observations. The individual weights must also sum to one.
- Check the final sign, not just the last prediction. Add \(\alpha_t h_t(x_i)\) across rounds and classify by the sign of the sum. A zero score is a tie and requires a stated tie convention.
Check Your Understanding
For each problem, use normalized current weights and the coefficient-weighted vote convention described above.
- A learner has current weights \((0.10,0.25,0.40,0.25)\) and misclassifies observations 2 and 4. Find its weighted error and coefficient. (Answer: \(\epsilon=0.5000\), \(\alpha=0\).)
- At a round, the weights are \((0.20,0.30,0.50)\), and a learner misclassifies only observation 1. Find the weighted error and coefficient. (Answer: \(\epsilon=0.2000\), \(\alpha=\ln 2\approx0.6931\).)
- Current weights are \((0.10,0.20,0.30,0.40)\). A learner gets observations 1 and 4 wrong. Give the weighted error and the total updated weight assigned to the mistaken group, assuming \(0<\epsilon<1/2\). (Answer: \(\epsilon=0.5000\), so \(\alpha=0\); at this boundary the update leaves the weights unchanged, and the mistaken group has weight \(0.50\).)
- Two learners have coefficients \(0.40\) and \(0.70\). For one observation their predictions are \((-1,+1)\), and its true label is \(+1\). Calculate the score and final prediction. (Answer: score \(=-0.40+0.70=0.30\); predict \(+1\), correctly.)
- A two-round ensemble has coefficients \(\alpha_1=\frac12\ln 3\) and \(\alpha_2=\frac12\ln 5\). For an observation, the first learner predicts \(+1\) and the second predicts \(-1\). Find the score and predicted class. (Answer: score \(=\frac12\ln 3-\frac12\ln 5=\frac12\ln(3/5)\approx-0.2554\); predict \(-1\).)