AdaBoost
Definition taught in Ensembles, random forests, and boosting, part of Statistical learning
AdaBoost
| Type | Definition |
| Taught in | Ensembles, random forests, and boosting |
| Part | Statistical learning |
| Questions using it | 1 |
Training data \{x_i,y_i\}_{i=1}^{n_{\mathrm{train}}}, with x_i\in\mathbb{R}^p and y_i\in\{-1,+1\}.
Definition
- Set w_{1,i}=1/n_{\mathrm{train}} for all i.
- For t=1,\ldots,T:
- Fit a learner f_t, taking values in \{-1,+1\}, to minimise the weighted training error \varepsilon_t =\frac{\sum_i w_{t,i}\,Q[y_i,f_t(x_i)]}{\sum_i w_{t,i}}, where Q[a,b]=0 if a=b and Q[a,b]=1 otherwise.
- Let \alpha_t=\frac12\log\frac{1-\varepsilon_t}{\varepsilon_t}.
- Update the weights. A correct case is multiplied by e^{-\alpha_t} and an incorrect case by e^{\alpha_t}, which is the single factor e^{-\alpha_t y_i f_t(x_i)}: w_{t+1,i} =\frac{w_{t,i}\,e^{-\alpha_t y_i f_t(x_i)}}{Z_t}, \qquad Z_t=\sum_{i=1}^{n_{\mathrm{train}}} w_{t,i}\,e^{-\alpha_t y_i f_t(x_i)}.
The ensemble is the sign of the weighted vote,
f(x)=\operatorname{sign}\Biggl(\sum_{t=1}^T \alpha_t f_t(x)\Biggr).
Used in
- Taught in Ensembles, random forests, and boosting, where the derivation and examples are.
- Questions that use it (1) — A tempting wrong turn
- All 7 questions on Ensembles, random forests, and boosting
See also
Training set · Ensemble method · Gradient boosting · Squared error of an average · Random forest · The reweighted error is one half · Why averaging helps · Ensemble error decomposition