📘

Gradient Descent for Linear Regression

HardLinear Regression 📚 Machine Learning 1

Implement batch gradient descent for simple linear regression.

Given data points $(x, y)$ , initial weight $w$ and bias $b$ , learning rate $\alpha$ , and number of iterations, update $w$ and $b$ to minimize Mean Squared Error:

$MSE = \frac{1}{n} \sum_{i=1}^{n} (y_i - (w \cdot x_i + b))^2$

The gradients are: $\frac{\partial MSE}{\partial w} = \frac{-2}{n} \sum_{i=1}^{n} x_i(y_i - (w \cdot x_i + b))$ $\frac{\partial MSE}{\partial b} = \frac{-2}{n} \sum_{i=1}^{n} (y_i - (w \cdot x_i + b))$

Return a tuple (w, b) after all iterations, both rounded to 4 decimal places.

Example:

Input:

X = [1, 2, 3]
y = [2, 4, 6]
w = 0.0, b = 0.0
learning_rate = 0.1, iterations = 100

Output:

(1.9715, 0.0647)

Reasoning:

We start with the given data points $(x, y)$ : $(1, 2)$ , $(2, 4)$ , $(3, 6)$ , initial weight $w = 0.0$ , bias $b = 0.0$ , learning rate $\alpha = 0.1$ , and number of iterations $= 100$ .
We calculate the gradients $\frac{\partial MSE}{\partial w}$ and $\frac{\partial MSE}{\partial b}$ using the given formulas: $\frac{\partial MSE}{\partial w} = \frac{-2}{n} \sum_{i=1}^{n} x_i(y_i - (w \cdot x_i + b))$ and $\frac{\partial MSE}{\partial b} = \frac{-2}{n} \sum_{i=1}^{n} (y_i - (w \cdot x_i + b))$ , and update $w$ and $b$ using $w = w - \alpha \cdot \frac{\partial MSE}{\partial w}$ and $b = b - \alpha \cdot \frac{\partial MSE}{\partial b}$ for each iteration.
We repeat the process of calculating gradients and updating $w$ and $b$ for $100$ iterations, which minimizes the Mean Squared Error $MSE = \frac{1}{n} \sum_{i=1}^{n} (y_i - (w \cdot x_i + b))^2$ .
After $100$ iterations, we obtain the updated values of $w$ and $b$ , which are then rounded to $4$ decimal places, resulting in the output $(1.9715, 0.0647)$ .

Constraints:

X and y are lists of equal length
learning_rate > 0, iterations >= 1
Initial w and b are given as floats
Return tuple (w, b) rounded to 4 decimal places

More from Machine Learning 1

RBF Kernel MatrixHard Polynomial KernelMedium Hinge LossEasy Linear Decision BoundaryEasy Gradient Boosting Residual StepHard

Background Knowledge

Linear Regression is a fundamental concept in Machine Learning that involves modeling the relationship between a dependent variable (target) and one or more independent variables (features) using a linear equation. The goal is to find the best-fitting line that minimizes the difference between predicted and actual values. In simple linear regression, we have one feature and one target variable, and the equation takes the form of $y = wx + b$ , where $w$ is the weight, $x$ is the feature, and $b$ is the bias.

The Mean Squared Error (MSE) is a common loss function used to evaluate the performance of a linear regression model. It calculates the average squared difference between predicted and actual values. The gradient descent algorithm is an optimization technique used to minimize the loss function by iteratively updating the model parameters ( $w$ and $b$ ) in the direction of the negative gradient. The gradients of the loss function with respect to the model parameters are used to compute the updates.

In batch gradient descent, the model parameters are updated after computing the gradients using the entire training dataset. This is in contrast to stochastic gradient descent, where the parameters are updated after computing the gradients using a single data point. Batch gradient descent is more computationally expensive but can lead to more stable convergence.

Algorithm/Approach

The general approach to solving this problem involves implementing the batch gradient descent algorithm to minimize the Mean Squared Error (MSE) loss function. The algorithm iteratively updates the model parameters ( $w$ and $b$ ) using the gradients of the loss function with respect to these parameters. The key components of the algorithm include:

Computing the predicted values using the current model parameters
Calculating the gradients of the loss function with respect to the model parameters
Updating the model parameters using the gradients and the learning rate
Repeating the process for a specified number of iterations

Step-by-Step Strategy

To implement the solution, follow these steps:

Initialize the model parameters ( $w$ and $b$ ) with the given values.
Compute the predicted values using the current model parameters and the feature values.
Calculate the gradients of the loss function with respect to the model parameters ( $w$ and $b$ ) using the predicted values and the actual values.
Update the model parameters using the gradients, the learning rate, and the update rules.
Repeat steps 2-4 for the specified number of iterations.
Return the final model parameters ( $w$ and $b$ ) rounded to 4 decimal places.

Common Pitfalls

When implementing the solution, watch out for the following common pitfalls:

Incorrectly computing the gradients of the loss function
Using the wrong update rules for the model parameters
Not properly initializing the model parameters
Not checking for convergence or using a sufficient number of iterations

Time & Space Complexity

The time complexity of the batch gradient descent algorithm is O(n * iterations), where n is the number of data points and iterations is the number of iterations. The space complexity is O(n), as we need to store the feature values, actual values, and predicted values. Note that the time and space complexity can vary depending on the specific implementation and the size of the dataset.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.