Gradient Boosting Residual Step

hardFREEEnsemble MethodsMachine Learning 1

Implement one step of Gradient Boosting for regression.

Given current predictions $\hat{y}$ and true values $y$ :

Compute residuals: $r_i = y_i - \hat{y}_i$
Fit a simple model to the residuals: compute the mean residual for each group defined by a feature threshold. Given the split threshold, predict the mean residual for left ( $\leq$ threshold) and right ( $>$ threshold) groups.
Update predictions: $\hat{y}_i' = \hat{y}_i + \eta \cdot h(x_i)$ where $\eta$ is the learning rate and $h(x_i)$ is the predicted residual.

Return the updated predictions, rounded to 4 decimal places.

Example

Input

y_true = [3, 6, 4, 8]
y_pred = [2, 5, 3, 7]
feature_values = [1, 3, 2, 4]
threshold = 2.5
learning_rate = 0.1

Output

[2.1, 5.1, 3.1, 7.1]

Reasoning

Inputs: four samples with targets $y = [3, 6, 4, 8]$ and current predictions $\hat{y} = [2, 5, 3, 7]$ . The feature $x = [1, 3, 2, 4]$ only picks each sample's side of the split; $\eta = 0.1$ scales the correction.
Residuals: $r = [3-2,\ 6-5,\ 4-3,\ 8-7] = [1, 1, 1, 1]$ , so every prediction is exactly 1 too low.
Split at 2.5: samples 1 and 3 ( $x = 1, 2$ ) fall left; samples 2 and 4 ( $x = 3, 4$ ) fall right. Sides follow the feature value, not list position. Left mean $= (1+1)/2 = 1$ , right mean $= (1+1)/2 = 1$ , so $h(x_i) = 1$ for everyone.
Update: $\hat{y}_i' = \hat{y}_i + 0.1 \cdot 1$ , giving [2.1, 5.1, 3.1, 7.1].
Notice: only 10% of the gap is closed, so each new residual is $0.9$ . With unequal residuals the two sides would get different corrections, which is what the split is for.

Constraints

y_true, y_pred: lists of actual and current predicted values
feature_values: list of feature values for splitting
threshold: split value
learning_rate: float > 0
Return list of updated predictions rounded to 4 decimal places

Learn this in

Ensemble MethodsML Study Plan

More from Machine Learning 1

RBF Kernel Matrixhard Polynomial Kernelmedium Hinge Losseasy Linear Decision Boundaryeasy Random Feature Subspacemedium

Concept primer

Background Knowledge

Gradient Boosting is a powerful ensemble method that combines multiple weak models to create a strong predictive model. The core idea is to iteratively train models to predict the residuals of the previous model, with each subsequent model attempting to correct the errors of the previous one. This process allows Gradient Boosting to handle complex interactions between features and capture non-linear relationships.

In the context of regression, Gradient Boosting aims to minimize the mean squared error between predictions and true values. The residuals, calculated as $r_i = y_i - \hat{y}_i$ , represent the errors of the current model. By fitting a simple model to these residuals, Gradient Boosting can identify areas where the current model is performing poorly and correct them in the next iteration. The learning rate, denoted by $\eta$ , controls the step size of each update, preventing overfitting and allowing the model to converge.

The simple model used to fit the residuals is typically a decision tree, which partitions the data into distinct regions based on feature values. In this problem, we're using a simplified version of this approach, where the data is split into two groups based on a feature threshold. The mean residual is calculated for each group, and these values are used to update the predictions. This process is a key component of Gradient Boosting, as it allows the model to adapt to the underlying patterns in the data.

Algorithm/Approach

The general approach to solving this problem involves the following steps:

Compute the residuals between the current predictions and true values
Fit a simple model to the residuals, using a feature threshold to split the data into two groups
Calculate the mean residual for each group
Update the predictions using the mean residuals and the learning rate

This approach is a simplified version of the Gradient Boosting algorithm, focusing on a single iteration of the process.

Step-by-Step Strategy

To implement the solution, follow these steps:

Calculate the residuals $r_i = y_i - \hat{y}_i$ for each data point
Choose a feature and threshold to split the data into two groups
Calculate the mean residual for each group
Update the predictions using the formula $\hat{y}_i' = \hat{y}_i + \eta \cdot h(x_i)$ , where $h(x_i)$ is the predicted residual for each data point
Round the updated predictions to 4 decimal places

Common Pitfalls

When implementing the solution, watch out for the following:

Incorrect calculation of residuals or mean residuals
Incorrect application of the learning rate
Failure to round the updated predictions to the correct number of decimal places

Time & Space Complexity

The time complexity of this solution is $O(n)$ , where $n$ is the number of data points, since we need to iterate over the data to calculate the residuals and update the predictions. The space complexity is also $O(n)$ , as we need to store the residuals and updated predictions for each data point. Note that this is a simplified version of the Gradient Boosting algorithm, and the actual time and space complexity may vary depending on the specific implementation and the size of the dataset.

solution.py

Python 3.13

Test results