Multiple Linear Regression (Normal Equation)

mediumFREELinear RegressionMachine Learning 1

Implement multiple linear regression using the normal equation.

Given a feature matrix $X$ (without bias column) and target vector $y$ , compute the weight vector $w$ that minimizes the mean squared error.

First, prepend a column of ones to $X$ to form the augmented matrix $X_a$ , then solve: $w = (X_a^T X_a)^{-1} X_a^T y$

Return the weight vector as a list, rounded to 4 decimal places. The first element is the bias/intercept.

You must implement matrix operations from scratch (transpose, multiply, invert).

Example

Input

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

Output

[0.0, 2.0]

Reasoning

Inputs: X holds $n = 3$ samples with $m = 1$ feature each ( $1, 2, 3$ ), and y holds their targets $2, 4, 6$ . We want weights $[w_0, w_1]$ so that $\hat y = w_0 + w_1 x$ .
The column of ones turns the intercept into an ordinary weight: $X_a = \begin{pmatrix}1&1\\1&2\\1&3\end{pmatrix}$ ( $3 \times 2$ ).
$X_a^T X_a = \begin{pmatrix}3&6\\6&14\end{pmatrix}$ : the top-left entry counts the samples, the off-diagonal is $\sum x_i = 6$ , and the bottom-right is $\sum x_i^2 = 14$ . Likewise $X_a^T y = \begin{pmatrix}12\\28\end{pmatrix}$ , i.e. $\sum y_i$ and $\sum x_i y_i$ .
Its determinant is $3 \cdot 14 - 6 \cdot 6 = 6$ , so the inverse is $\frac{1}{6}\begin{pmatrix}14&-6\\-6&3\end{pmatrix}$ .
Multiplying: $w_0 = \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] after rounding to 4 decimal places.
Notice the data lie exactly on $y = 2x$ , so the fit is perfect: zero intercept, slope $2$ . Shifting every target up by $1$ would change only $w_0$ .

Constraints

X is a 2D list (n samples x m features)
y is a 1D list of n targets
Return a list of (m+1) weights rounded to 4 decimal places
First weight is the intercept (bias term)
Implement matrix operations without numpy

Learn this in

Model Fitting and OptimizationCV Study Plan Linear AlgebraFoundations 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 (target) and one or more independent variables (features) using a linear equation. In Multiple Linear Regression, we have more than one feature, and the goal is to find the best-fitting linear line that minimizes the error between predicted and actual values. The Normal Equation is a closed-form solution to find the optimal weights for the linear regression model.

The Normal Equation is derived by taking the partial derivatives of the Mean Squared Error (MSE) with respect to each weight and setting them to zero. This results in the equation: $w = (X_a^T X_a)^{-1} X_a^T y$ , where $X_a$ is the augmented feature matrix with a bias column, $y$ is the target vector, and $w$ is the weight vector. To implement this equation, we need to perform matrix operations such as transpose, multiplication, and inversion.

Matrix operations are essential in linear algebra and are used extensively in machine learning. The transpose of a matrix is obtained by swapping its rows with columns. Matrix multiplication involves multiplying corresponding elements of two matrices and summing them up. Matrix inversion is the process of finding a matrix that, when multiplied by the original matrix, results in the identity matrix. These operations can be implemented from scratch using nested loops and basic arithmetic operations.

Algorithm/Approach

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

Preprocess the feature matrix by adding a bias column
Compute the transpose of the augmented matrix
Calculate the product of the transposed matrix and the original matrix
Invert the resulting matrix
Multiply the inverted matrix with the transposed matrix and the target vector to obtain the weight vector

This approach requires implementing matrix operations from scratch, which can be challenging but helps to understand the underlying mathematics.

Step-by-Step Strategy

To implement the solution, follow these steps:

Add a bias column to the feature matrix $X$ to form the augmented matrix $X_a$ .
Compute the transpose of the augmented matrix $X_a$ .
Calculate the product of the transposed matrix $X_a^T$ and the original matrix $X_a$ .
Invert the resulting matrix $(X_a^T X_a)$ .
Multiply the inverted matrix with the transposed matrix $X_a^T$ and the target vector $y$ to obtain the weight vector $w$ .
Round the weight vector to 4 decimal places.

Common Pitfalls

When implementing the solution, watch out for the following:

Incorrectly adding the bias column to the feature matrix
Failing to handle edge cases, such as a singular matrix
Incorrectly implementing matrix operations, such as transpose or multiplication
Not rounding the weight vector to the correct number of decimal places

Time & Space Complexity

The time complexity of the solution is O(n^3 + m^3), where n is the number of features and m is the number of samples. This is because matrix inversion has a time complexity of O(n^3) and matrix multiplication has a time complexity of O(m^3). The space complexity is O(n^2 + m^2), as we need to store the augmented matrix, the transposed matrix, and the inverted matrix.

solution.py

Python 3.13

Test results