Gradient Boosting with Stumps - Supervised Learning

Gradient Boosting with Stumps

Implement fit_stump (the best depth-1 regression tree) and gradient_boosting (a squared-loss booster that adds one shrunken stump per round).

Background

Gradient boosting builds a strong model as a sum of weak ones: each new learner is fit to the negative gradient of the loss at the current predictions. For the squared loss L = 0.5 * (y - F)^2 the negative gradient is simply the residual y - F. Boosted trees (XGBoost, LightGBM, sklearn's HistGradientBoosting) are still the go-to models for tabular data.

1. fit_stump(X, r): best depth-1 tree

A stump splits on one feature j at a threshold t: samples with X[:, j] <= t go left, the others go right, and each side predicts the mean of r on that side.

Search exhaustively:

1. For each feature j = 0 .. d-1, take the sorted unique values u of X[:, j]. The candidate thresholds are the midpoints (u[:-1] + u[1:]) / 2 (a feature with a single unique value has none).
2. Score each candidate by the sum of squared errors

SSE = sum_left (r - mean_left)^2 + sum_right (r - mean_right)^2

3. Keep the smallest SSE. Ties: keep the first one found, scanning features in order and thresholds in ascending order (replace the best only on a strictly smaller SSE).
4. If there is no candidate at all, return (0, inf, mean(r), mean(r)).

2. gradient_boosting(X, y, n_rounds, learning_rate)

F_0 = mean(y)                          # constant initial prediction, shape (n,)
for m = 1 .. n_rounds:
    r   = y - F_{m-1}                   # residuals = negative gradient
    h_m = fit_stump(X, r)
    F_m = F_{m-1} + learning_rate * h_m(X)
    loss_m = mean((y - F_m)^2)          # training MSE after round m

This matches sklearn.ensemble.GradientBoostingRegressor(loss='squared_error', max_depth=1, n_estimators=n_rounds, learning_rate=learning_rate), whose train_score_ is our 'losses' (sklearn breaks exact ties between features at random, so tie cases may differ).

Inputs

• X: float array (n, d); y and r: float arrays (n,)
• n_rounds: int; learning_rate: float in (0, 1]

Expected Return Format

fit_stump returns a tuple (feature, threshold, left_value, right_value): an int and three floats.

gradient_boosting returns a dictionary with these keys:

• 'f0': the initial constant prediction (float)
• 'stumps': list of n_rounds tuples (feature, threshold, left_value, right_value)
• 'predictions': final training predictions F_M, shape (n,)
• 'losses': list of n_rounds floats, the training MSE after each round

Edge Cases and Conventions

• Because each stump's leaf values are the least-squares fit to the residuals, the training loss is non-increasing for 0 < learning_rate <= 1.
• A sample exactly on a threshold goes left (<=).

Constraints

• NumPy only; no sklearn. Scoring all thresholds of one feature at once (with a (T, n) mask) is encouraged.

Follow-up

• For log loss (classification), what are the residuals, and why do leaf values need a Newton step instead of a plain mean?
• Why does a smaller learning rate with more rounds usually generalise better?

Input: fit_stump(np.array([[1], [2], [3], [4], [5], [6]]), np.array([-2., -2., -2., 2., 2., 2.]))
Output: (0, 3.5, -2.0, 2.0)

Input: gradient_boosting(np.array([[1], [2], [3], [4], [5], [6]]), np.array([1., 1., 1., 5., 5., 5.]), n_rounds=3, learning_rate=0.5)
Output: {'f0': 3.0, 'losses': [1.0, 0.25, 0.0625], ...}

import numpy as np

def fit_stump(X, r):
    """
    Exhaustively find the best depth-1 regression tree for targets r.

    Args:
        X: Features, shape (n, d)
        r: Targets (residuals), shape (n,)

    Returns:
        (feature, threshold, left_value, right_value)
        Left side is X[:, feature] <= threshold; ties keep the first
        (feature, threshold) found; no candidate -> (0, inf, mean(r), mean(r)).
    """
    # Your code here
    pass


def gradient_boosting(X, y, n_rounds=10, learning_rate=0.1):
    """
    Gradient boosting with decision stumps on squared loss.

    Args:
        X: Features, shape (n, d)
        y: Targets, shape (n,)
        n_rounds: Number of boosting rounds
        learning_rate: Shrinkage applied to every stump

    Returns:
        dict with 'f0' (float), 'stumps' (list of tuples),
        'predictions' (n,), 'losses' (list of n_rounds floats)
    """
    # Your code here
    pass