05 Decision Trees — Exercises¶

Test your understanding of impurity measures, information gain, tree construction, and overfitting behaviour.

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: Entropy and Gini¶

A node contains 10 samples with the following class labels:

$$y = [A, A, A, A, B, B, B, C, C, C]$$

So $p_A = 4/10$, $p_B = 3/10$, $p_C = 3/10$.

Tasks (derive by hand, then verify numerically):

1. Compute the Gini impurity: $G = 1 - \sum_k p_k^2$.
2. Compute the entropy: $H = -\sum_k p_k \log_2 p_k$.
3. Now consider a split that sends $[A, A, A, A, B]$ left and $[B, B, C, C, C]$ right. Compute the weighted Gini impurity of the children and the information gain.

Expected results:

Quantity	Value
$G(\text{parent})$	$1 - (0.16 + 0.09 + 0.09) = 0.66$
$H(\text{parent})$	$\approx 1.5710$ bits
$G(\text{left})$	$1 - (16/25 + 1/25) = 0.32$
$G(\text{right})$	$1 - (4/25 + 9/25) = 0.48$
Weighted Gini	$(5/10)(0.32) + (5/10)(0.48) = 0.40$
Info gain (Gini)	$0.66 - 0.40 = 0.26$

In [2]:

# Verify your hand calculations
y_parent = np.array([0, 0, 0, 0, 1, 1, 1, 2, 2, 2])  # A=0, B=1, C=2
y_left = np.array([0, 0, 0, 0, 1])                     # 4 A's and 1 B
y_right = np.array([1, 1, 2, 2, 2])                    # 2 B's and 3 C's


def gini(y):
    _, counts = np.unique(y, return_counts=True)
    p = counts / counts.sum()
    return float(1 - np.sum(p ** 2))


def entropy_bits(y):
    _, counts = np.unique(y, return_counts=True)
    p = counts / counts.sum()
    p = p[p > 0]
    return float(-np.sum(p * np.log2(p)))


g_parent = gini(y_parent)
h_parent = entropy_bits(y_parent)
g_left = gini(y_left)
g_right = gini(y_right)
weighted_gini = (len(y_left) / len(y_parent)) * g_left + (len(y_right) / len(y_parent)) * g_right
info_gain = g_parent - weighted_gini

print(f"Gini(parent)  = {g_parent:.4f}")
print(f"Entropy(parent) = {h_parent:.4f} bits")
print(f"Gini(left)    = {g_left:.4f}")
print(f"Gini(right)   = {g_right:.4f}")
print(f"Weighted Gini = {weighted_gini:.4f}")
print(f"Info gain     = {info_gain:.4f}")

assert np.isclose(g_parent, 0.66, atol=1e-10)
assert np.isclose(h_parent, 1.5710, atol=0.001)
assert np.isclose(g_left, 0.32, atol=1e-10)
assert np.isclose(g_right, 0.48, atol=1e-10)
assert np.isclose(weighted_gini, 0.40, atol=1e-10)
assert np.isclose(info_gain, 0.26, atol=1e-10)
print("All hand-calculation checks passed.")

# Verify your hand calculations y_parent = np.array([0, 0, 0, 0, 1, 1, 1, 2, 2, 2]) # A=0, B=1, C=2 y_left = np.array([0, 0, 0, 0, 1]) # 4 A's and 1 B y_right = np.array([1, 1, 2, 2, 2]) # 2 B's and 3 C's def gini(y): _, counts = np.unique(y, return_counts=True) p = counts / counts.sum() return float(1 - np.sum(p ** 2)) def entropy_bits(y): _, counts = np.unique(y, return_counts=True) p = counts / counts.sum() p = p[p > 0] return float(-np.sum(p * np.log2(p))) g_parent = gini(y_parent) h_parent = entropy_bits(y_parent) g_left = gini(y_left) g_right = gini(y_right) weighted_gini = (len(y_left) / len(y_parent)) * g_left + (len(y_right) / len(y_parent)) * g_right info_gain = g_parent - weighted_gini print(f"Gini(parent) = {g_parent:.4f}") print(f"Entropy(parent) = {h_parent:.4f} bits") print(f"Gini(left) = {g_left:.4f}") print(f"Gini(right) = {g_right:.4f}") print(f"Weighted Gini = {weighted_gini:.4f}") print(f"Info gain = {info_gain:.4f}") assert np.isclose(g_parent, 0.66, atol=1e-10) assert np.isclose(h_parent, 1.5710, atol=0.001) assert np.isclose(g_left, 0.32, atol=1e-10) assert np.isclose(g_right, 0.48, atol=1e-10) assert np.isclose(weighted_gini, 0.40, atol=1e-10) assert np.isclose(info_gain, 0.26, atol=1e-10) print("All hand-calculation checks passed.")

Gini(parent)  = 0.6600
Entropy(parent) = 1.5710 bits
Gini(left)    = 0.3200
Gini(right)   = 0.4800
Weighted Gini = 0.4000
Info gain     = 0.2600
All hand-calculation checks passed.

Exercise 2 — Coding: Information Gain Function¶

Implement a function best_threshold(X_col, y) that finds the threshold $t$ for a single feature column that maximises information gain (using Gini impurity).

Requirements:

• Scan midpoints between consecutive sorted distinct values.
• Return (best_threshold, best_gain). If no valid split exists, return (None, 0.0).
• Use the incremental counting approach (don't recompute Gini from scratch each time).

Test case:

X_col = [1.0, 2.0, 3.0, 4.0, 5.0, 6.0]
y     = [0,   0,   0,   1,   1,   1]

The best threshold should be 3.5 (perfectly separates the classes), with information gain = 0.5 (parent Gini = 0.5, children Gini = 0.0).

In [3]:

def best_threshold(X_col, y):
    """Find the threshold that maximises Gini information gain.

    Parameters
    ----------
    X_col : 1D array of shape (n,), feature values
    y : 1D array of shape (n,), integer class labels starting from 0

    Returns
    -------
    (threshold, gain) : tuple
        Best threshold and its information gain. (None, 0.0) if no valid split.
    """
    # TODO: implement
    # Hints:
    # 1. Sort by X_col
    # 2. Track left_counts and right_counts incrementally
    # 3. Skip duplicate values
    # 4. Compute Gini from counts: 1 - sum((counts/total)^2)
    pass

def best_threshold(X_col, y): """Find the threshold that maximises Gini information gain. Parameters ---------- X_col : 1D array of shape (n,), feature values y : 1D array of shape (n,), integer class labels starting from 0 Returns ------- (threshold, gain) : tuple Best threshold and its information gain. (None, 0.0) if no valid split. """ # TODO: implement # Hints: # 1. Sort by X_col # 2. Track left_counts and right_counts incrementally # 3. Skip duplicate values # 4. Compute Gini from counts: 1 - sum((counts/total)^2) pass

Solution 2¶

In [4]:

def best_threshold(X_col, y):
    """Find the threshold that maximises Gini information gain.

    Parameters
    ----------
    X_col : 1D array of shape (n,), feature values
    y : 1D array of shape (n,), integer class labels starting from 0

    Returns
    -------
    (threshold, gain) : tuple
        Best threshold and its information gain. (None, 0.0) if no valid split.
    """
    order = np.argsort(X_col, kind="stable")
    x_sorted = np.asarray(X_col)[order]
    y_sorted = np.asarray(y)[order]
    n = len(y_sorted)
    n_classes = int(y_sorted.max()) + 1
    total_counts = np.bincount(y_sorted, minlength=n_classes)

    def gini_from_counts(counts, total):
        p = counts / total
        return 1.0 - np.sum(p ** 2)

    parent_gini = gini_from_counts(total_counts, n)
    left_counts = np.zeros(n_classes, dtype=int)
    right_counts = total_counts.copy()
    best_t, best_gain = None, 0.0

    for i in range(n - 1):
        c = y_sorted[i]
        left_counts[c] += 1
        right_counts[c] -= 1
        # Skip duplicate values — no valid threshold between equal x's
        if x_sorted[i] == x_sorted[i + 1]:
            continue
        n_left, n_right = i + 1, n - i - 1
        weighted = (n_left / n) * gini_from_counts(left_counts, n_left) \
            + (n_right / n) * gini_from_counts(right_counts, n_right)
        gain = parent_gini - weighted
        if gain > best_gain:
            best_gain = gain
            best_t = (x_sorted[i] + x_sorted[i + 1]) / 2.0

    return best_t, best_gain


# Deterministic checks
X_test = np.array([1.0, 2.0, 3.0, 4.0, 5.0, 6.0])
y_test = np.array([0, 0, 0, 1, 1, 1])

thresh, gain = best_threshold(X_test, y_test)
assert np.isclose(thresh, 3.5, atol=1e-10), f"Expected threshold 3.5, got {thresh}"
assert np.isclose(gain, 0.5, atol=1e-10), f"Expected gain 0.5, got {gain}"
print(f"Test 1 passed: threshold={thresh}, gain={gain:.4f}")

# All same class — no valid split
y_pure = np.array([0, 0, 0, 0, 0, 0])
thresh2, gain2 = best_threshold(X_test, y_pure)
assert gain2 == 0.0, f"Pure node should have gain=0, got {gain2}"
print(f"Test 2 passed: pure node → gain={gain2}")

# Imperfect split
y_mix = np.array([0, 0, 1, 0, 1, 1])
thresh3, gain3 = best_threshold(X_test, y_mix)
assert gain3 > 0.0, "Should find some positive gain"
print(f"Test 3 passed: threshold={thresh3}, gain={gain3:.4f}")
print("All information gain checks passed.")

def best_threshold(X_col, y): """Find the threshold that maximises Gini information gain. Parameters ---------- X_col : 1D array of shape (n,), feature values y : 1D array of shape (n,), integer class labels starting from 0 Returns ------- (threshold, gain) : tuple Best threshold and its information gain. (None, 0.0) if no valid split. """ order = np.argsort(X_col, kind="stable") x_sorted = np.asarray(X_col)[order] y_sorted = np.asarray(y)[order] n = len(y_sorted) n_classes = int(y_sorted.max()) + 1 total_counts = np.bincount(y_sorted, minlength=n_classes) def gini_from_counts(counts, total): p = counts / total return 1.0 - np.sum(p ** 2) parent_gini = gini_from_counts(total_counts, n) left_counts = np.zeros(n_classes, dtype=int) right_counts = total_counts.copy() best_t, best_gain = None, 0.0 for i in range(n - 1): c = y_sorted[i] left_counts[c] += 1 right_counts[c] -= 1 # Skip duplicate values — no valid threshold between equal x's if x_sorted[i] == x_sorted[i + 1]: continue n_left, n_right = i + 1, n - i - 1 weighted = (n_left / n) * gini_from_counts(left_counts, n_left) \ + (n_right / n) * gini_from_counts(right_counts, n_right) gain = parent_gini - weighted if gain > best_gain: best_gain = gain best_t = (x_sorted[i] + x_sorted[i + 1]) / 2.0 return best_t, best_gain # Deterministic checks X_test = np.array([1.0, 2.0, 3.0, 4.0, 5.0, 6.0]) y_test = np.array([0, 0, 0, 1, 1, 1]) thresh, gain = best_threshold(X_test, y_test) assert np.isclose(thresh, 3.5, atol=1e-10), f"Expected threshold 3.5, got {thresh}" assert np.isclose(gain, 0.5, atol=1e-10), f"Expected gain 0.5, got {gain}" print(f"Test 1 passed: threshold={thresh}, gain={gain:.4f}") # All same class — no valid split y_pure = np.array([0, 0, 0, 0, 0, 0]) thresh2, gain2 = best_threshold(X_test, y_pure) assert gain2 == 0.0, f"Pure node should have gain=0, got {gain2}" print(f"Test 2 passed: pure node → gain={gain2}") # Imperfect split y_mix = np.array([0, 0, 1, 0, 1, 1]) thresh3, gain3 = best_threshold(X_test, y_mix) assert gain3 > 0.0, "Should find some positive gain" print(f"Test 3 passed: threshold={thresh3}, gain={gain3:.4f}") print("All information gain checks passed.")

Test 1 passed: threshold=3.5, gain=0.5000
Test 2 passed: pure node → gain=0.0
Test 3 passed: threshold=2.5, gain=0.2500
All information gain checks passed.

Exercise 3 — Conceptual: Overfitting and Pruning¶

Questions:

1. When do decision trees overfit? Explain the mechanism — why does a fully grown tree have zero training error but potentially high test error? What is the tree doing to the training data in this case?

2. Depth limit vs pruning. Both control tree complexity. What is the key advantage of post-hoc pruning (cost-complexity pruning) over simply setting a maximum depth before training? Give a concrete example where limiting depth to 3 everywhere would hurt performance.

3. Instability. You train two decision trees on two bootstrap samples of the same dataset. The trees make different predictions on 25% of test points.

   • Is this high or low variance? High or low bias?
   • Propose a single-sentence solution that directly addresses this weakness.
   • Why does averaging many such trees (as in Random Forests) reduce variance but not bias?

Hints¶

1. Think about what each leaf of a fully grown tree contains. How many training points reach the deepest leaves? What happens when a leaf has just 1 sample?

2. Consider a dataset where one region of feature space needs depth 8 to capture a complex interaction, but another region is simple (depth 2 suffices). What does depth=3 do to both regions?

3. Recall the bias-variance decomposition: $E[(\hat{f} - f)^2] = \text{bias}^2 + \text{variance}$. What does averaging do to each term?

Exercise 4 — Coding: Gini vs Entropy Comparison¶

Train two decision trees on the same dataset — one using Gini impurity, the other using entropy. Compare their test accuracy across different depths.

Tasks:

1. Use generate_classification_data(n_samples=300, n_features=4, n_classes=3, random_state=99).
2. Split into 200 train / 100 test.
3. For each max_depth in $[1, 2, \dots, 10]$, train both a Gini tree and an entropy tree (using the scratch implementation from the notebook).
4. Plot test accuracy vs depth for both criteria on the same axes.
5. Are the results very different?

Deterministic check: Both criteria should achieve test accuracy $\ge 0.80$ at depth 5.

In [5]:

from ml_first_principles.data_utils import generate_classification_data

# TODO: generate data, split, train trees, plot comparison
# X_ex4, y_ex4 = generate_classification_data(...)
# ...
# assert gini_acc_depth5 >= 0.80
# assert entropy_acc_depth5 >= 0.80

from ml_first_principles.data_utils import generate_classification_data # TODO: generate data, split, train trees, plot comparison # X_ex4, y_ex4 = generate_classification_data(...) # ... # assert gini_acc_depth5 >= 0.80 # assert entropy_acc_depth5 >= 0.80

Exercise 5 — Conceptual: Trees vs Linear Models¶

Questions:

1. Give an example of a dataset where logistic regression will outperform a decision tree, and explain why. Give another example where the reverse is true.

2. Decision trees do not need feature scaling (standardisation). Why not? What property of the split criterion makes trees invariant to monotone transformations of features?

3. A decision tree trained on a 2D dataset produces 8 rectangular regions. What is the minimum depth of such a tree? What is the maximum number of leaves a tree of depth $d$ can have?