Normal equation and non-invertibility

Normal equation:Capture

  • What if XTX is non-invertible(singular/degenerate)
  • R: ginv(X’*X)*X’y from {MASS}
  • Octave: pinv(X’*X)*X’y

The issue of XTbeing non-invertible should happen pretty rarely.  R and also Octave, have different functions for inverting matrices:

  • R:
    • solve() from {base}
    • ginv() from {MASS} – Generalized Inverse of a Matrix (computes the value of θ that you want even if XTX is non-invertible)
  • Octave:
    • inv() – inverse
    • pinv() – pseudoinverse (computes the value of θ that you want even if XTX is non-invertible)

Most common causes for the non-invertibility of  XTX :

  • Redundant features (linearly dependent).
    • E.g. x1 = size in feet2
               x2= size in m2

Concretely, let’s say we want to predict housing prices. If xis the size of the house in square feet and xis the size of the house in square meters, then you will have a linear dependence between these two features, because 1m = 3.28 feet, they will always satisfy the constraint:
                               x= (3.28)2x2

If we will remove one of these features, the non-invertibility problem should be solved.

  • Too many features (e.g. m ≤ n, so if we are trying to run the learning algorithm having more features then observations in the training set).

For example, let’s imagine we have m = 10 training examples and n = 100 features, then we are trying to fit a parameter back to θ which is n+1 dimensional. So, we would be trying to fit 101 parameters from just 10 training observations, which obviously is not a good idea.

If this would be the situation, a proper solution would be to delete some features or use regularization.

 

Advertisements
Tagged with: , , , , , , , ,
Posted in Coursera

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: