Train gradient boosted trees

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

In gradient boosting, increasing the number of iterations reduces the error on the training set, but increases the risk of overfitting.^[1] An optimal number of gradient boosting iterations is often selected by monitoring prediction error on a separate validation data set.^[1] Hold back a validation set and let it decide when to stop adding trees, rather than fixing a large number of rounds in advance. (Meridian's view) In tree boosting, the higher the tree depth, the more likely the model will overfit the training data.^[1]

Shrinkage regularises gradient boosting by scaling the contribution of each weak learner by a constant factor, called the learning rate.^[2][1] Small learning rates have been found empirically to improve generalisation dramatically over gradient boosting without shrinkage, at the price of more computation, since a lower learning rate requires more iterations.^[1] In scikit-learn, smaller values of the learning_rate parameter require larger numbers of weak learners to keep the same training error.^[2]

In scikit-learn, the histogram-based gradient boosting estimators can be orders of magnitude faster than the GradientBoostingClassifier and GradientBoostingRegressor estimators when there are more than tens of thousands of samples.^[2] In scikit-learn, the histogram-based gradient boosting estimators stop early by default when the training set has at least 10,000 samples, using the validation loss.^[2] In scikit-learn, GradientBoostingClassifier with more than two classes induces one regression tree per class at each iteration.^[2] In RapidMiner's Gradient Boosted Trees operator, which runs H2O, the result may depend on the number of threads used, and a reproducible parameter makes model building reproducible, with parallelism set by a maximum number of threads.^[3]

The method

The idea of gradient boosting originated in the observation by Leo Breiman that boosting can be interpreted as an optimisation algorithm on a suitable cost function.^[1] Jerome H. Friedman developed explicit regression gradient boosting algorithms, in 1999 and later in 2001.^[1] KNIME's Gradient Boosted Trees Learner follows the algorithm in section 4.6 of Friedman's paper Greedy Function Approximation: A Gradient Boosting Machine, using very shallow regression trees.^[4]

In least-squares regression, each stage of gradient boosting fits a new estimator to the residuals of the model so far, so each new estimator attempts to correct the errors of its predecessor.^[1] In scikit-learn, the initial gradient boosting model is by default the constant that minimises the loss, which for a least-squares loss is the mean of the target values.^[2] Gradient boosting extends to other losses by plugging in a different loss and its gradient, following from the observation that residuals are proportional to the negative gradients of the mean squared error loss.^[1] Gradient boosting targets pseudo-residuals instead of the residuals of traditional boosting.^[1] Gradient boosting is typically used with decision trees of a fixed size as base learners, especially classification and regression trees (CARTs).^[1] The number of terminal nodes in each boosted tree controls the maximum allowed level of interaction between variables in the model.^[1][2]

Friedman also proposed stochastic gradient boosting, motivated by Breiman's bootstrap aggregation (bagging), in which each base learner is fitted on a subsample of the training set drawn at random without replacement.^[1][2] A subsample of 0.5, half the training set for each base learner, is a typical value in stochastic gradient boosting.^[1][2] The histogram-based gradient boosting estimators in scikit-learn, inspired by LightGBM, first bin the input samples into integer-valued bins, typically 256, which greatly reduces the number of splitting points to consider.^[2]

Compared with the alternatives

Gradient boosting generalises boosting to arbitrary differentiable loss functions.^[2][1] In scikit-learn's histogram-based gradient boosting, trees are built sequentially, each trained to correct the errors of the previous ones, which lets the model improve with relatively few trees.^[2] Gradient-boosted trees usually outperform random forests.^[1] A usual winner is not a guaranteed one: compare a boosted model and a forest on the same held-out rows before settling on either. (Meridian's view)

Sources

1. [1]Gradient boosting - Wikipediasecondary source
2. [2]1.11. Ensembles: Gradient boosting, random forests, bagging, voting, stacking — scikit-learn 1.9.1 documentationdocumentation
3. [3]Gradient Boosted Trees - Rapidminer Documentationdocumentation
4. [4]Gradient Boosted Trees Learnerdocumentation