Boosting

Summary

The underlying idea of this method is to combine simple "rules" or weak learners, each performing only slightly better than random, to form an ensemble such that the performance of the single ensemble member is improved, i.e "boosted". Let $h_{1},h_{2},\ldots ,h_{T}$ be a set of hypotheses, and consider the composite ensemble hypothesis

$f(x)=\sum _{t=1}^{T}\alpha _{t}h_{t}(x)$

Here $\alpha _{t}$ denotes the coefficient with which the ensemble member $h_{t}$ is combined; both $\alpha _{t}$ and the learner or the hypotheses $h_{t}$ are to be learned within the Boosting procedure. The coefficients $\alpha _{t}'s$ (or weights) are set in iterations. The intuitive idea is that examples that are misclassified get higher weights in the next iteration, for instance the examples near the decision boundary are usually harder to classify and therefor get high weights after a few iterations.

AdaBoost

Tha AdaBoost algorithm by Freund and Schapire is one of the most successful Boosting algorithm. We focus on the problem of binary classfication and present the AdaBoost algorithm for it.

A non negative weighting $\mathbf {d} ^{(t)}=(d_{1}^{(t)},\ldots ,d_{N}^{(t)})$ is assigned to the data at step $t$, and a weak learner $h_{t}$ is constructed based on $\mathbf {d} ^{(t)}$. This weighting is updated at each iteration $t$ according to the weighted error incurred by the weak learner in the last iteration. At each step $t$, the weak learner is required to produce a small weighted empirical error defined by

$\varepsilon _{t}(h_{t},\mathbf {d} ^{(t)})=\sum _{n=1}^{N}d_{n}^{(t)}\mathbf {I} (y_{n}\neq h_{t}({\boldsymbol {x}}_{n}))$

After selecting the hypothesis $h_{t}$, its weight $\alpha _{t}$ is computed such that it minimizes a certain loss function. In AdaBoost one minimizes

$\mathrm {G} ^{AB}(\alpha )=\sum _{n=1}^{N}\mathrm {exp} \{-y_{n}(\alpha h_{t}({\boldsymbol {x}}_{n})+f_{t-1}({\boldsymbol {x}}_{n}))\}$,

where $f_{t-1}$ is the combined hypotheses of the previous iteration given by

$f_{t-1}({\boldsymbol {x}}_{n})=\sum _{r=1}^{t-1}\alpha _{r}h_{r}({\boldsymbol {x}}_{n})$

For AdaBoost it has been shown that $\alpha _{t}$ can be computed analytically leading to the expression in step (3c) of the algorithm. Based on the new combined hypotheses, the weighting ${\boldsymbol {d}}$ of the sample is updated as in step (3d) of algorithm. The initial weighting ${\boldsymbol {d}}^{(1)}$ is chosen uniformly: $d_{n}^{(n)}=1/N$