Decision trees and gradient boosting

The linear models of lesson 03 draw one straight boundary through the data. Decision trees draw a staircase instead, one axis-aligned cut at a time, and they find interactions between features without being told. On their own they overfit badly. Combined by gradient boosting, they are the model that wins most tabular competitions and sits behind most production scoring systems for structured data. This lesson fits both on the breast cancer dataset bundled with scikit-learn, shows what depth does, and ends with the caveats that every feature importance plot should carry.

What a tree is

A decision tree is a sequence of yes-or-no questions about single features. Start at the root with all the training rows. Ask “is worst perimeter at most 106.1”. Rows that answer yes go left, the rest go right. Ask another question at each child, and so on, until a node is pure (all one class) or a stopping rule is hit. A leaf predicts the majority class of the training rows that reached it, or the fraction of each class if you want probabilities.

There are no weights, no gradient and no learning rate. Training is a greedy search: at each node, try every feature and every threshold between adjacent sorted values, score each candidate split, and keep the best one. The score is how much the split reduces impurity.

One split by hand

Gini impurity for a node is 1 minus the sum over classes of the squared class fraction. A node with 50 % of each class scores 0.5, the worst possible for two classes. A pure node scores 0.

The dataset has 569 tumours described by 30 measurements, labelled malignant or benign. After a 75 % training split there are 426 training rows, 159 malignant and 267 benign. The root’s class fractions are 0.373 and 0.627, so its Gini impurity is 1 minus 0.139 minus 0.393, which is 0.468. The best split the search finds is worst perimeter at or below 106.1. It sends 259 rows left, of which 11 are malignant (impurity 0.081), and 167 rows right, of which 148 are malignant (impurity 0.202). The weighted impurity of the children is 259 times 0.081 plus 167 times 0.202, divided by 426, which is about 0.128. The split reduced impurity from 0.468 to 0.128, and no other feature and threshold does better. That one question, a one-level tree called a stump, is already a usable classifier.

import numpy as np
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier, export_text

data = load_breast_cancer()
X, y = data.data, data.target
print("samples:", X.shape[0], " features:", X.shape[1],
      " classes:", data.target_names.tolist())

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.25, random_state=0, stratify=y)

stump = DecisionTreeClassifier(max_depth=1, random_state=0).fit(X_train, y_train)
print(export_text(stump, feature_names=list(data.feature_names)))
print("depth-1 test accuracy:", round(stump.score(X_test, y_test), 3))

samples: 569  features: 30  classes: ['malignant', 'benign']
|--- worst perimeter <= 106.10
|   |--- class: 1
|--- worst perimeter >  106.10
|   |--- class: 0

depth-1 test accuracy: 0.888

Class 1 is benign in this dataset’s encoding. A single threshold on one measurement classifies 88.8 % of unseen tumours correctly. The diagram shows the tree one level deeper, with the row counts at each node.

The first two levels of the tree fitted to the training rows. Each box shows the question, or for a leaf the malignant and benign counts of the training rows that reached it. The second level asks about worst concave points on both sides but with different thresholds.

Read the leaves. The far left, small perimeter and few concave points, is 239 benign to 1 malignant, and the far right is 128 malignant to 2 benign. The two middle leaves are nearly even and would need further questions. Notice that the second level asks the same feature on both sides but with different thresholds. That is an interaction the tree found on its own: the concave-points cut that matters depends on the perimeter. A linear model cannot express that without a hand-built feature.

Depth, overfitting and the gap

Letting the tree grow until every leaf is pure gives a training accuracy of 100 %, because every training row has been sorted into a leaf of its own class. That is memorisation, not learning. The block fits trees of increasing depth and reports training accuracy next to a 5-fold cross-validated accuracy on the training rows, which is the honest estimate that lesson 06 explains in detail.

import numpy as np
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split, cross_val_score
from sklearn.tree import DecisionTreeClassifier

data = load_breast_cancer()
X_train, X_test, y_train, y_test = train_test_split(
    data.data, data.target, test_size=0.25, random_state=0, stratify=data.target)

print("depth  train   cv(5)   leaves")
for depth in (1, 2, 3, 4, 6, 8, None):
    tree = DecisionTreeClassifier(max_depth=depth, random_state=0)
    cv = cross_val_score(tree, X_train, y_train, cv=5).mean()
    tree.fit(X_train, y_train)
    label = "full" if depth is None else str(depth)
    print(f"{label:>5}  {tree.score(X_train, y_train):.3f}   {cv:.3f}   {tree.get_n_leaves()}")

depth  train   cv(5)   leaves
    1  0.930   0.897   2
    2  0.932   0.927   4
    3  0.977   0.925   8
    4  0.986   0.923   13
    6  1.000   0.925   18
    8  1.000   0.925   18
 full  1.000   0.925   18

Training accuracy climbs with depth and reaches 100 % at depth 6, where the tree has 18 leaves and nothing left to split (deeper settings produce the same tree). Cross-validated accuracy rises from 0.897 to 0.927 at depth 2 and then stays flat at about 0.925 while the gap between the two columns opens from 0.005 to 0.075. Everything the tree learned past depth 2 was specific to the training rows. The gap is the measure of overfitting, and max_depth (or min_samples_leaf, which stops a split when a child would be too small) is the control. The right depth is the one where the held-out score stops improving, not the one where the training score is highest.

Trees are also unstable. Change a few training rows and the root split can change feature, which reshuffles the whole tree below it. Both problems, overfitting and instability, are what ensembles fix.

Gradient boosting

The idea is to build the model as a sum of many small trees, each one correcting the errors of the sum so far. For a regression loss it goes like this. Start with a constant prediction, the mean of the labels. Compute each example’s residual, label minus current prediction. Fit a shallow tree to the residuals. Add that tree’s predictions to the model, scaled by a learning rate such as 0.1. Recompute the residuals, which are now smaller, and repeat for a few hundred rounds.

Work the first round with three labels, 10, 20 and 30. The constant start is 20, so the residuals are minus 10, 0 and 10. A stump that separates the first example from the other two predicts minus 10 on the left and 5 on the right (the mean of 0 and 10). With a learning rate of 0.1 the model becomes 19 for the first example and 20.5 for the others. The new residuals are minus 9, minus 0.5 and 9.5. Each round removes a tenth of the remaining error in the direction the tree can express, and after enough rounds the sum of stumps has carved out the labels.

The word “gradient” is there because the residual is the negative gradient of the squared-error loss with respect to the prediction. For other losses, such as the log loss of a classifier, the same recipe fits each tree to the negative gradient of that loss instead. It is the training loop of lesson 04 with a tree as the step. The learning rate plays the same role, and so does the number of rounds: too many rounds at too high a rate and the ensemble starts fitting noise.

HistGradientBoostingClassifier is scikit-learn’s fast implementation. It bins each feature into at most 255 histogram buckets before training, which makes finding a split cheap, and it handles missing values and tens of thousands of rows comfortably on a laptop.

import numpy as np
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
from sklearn.ensemble import HistGradientBoostingClassifier

data = load_breast_cancer()
X_train, X_test, y_train, y_test = train_test_split(
    data.data, data.target, test_size=0.25, random_state=0, stratify=data.target)

tree = DecisionTreeClassifier(max_depth=3, random_state=0).fit(X_train, y_train)
print("depth-3 tree test accuracy:", round(tree.score(X_test, y_test), 3))

for n_trees in (10, 50, 200):
    gb = HistGradientBoostingClassifier(
        max_iter=n_trees, learning_rate=0.1, max_depth=3, random_state=0)
    gb.fit(X_train, y_train)
    print(f"boosting, {n_trees:3d} trees, test accuracy: {gb.score(X_test, y_test):.3f}")

depth-3 tree test accuracy: 0.916
boosting,  10 trees, test accuracy: 0.937
boosting,  50 trees, test accuracy: 0.944
boosting, 200 trees, test accuracy: 0.958

Two hundred depth-3 trees, each one weak, score 0.958 on the test set against 0.916 for the single depth-3 tree. The test set has 143 rows, so each percentage point is about 1.4 tumours, and the difference between 50 and 200 trees is two of them. Treat small differences as noise unless a cross-validation confirms them. The important parameters are max_iter (rounds), learning_rate and the size of each tree, and they trade off: a smaller learning rate needs more rounds and usually generalises a little better. Early stopping, which HistGradientBoostingClassifier turns on automatically for larger datasets, watches a validation score and stops adding trees when it stops improving.

Random forests are the other tree ensemble you will meet. They train many deep trees on random subsets of rows and features, independently, and average them. Boosting trains shallow trees in sequence, each fixing the last. Boosting usually wins on accuracy for tabular data, and forests are harder to overfit by accident. The classical ML hub compares them.

Feature importance, with caveats

Tree models come with a tempting number per feature: how much it contributed. The default, impurity-based importance, adds up the impurity reduction from every split on each feature, weighted by the rows it touched. It is cheap and it is computed on the training rows, which is the first problem: a feature that the model used to memorise noise scores well.

The second problem is bias. Features with many distinct values offer the search more candidate thresholds, so they win more splits by chance, and a continuous feature will be ranked above an informative binary one for that reason alone.

The third problem is correlation. When two features carry the same information the tree picks one at each split, often arbitrarily, and the importance is divided between them in a way that reflects tie-breaking rather than usefulness. Drop one and the other’s score roughly doubles.

Permutation importance addresses the first problem. Take the fitted model and a held-out set, shuffle one column so it carries no information, and measure how much the score drops. Repeat with fresh shuffles to see the noise. It does not address correlation: shuffling one of two correlated columns leaves its twin intact, so the model barely suffers and both look unimportant.

import numpy as np
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.ensemble import HistGradientBoostingClassifier
from sklearn.inspection import permutation_importance

data = load_breast_cancer()
names = np.array(data.feature_names)
X_train, X_test, y_train, y_test = train_test_split(
    data.data, data.target, test_size=0.25, random_state=0, stratify=data.target)

gb = HistGradientBoostingClassifier(max_iter=200, learning_rate=0.1,
                                    max_depth=3, random_state=0)
gb.fit(X_train, y_train)

# Permutation importance: shuffle one column of the test set and see how
# much accuracy falls. Repeated 10 times so the noise is visible.
result = permutation_importance(gb, X_test, y_test, n_repeats=10, random_state=0)
order = np.argsort(result.importances_mean)[::-1]
print("feature                   drop in accuracy (mean +/- std)")
for i in order[:6]:
    print(f"{names[i]:<24}  {result.importances_mean[i]:.3f} +/- {result.importances_std[i]:.3f}")

# How correlated is the top feature with its siblings?
corr = np.corrcoef(data.data.T)
top = order[0]
partners = np.argsort(np.abs(corr[top]))[::-1][1:4]
print(f"\nfeatures most correlated with '{names[top]}':")
for j in partners:
    print(f"  {names[j]:<24} r = {corr[top, j]:.3f}")

feature                   drop in accuracy (mean +/- std)
mean concave points       0.024 +/- 0.009
worst concave points      0.023 +/- 0.008
worst smoothness          0.021 +/- 0.004
worst texture             0.017 +/- 0.008
mean texture              0.014 +/- 0.005
worst area                0.013 +/- 0.012

features most correlated with 'mean concave points':
  mean concavity           r = 0.921
  worst concave points     r = 0.910
  worst perimeter          r = 0.856

Shuffling the top feature costs the model 2.4 points of accuracy, plus or minus 0.9. The next three are within one standard deviation of it, so the ranking among them is not meaningful. And the top feature has a correlation of 0.92 with mean concavity and 0.91 with worst concave points, so when one is shuffled the model reads the others, and all three are undervalued. Worst perimeter, the root split of every tree in the first section, does not appear in the top six at all for the same reason: the model can replace it with worst area or worst radius, which are near copies.

Exercise

Replace max_depth with min_samples_leaf in the depth sweep, trying 1, 5, 10, 20 and 50, and report train and cross-validated accuracy. Which control gives the better held-out score on this data.
Run the boosting block with learning_rate=0.02 and max_iter=1000, then with learning_rate=0.5 and max_iter=40. Compare test accuracy and training time, and say which you would ship.
HistGradientBoostingClassifier has no feature_importances_ attribute, so fit a GradientBoostingClassifier with the same settings, print its impurity-based importances for the same six features, and compare the two rankings. Then drop mean concave points, refit, and watch what happens to mean concavity.

Summary

A decision tree is a greedy sequence of single-feature thresholds, each chosen to reduce impurity the most. One split on worst perimeter classifies 89 % of unseen tumours.
Training accuracy rises with depth to 100 %. Held-out accuracy stops improving early, and the gap between them is the overfitting to control with max_depth or min_samples_leaf.
Gradient boosting fits each new shallow tree to the negative gradient of the loss (the residuals, for squared error) and adds it scaled by a learning rate. Two hundred weak trees beat one strong one.
Impurity importance is computed on training rows and favours high-cardinality features. Permutation importance on held-out rows is better, but correlated features still share and hide credit.
No importance score implies cause. A single dominant feature is a reason to check for leakage before it is a reason to celebrate.