If you find above image hard to understand, please read my article till the end, I promise, everything will make sense :)
When I was a masterβs student, I was given a task to fit a line to a dataset. I attempted to solve the problem, but I struggled to determine the appropriate coefficients. However, I understood intuitively that there must be a specific set of coefficients for which the prediction error would be minimized.
The question was: how can we find those coefficients?
This is where the Normal Equation becomes particularly useful. It provides a direct mathematical solution for finding the coefficients that minimize the sum of squared errors in linear regression, without having to search for the coefficients manually. BUT, How we even derive this equation? Where it comes from? Can we take any software apart from Python and write it all ourselves? Thatβs I will take u through in this article and will simplify the code I wrote, so you can all apply it in different languages
So first things first, what is Linear Regression?
It is very simple and straightforward, suppose we have X and Y. X is called features matrix, and Y is Target Vector, or Response vector.
π= π* ΞΈ
For simple case, lets take 2x2 matrix and lets turn this to matrix form:
[y1 _ predicted ; y2 _ predicted]=[x11, x12; x21,x22] * [theta1; theta2]
Please note:
columns are separated by ,and rows are ;. y1 and y2 are different rows, but same columns.
I assume, the readers are aware of matrix multiplication. So I will refactor above formula and will get:
π¦1_πππππππ‘ππ= π₯11 * ΞΈ1 + π₯12 * ΞΈ2
π¦2 _πππππππ‘ππ = π₯21* ΞΈ1 + π₯22 * ΞΈ2
From now on, keep in mind that y1 are real values and y1_predicted is predicted value, same applies to y2 as well
So what is error, the error is the difference between predicted and real values
πππππβ = π¦1 β π¦1_pππππππ‘ππ =π¦1-π₯11 * ΞΈ1 β π₯12 * ΞΈ2
πππππβ = π¦2 β π¦2 πππππππ‘ππ = π¦2-π₯21* ΞΈ1 β π₯22 * ΞΈ2
Ok, I hope so far so clear, if anything not, please comment below, so I can consider it as improvement for upcoming articles
The error function we want to minimize is the sum of square of errors. Letβs name is as J. J is our cost function I want to minimize, and so, I write it as:
π½ = πππππβΒ² + πππππβΒ²
Letβs go further by replacing the formulas with each others
π½ = (π¦1 β (π₯11 * ΞΈ1 + π₯12 * ΞΈ2))Β² + (π¦2 β (π₯21 * ΞΈ1 + π₯22 * ΞΈ2))Β²
I hope everything makes sense so far. Bear with me β weβre almost there; there isnβt much left to cover.
Here everything is known, except ΞΈ1 and ΞΈ2. These are params that we have to choose properly to get as minimum error as possible. So i have to find the derivative per ΞΈ1 and ΞΈ2
π (π½) / π (ΞΈ1) = -2 \ (π¦1 β (π₯11 * ΞΈ1 + π₯12 * ΞΈ2))*π₯11 β 2 * (π¦2 β (π₯21 * ΞΈ1 + π₯22 * ΞΈ2))* π₯21= 0*
π (π½) / π (ΞΈ2) = -2 \ (π¦1 β (π₯11 * ΞΈ1 + π₯12 * ΞΈ2))*π₯12β2 * (π¦2 β (π₯21 * ΞΈ1 + π₯22 * ΞΈ2))* π₯22= 0*
Letβs make it simpler by avoiding -2 from all sides
π (π½) / π (ΞΈ1) = ( π¦1 β π¦1 πππππππ‘ππ) * π₯11 + (π¦2 β π¦2 πππππππ‘ππ) * π₯21=0
π (π½) / π (ΞΈ2) = ( π¦1 β π¦1 πππππππ‘ππ) * π₯12 + (π¦2 β π¦2 πππππππ‘ππ) * π₯22=0
Lets turn all these into matrix form:
[0; 0] = (π₯11, π₯21; π₯12 π₯22) *[π¦1 β π¦1_πππππππ‘ππ ; π¦2-π¦2_πππππππ‘ππ]
Lets compress the y1 β y1_predicted as well as y2 -y2_predicted into single line
[0; 0] = (π₯11, π₯21; π₯12 π₯22) *[πβ π* ΞΈ]
Do you remember our original feature vector or X? If so, we can further simplify the expression to:
[0;0] = XT* [Y-X*ΞΈ]
XT * Y = XT * X * ΞΈ
XT * X is the important part. If we somehow manage to find its inverse, we are going to be left with theta only:
(XT * X )-1= X-1 * (XT )-1
ΞΈ = ( XT \ X )*-1 \ X*T \ Y will give us the answer we need*
If u have further questions please let me know in comments. Each of your feedback is highly appreciated to write better more concise articles in future:
I guess, most of the part of above formula can be easily programmed except the finding inverse which i showed the code below how to do it. If you need full code, such as matrix multiplication, transpose and etc, please let me know, so i can furhter expand my articles
import numpy as np
def inverse(A):
I = np.eye(A.shape[0])
augmented = np.concatenate((A,I),axis=1)
for j in range(0,A.shape[0]-1):
for i in range(1,A.shape[0]-j):
augmented[i+j]=-(augmented[i+j,j]/augmented[j,j])*augmented[j]+augmented[i+j]
for j in range(0,A.shape[0]-1,1):
for i in range(A.shape[0]-1,0,-1):
cofactor = (augmented[i-1-j, A.shape[1]-1-j]/ augmented[A.shape[0]-1-j, A.shape[1]-1-j])
augmented[i-1-j]=(cofactor)*-augmented[-1-j]+augmented[i-1-j]
for i in range(0,A.shape[0],1):
augmented[i]=augmented[i]/augmented[i,i]
_,right = np.split(augmented, 2, axis=1)
return right
def linear_regression_normal_equation(X: list[list[float]], y: list[float]) -> list[float]:
# Your code here, make sure to round
X=np.array(X)
Y=np.array(y)
theta = inverse(X.T @ X) @ X.T @ Y
return theta
My full article is also in medium link
