06 Ensemble Methods — Exercises¶

Test your understanding of bagging, random forests, boosting, and the bias-variance decomposition of ensemble methods.

Prerequisites. Read theory.md and work through first_principles.ipynb before attempting these.

In [1]:

import random

import matplotlib.pyplot as plt
import numpy as np

%load_ext autoreload
%autoreload 2

SEED = 42
random.seed(SEED)
rng = np.random.default_rng(SEED)

plt.rcParams["figure.dpi"] = 90

import random import matplotlib.pyplot as plt import numpy as np %load_ext autoreload %autoreload 2 SEED = 42 random.seed(SEED) rng = np.random.default_rng(SEED) plt.rcParams["figure.dpi"] = 90

Exercise 1 — Hand Calculation: AdaBoost Weights After 1 Round¶

Consider 5 training examples with labels $y_i \in \{-1, +1\}$ and initial equal weights $w_i^{(1)} = 1/5$.

$i$	$y_i$	$h_1(x_i)$
1	+1	+1
2	+1	+1
3	-1	-1
4	-1	+1
5	+1	-1

The first weak learner $h_1$ misclassifies examples 4 and 5.

Tasks (derive by hand, then verify numerically):

1. Compute the weighted error $\epsilon_1 = \sum_i w_i^{(1)} \cdot \mathbb{1}[h_1(x_i) \ne y_i]$.
2. Compute the learner weight $\alpha_1 = \frac{1}{2} \ln\frac{1-\epsilon_1}{\epsilon_1}$.
3. Compute the unnormalized updated weights $w_i^{(2)} = w_i^{(1)} \exp(-\alpha_1 y_i h_1(x_i))$.
4. Normalize so the weights sum to 1. Which examples now have the largest weights?

Expected results:

• $\epsilon_1 = 2/5 = 0.4$
• $\alpha_1 = \frac{1}{2} \ln(3/2) \approx 0.2027$
• After normalization, misclassified examples (4, 5) should have larger weights than correctly classified examples (1, 2, 3).

In [2]:

# Verify your hand calculations
y = np.array([1, 1, -1, -1, 1])
h1 = np.array([1, 1, -1, 1, -1])
n = len(y)
w = np.full(n, 1.0 / n)  # equal initial weights

# TODO: compute epsilon_1, alpha_1, updated weights
# epsilon_1 = ...
# alpha_1 = ...
# w_unnorm = ...
# w_new = w_unnorm / w_unnorm.sum()

# Expected checks (uncomment after implementing):
# assert np.isclose(epsilon_1, 0.4, atol=1e-10)
# assert np.isclose(alpha_1, 0.5 * np.log(1.5), atol=1e-10)
# assert np.isclose(w_new.sum(), 1.0, atol=1e-12)
# # Misclassified examples (4, 5) should have higher weight
# assert w_new[3] > w_new[0], "Misclassified example 4 should have higher weight"
# assert w_new[4] > w_new[0], "Misclassified example 5 should have higher weight"
# print(f"epsilon_1 = {epsilon_1:.4f}")
# print(f"alpha_1   = {alpha_1:.4f}")
# print(f"Updated weights: {w_new}")
# print("All AdaBoost weight checks passed.")

# Verify your hand calculations y = np.array([1, 1, -1, -1, 1]) h1 = np.array([1, 1, -1, 1, -1]) n = len(y) w = np.full(n, 1.0 / n) # equal initial weights # TODO: compute epsilon_1, alpha_1, updated weights # epsilon_1 = ... # alpha_1 = ... # w_unnorm = ... # w_new = w_unnorm / w_unnorm.sum() # Expected checks (uncomment after implementing): # assert np.isclose(epsilon_1, 0.4, atol=1e-10) # assert np.isclose(alpha_1, 0.5 * np.log(1.5), atol=1e-10) # assert np.isclose(w_new.sum(), 1.0, atol=1e-12) # # Misclassified examples (4, 5) should have higher weight # assert w_new[3] > w_new[0], "Misclassified example 4 should have higher weight" # assert w_new[4] > w_new[0], "Misclassified example 5 should have higher weight" # print(f"epsilon_1 = {epsilon_1:.4f}") # print(f"alpha_1 = {alpha_1:.4f}") # print(f"Updated weights: {w_new}") # print("All AdaBoost weight checks passed.")

Solution (Exercise 1)¶

In [3]:

# Solution — AdaBoost quantities after round 1
y = np.array([1, 1, -1, -1, 1])
h1 = np.array([1, 1, -1, 1, -1])
n = len(y)
w = np.full(n, 1.0 / n)

epsilon_1 = float(np.sum(w[h1 != y]))
alpha_1 = 0.5 * np.log((1.0 - epsilon_1) / epsilon_1)
w_unnorm = w * np.exp(-alpha_1 * y * h1)
w_new = w_unnorm / w_unnorm.sum()

assert np.isclose(epsilon_1, 0.4, atol=1e-10)
assert np.isclose(alpha_1, 0.5 * np.log(1.5), atol=1e-10)
assert np.isclose(w_new.sum(), 1.0, atol=1e-12)
assert w_new[3] > w_new[0], "Misclassified example 4 should have higher weight"
assert w_new[4] > w_new[0], "Misclassified example 5 should have higher weight"
print(f"epsilon_1 = {epsilon_1:.4f}")
print(f"alpha_1   = {alpha_1:.4f}")
print(f"Updated weights: {np.round(w_new, 4)}")
print("All AdaBoost weight checks passed.")

# Solution — AdaBoost quantities after round 1 y = np.array([1, 1, -1, -1, 1]) h1 = np.array([1, 1, -1, 1, -1]) n = len(y) w = np.full(n, 1.0 / n) epsilon_1 = float(np.sum(w[h1 != y])) alpha_1 = 0.5 * np.log((1.0 - epsilon_1) / epsilon_1) w_unnorm = w * np.exp(-alpha_1 * y * h1) w_new = w_unnorm / w_unnorm.sum() assert np.isclose(epsilon_1, 0.4, atol=1e-10) assert np.isclose(alpha_1, 0.5 * np.log(1.5), atol=1e-10) assert np.isclose(w_new.sum(), 1.0, atol=1e-12) assert w_new[3] > w_new[0], "Misclassified example 4 should have higher weight" assert w_new[4] > w_new[0], "Misclassified example 5 should have higher weight" print(f"epsilon_1 = {epsilon_1:.4f}") print(f"alpha_1 = {alpha_1:.4f}") print(f"Updated weights: {np.round(w_new, 4)}") print("All AdaBoost weight checks passed.")

epsilon_1 = 0.4000
alpha_1   = 0.2027
Updated weights: [0.1667 0.1667 0.1667 0.25   0.25  ]
All AdaBoost weight checks passed.

Exercise 2 — Coding: Implement Bagging Classifier¶

Implement a bagging classifier that wraps decision trees. Unlike random forest, bagging uses all features at every split — only the bootstrap sampling provides diversity.

Tasks:

1. Implement BaggingClassifier with fit(X, y) and predict(X) methods.
2. Use DecisionTreeClassifier from ml_first_principles.tree_models.
3. Each tree trains on a bootstrap sample of size $n$ (with replacement).
4. Prediction is by majority vote.

Deterministic check: On the dataset below, bagging with 50 trees and max_depth=5 should achieve $\ge 0.90$ accuracy on the training set.

Bonus: Compare your bagging (all features) with the scratch RF from first_principles.ipynb (random feature subsets) — which has lower test error?

In [4]:

from ml_first_principles.tree_models import DecisionTreeClassifier
from ml_first_principles.data_utils import generate_classification_data
from ml_first_principles.metrics import accuracy


class BaggingClassifier:
    """Bagging classifier using decision trees (all features at each split)."""

    def __init__(self, n_estimators=50, max_depth=5, random_state=None):
        self.n_estimators = n_estimators
        self.max_depth = max_depth
        self.random_state = random_state
        self.trees_ = []
        self.classes_ = None

    def fit(self, X, y):
        # TODO: implement
        # 1. Store unique classes
        # 2. For each estimator:
        #    a. Draw bootstrap sample (sample with replacement)
        #    b. Train a DecisionTreeClassifier (max_features=None for all features)
        #    c. Append to self.trees_
        pass

    def predict(self, X):
        # TODO: implement majority vote
        pass

    def score(self, X, y):
        return accuracy(y, self.predict(X))


# Deterministic check (uncomment after implementing, or see the solution below)
# X_bag, y_bag = generate_classification_data(
#     n_samples=300, n_features=4, n_classes=2, random_state=42
# )
#
# bag = BaggingClassifier(n_estimators=50, max_depth=5, random_state=42)
# bag.fit(X_bag, y_bag)
# bag_acc = bag.score(X_bag, y_bag)
# print(f"Bagging train accuracy: {bag_acc:.4f}")
# assert bag_acc >= 0.90, f"Expected >= 0.90, got {bag_acc}"
# print("Bagging check passed.")

from ml_first_principles.tree_models import DecisionTreeClassifier from ml_first_principles.data_utils import generate_classification_data from ml_first_principles.metrics import accuracy class BaggingClassifier: """Bagging classifier using decision trees (all features at each split).""" def __init__(self, n_estimators=50, max_depth=5, random_state=None): self.n_estimators = n_estimators self.max_depth = max_depth self.random_state = random_state self.trees_ = [] self.classes_ = None def fit(self, X, y): # TODO: implement # 1. Store unique classes # 2. For each estimator: # a. Draw bootstrap sample (sample with replacement) # b. Train a DecisionTreeClassifier (max_features=None for all features) # c. Append to self.trees_ pass def predict(self, X): # TODO: implement majority vote pass def score(self, X, y): return accuracy(y, self.predict(X)) # Deterministic check (uncomment after implementing, or see the solution below) # X_bag, y_bag = generate_classification_data( # n_samples=300, n_features=4, n_classes=2, random_state=42 # ) # # bag = BaggingClassifier(n_estimators=50, max_depth=5, random_state=42) # bag.fit(X_bag, y_bag) # bag_acc = bag.score(X_bag, y_bag) # print(f"Bagging train accuracy: {bag_acc:.4f}") # assert bag_acc >= 0.90, f"Expected >= 0.90, got {bag_acc}" # print("Bagging check passed.")

Solution (Exercise 2)¶

In [5]:

# Solution — bagging with bootstrap samples and majority vote
class BaggingClassifierSolution(BaggingClassifier):
    def fit(self, X, y):
        X = np.asarray(X, dtype=float)
        y = np.asarray(y)
        self.classes_ = np.unique(y)
        gen = np.random.default_rng(self.random_state)
        self.trees_ = []
        for _ in range(self.n_estimators):
            idx = gen.integers(0, X.shape[0], size=X.shape[0])
            seed = int(gen.integers(0, np.iinfo(np.int32).max))
            tree = DecisionTreeClassifier(max_depth=self.max_depth, random_state=seed)
            tree.fit(X[idx], y[idx])
            self.trees_.append(tree)
        return self

    def predict(self, X):
        votes = np.asarray([tree.predict(X) for tree in self.trees_])
        out = []
        for column in votes.T:
            counts = np.array([np.sum(column == label) for label in self.classes_])
            out.append(self.classes_[np.argmax(counts)])
        return np.asarray(out)


X_bag, y_bag = generate_classification_data(
    n_samples=300, n_features=4, n_classes=2, random_state=42
)
bag = BaggingClassifierSolution(n_estimators=50, max_depth=5, random_state=42)
bag.fit(X_bag, y_bag)
bag_acc = bag.score(X_bag, y_bag)
print(f"Bagging train accuracy: {bag_acc:.4f}")
assert bag_acc >= 0.90, f"Expected >= 0.90, got {bag_acc}"
print("Bagging check passed.")

# Solution — bagging with bootstrap samples and majority vote class BaggingClassifierSolution(BaggingClassifier): def fit(self, X, y): X = np.asarray(X, dtype=float) y = np.asarray(y) self.classes_ = np.unique(y) gen = np.random.default_rng(self.random_state) self.trees_ = [] for _ in range(self.n_estimators): idx = gen.integers(0, X.shape[0], size=X.shape[0]) seed = int(gen.integers(0, np.iinfo(np.int32).max)) tree = DecisionTreeClassifier(max_depth=self.max_depth, random_state=seed) tree.fit(X[idx], y[idx]) self.trees_.append(tree) return self def predict(self, X): votes = np.asarray([tree.predict(X) for tree in self.trees_]) out = [] for column in votes.T: counts = np.array([np.sum(column == label) for label in self.classes_]) out.append(self.classes_[np.argmax(counts)]) return np.asarray(out) X_bag, y_bag = generate_classification_data( n_samples=300, n_features=4, n_classes=2, random_state=42 ) bag = BaggingClassifierSolution(n_estimators=50, max_depth=5, random_state=42) bag.fit(X_bag, y_bag) bag_acc = bag.score(X_bag, y_bag) print(f"Bagging train accuracy: {bag_acc:.4f}") assert bag_acc >= 0.90, f"Expected >= 0.90, got {bag_acc}" print("Bagging check passed.")

Bagging train accuracy: 1.0000
Bagging check passed.

Exercise 3 — Conceptual: Why Does Random Feature Selection Help?¶

Random forest differs from plain bagging in one way: at each split, only a random subset of $m_{\text{try}} = \lfloor\sqrt{d}\rfloor$ features is considered.

Questions:

1. Correlation argument. Suppose one feature is much stronger than the others. In plain bagging, every tree will likely split on this feature at the root. How does this affect the pairwise correlation $\rho$ between trees? What happens to the variance formula $\text{Var}(H) = \rho\sigma^2 + \frac{1-\rho}{M}\sigma^2$?

2. Bias-variance trade-off. Random feature selection makes each individual tree weaker (higher bias) because it sometimes cannot use the best feature. Why is this trade-off still favorable in terms of ensemble error?

3. Extreme case. What happens if $m_{\text{try}} = 1$ (consider only one random feature per split)? What if $m_{\text{try}} = d$ (consider all features)? Which extreme recovers plain bagging?

4. Practical implication. A colleague reports that their random forest has the same accuracy whether they use 50 or 500 trees. Explain why this is expected, using the variance formula.

Write your answers here.

1. ...
2. ...
3. ...
4. ...

Exercise 4 — Coding: Variance Reduction Simulation¶

Empirically verify that averaging $M$ noisy predictors reduces variance.

Setup:

• True function: $f(x) = \sin(x)$ for $x \in [0, 2\pi]$.
• Each "predictor" adds Gaussian noise: $h_m(x) = \sin(x) + \epsilon_m$, $\epsilon_m \sim \mathcal{N}(0, 1)$.

Tasks:

1. For $M \in \{1, 5, 10, 50, 100\}$, generate $M$ noisy predictions at $x = \pi/4$ and compute the variance of their average across 1000 repetitions.
2. Plot empirical variance vs $M$ and overlay the theoretical curve $\sigma^2/M$.
3. Verify that the empirical variance is close to $1/M$ (since $\sigma^2 = 1$ and predictors are independent, so $\rho = 0$).

Deterministic check: For $M=100$, the empirical variance should be within $[0.005, 0.03]$ (near $1/100 = 0.01$).

In [6]:

# TODO: implement the variance reduction simulation
# M_values = [1, 5, 10, 50, 100]
# n_reps = 1000
# x_test = np.pi / 4
# true_val = np.sin(x_test)
# empirical_vars = []
#
# for M in M_values:
#     averages = []
#     for _ in range(n_reps):
#         predictions = true_val + rng.normal(0, 1, size=M)
#         averages.append(np.mean(predictions))
#     empirical_vars.append(np.var(averages))
#
# # Plot and compare with 1/M
# ...
#
# # Deterministic check
# assert 0.005 < empirical_vars[-1] < 0.03, f"Var for M=100: {empirical_vars[-1]}"

# TODO: implement the variance reduction simulation # M_values = [1, 5, 10, 50, 100] # n_reps = 1000 # x_test = np.pi / 4 # true_val = np.sin(x_test) # empirical_vars = [] # # for M in M_values: # averages = [] # for _ in range(n_reps): # predictions = true_val + rng.normal(0, 1, size=M) # averages.append(np.mean(predictions)) # empirical_vars.append(np.var(averages)) # # # Plot and compare with 1/M # ... # # # Deterministic check # assert 0.005 < empirical_vars[-1] < 0.03, f"Var for M=100: {empirical_vars[-1]}"

Solution (Exercise 4)¶

In [7]:

# Solution — averaging M independent predictors shrinks variance like 1/M
M_values = [1, 5, 10, 50, 100]
n_reps = 1000
x_test = np.pi / 4
true_val = np.sin(x_test)
empirical_vars = []

for M in M_values:
    averages = []
    for _ in range(n_reps):
        predictions = true_val + rng.normal(0, 1, size=M)
        averages.append(np.mean(predictions))
    empirical_vars.append(np.var(averages))

fig, ax = plt.subplots(figsize=(7, 4.5))
ax.loglog(M_values, empirical_vars, "o-", label="Empirical variance of the average")
ax.loglog(M_values, [1.0 / M for M in M_values], "--", label=r"Theoretical $\sigma^2 / M = 1/M$")
ax.set_xlabel("Number of averaged predictors $M$")
ax.set_ylabel("Variance of the averaged prediction")
ax.legend()
ax.grid(True, alpha=0.3)
plt.show()

assert 0.005 < empirical_vars[-1] < 0.03, f"Var for M=100: {empirical_vars[-1]}"
print(f"Variance at M=100: {empirical_vars[-1]:.4f} (theory: {1/100:.4f})")

# Solution — averaging M independent predictors shrinks variance like 1/M M_values = [1, 5, 10, 50, 100] n_reps = 1000 x_test = np.pi / 4 true_val = np.sin(x_test) empirical_vars = [] for M in M_values: averages = [] for _ in range(n_reps): predictions = true_val + rng.normal(0, 1, size=M) averages.append(np.mean(predictions)) empirical_vars.append(np.var(averages)) fig, ax = plt.subplots(figsize=(7, 4.5)) ax.loglog(M_values, empirical_vars, "o-", label="Empirical variance of the average") ax.loglog(M_values, [1.0 / M for M in M_values], "--", label=r"Theoretical $\sigma^2 / M = 1/M$") ax.set_xlabel("Number of averaged predictors $M$") ax.set_ylabel("Variance of the averaged prediction") ax.legend() ax.grid(True, alpha=0.3) plt.show() assert 0.005 < empirical_vars[-1] < 0.03, f"Var for M=100: {empirical_vars[-1]}" print(f"Variance at M=100: {empirical_vars[-1]:.4f} (theory: {1/100:.4f})")

Variance at M=100: 0.0094 (theory: 0.0100)

Exercise 5 — Conceptual: Boosting vs Bagging Failure Modes¶

Questions:

1. A dataset has 5% mislabelled examples. Would you prefer random forest or gradient boosting? Explain in terms of how each method treats misclassified examples.

2. You train a gradient boosting model with 1000 trees and observe that training loss is near zero but test loss is high. Propose three concrete modifications to reduce overfitting (be specific about which hyperparameter to change and in which direction).

3. Explain why random forest can never overfit by adding more trees (increasing $M$), while gradient boosting can. Relate your answer to the difference between averaging and sequential fitting.

Write your answers here.

1. ...
2. ...
3. ...