Gradient Boosting with Stumps

Train a gradient boosted regressor for squared error, with regression stumps as the weak learners, and return its predictions on new data.

Gradient boosting builds a model as a sum of small corrections. It starts from a constant, the mean of y. Each round fits a stump to the residuals, the part of y that the model does not explain yet, and adds a shrunken copy of that stump to the model. For squared error, the residuals are exactly the negative gradient of the loss, which gives the method its name.

F_0(x) = mean(y)
for each round:
    r      = y - F(X)                 # residuals on the training data
    stump  = best regression stump for (X, r)
    F(x)   = F(x) + lr * stump(x)

A regression stump has a feature j and a threshold t. It predicts the mean residual of the training rows with X[i, j] <= t on that side, and the mean residual of the other rows on the other side. Choose the stump with the lowest sum of squared errors on the residuals. Try every feature and every midpoint between consecutive unique values. Break ties by lower feature index, then lower threshold. If no feature has two unique values, skip the round.

Function signature

def gradient_boost(X, y, X_test, n_rounds, lr):

Example

Input

X = np.array([[1.0], [2.0], [3.0], [4.0]])
y = np.array([1.0, 1.0, 3.0, 3.0])
X_test = np.array([[1.5], [3.5]])
gradient_boost(X, y, X_test, n_rounds=1, lr=0.5)

Output

array([1.5, 2.5])

Reasoning

The model starts at mean(y) = 2, so the residuals are [-1, -1, 1, 1]. The best stump splits at 2.5, with means -1 on the left and +1 on the right. After one round with lr = 0.5, a point on the left gets 2 - 0.5 = 1.5 and a point on the right gets 2 + 0.5 = 2.5.

Constraints and notes

• With n_rounds = 0 every prediction is mean(y).
• Compare errors with a small tolerance, such as 1e-12, so that the tie rules hold.
• Return an array of shape (n_test,).