Decision Trees, Random Forests and Gradient Boosting

A decision tree predicts by asking a sequence of yes-or-no questions about the features, each answer sending the example down one branch until it reaches a leaf that holds the prediction.

Definition: Each internal node tests one feature against one threshold, such as debt-to-income above 0.4? A leaf predicts the majority class (classification) or the mean label (regression) of the training examples that ended up there.

Trees have properties the linear models from earlier in this course lack:

• Interactions for free. A split on income inside the branch for young applicants means income matters differently by age, with no engineered feature.
• No scaling needed. A threshold on square metres works the same as one on square feet.
• Mixed feature types. Numbers, categories and missing values can all be split on.
• Readable when small. A depth-3 tree fits on a slide and can be checked by a domain expert.

Their weakness is the flip side of that flexibility, and fixing it is what random forests and boosting are for.

Each path from the top to a leaf is one rule. This tree encodes three.

Trees are grown greedily. At each node the algorithm tries every feature and every candidate threshold, and keeps the split that makes the children purest. For classification, scikit-learn's default purity measure is Gini impurity, the chance that two examples drawn at random from the node have different labels:

A worked split: a node holds 10 examples, 5 of each class, so $G = 1 - (0.5^2 + 0.5^2) = 0.5$. A candidate threshold sends 4 examples left, all positive ($G = 0$), and 6 right, 1 positive and 5 negative:

Weighted by size, the children score $0.4 \times 0 + 0.6 \times 0.278 \approx 0.167$, an impurity decrease of $0.333$. The algorithm compares that decrease with every other candidate, takes the best, and recurses into each child.

Gotcha: Greedy means locally best. A split that looks useless alone but enables a great split below it can be skipped, which is one reason single trees are unstable.

Left unconstrained, a tree keeps splitting until every leaf is pure, which on data without exact duplicates means one leaf per awkward example. That is a lookup table with extra steps.

On scikit-learn's built-in breast cancer dataset (569 tumours, 30 measurements each), a fully grown tree scores 100% on its training data and 91.7% under five-fold cross-validation. Capping the depth at 3 lowers training accuracy to 97.9% but leaves cross-validated accuracy at 91.7%: less memorisation, no better generalization.

The usual controls, all constructor arguments in scikit-learn:

The deeper problem is variance: retrain on a slightly different sample and the top split can change, reshaping everything below it. Constraining the tree trades that variance for bias. Ensembles find a better trade.

If individual trees are unstable, average many of them. Leo Breiman's random forest (Machine Learning, 2001) builds each tree with two sources of randomness:

1. Bootstrap sampling: each tree trains on a sample of the rows drawn with replacement, so each sees a different dataset.
2. Random features per split: each split considers only a random subset of the features. scikit-learn's default for classification is the square root of the feature count, so about 5 of 30.

The forest predicts by majority vote or by averaging. Breiman showed that a forest's error depends on two things: the strength of the individual trees and the correlation between them. Averaging only cancels errors the trees do not share. Random feature selection exists to decorrelate them, because without it every tree would pick the same dominant feature at the top and make the same mistakes.

Key idea: Breiman also proved that the forest's generalization error converges as trees are added. More trees cost compute but do not cause overfitting; past some point they simply stop moving the score.

Boosting builds trees in sequence instead of in parallel. Each new tree is fitted to what the ensemble so far gets wrong. Jerome Friedman's formulation (Annals of Statistics, 2001) treats this as gradient descent in the space of functions:

For squared error the negative gradient is simply the residual $y - F_{m-1}(x)$, so each small tree $h_m$ literally predicts the remaining error. Other losses, such as log loss for classification, plug into the same recipe through their gradients.

The learning rate $\nu$ (scikit-learn's default is 0.1) shrinks each tree's contribution, so no single tree can dominate. Smaller rates need more trees but usually generalize better. Unlike a forest, boosting can overfit as trees are added, because each one chases the training residuals further. The standard guard is early stopping: hold out a validation slice and stop when its score has not improved for a set number of rounds.

Each stage passes on what it could not explain. The final prediction is the sum of all stages.

In practice: A random forest with default settings is hard to get badly wrong, which makes it a strong second baseline after a linear model. Gradient boosting usually edges ahead on large tabular datasets once tuned. scikit-learn's HistGradientBoostingClassifier, which bins features into at most 256 values, is described in its documentation as orders of magnitude faster than the classic implementation once samples number in the tens of thousands.

Across many datasets, tree ensembles are the method to beat on tables. Grinsztajn, Oyallon and Varoquaux (NeurIPS 2022 Datasets and Benchmarks) compared tree-based models with deep learning on 45 tabular datasets and found trees remained state of the art on medium-sized data of around 10,000 samples. They traced the gap to three inductive biases: neural networks are less robust to uninformative features, do not respect the orientation of the data, and struggle to learn irregular functions.

A benchmark average does not decide your dataset, though. Here is the breast cancer data again, five-fold cross-validated:

The ensembles improve on the single tree by 4.6 to 5 points, exactly as the variance story predicts. But scaled logistic regression beats them all at 98.1%, on 569 rows where the classes are separated almost linearly.

A reasonable starting configuration, evaluated with cross-validation:

from sklearn.ensemble import HistGradientBoostingClassifier
from sklearn.model_selection import cross_val_score

hgb = HistGradientBoostingClassifier(
    learning_rate=0.05,
    max_iter=1000,           # upper bound; early stopping picks the real number
    max_leaf_nodes=31,       # size of each tree
    min_samples_leaf=20,
    early_stopping=True,     # hold out 10% and stop when it stalls
    n_iter_no_change=20,
    random_state=0,
)
scores = cross_val_score(hgb, X, y, cv=5, scoring="average_precision")
print(f"{scores.mean():.3f} +/- {scores.std():.3f}")

Three things this estimator does that save preprocessing work, per the scikit-learn documentation:

• Missing values are handled natively: at each split it learns whether rows with a missing value should go left or right.
• Categorical columns with a pandas categorical dtype are split on natively by default, no one-hot encoding needed.
• No scaling is needed, as with any tree.

Tune the learning rate and tree size first; the number of rounds then takes care of itself through early stopping.

Tree ensembles expose feature_importances_, the total impurity decrease each feature produced across all splits. It is fast and tempting, and the scikit-learn documentation warns it is strongly biased toward high-cardinality features: a column with thousands of distinct values, even a random ID, offers so many thresholds that some will reduce impurity by chance. It is also computed on training data, so it can credit features that only helped the model overfit.

The documented alternative is permutation importance, computed on held-out data: shuffle one column, and measure how much the score drops.

from sklearn.inspection import permutation_importance

result = permutation_importance(model, X_test, y_test, n_repeats=10, random_state=0)
for i in result.importances_mean.argsort()[::-1][:5]:
    print(feature_names[i], round(result.importances_mean[i], 4))

Gotcha: Importance describes the model, not the world. Two correlated features can split the credit between them, so each looks weak alone even when the information they share is vital. And a feature being important never means changing it will change the outcome; that is a causal question.