Machine Learning - 2.2 - Normal Equation
Week 2, part 2 of professor Andrew Ng’s Machine Learning course. In this post we’ll look at an alternative to the Gradient Descent algorithm along with its pros and cons.
See the other posts at Machine Learning Course Structure
1. Normal Equation
Purely mathematically, for a hypothesis function we can find its minimum value by taking the derivative and finding x where the derivative = 0.
1.1. The formula
Applying the matrix-by-vector multiplication introduced in the previous post, we get this formula:
$latex \theta = (X^TX)^{-1}X^Ty$
1.2. Comparison
Gradient Descent
Normal Equation
Needs you to pick alpha
No need to pick alpha
Needs many iterations
Computed in one shot
Complexity $latex O (kn^2)$
Complexity $latex O (n^3)$, needs the inverse of $latex X^TX$
Still runs fine for large n
Slow if n is too large
In short, if the number of features is too large you should use the Gradient Descent algorithm to get a result quickly.
1.3. Non-invertibility
In some rare cases the result of $latex X^TX$ is noninvertible.
This happens for these reasons: + There are redundant features. For example 2 features very tightly related to each other (one feature depending linearly on the other, say). + There are too many features (m <= n).
To solve this problem we can delete some of the redundant features (like x1 being the area in square meters and x2 the area in square miles), or use the regularization methods covered in later parts.