Handson-ml: chapter 4: Computational Complexity --"n is the number of features"?

[Jerryd99]

in chapter 4: Computational Complexity, page 110, said
"The Normal Equation computes the inverse of XT ·X, which is an n × n matrix (where n is the number of features)."

but i think X is a m*n matrix ( n is the number of features, and m is the size of training dataset),
Which one is true?

Thanks for the wonderful book!

[vd1]

X is an m * n matrix
XT is an n * m matrix
XT X is an n * n matrix

On 23 February 2018 at 08:37, JerryDai [e-mail] wrote:

in chapter 4: Computational Complexity, page 110, said
"The Normal Equation computes the inverse of XT ·X, which is an n × n
matrix (where n is the number of features)."

but i think X is a m*n matrix ( n is the number of features, and m is the
size of training dataset),
Which one is true?

Thanks for the wonderful book!

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
https://github.com/ageron/handson-ml/issues/184, or mute the thread
https://github.com/notifications/unsubscribe-auth/AAcCLtJhqlPM4x8kaXnP40IcbagKxwXBks5tXmqegaJpZM4SQffs
.

[ageron]

Hi @Jerryd99 ,

@vd1 is quite right (thanks Vincent).

By the way, I made a mistake in the book, which I am currently fixing: the LinearRegression class does not actually use the Normal Equation, it computes the pseudoinverse of X (specifically the Moore-Penrose pseudoinverse), and it multiplies it by y. It gives the same result as the normal equation, but it has two important advantages:

1. It is O(n^2) instead of O(n^2.4) to O(n^3). So it's much faster than the Normal Equation when there are many features.
2. It behaves better when some of the eigenvalues of X are small (or equal to zero). In plain English, this is when some features are highly correlated (or perfectly correlated, that is when one feature is a linear combination of the others). It also behaves well when m < n. More details below.

When some features are linear combinations of the others, or when m < n, the matrix X^T X is not invertible (it is said to be "singular" or "degenerate"). So the Normal Equation cannot be used. However, the pseudoinverse is always defined: it is based on the SVD decomposition of the matrix X, which finds the eigenvalues and eigenvectors of the matrix (as explained in chapter 8 on dimensionality reduction, when talking about PCA), so it can simply ignore the eigenvalues that are smaller than a tiny threshold. This means that the LinearRegression class will find the optimal solution even when some features are redundant or when m < n.
This also explains two parameters that the LinearRegression predictor learns during training:

• rank_ is the rank of the matrix X, i.e., the number of eigenvalues that are not tiny or zero.
• singular_ is the list of eigenvalues (just like PCA().fit(X).singular_values_). If a feature is a linear combination of other features, then one of these features will have a tiny or zero eigenvalue.

Fortunately, this error does not change much of what I wrote in the book about the LinearRegression class: it is based on an analytical solution, it performs poorly when there is a large number of features, it is linear with regards to the number of instances, it does not support out-of-core (i.e., all data must fit in memory to use it), it does not require feature scaling, the order of the instances in the training set does not matter, and so on. You could say it's an implementation detail, but it's quite an important one, and I apologize for the error.

Hope this helps,
Aurélien