next up previous
Next: EM Algorithm Applet [3 Up: MLA_Exercises_160106 Previous: Bagging and Boosting [6+2*

Forward Stagewise Additive Modeling [4 P]

Boosting can be seen as a way of fitting an additive model of the form

$\displaystyle f(x) = \sum_{m=1}^{M} \beta_m C(x; \gamma_m), $

where $ \beta_m,  m=1,\ldots,M$ are the expansion coefficients, i.e. the weights of the contributions of the weak classifiers in AdaBoost. $ C(x; \gamma_m)$ are the basis functions, in AdaBoost these are the individual classifiers $ C_m(x) := C(x; \gamma_m) \in \{-1, 1\}$ , where $ \gamma_m$ is the parametrization of the classifiers (e.g. a string describing split variables, split points and predictions of a decision tree). Additive models are fit by minimizing a loss function $ L(y, f(x))$ averaged over the training data:

$\displaystyle \min_{\{\beta_m, \gamma_m\}_{m=1}^M} \sum_{i=1}^{N} L \left( y_i, \sum_{m=1}^M \beta_m C(x_i; \gamma_m) \right).$

In forward stagewise modeling we start with $ f_0(x) = 0$ and add new basis functions sequentially, without adjusting the parameters and coefficients of those that have already been added. So at iteration $ m$ we find the new expansion coefficient $ \beta_m$ and the parameters $ \gamma_m$ of the classifier $ C_m$ by

$\displaystyle (\beta_m, \gamma_m) = \arg \min_{\beta, \gamma} \sum_{i=1}^N L(y_i, f_{m-1}(x_i) + \beta C(x_i, \gamma)) $

$\displaystyle f_m(x) = f_{m-1}(x) + \beta_m C(x; \gamma_m) $

Show that AdaBoost.M12 is equivalent to forward stagewise additive modeling using the exponential loss function $ L(y, f(x)) = exp(-y f(x))$ . Prove all details.

Hints:


next up previous
Next: EM Algorithm Applet [3 Up: MLA_Exercises_160106 Previous: Bagging and Boosting [6+2*
Pfeiffer Michael 2006-01-18