= Solution
Use labels $y_i\in\{-1,1\}$ and base predictions $G_m(x)\in\{-1,1\}$. The binary <AdaBoost> algorithm starts with observation weights $D_1(i)=1/n$ and score $F_0(x)=0$. For rounds $m=1,\ldots,M$:
* Fit the <weak learner> to the training observations using weights $D_m(i)$, producing $G_m$.
* Compute its weighted error $\epsilon_m=\sum_iD_m(i)\mathbf1_{\{G_m(x_i)\ne y_i\}}$.
* For $0<\epsilon_m<1/2$, choose $\alpha_m=\tfrac12\log[(1-\epsilon_m)/\epsilon_m]$ and update $F_m=F_{m-1}+\alpha_mG_m$.
* Reweight and normalize: $D_{m+1}(i)=D_m(i)e^{-\alpha_m y_iG_m(x_i)}/Z_m$, where $Z_m$ is the sum of the unnormalized weights.
The final classifier is
$$
\boxed{\widehat G(x)=\operatorname{sign}\left\{\sum_{m=1}^M\alpha_mG_m(x)\right\}.}
$$
Resolve a zero-score tie by a fixed convention. A classifier with error above $1/2$ may be sign-reversed if the base class permits it; otherwise it fails the weak-learning requirement and should be replaced. Error $1/2$ gives zero weight and no improvement. Error zero gives the limiting perfect-classifier step with infinite coefficient, so terminate with that classifier rather than computing the undefined finite update. Misclassified observations are multiplied by $e^{\alpha_m}$ and correctly classified observations by $e^{-\alpha_m}$, increasing the relative weight of errors for the next round. The procedure is sequential, and its number of rounds is a tuning parameter.
Back to article page
