Decision Trees, Random Forests and Gradient Boosting

On tabular data, tree ensembles (random forests and gradient-boosted trees) remain the strongest default. Interviewers expect you to explain how a tree chooses a split, why single trees overfit, how bagging and boosting differ, and what the key hyperparameters do. You should also be able to code a split search.

1. A decision tree

A tree recursively partitions the feature space with axis-aligned questions ("is income > 40k?"). Each leaf predicts the majority class (classification) or the mean target (regression). Training is greedy and top-down: at each node, pick the split that most reduces impurity, then recurse on both sides.

Impurity measures

For a node with class proportions $p_k$:

• Gini impurity: $G=1-{\sum }_k{p}_k^2$. Zero when pure; 0.5 for a 50/50 binary node.
• Entropy: $H=-{\sum }_k{p}_k{\log }_2{p}_k$. Zero when pure; 1 bit for a 50/50 binary node.
• Variance (regression): the split minimises the weighted variance of the target in the children.

The split is chosen to maximise information gain: parent impurity minus the sample-weighted impurity of the children. Gini and entropy rarely produce meaningfully different trees; Gini is slightly cheaper.

import numpy as np

def gini(y):
    if len(y) == 0:
        return 0.0
    p = np.bincount(y) / len(y)
    return 1.0 - np.sum(p ** 2)

def best_split(x, y):
    """Best threshold on one numeric feature by weighted Gini."""
    order = np.argsort(x)
    x, y = x[order], y[order]
    best = (None, gini(y))
    for i in range(1, len(x)):
        if x[i] == x[i - 1]:
            continue
        t = (x[i] + x[i - 1]) / 2
        left, right = y[:i], y[i:]
        score = (len(left) * gini(left) + len(right) * gini(right)) / len(y)
        if score < best[1] - 1e-12:
            best = (t, score)
    return best

assert gini(np.array([0, 0, 1, 1])) == 0.5
assert gini(np.array([1, 1, 1])) == 0.0
x = np.array([1.0, 2.0, 3.0, 10.0, 11.0, 12.0])
y = np.array([0, 0, 0, 1, 1, 1])
t, score = best_split(x, y)
assert t == 6.5 and score == 0.0                       # a perfect split between 3 and 10

The search sorts a feature once and scans thresholds: $O(n\log n)$ per feature per node, and $O(n)$ per feature if you maintain running class counts.

Strengths and weaknesses

Controlling a tree

Limit max depth, require a minimum samples per leaf, set a minimum impurity decrease, or prune after growing (cost-complexity pruning). These are all regularisation: they trade variance for bias.

2. Bagging and random forests

Bagging (bootstrap aggregating) trains many trees on bootstrap samples (sampling with replacement) and averages their predictions (or takes a majority vote). Averaging $B$ models with variance ${\sigma }^2$ and pairwise correlation $\rho$ gives variance

$\rho {\sigma }^2+\frac{1-\rho }{B}{\sigma }^2$

so averaging helps only as far as the trees are decorrelated. A random forest adds a second source of randomness: at each split, consider only a random subset of features (often $\sqrt{d}$ for classification, $d/3$ for regression). That lowers $\rho$ and improves the ensemble.

Useful facts:

• Out-of-bag (OOB) error: each tree leaves out about 37% of the data (a sample of $n$ drawn with replacement excludes a given point with probability $(1-1/n{)}^n\to e^{-1}\approx 0.368$). Predicting those points with the trees that did not see them gives a free validation estimate.
• Forests rarely overfit by adding more trees; they plateau.
• They need little tuning and are a strong baseline.
• Feature importance: impurity-based importance is biased toward high-cardinality and continuous features; permutation importance (shuffle a feature on held-out data and measure the drop) is more trustworthy. SHAP values give per-prediction attributions.

import numpy as np

n = 100000
rng = np.random.default_rng(0)
sample = rng.integers(0, n, size=n)
oob_fraction = 1 - len(np.unique(sample)) / n
assert abs(oob_fraction - np.exp(-1)) < 0.005          # about 36.8 % of rows are out-of-bag

3. Boosting

Boosting builds the model sequentially, each new weak learner correcting the errors of the current ensemble. It mainly reduces bias.

AdaBoost (idea)

Reweight training examples so misclassified ones count more, fit the next weak learner, and combine learners with weights based on their accuracy.

Gradient boosting

View boosting as gradient descent in function space. Start with a constant prediction. At each round, compute the negative gradient of the loss with respect to the current predictions (the "pseudo-residuals"), fit a small tree to them, and add it with a learning rate $\eta$:

$F_m(x)=F_{m-1}(x)+\eta h_m(x)$

For squared error the pseudo-residuals are exactly the residuals $y-F_{m-1}(x)$. For log loss they are $y-p$. Shallow trees (depth 3 to 8) work well.

import numpy as np

def fit_stump(x, r):
    """A regression stump: best threshold on x minimising squared error of the residuals r."""
    order = np.argsort(x); x, r = x[order], r[order]
    best = (None, None, None, np.inf)
    for i in range(1, len(x)):
        if x[i] == x[i - 1]:
            continue
        lm, rm = r[:i].mean(), r[i:].mean()
        sse = ((r[:i] - lm) ** 2).sum() + ((r[i:] - rm) ** 2).sum()
        if sse < best[3]:
            best = ((x[i] + x[i - 1]) / 2, lm, rm, sse)
    return best[:3]

def predict_stump(stump, x):
    t, lm, rm = stump
    return np.where(x <= t, lm, rm)

rng = np.random.default_rng(0)
x = rng.uniform(0, 1, 300)
y = np.sin(2 * np.pi * x) + rng.normal(0, 0.1, 300)

pred = np.full_like(y, y.mean())
mse = [np.mean((y - pred) ** 2)]
for _ in range(100):
    stump = fit_stump(x, y - pred)                      # fit to the residuals
    pred = pred + 0.1 * predict_stump(stump, x)         # learning rate 0.1
    mse.append(np.mean((y - pred) ** 2))

assert all(a >= b - 1e-12 for a, b in zip(mse, mse[1:]))    # training error never increases
assert mse[-1] < 0.2 * mse[0]                               # 100 tiny stumps trace a sine wave

Modern libraries

XGBoost, LightGBM and CatBoost add second-order gradient information, regularisation on leaf weights, column and row subsampling, histogram-based splits for speed, and native handling of missing values (and categorical features in LightGBM and CatBoost). Know the headline difference: LightGBM grows trees leaf-wise (faster, can overfit small data), XGBoost level-wise by default, CatBoost uses ordered target statistics for categoricals.

Key hyperparameters

4. Random forest versus gradient boosting

5. When trees are the wrong tool

• Extrapolation: a tree predicts within the range of training targets; a linear trend continues beyond it. For trending targets, model the trend separately.
• Images, audio, text: deep networks learn useful representations that trees cannot.
• Very high-dimensional sparse features: linear models can be better.
• Smooth functions: trees approximate them as steps.

6. Common mistakes

• Using impurity importance as if it were causal or unbiased.
• No early stopping in boosting, so the model overfits as rounds increase.
• Leaving categorical encoding careless: one-hot encoding a high-cardinality feature explodes the feature space; target encoding without proper out-of-fold computation leaks the label.
• Tuning depth only and forgetting learning rate and number of trees interact.
• Scaling features for trees (harmless but pointless).
• Believing a forest is interpretable because a tree is.

7. Practice questions

1. How does a decision tree choose a split? Compute the Gini gain on a small example.
2. Why do single decision trees overfit, and how does bagging help? Show the variance formula.
3. What does the extra feature randomness in random forests achieve?
4. Explain gradient boosting as gradient descent in function space.
5. What are out-of-bag samples, and why is OOB error a valid estimate?
6. How do the learning rate and the number of trees interact?
7. Why is impurity-based feature importance unreliable, and what do you use instead?
8. A tree regressor predicts a flat line past the training range. Why, and what do you do?