📘

Ridge Regression

MediumLinear Regression 📚 Machine Learning 1

Implement Ridge Regression (L2 regularization) using the regularized normal equation.

Given feature matrix $X$ (without bias column), target vector $y$ , and regularization parameter $\lambda$ , compute: $w = (X_a^T X_a + \lambda I')^{-1} X_a^T y$

where $X_a$ has a column of ones prepended, and $I'$ is the identity matrix with the top-left element set to 0 (we don't regularize the bias).

Return the weight vector as a list, rounded to 4 decimal places.

Example:

Input:

X = [[1], [2], [3]]
y = [2, 4, 6]
lambda_reg = 0.0

Output:

[0.0, 2.0]

Reasoning:

First, we prepend a column of ones to the feature matrix $X$ to get $X_a$ : $X_a = [[1, 1], [1, 2], [1, 3]]$
Then, we calculate $X_a^T X_a$ and $X_a^T y$ : $X_a^T X_a = [[3, 6], [6, 14]]$ and $X_a^T y = [[2 + 4 + 6], [2 + 8 + 12]] = [[12], [22]]$
Next, we compute the regularized matrix $X_a^T X_a + \lambda I'$ , where $\lambda = 0.0$ and $I'$ is the identity matrix with the top-left element set to 0: $X_a^T X_a + \lambda I' = [[0, 6], [6, 14]]$
Finally, we calculate the weight vector $w = (X_a^T X_a + \lambda I')^{-1} X_a^T y$ : $w = [[0.0], [2.0]]$ , which when rounded to 4 decimal places gives the output $[0.0, 2.0]$

Constraints:

X is a 2D list (n x m), y is a 1D list of n targets
lambda_reg is a positive float
Return list of (m+1) weights rounded to 4 decimal places
First weight is the intercept (not regularized)
Implement without numpy

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 and one or more independent variables. In this context, Ridge Regression is a type of linear regression that uses L2 regularization, which adds a penalty term to the loss function to prevent overfitting. The penalty term is proportional to the magnitude of the model's weights, which helps to reduce the impact of noise in the data.

The regularized normal equation is a closed-form solution to the Ridge Regression problem, which is given by the formula: $w = (X_a^T X_a + \lambda I')^{-1} X_a^T y$ . Here, $X_a$ is the feature matrix with a column of ones prepended (i.e., the bias column), $y$ is the target vector, $\lambda$ is the regularization parameter, and $I'$ is the identity matrix with the top-left element set to 0. This equation is derived by minimizing the mean squared error (MSE) between the predicted and actual values, subject to the L2 regularization constraint.

The key concept in Ridge Regression is the use of L2 regularization, which helps to prevent overfitting by adding a penalty term to the loss function. The regularization parameter $\lambda$ controls the strength of the penalty term, with larger values of $\lambda$ resulting in smaller weights and a more biased model. The identity matrix $I'$ is used to exclude the bias term from the regularization penalty, which is why the top-left element is set to 0.

Algorithm/Approach

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

Preprocessing the feature matrix $X$ by adding a column of ones (i.e., the bias column)
Computing the regularized normal equation using the given formula
Solving for the weight vector $w$ using a suitable method (e.g., matrix inversion)

Step-by-Step Strategy

To implement the solution, follow these steps:

Import the necessary libraries and define the input variables ( $X$ , $y$ , $\lambda$ )
Prepend a column of ones to the feature matrix $X$ to create $X_a$
Compute the matrix product $X_a^T X_a$
Create the identity matrix $I'$ with the top-left element set to 0
Compute the regularized matrix $X_a^T X_a + \lambda I'$
Compute the matrix product $X_a^T y$
Solve for the weight vector $w$ using matrix inversion
Round the weight vector $w$ to 4 decimal places

Common Pitfalls

Some common pitfalls to watch out for when implementing Ridge Regression include:

Forgetting to add the bias column to the feature matrix $X$
Incorrectly computing the regularized normal equation
Using an incorrect value for the regularization parameter $\lambda$
Failing to round the weight vector $w$ to the correct number of decimal places

Time & Space Complexity

The time complexity of the Ridge Regression algorithm is $O(n^3)$ , where $n$ is the number of features, due to the matrix inversion step. The space complexity is $O(n^2)$ , as we need to store the feature matrix $X_a$ and the regularized matrix $X_a^T X_a + \lambda I'$ . Note that these complexities assume that the matrix inversion is performed using a standard method (e.g., Gaussian elimination).

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.