Gradient Boosting¶

Gradient Boosting is an approach in ensemble learning where models are trained in succession with adaptively weighted training sets to correct the errors of previous models. At its core, gradient boosting applies the principle of gradient descent to the functional space of predictive models.

Boosting algorithms typically use large populations of weak learners like shallow decision trees. Many variations of boosting have been introduced with different approaches to reweighting training data, with AdaBoost perhaps being the most popular. Consider a dataset $\left\{\right(x_1,y_1),...,(x_n,y_n\left)\right\}$ where a set of weak classifiers $\{f_1,...,f_m\}$ are combined to output a classification label $y_n\in \{1,...,C\}$ for each item. The boosted ensemble makes predictions using a linear combination of the individual classifiers weighted by ${\alpha }_i$.

$$F\left(x_i\right)={\alpha }_1{f}_1\left(x_i\right)+...+{\alpha }_n{f}_m\left(x_i\right)$$

Observation weights are initialized to $w_i=\frac{1}{n}$ for each sample in the training set. Then, for each classifier in the ensemble of size $m$, a classifier $f_m$ is fit to the training data using the training set weights where the error is computed:

$$err\left(f_m\right)=\frac{{\sum }_{i=1}^n{w}_{i}I(c_i\ne f_m(x_i\left)\right)}{{\sum }_{i=1}^n{w}_i}$$

The classifier weight ${\alpha }_m$ is then computed:

$${\alpha }_m=log\frac{1-err\left(f_m\right)}{err\left(f_m\right)}+log(C-1)$$

The observation weights are then updated to assign more importance to samples the previous classifier misclassified and then re-normalized such that the observation weights ${\sum }_{i=1}^n{w}_i=1$.

$$w_i\leftarrow w_i\cdot exp({\alpha }_m\cdot I(y_i\ne f_m\left(x_i\right)\left)\right)$$