ML-Linear Regression

Normal Equation, a way other than gradient descent-Andrew Ng

Intuition

In normal equation, unlike gradient descent which iterates to reduce the cost gradually, we set the derivative of the cost function to 0.

Gradient descent must iterate many times in order to converge to a local minima. However, we can compute the parameters analytically, and it’s called the “Normal Equation”. Using the normal equation, we don’t have to iterate many times, it gives us the desired parameters at one calculation. The formula is as follows:

Before we move on to the derivation or this formula, we must know the differences between gradient descent and this normal equation method.

Since normal equation works very slow if the data size gets bigger, it is recommended only when the data size n ≤ 10,000.

Normal Equation Derivation

Firstly, we have the hypothesis function:

and we also have the cost function we’d like to minimize:

Here, we are using the matrix notation, so the parameters theta that we want can be represented as this:

we add a feature x0 = 1, just for the convenience of calculation(Adding this, we can write it as a matrix multiplication). By doing that, we can now write our hypothesis function like this:

Now we can apply this to our cost function:

*additional explanation to cost function

We can throw away the 1/2m part and simplify it a bit:

The specific calculations are as follows:

So we get this:

and this:

And we finally get the first formula,

Normal Equation Non-invertibility

The pinv() function of Octave, which returns the inverse matrix, does not stop even if the given matrix in not invertible. In this case, the parameters cannot be learned. This happens when the X matrix is singular or degenerate.

Get Jaehoon Jang’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

There are two reasons for this problem.

1. Linearly dependent features

It happens when features in the X matrix are linearly independent say, the same content with just different measurements(e.g. feet, meter). You can erase one of those features to get it right

2. Too many features

It happens when the number of features is relatively large to the size of the dataset. In this case erase some features or use regularization.