Boost a weak learner

Status

What other tools call it

Meridian's classification; an independent blind rating agreed on 95.7% of 324 rows (variant, version 3).

Background

When to use it

Boosting improves a model's accuracy particularly by reducing bias, and is used in supervised learning for both classification and regression.^[1] Convex boosting algorithms such as AdaBoost and LogitBoost can be defeated by random noise, a limitation Long and Servedio pointed out in 2008.^[1] In AdaBoost, the error for a row grows exponentially the more confidently the row is misclassified, which results in excessive weights being assigned to outliers.^[3] Where AdaBoost is applied in statistics, early stopping is used to reduce overfitting: training stops once performance on a held-out validation set falls while performance on the training set still improves.^[3]

Gradient boosting is a form of boosting whose weak learners are typically simple decision trees, and with a decision tree as the weak learner the result is called gradient-boosted trees.^[4] In gradient boosting, raising the number of iterations lowers the error on the training set but raises the risk of overfitting.^[4] An optimal number of gradient boosting iterations is often selected by monitoring prediction error on a separate validation data set.^[4] Gradient boosting is regularised by shrinkage, which scales each new model by a learning rate, and small learning rates such as below 0.1 have been found to improve generalisation dramatically.^[4] A lower learning rate in gradient boosting requires more iterations, so training and querying take longer.^[4] Boosting can increase the accuracy of a base learner such as a decision tree, but it sacrifices intelligibility, since following the paths of hundreds or thousands of trees is much harder than following one.^[4]

Hold back a validation set before you boost, and let it decide when to stop adding rounds. (Meridian's view) Look at the rows that end up carrying the most weight before trusting a boosted model, in case they are errors in the data rather than hard cases. (Meridian's view)

The method

Boosting grew from a question Kearns and Valiant posed in 1988 and 1989: can a set of weak learners create a single strong learner?^[1] Robert Schapire's affirmative answer in a 1990 paper led to practical boosting algorithms, and Freund and Schapire later developed AdaBoost.^[1] AdaBoost was formulated by Yoav Freund and Robert Schapire in 1995, and the two won the 2003 Gödel Prize for the work.^[3]

Most boosting algorithms learn weak classifiers one at a time with respect to a distribution over the training data, adding each to the final classifier with a weight related to its accuracy.^[1] After each weak learner is added, misclassified rows gain weight and correctly classified rows lose weight, so later weak learners focus on the rows earlier ones misclassified.^[1] AdaBoost's weak learners need only perform slightly better than random guessing for the final model to be proven to converge to a strong learner.^[3]

Gradient boosting starts from a model consisting of a constant function and expands it greedily, adding one base learner at a time to lower a loss function on the training set.^[4] In least-squares regression, each new gradient boosting model is fitted to the residuals the model built so far leaves.^[4] Gradient boosting generalises other boosting methods by allowing the optimisation of an arbitrary differentiable loss function.^[4] Leo Breiman observed that boosting can be interpreted as an optimisation algorithm on a cost function, and Jerome H. Friedman then developed explicit regression gradient boosting algorithms in 1999 and 2001.^[4] RapidMiner's Additive Regression operator starts from a default model of the mean or mode, learns each new base model on the residuals, and predicts by adding all the base models' predictions.^[5] Gradient boosting goes by several names, among them Gradient Boosting Machine (GBM), Multiple Additive Regression Trees (MART) and Boosted Regression Trees (BRT).^[4]

Compared with the alternatives

Bootstrap aggregating (bagging) fits the same model to random samples of the training data in parallel, while boosting trains each base model in sequence on the up-weighted errors of the one before.^[2] In some cases boosting has yielded better accuracy than bagging, but boosting tends to over-fit more.^[2] In scikit-learn, bagging methods work best with strong and complex models such as fully developed decision trees, while boosting methods usually work best with weak models such as shallow decision trees.^[6] Gradient-boosted trees usually outperform a random forest, which is a common application of bagging.^[4][2]

Sources

1. [1]Boosting (machine learning) - Wikipediasecondary source
2. [2]Ensemble learning - Wikipediasecondary source
3. [3]AdaBoost - Wikipediasecondary source
4. [4]Gradient boosting - Wikipediasecondary source
5. [5]Additive Regression - Rapidminer Documentationdocumentation
6. [6]1.11. Ensembles: Gradient boosting, random forests, bagging, voting, stacking — scikit-learn 1.9.1 documentationdocumentation