Tree ensembles in plain terms

I met decision trees, random forests and XGBoost one evening in a course an assistant was giving me on the scikit-learn workflow. A few months later I ran a random forest, XGBoost and gradient boosting myself, on my own computer in VS Code. One install line brought all of them:

pip install pandas numpy scikit-learn xgboost shap matplotlib seaborn

After that each model is a few lines of Python, so you can run all of them without knowing what they are. They are all built from the same piece, the decision tree.

A decision tree

A decision tree predicts a number by asking yes or no questions about the inputs, one after another. Say the first one is whether the temperature is above 800 C, and the next one is whether the feed is type A. Each answer sends the run down one branch, and at the end of the branches there is a leaf. The prediction for a run that lands in a leaf is the mean of the training runs that landed in the same leaf.11scikit-learn user guide, section 1.10: a tree as a piecewise constant approximation; little data preparation; overfitting, instability and the statement that trees “are not good at extrapolation”; leaf values as the node mean under squared error; the tips on max_depth and min_samples_leaf. It looks like a troubleshooting chart an operator would follow, only here the algorithm picks the questions and the thresholds, and it picks each one so the runs on either side are as alike in their result as possible.

The scikit-learn guide calls the result a piecewise constant approximation.11scikit-learn user guide, section 1.10: a tree as a piecewise constant approximation; little data preparation; overfitting, instability and the statement that trees “are not good at extrapolation”; leaf values as the node mean under squared error; the tips on max_depth and min_samples_leaf. If you plot the prediction against one input you get a staircase and never a smooth curve.

A tree assumes very little. It does not assume a straight line or any other form, and the guide says it needs little data preparation, where other methods often need the inputs normalized first.11scikit-learn user guide, section 1.10: a tree as a piecewise constant approximation; little data preparation; overfitting, instability and the statement that trees “are not good at extrapolation”; leaf values as the node mean under squared error; the tips on max_depth and min_samples_leaf. In scikit-learn it is DecisionTreeRegressor.

The settings control how far the sorting goes. max_depth is how many questions can come in a row, and min_samples_leaf is the smallest number of training runs allowed in a leaf. If you put no limit, the tree keeps splitting until every training run sits in its own leaf, so it reproduces the training data and that is overfitting. The guide suggests starting with a depth of 3.11scikit-learn user guide, section 1.10: a tree as a piecewise constant approximation; little data preparation; overfitting, instability and the statement that trees “are not good at extrapolation”; leaf values as the node mean under squared error; the tips on max_depth and min_samples_leaf. It also says a tree is unstable, meaning a small change in the data can give a completely different tree, and that the way around it is to use trees inside an ensemble.11scikit-learn user guide, section 1.10: a tree as a piecewise constant approximation; little data preparation; overfitting, instability and the statement that trees “are not good at extrapolation”; leaf values as the node mean under squared error; the tips on max_depth and min_samples_leaf. An ensemble is many models combined into one, and the next three are ensembles of trees.

A random forest

A random forest grows many trees and averages their predictions. Two things make the trees different from each other. Each tree is built on a bootstrap sample, which is a random draw of the training runs with replacement, so some runs appear twice and some do not appear. And at each split the tree may be allowed to look at only a random subset of the features. The guide says the purpose of both is to decrease the variance of the forest.22scikit-learn user guide, section 1.11: bootstrap samples and random feature subsets in random forests, to decrease variance; n_estimators and max_features; gradient boosting as an additive model fitted to negative gradients; learning_rate as shrinkage and its interaction with n_estimators; subsample.

I think of it like replicate analyses. One determination has scatter, and the mean of many has less, as long as they do not all carry the same error. Breiman’s paper says the error of a forest depends on how strong the individual trees are and on the correlation between them,33Breiman (2001), abstract: generalization error converges to a limit as the number of trees becomes large and depends on the strength of the individual trees and the correlation between them. so the randomness is there to make the trees less correlated.

The main settings are n_estimators, the number of trees, and max_features, the size of the random subset at each split.22scikit-learn user guide, section 1.11: bootstrap samples and random feature subsets in random forests, to decrease variance; n_estimators and max_features; gradient boosting as an additive model fitted to negative gradients; learning_rate as shrinkage and its interaction with n_estimators; subsample. Breiman showed that the error converges to a limit as you add trees,33Breiman (2001), abstract: generalization error converges to a limit as the number of trees becomes large and depends on the strength of the individual trees and the correlation between them. so more trees cost you computing time and do not overfit. In a tuning search I ran later, the random forest was one of the slow models to tune.

Gradient boosting

Boosting also adds trees together, but it builds them one after another. Each new tree is fitted to what the trees before it still get wrong. In Friedman’s method the new tree is fitted to the negative gradient of the loss, and for squared error that is the current residual, measured minus predicted.44Friedman (2001), abstract: function estimation as numerical optimization in function space, a general gradient descent boosting method for any fitting criterion, with specific algorithms for regression trees. 22scikit-learn user guide, section 1.11: bootstrap samples and random feature subsets in random forests, to decrease variance; n_estimators and max_features; gradient boosting as an additive model fitted to negative gradients; learning_rate as shrinkage and its interaction with n_estimators; subsample. To me it is like trimming out an offset in small moves until it is gone.

So the settings mean different things here. n_estimators is the number of correction steps. learning_rate is the fraction of each correction that is kept, and it is also called shrinkage. The guide says the two interact strongly, a smaller learning rate needs more trees, and small values favor better test error.22scikit-learn user guide, section 1.11: bootstrap samples and random feature subsets in random forests, to decrease variance; n_estimators and max_features; gradient boosting as an additive model fitted to negative gradients; learning_rate as shrinkage and its interaction with n_estimators; subsample. max_depth is the size of each small tree, and subsample fits each tree on a random fraction of the runs.22scikit-learn user guide, section 1.11: bootstrap samples and random feature subsets in random forests, to decrease variance; n_estimators and max_features; gradient boosting as an additive model fitted to negative gradients; learning_rate as shrinkage and its interaction with n_estimators; subsample.

Boosting cuts the error down step by step, and if you give it enough steps it goes on to fit the noise in the training runs. So in boosting the number of trees is a setting you have to tune, and the guide treats shrinkage as a way to control overfitting.22scikit-learn user guide, section 1.11: bootstrap samples and random feature subsets in random forests, to decrease variance; n_estimators and max_features; gradient boosting as an additive model fitted to negative gradients; learning_rate as shrinkage and its interaction with n_estimators; subsample. In scikit-learn it is GradientBoostingRegressor.

XGBoost

XGBoost is a separate library, which is why it has its own name in the install line, and the method inside it is gradient boosting of trees. Chen and Guestrin describe it as a scalable tree boosting system, and most of their paper is about speed on very large data, like handling sparse inputs and using memory and disk well.55Chen and Guestrin (2016), abstract and sections 2.1 and 2.3: the regularized objective penalizing the number of leaves and the leaf weights; shrinkage after Friedman and column subsampling as in random forests. I do not think any of that matters for a table of a few tens of rows.

What matters at any size is that XGBoost adds a penalty to the loss for how complex each tree is, counted by the number of leaves and the size of the leaf values. The authors say that with this term set to zero you are back to traditional gradient tree boosting.55Chen and Guestrin (2016), abstract and sections 2.1 and 2.3: the regularized objective penalizing the number of leaves and the leaf weights; shrinkage after Friedman and column subsampling as in random forests. It also uses shrinkage from Friedman and it subsamples the feature columns like a random forest does.55Chen and Guestrin (2016), abstract and sections 2.1 and 2.3: the regularized objective penalizing the number of leaves and the leaf weights; shrinkage after Friedman and column subsampling as in random forests. In Python the penalty is reg_lambda and gamma, the shrinkage is learning_rate and the column subsampling is colsample_bytree, next to the same n_estimators and max_depth as before.66XGBoost documentation, XGBoost parameters: eta (alias learning_rate), max_depth, colsample_bytree, lambda (alias reg_lambda) and gamma. The model is XGBRegressor.

Outside the training range

Every one of these models ends in leaves, and a leaf holds a constant that came from training runs. Say a tree was trained on runs between 600 and 900 C and you ask it about 1000 C. The last question about temperature that the tree learned has its threshold somewhere below 900 C. The 1000 C point answers that question the same way a 900 C run does, so it lands in the same leaf and gets the same prediction. The staircase is flat after its last step. The scikit-learn guide says it directly, tree predictions are piecewise constant and so they are not good at extrapolation.11scikit-learn user guide, section 1.10: a tree as a piecewise constant approximation; little data preparation; overfitting, instability and the statement that trees “are not good at extrapolation”; leaf values as the node mean under squared error; the tips on max_depth and min_samples_leaf.

Averaging does not change this, because an average of flat lines is flat, and a sum of small flat corrections is flat too. So a forest or a boosted model follows the trend up to the edge of the data and then holds the last value, and no setting fixes that. A straight line fit would at least keep its slope, right or wrong. A tree ensemble gives you the answer for the nearest condition it has seen, and it gives no sign that you asked outside its range. So before I believe a prediction from one of these, I compare the new condition with the minimum and maximum of each feature in the training table.

Footnotes

1. scikit-learn user guide, section 1.10: a tree as a piecewise constant approximation; little data preparation; overfitting, instability and the statement that trees “are not good at extrapolation”; leaf values as the node mean under squared error; the tips on max_depth and min_samples_leaf. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

2. scikit-learn user guide, section 1.11: bootstrap samples and random feature subsets in random forests, to decrease variance; n_estimators and max_features; gradient boosting as an additive model fitted to negative gradients; learning_rate as shrinkage and its interaction with n_estimators; subsample. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

3. Breiman (2001), abstract: generalization error converges to a limit as the number of trees becomes large and depends on the strength of the individual trees and the correlation between them. ↩ ↩²

4. Friedman (2001), abstract: function estimation as numerical optimization in function space, a general gradient descent boosting method for any fitting criterion, with specific algorithms for regression trees. ↩

5. Chen and Guestrin (2016), abstract and sections 2.1 and 2.3: the regularized objective penalizing the number of leaves and the leaf weights; shrinkage after Friedman and column subsampling as in random forests. ↩ ↩² ↩³

6. XGBoost documentation, XGBoost parameters: eta (alias learning_rate), max_depth, colsample_bytree, lambda (alias reg_lambda) and gamma. ↩