Trees, Forests, and Boosting

Machine Learning Chapter

Trees, Forests, and Boosting

Decision trees divide a problem into simple local rules. Forests make those rules stable by averaging many trees. Boosting makes them sharper by learning from previous errors.

1. Trees split space Regression trees predict with local averages inside regions.

2. Depth controls complexity Shallow trees underfit; very deep trees can memorize noise.

3. Forests average disagreement Bagging and random forests reduce variance through diversity.

4. Boosting corrects residuals Sequential learners add small corrections to the current model.

Tree regions Forest average Residual correction

Chapter Map

How the Ideas Fit Together

This chapter begins with a single regression tree, then shows why an average of many trees can be more reliable, and finally explains how boosting builds an additive model one correction at a time.

TreePartition feature space and predict with leaf averages.

DepthControl the tradeoff between underfitting and overfitting.

EnsembleCombine many imperfect learners through voting or averaging.

ForestUse bootstrap samples and feature randomness to reduce variance.

BoostingAdd small sequential corrections to reduce remaining error.

How to Read

Read the short explanation first, manipulate the explorer, then open the mathematical details if you want the formal objective or derivation. The Python snippets are minimal and self-contained.

Companion Materials

The notebook, PDF, and HTML export linked in the sidebar provide executable examples and companion notes, but the chapter itself is self-contained.

Part 1

Regression Trees

A regression tree predicts a numerical target by recursively splitting the feature space into regions. Each leaf predicts the average target value of the training observations in that region.

Definition

A split is useful when the child nodes have smaller target variation than the parent node.

RSS(split) = sum_left(y_i - mean_left)^2 + sum_right(y_i - mean_right)^2

The noisy sine example is useful because a line misses the curve, while a tree approximates it with simple horizontal steps. The tree is not fitting a smooth function; it is building local averages.

Mathematical details: tree objective

Let the feature vector be x = (x_1, ..., x_p), and let a tree divide the feature space into disjoint regions R_1, ..., R_J. For regression, the prediction in region R_j is the average response among training points that fall in that region.

c_j = average(y_i : x_i in R_j)

f(x) = sum_{j=1}^J c_j I(x in R_j)

The tree searches for partitions that make the within-region squared error small.

RSS = sum_{j=1}^J sum_{i: x_i in R_j} (y_i - c_j)^2

Because searching all possible partitions is infeasible, common tree algorithms use greedy recursive binary splitting. At a node, choose a feature j and threshold s, then form two regions.

R_left(j,s) = {x | x_j < s}, R_right(j,s) = {x | x_j >= s}

The chosen split is the pair (j, s) that gives the largest decrease in residual sum of squares at that node.

Split Explorer

Split threshold

Left mean0.00

Right mean0.00

Split RSS0.00

Minimal Python: Decision Tree Regression

import numpy as np
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeRegressor
from sklearn.metrics import mean_squared_error

rng = np.random.default_rng(42)
X = np.linspace(-3, 3, 120).reshape(-1, 1)
y = np.sin(1.35 * X).ravel() + rng.normal(0, 0.18, size=120)

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

tree = DecisionTreeRegressor(max_depth=3, random_state=42)
tree.fit(X_train, y_train)
pred = tree.predict(X_test)

print(mean_squared_error(y_test, pred))

Model Capacity

Depth and Overfitting

The parameter max_depth limits the longest path from root to leaf. A depth of 3 can create up to 8 leaves, because each split can double the number of regions.

maximum leaves <= 2^depth

A useful contrast is bias versus variance. A shallow tree has high bias; a very deep tree has high variance. The best model is usually between those extremes.

Pruning idea

Restrict depth, minimum leaf size, or cost-complexity to stop the tree from chasing noise.

Mathematical details: depth and capacity

In a binary tree, each internal node can split into two children. If every path is allowed to split d times, the maximum number of leaves is 2^d. More leaves mean more regions and a more flexible prediction function.

depth d => at most 2^d leaves

Increasing depth usually lowers training error because each leaf can specialize to fewer observations. Test error may first decrease, then increase when the tree starts fitting random noise.

expected prediction error = bias^2 + variance + irreducible noise

Shallow trees tend to have high bias. Deep trees tend to have high variance. Regularization parameters such as max_depth, min_samples_leaf, and cost-complexity pruning control this tradeoff.

Depth Explorer

Tree depth

Leaves8

Train MSE0.00

Test MSE0.00

Part 2

Why Ensembles Work

A helpful starting point is Condorcet's Jury Theorem. If each voter is independently better than chance, the majority vote becomes more reliable as the number of voters grows.

P(majority correct) = sum_{k > n/2} C(n,k) p^k (1-p)^(n-k)

For machine learning, the quiet word is independently. Ensembles improve when base models are accurate enough and make different errors.

Core principle

Ensemble strength = individual skill + diversity.

Mathematical details: majority voting

Suppose n independent voters each choose the correct binary class with probability p. Let S_n be the number of correct votes. Then S_n follows a binomial distribution.

S_n ~ Binomial(n, p)

The majority is correct when more than half of the voters are correct.

P(majority correct) = P(S_n > n/2)

P(S_n > n/2) = sum_{k=floor(n/2)+1}^n C(n,k) p^k (1-p)^(n-k)

If p > 0.5 and the votes are independent, this probability increases toward 1 as n grows. If p < 0.5, adding more voters confidently amplifies the wrong answer. If learners are highly correlated, the independence assumption breaks, and the ensemble gains less.

Majority Vote Explorer

Number of voters Each voter accuracy

Majority correct0%

Single voter0%

LessonDiversify

Part 3

Bagging and Random Forests

Bagging trains many trees independently on bootstrap samples and averages their predictions. Random forests add random feature selection at each split, which reduces correlation among trees.

Single Tree

Easy to explain, high variance, sensitive to small changes in the training data.

Bagging

Bootstrap samples create many different trees. Regression uses averaging; classification uses voting.

Random Forest

Bagging plus feature randomness. Diversity is increased because trees cannot all pick the same dominant feature at every split.

h_bag(x) = (1 / B) sum_{b=1}^B h_b(x)

Mathematical details: bagging, random forests, and variance

Bagging creates B bootstrap datasets D_1, ..., D_B by sampling from the original training set with replacement. A base learner h_b is fitted to each bootstrap dataset, and predictions are averaged for regression.

h_bag(x) = (1 / B) sum_{b=1}^B h_b(x)

For classification, the average is replaced by majority vote. Bagging works especially well for decision trees because deep trees are low-bias but high-variance learners.

The value of diversity can be seen from a simple variance approximation. If each tree has variance sigma^2 and the pairwise correlation between trees is rho, then the variance of the average is approximately:

Var(average) = sigma^2 * [rho + (1 - rho) / B]

Increasing B helps, but the limiting variance is rho * sigma^2. This is why random forests add feature randomness: reducing correlation rho can be as important as increasing the number of trees.

Random forest = bootstrap sampling + random feature subset at each split

When the number of candidate features at each split equals all p features, a random forest reduces to ordinary bagging of decision trees.

Forest Averaging Explorer

Number of trees Tree correlation

Forest MSE0.00

DiversityHigh

Variance gain0%

Example MSE Comparison

Higher MSE Lower MSE

Minimal Python: Bagging

from sklearn.ensemble import BaggingRegressor
from sklearn.tree import DecisionTreeRegressor

bag = BaggingRegressor(
    estimator=DecisionTreeRegressor(max_depth=4),
    n_estimators=100,
    random_state=42
)
bag.fit(X_train, y_train)
print(mean_squared_error(y_test, bag.predict(X_test)))

Minimal Python: Random Forest

from sklearn.ensemble import RandomForestRegressor

rf = RandomForestRegressor(
    n_estimators=300,
    max_depth=4,
    max_features="sqrt",
    random_state=42
)
rf.fit(X_train, y_train)
print(mean_squared_error(y_test, rf.predict(X_test)))

Part 4

Gradient Boosting

Boosting builds an additive model sequentially. Each new tree is trained to improve the current ensemble, often by fitting residuals or negative gradients.

g_t(x) = g_{t-1}(x) + learning_rate * f_t(x)

Start with a simple prediction, such as the mean of y.
Compute residuals: current error for each training point.
Fit a small tree to the residuals.
Add a shrunken version of that tree to the current model.
Stop using validation performance, not training performance alone.

Mathematical details: gradient boosting algorithm

Gradient boosting builds an additive model. For squared-error regression, the initial prediction is often the average of the response values.

g_0(x) = average(y_i)

At step t, compute residuals from the current model.

r_i^(t) = y_i - g_{t-1}(x_i)

Fit a small regression tree f_t(x) to the residuals, then update the model with a learning rate lambda.

g_t(x) = g_{t-1}(x) + lambda f_t(x)

For general differentiable loss functions, the residual is replaced by the negative gradient of the loss with respect to the current prediction. This is why the method is called gradient boosting.

pseudo_residual_i = - d L(y_i, g(x_i)) / d g(x_i)

Small learning rates usually require more trees but can improve generalization. Tree depth controls the complexity of each correction.

Boosting Stage Explorer

Boosting stage Learning rate

Current MSE0.00

Last splitnone

BehaviorSteady

Minimal Python: Gradient Boosting

from sklearn.ensemble import GradientBoostingRegressor

gb = GradientBoostingRegressor(
    n_estimators=120,
    learning_rate=0.05,
    max_depth=2,
    random_state=42
)
gb.fit(X_train, y_train)
print(mean_squared_error(y_test, gb.predict(X_test)))

Part 5

AdaBoost and XGBoost

AdaBoost and XGBoost are both boosting methods, but they emphasize different mechanisms. AdaBoost reweights difficult cases; XGBoost is an optimized gradient boosting system with regularization and fast tree construction.

AdaBoost

In classification, each weak learner receives more attention on examples that previous learners misclassified. The final classifier is a weighted vote.

G(x) = sign(sum_m alpha_m G_m(x))

Mathematical details

Initialize observation weights equally. At iteration m, fit a weak classifier G_m and compute its weighted error.

err_m = sum_i w_i I(y_i != G_m(x_i)) / sum_i w_i

The classifier receives a larger vote when its weighted error is smaller.

alpha_m = log((1 - err_m) / err_m)

Misclassified observations receive increased weight, so the next weak learner focuses on difficult cases.

w_i <- w_i exp(alpha_m I(y_i != G_m(x_i)))

XGBoost

XGBoost adds regularization, efficient split search, missing-value handling, and strong engineering around gradient boosted trees.

objective = loss + regularization

Mathematical details

XGBoost minimizes a regularized objective. The loss measures prediction error, while the regularization term penalizes overly complex trees.

Obj = sum_i L(y_i, yhat_i) + sum_k Omega(f_k)

A common tree penalty counts leaves and shrinks leaf weights.

Omega(f) = gamma T + (1/2) lambda sum_{j=1}^T w_j^2

Here T is the number of leaves and w_j is the score assigned to leaf j. Regularization is a major reason XGBoost can fit powerful boosted trees while controlling overfitting.

Minimal Python: AdaBoost

from sklearn.ensemble import AdaBoostRegressor

ada = AdaBoostRegressor(n_estimators=100, random_state=42)
ada.fit(X_train, y_train)
print(mean_squared_error(y_test, ada.predict(X_test)))

Minimal Python: XGBoost

from xgboost import XGBRegressor

xgb = XGBRegressor(
    n_estimators=150,
    max_depth=2,
    learning_rate=0.05,
    random_state=42
)
xgb.fit(X_train, y_train)
print(mean_squared_error(y_test, xgb.predict(X_test)))

Part 6

Validation and Leakage Lab

The S&P 500 example is valuable because it moves from synthetic data to real time-ordered data. It should be framed carefully: predicting today's close from today's open is not the same as forecasting tomorrow's market.

Leakage rule

A feature is honest only if it would be known at the moment the prediction is made.

For a forecasting lab, prefer lagged features such as yesterday's close, lagged returns, rolling volatility, and lagged volume. Use chronological splits rather than random splits.

Mathematical details: time-aware validation

In ordinary random train-test splitting, future observations can accidentally influence training when the data have time order. For forecasting, the model should train only on observations available before the test period.

train = {t : t <= split_date}, test = {t : t > split_date}

Lagged features preserve the prediction timeline. For example, if the target is today's close, yesterday's close is known before today ends, but today's high and low are only known after the trading day unfolds.

x_t = [close_{t-1}, return_{t-1}, volatility_{t-1}, ...]

target_t = close_t

A high R2 score is meaningful only after checking this timing. Otherwise, the model may be solving an easier retrospective reconstruction problem rather than a genuine prediction problem.

Feature Timing Checker

Today's open Today's high Today's low Today's volume Yesterday's close and returns

Minimal Python: Time-Aware Market Features

import pandas as pd
from sklearn.ensemble import RandomForestRegressor
from sklearn.metrics import mean_squared_error, r2_score

sp500 = pd.read_csv("sp500_data.csv", index_col=0, parse_dates=True)
sp500 = sp500.sort_index()

data = pd.DataFrame(index=sp500.index)
data["target_close"] = sp500["Close"]
data["close_lag1"] = sp500["Close"].shift(1)
data["return_lag1"] = sp500["Close"].pct_change().shift(1)
data["volatility_5"] = sp500["Close"].pct_change().rolling(5).std().shift(1)
data = data.dropna()

split_date = "2024-12-24"
train = data.loc[:split_date]
test = data.loc[split_date:]

X_train = train.drop(columns="target_close")
y_train = train["target_close"]
X_test = test.drop(columns="target_close")
y_test = test["target_close"]

rf = RandomForestRegressor(n_estimators=300, random_state=42)
rf.fit(X_train, y_train)
pred = rf.predict(X_test)

print(mean_squared_error(y_test, pred))
print(r2_score(y_test, pred))

Exercises

Practice and Discussion

These exercises turn the chapter ideas into small modeling tasks. They can be solved in any Python environment that has scikit-learn installed.

Exercise 1: California Housing

Fit a decision tree regressor, random forest regressor, and gradient boosting regressor. Compare MSE and R2. Explain which hyperparameter most clearly controls overfitting.

Exercise 2: Synthetic Classification

Fit a decision tree classifier and a gradient boosting classifier. Compare accuracy, precision, recall, F1-score, and the decision boundary.

Exercise 3: Breast Cancer Dataset

Use sklearn.datasets.load_breast_cancer. Compare a tree, random forest, and gradient boosting model. Include confusion matrices and discuss false negatives.

Quick check: Which method builds trees independently and mainly reduces variance?

Quick check: What is the main idea of gradient boosting?

Quick check: In a market forecasting task, which feature is usually safer?

Summary

Quick Reference

The table below summarizes the main methods, what they are trying to reduce, and the knobs that most often matter in practice.

Method	Main idea	Reduces	Key knobs
Decision Tree	Recursive splits and leaf averages	Bias when deep enough	`max_depth`, `min_samples_leaf`
Bagging	Average trees from bootstrap samples	Variance	`n_estimators`, base tree size
Random Forest	Bagging plus random feature subsets	Variance and tree correlation	`max_features`, `n_estimators`
Gradient Boosting	Sequential trees fit residuals or gradients	Bias, then variance if tuned	`learning_rate`, `n_estimators`, depth
XGBoost	Regularized, optimized gradient boosting	Bias with stronger regularization control	depth, learning rate, regularization

Download Notebook Open PDF handout Open HTML export