= Solution
The <AdaBoost> algorithm starts with weights $w_i^{(1)}=1/n$. For $m=1,\ldots,M$:
* choose $\widehat h_m\in B$ minimizing the weighted classification error
$$
\varepsilon_m=\sum_{i=1}^nw_i^{(m)}
\mathbf1_{\{Y_i\ne\widehat h_m(X_i)\}};
$$
* set
$$
\widehat\beta_m=\frac12\log\frac{1-\varepsilon_m}{\varepsilon_m};
$$
* update and normalize
$$
w_i^{(m+1)}
=\frac{w_i^{(m)}
e^{-\widehat\beta_mY_i\widehat h_m(X_i)}}{
\sum_jw_j^{(m)}
e^{-\widehat\beta_mY_j\widehat h_m(X_j)}}.
$$
Because $h\in B$ implies $-h\in B$, the selected classifier can always have weighted error at most $1/2$, so $\widehat\beta_m\geq0$. The output score is
$$
\boxed{\widehat f=\sum_{m=1}^M\widehat\beta_m\widehat h_m}.
$$
Back to article page
