Preporato

One gradient boosting round

Medium14 min10 hidden tests

A food delivery app predicts delivery time in minutes. Its boosted model already makes a prediction for every order, and the next round adds a stump: a one-question tree that splits orders on distance at a given threshold. Write boosting_step(x, y, preds, threshold, lr) that fits the stump to the current residuals under squared loss and returns the updated predictions.

Drag the threshold

pred += lr × mean residual of its leaf
True minutesPrediction nowResidualAfter this round

Residuals y − pred: −10, −6, 5, 11. Left leaf (x ≤ 2.5): mean −8. Right leaf: mean 8. New predictions = 20 + 0.50 × leaf: 16, 16, 24, 24.

New predictions 16, 16, 24, 24.

Examples

Short trips move down, long trips move up

boosting_step([1.0, 2.0, 3.0, 4.0], [10.0, 14.0, 25.0, 31.0], [20.0, 20.0, 20.0, 20.0], 2.5, 0.5)

returns [16, 16, 24, 24]

A distance equal to the threshold goes left

boosting_step([2.0, 5.0, 2.0, 8.0], [30.0, 42.0, 26.0, 50.0], [37.0, 37.0, 37.0, 37.0], 2.0, 0.1)

returns [36.1, 37.9, 36.1, 37.9]

Requirements

  • x (distance), y (true minutes) and preds (current predictions) are lists of n floats, n >= 1. threshold is a float and lr, the learning rate, a float of 0 or more.
  • Use squared loss L = (y - pred)^2 / 2, so the negative gradient for each order is its residual, y - pred.
  • Orders with x <= threshold go to the left leaf, the rest to the right. Each leaf's value is the mean residual of its orders. A leaf with no orders has value 0.0.
  • Return a new 1-D float array of length n: each prediction plus lr times its leaf's value.
The idea behind it

Gradient boosting builds a model as a sum of small trees, added one round at a time. Each new tree is fit to the negative gradient of the loss with respect to the current predictions. For squared loss, (y - pred)^2 / 2, that negative gradient is the residual y - pred: the part of each target the model still misses. A tree's leaf that holds several examples predicts their mean residual, because the mean is what minimizes squared error inside the leaf. The new tree's output is scaled by a learning rate, often 0.05 to 0.3, before it is added. This shrinkage makes each round a small correction, so many rounds together fit the data without chasing noise. The same loop, with other losses and deeper trees, runs inside XGBoost, LightGBM and CatBoost.

pythonCtrl+Enter runs
import numpy as np

def boosting_step(x, y, preds, threshold, lr):
"""One gradient boosting round with a stump, under squared loss.

x: list of n floats, the feature the stump splits on
y: list of n floats, the true targets
preds: list of n floats, the model's current predictions
threshold: float, x <= threshold goes to the left leaf
lr: float >= 0, the learning rate (shrinkage)
Returns a new 1-D float array of n updated predictions:
preds + lr * (mean residual of each order's leaf).
"""
raise NotImplementedError

Stuck? Reveal one rung at a time

Worked solution

Pro includes the solution and walkthrough for every problem, plus the hands-on labs. The first problem of each topic is free.

Get Pro Sign in