📘

Multiple Linear Regression (Normal Equation)

MediumLinear Regression 📚 Machine 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:

First, we prepend a column of ones to $X$ to form the augmented matrix $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 = [[1, 1, 1], [1, 2, 3]] \cdot [[1, 1], [1, 2], [1, 3]] = [[3, 6], [6, 14]]$ and $X_a^T y = [[1, 1, 1], [1, 2, 3]] \cdot [2, 4, 6] = [12, 28]$
Next, we calculate the inverse of $X_a^T X_a$ : $(X_a^T X_a)^{-1} = [[3, 6], [6, 14]]^{-1} = \frac{1}{(3 \cdot 14 - 6 \cdot 6)} \cdot [[14, -6], [-6, 3]] = \frac{1}{6} \cdot [[14, -6], [-6, 3]] = [[\frac{7}{3}, -1], [-1, \frac{1}{2}]]$
Finally, we calculate the weight vector $w = (X_a^T X_a)^{-1} X_a^T y = [[\frac{7}{3}, -1], [-1, \frac{1}{2}]] \cdot [12, 28] = [0, 2]$

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

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. 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

0/0

Run code to see test results.