Trees & ensembles

A decision tree predicts by asking a sequence of questions.

An ensemble combines several models so their different strengths and mistakes can produce a better final prediction.

Why this matters

Tabular business data often contains thresholds and interactions: an account may be risky only when it is both new and experiencing repeated failures.

Trees discover such branching patterns without requiring every interaction to be written manually. Ensembles make individual trees more stable or more accurate.

Plain-English mental model

Part 1 — Anatomy of a decision tree

A tree contains:

• root node: the first question;
• internal node: another feature question;
• branch: one answer path;
• leaf: terminal prediction;
• depth: number of splits along a longest root-to-leaf path.

For a numeric feature, a question is commonly:

failed_attempts < 2.5?

Thresholds between observed values are considered during training.

For classification, a leaf stores training class counts or proportions. For regression, it commonly predicts the mean target of training rows in that leaf.

Prediction is deterministic traversal

def predict_urgency(failed_attempts, account_age_days):
    if failed_attempts < 3:
        return 0.10
    if account_age_days < 7:
        return 0.80
    return 0.375

print(predict_urgency(4, 2))
print(predict_urgency(1, 100))

This code represents a fitted tree. Training is the process that selected features, thresholds, and leaf values.

Part 2 — Trees search for cleaner children

A classification node is pure when every row has the same class.

ImpurityImpurityA score describing how mixed the target classes are inside a tree node. A pure classification node contains one class; Gini impurity and entropy are common measures. measures class mixing.

Gini impurity

Gini impurityGini impurityOne minus the sum of squared class proportions in a node. It is zero for a pure node and estimates how often a randomly labelled item would be misclassified under the node proportions. is:

Gini = 1 - Σ p_k²

For 6 urgent and 4 not urgent:

p_urgent = 0.6
p_not = 0.4
Gini = 1 - 0.6² - 0.4² = 0.48

A pure binary node has Gini 0. A perfectly balanced binary node has Gini 0.5.

Entropy

Entropy is:

entropy = -Σ p_k log₂(p_k)

A pure node has entropy 0. A balanced binary node has entropy 1 bit.

Gini and entropy often select similar trees, but not always. Neither is a guarantee of product value.

Part 3 — Information gain scores a split

Children of different sizes must be weighted:

weighted child impurity
= (n_left/n_parent)×impurity_left
+ (n_right/n_parent)×impurity_right

Information gainInformation gainParent impurity minus the child impurities weighted by child size. A tree prefers candidate splits that produce the largest reduction under its chosen impurity measure. is:

gain = parent impurity - weighted child impurity

Higher gain means the split reduced impurity more.

Expected output:

0.5 0.1
1.5 0.25
2.5 0.5
3.5 0.25
4.5 0.1

Part 4 — Regression trees reduce numerical error

A regression tree asks the same feature questions but works with numerical targets.

Common leaf prediction:

leaf prediction = mean target in leaf

Candidate splits can minimise weighted squared error or variance.

Example targets:

left child:  [10, 12, 14] → prediction 12
right child: [40, 45]     → prediction 42.5

Regression-tree predictions are piecewise constant. They do not extrapolate a trend beyond observed leaves the way a line can.

Part 5 — Why one deep tree overfits

A tree can keep splitting until leaves contain one row.

Training error may become zero, but tiny data changes can produce a different upper split and a very different tree. This is high variance.

Control complexity with:

• maximum depth;
• minimum rows required to split;
• minimum rows per leaf;
• maximum number of leaves;
• minimum impurity decrease;
• pruning after growth.

Choose these with validation or cross-validation, not test data.

Shallow trees may underfit. Deep trees may memorise. There is no universal ideal depth.

Part 6 — Trees handle features differently from linear models

Advantages:

• capture thresholds and interactions;
• usually do not require standardisation;
• can mix nonlinear feature effects;
• paths can be inspected;
• support classification and regression.

Limitations:

• greedy splitting does not guarantee the globally best tree;
• small data changes can alter structure;
• axis-aligned splits may approximate smooth diagonal boundaries inefficiently;
• leaf probabilities can be poorly calibrated;
• standard implementations vary in missing and categorical handling;
• feature importance can mislead.

Never encode a nominal category such as red/green/blue as 1/2/3 unless the implementation treats it categorically; otherwise numeric thresholds invent an order.

Part 7 — Bootstrap sampling creates varied training sets

A bootstrap sampleBootstrap sampleA dataset formed by drawing the same number of rows from a source dataset with replacement, so some rows repeat and others are omitted. Bagging trains each base learner on a different bootstrap sample. draws n rows from n training rows with replacement.

Some rows appear multiple times. Others are absent.

Expected output:

1 ['B', 'A', 'B', 'A', 'A'] omitted: ['C', 'D', 'E']
2 ['C', 'E', 'E', 'D', 'B'] omitted: ['A']
3 ['C', 'B', 'A', 'A', 'B'] omitted: ['D', 'E']

Rows omitted from one tree’s bootstrap sample are out-of-bag for that tree and can support an internal performance estimate. Keep a genuine final test set.

Part 8 — Bagging averages unstable models

Bootstrap aggregatingBaggingBootstrap aggregating trains models independently on resampled training datasets and averages or votes over their predictions, mainly reducing variance when base models make partly different errors., shortened to bagging:

1. Draw many bootstrap samples.
2. Fit one base model independently to each sample.
3. Average regression predictions or vote/average classification probabilities.

If models make partly independent errors, averaging reduces variance.

Bagging helps unstable learners such as deep trees. Bagging nearly identical models with perfectly correlated errors provides little benefit.

Part 9 — Random forests decorrelate trees

A random forestRandom forestA bagged collection of decision trees that also considers random feature subsets at splits, encouraging diverse trees whose averaged predictions are more stable than one deep tree. adds another source of variation:

• bootstrap rows for each tree;
• consider only a random subset of features at each split.

Why random features?

If one strong feature dominates, every bagged tree may choose it at the root and become similar. Random feature subsets force alternative useful structures. Averaging diverse trees can be more stable.

Important settings:

• number of trees;
• features considered per split;
• maximum depth;
• minimum leaf size;
• class weights;
• bootstrap choice.

More trees generally stabilise the average but increase compute and memory. They do not fix biased data or an overfitting split protocol.

Part 10 — Feature importance needs caution

Common tree importance methods:

• impurity importance: total weighted impurity reduction attributed to a feature;
• permutation importance: measure validation-score decrease after shuffling one feature.

Impurity importance can favour continuous or high-cardinality features with more split opportunities.

Permutation importance can understate correlated features because a partner still supplies similar information. It must be calculated on held-out data with a meaningful metric.

Importance means the model used a feature for prediction under this data—not that the feature causes the outcome.

Part 11 — Boosting learns sequential corrections

BoostingBoostingA sequential ensemble strategy in which each new weak learner focuses on errors or loss gradients left by the current ensemble, and the learners are combined into one additive prediction. combines weak learners sequentially.

For squared-error gradient boostingGradient boostingBoosting that fits each new learner to the negative gradient of a differentiable loss with respect to current predictions. For squared error, that negative gradient is the residual.:

1. Start with a baseline, often mean target.
2. Calculate residuals.
3. Fit a small tree to those residuals.
4. Add a shrunken version of its prediction.
5. Recalculate residuals.
6. Repeat.

new_prediction
= old_prediction + learning_rate × new_tree_prediction

For other differentiable losses, each tree fits the negative gradient—often called a pseudo-residual.

Worked residual correction

Targets:

[10, 20, 30]

Initial prediction is mean 20:

predictions = [20, 20, 20]
residuals   = [-10, 0, 10]

Suppose a stump predicts residual corrections [-8, 0, 8] and learning rate is 0.5:

new predictions = [16, 20, 24]
new residuals   = [-6, 0, 6]

The next tree focuses on what remains.

Small trees and learning rates regularise the sequence. Too many boosting rounds can overfit.

Part 12 — XGBoost, LightGBM, and CatBoost

These are optimised gradient-boosted tree libraries, not three completely different learning paradigms.

XGBoost

XGBoost provides a regularised gradient-boosting objective, second-order gradient information, sparsity-aware processing, column sampling, and efficient parallel systems.

It is a mature general-purpose baseline with extensive tooling.

LightGBM

LightGBM uses histogram-based splits and commonly grows trees leaf-wise by expanding the leaf with greatest gain.

Leaf-wise growth can reduce loss quickly but may overfit small datasets unless leaf count, depth, and minimum leaf data are controlled.

It also includes optimisations such as gradient-based one-side sampling and exclusive feature bundling.

CatBoost

CatBoost is designed for strong handling of categorical features. Ordered target statistics and ordered boosting reduce leakage and prediction shift that naive target encoding can introduce.

Do not precompute category target means using all rows; that leaks labels regardless of library.

Choose by evidence

Compare:

• data size and sparsity;
• categorical feature needs;
• missing-value semantics;
• training and inference constraints;
• validation quality;
• probability calibration;
• reproducibility and deployment environment.

Tune equivalent capacity, not just default settings. No library wins every dataset.

Part 13 — Stacking learns how to combine models

StackingStackingTraining a meta-model to combine predictions from several base models. Meta-training features must be created out of fold so the base predictions for each row come from models that did not train on that row. uses predictions from base models as inputs to a meta-model.

Example base models:

• logistic regression;
• random forest;
• gradient boosting.

Correct training:

1. Divide training data into folds.
2. For each fold, fit base models on other folds.
3. Predict the held-out fold.
4. Concatenate out-of-fold predictions.
5. Fit the meta-model on those predictions and targets.
6. Refit each base model on all training data.
7. At inference, send base predictions into the meta-model.

If the meta-model sees in-sample base predictions, it learns from base-model memorisation and fails on unseen inputs.

Stacking adds latency, operational dependencies, and debugging complexity. It must beat the best single model meaningfully.

Worked example — triage ticket urgency

1. Evidence

Split by customer and time. Features must exist at ticket creation. Keep latest months sealed for test.

2. Single tree

Fit a shallow classification tree. Inspect paths and minimum leaf counts. It exposes candidate interactions but may vary across folds.

3. Random forest

Fit many bootstrapped trees with random feature subsets. Compare validation recall, precision, calibration, latency, and group slices.

4. Gradient boosting

Fit shallow boosted trees with a small learning rate and early stopping on validation data. Avoid using the test set for the stopping round.

5. Select

If boosting improves the declared metric but is poorly calibrated, calibrate with separate validation evidence. If the forest is nearly as good and easier to operate, simpler may win.

6. Explain honestly

Show validated feature dependence and representative paths, but do not claim one tree explains the entire ensemble or proves causality.

In a real AI system

Common mistakes

Exercises

Knowledge check

Practice activity

rows = [(0, 0), (1, 0), (2, 0), (3, 1), (4, 1), (5, 1)]

def gini(labels):
    positive = sum(labels) / len(labels)
    return 1 - positive ** 2 - (1 - positive) ** 2

# Generate midpoint thresholds and calculate gain.

rows = sorted(rows)
labels = [label for _, label in rows]
parent = gini(labels)
thresholds = [
    (left[0] + right[0]) / 2
    for left, right in zip(rows, rows[1:])
    if left[0] != right[0]
]

best = None
for threshold in thresholds:
    left = [label for value, label in rows if value < threshold]
    right = [label for value, label in rows if value >= threshold]
    weighted = (
        len(left) / len(rows) * gini(left)
        + len(right) / len(rows) * gini(right)
    )
    gain = parent - weighted
    candidate = (gain, threshold, sum(left) / len(left), sum(right) / len(right))
    if best is None or candidate > best:
        best = candidate

gain, threshold, left_probability, right_probability = best
print("threshold:", threshold)
print("gain:", gain)
print("leaf probabilities:", left_probability, right_probability)

threshold: 2.5
gain: 0.5
leaf probabilities: 0.0 1.0

Key takeaways

Flashcards

One-page sketchnote summary

gain = impurity(parent) - weighted_impurity(children)
forest = average(independent_tree_predictions)
boosted += learning_rate * next_correction
meta.fit(out_of_fold_predictions, targets)

Resources