Ridge Regression

mediumFREELinear RegressionMachine 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

Inputs: $X$ holds 3 samples with one feature each ( $x = 1, 2, 3$ ), $y$ holds their targets $2, 4, 6$ , and $\lambda = 0$ (no penalty).
Augment: prepending the ones column gives rows $(1, 1), (1, 2), (1, 3)$ . Weights are intercept $b$ , then slope $w_1$ .
Build the system: $X_a^T X_a = \begin{pmatrix} 3 & 6 \\ 6 & 14 \end{pmatrix}$ (count, $\sum x$ , $\sum x^2$ ) and $X_a^T y = (12, 28)$ ( $\sum y$ , $\sum x y$ ). $\lambda I'$ would add to the bottom-right entry only.
Solve: the determinant is $3 \cdot 14 - 6 \cdot 6 = 6$ , so the inverse is $\frac{1}{6}\begin{pmatrix} 14 & -6 \\ -6 & 3 \end{pmatrix}$ . Then $b = \frac{14 \cdot 12 - 6 \cdot 28}{6} = 0$ and $w_1 = \frac{-6 \cdot 12 + 3 \cdot 28}{6} = 2$ , giving [0.0, 2.0].
Notice: the data lies exactly on $y = 2x$ . With $\lambda = 1$ the bottom-right entry becomes $15$ , the slope shrinks to $\frac{12}{9} \approx 1.3333$ , and the unpenalised intercept rises to $1.3333$ to compensate.

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

Learn this in

Linear AlgebraFoundations Probability & StatisticsFoundations Introduction to MLML Study Plan Linear RegressionML Study Plan

More from Machine Learning 1

RBF Kernel Matrixhard Polynomial Kernelmedium Hinge Losseasy Linear Decision Boundaryeasy Gradient Boosting Residual Stephard

Concept primer

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