Skip to content
Tutorials Center
My learning

Topics

Lesson 56 of 62 ยท Projects

Project: Linear Regression from Scratch

Fit linear regression four ways with NumPy: normal equations, QR, SVD and lstsq. See why conditioning matters, then tame collinear features with ridge regression.

Linear regression is least squares with a name tag: find the weights w that make X @ w as close as possible to the targets y. You met the idea in least squares. This project goes one level deeper and asks the question that separates a textbook from a library: how should the weights actually be computed?

There are at least three decent answers, the normal equations, QR and SVD. On easy data they all agree to many digits. On hard data, one of them quietly falls apart. You will fit all three, build a deliberately nasty problem to watch it happen, and then fix a second kind of trouble (nearly duplicated features) with ridge regression, which falls out of the SVD in two lines.

Three roads to the same weights

Normal equations Solve X.T X w = X.T y. Fast, but squares the conditioning.
QR Factor X = QR, then back-substitute. Stable and common.
SVD Most robust. Exposes every direction's strength.

lstsq in NumPy uses an SVD-based method.

1 / 2

Step 1: the design matrix

Linear regression is linear in the weights, not necessarily in the inputs. To fit a curve y = w0 + w1 x + w2 x^2, we build a design matrix whose columns are the features 1, x and x^2. Each row is one observation; each column is one thing the model can weigh. The model is still just X @ w.

We invent noisy data from the curve 2 + 0.5 x - 0.08 x^2, so we know the weights we hope to recover.

Python Design matrix and the normal equations

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The fitted weights are close to the truth but not identical, which is expected: 60 noisy points cannot pin down three numbers exactly. The RMSE is close to the 0.4 noise level we put in, so the curve explains everything that is explainable.

Step 2: three solvers, one answer

The normal equations come from setting the gradient of the squared error to zero. Two alternatives avoid forming X.T @ X:

  • QR: factor X = Q R, where Q has orthonormal columns and R is upper triangular (Gram-Schmidt and QR). The equations collapse to R w = Q.T @ y, solved by back-substitution.
  • SVD: factor X = U S V.T (SVD). The solution is w = V @ ((U.T @ y) / s), which divides each component by its singular value. This is the pseudoinverse at work, and np.linalg.lstsq uses an SVD-based routine.
Python Four solvers compared

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All four rows print the same weights. The last three lines show the catch of the normal equations: the condition number of X.T @ X is the square of the condition number of X (about 139 versus 19,000 here). Condition number measures how much errors in the input can grow in the output, and floating point arithmetic starts at a relative error near 1e-16. A matrix with condition number 1e8 squares to 1e16, and then every digit is lost.

Step 3: a problem where the normal equations fail

Polynomials of high degree are the classic stress test: the columns 1, x, x^2, ..., x^d look more and more alike on [0, 1], so the design matrix becomes nearly rank-deficient. We fit sin(2*pi*x) with polynomials of growing degree and measure how well each solver's weights reproduce the targets.

Python Stress test: polynomial degree versus solver

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Up to degree 9 all three solvers give the same residual. At degree 12 the normal equations are already behind (about 5e-7 against 4e-7 for QR and SVD), and at degree 15 the gap is huge: roughly 1e-6 versus 4e-11. The condition number of X.T @ X there is around 1e18 (the exact digits vary with the linear algebra library), beyond what double precision can handle, so the solve returns mostly noise. QR and SVD work with X itself, so they only face 1e11.

This fit is a numerical demo, not a modelling recommendation: a degree-15 polynomial through 40 points is a bad model for other reasons (it would swing wildly between data points). In practice you would use an orthogonal polynomial basis, a spline or regularization. Here the point is numerical: the same data gives different answers depending on the algorithm.

Step 4: collinear features and ridge regression

A different kind of trouble arises when two features carry almost the same information, such as a temperature in Celsius and the same temperature in Fahrenheit plus noise. The model cannot tell them apart, so it can give one a huge positive weight and the other a huge negative weight, and the sum stays almost the same. The weights are meaningless and change wildly from one sample to the next.

Ridge regression adds a penalty lambda * |w|^2 to the squared error. The solution is a small modification of the normal equations:

TEXT
w = (X.T @ X + lambda * I)^-1 @ X.T @ y

Adding lambda * I lifts every eigenvalue of X.T @ X by lambda, so the matrix is always invertible and well behaved. In SVD terms, plain least squares divides by every singular value s, which explodes when s is tiny. Ridge replaces 1/s by s / (s^2 + lambda), which is harmless for big s and tends to 0 for tiny s: it quietly switches off the unstable directions.

Python Ridge regression tames collinear features

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Plain least squares returns weights such as [-22, 25], [-9.2, 12.1] and [-2.6, 5.7]: enormous, opposite in sign and different for each noise draw, yet each pair adds up to roughly the true 3. Ridge gives [1.5, 1.5] every time. The two columns share the job equally, which is the sensible answer for two copies of one signal. The SVD view shows one singular value near 7 and the other near 0.005; with lambda = 0 the second direction is divided by 0.005 and amplified (the weights have length 33), and with lambda = 1 it is suppressed (length 2.1).

In practice standardize your features first, so one lambda treats all columns fairly, and do not penalize the intercept (center y and the features, or leave the first column of ones out of the penalty). Choose lambda by validation error, as in the recommender project.

Which solver should you use?

Situation Use
Quick, well-conditioned problems np.linalg.lstsq
Many rows, few columns, speed matters QR (np.linalg.qr)
Suspected rank deficiency or tiny singular values SVD or lstsq with a tolerance
Collinear features Ridge, via solve(X.T @ X + lam * I, ...) or the SVD formula
Teaching and small clean problems Normal equations

The normal equations are not wrong; they are the fastest option on healthy data and the easiest to explain. Just know when to leave them.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. If cond(X) is 1e8, roughly what is cond(X.T @ X)?

    Forming X.T @ X squares the condition number. At 1e16 a double has no correct digits left, which is why QR or SVD is preferred on such problems.
  2. 2. Which statement about the design matrix X for y = w0 + w1 x + w2 x^2 is true?

    Least squares only needs the model to be linear in the weights. Curves are fitted by putting functions of x into the columns.
  3. 3. In the SVD solution w = V @ ((U.T @ y) / s), what causes instability?

    Orthogonal matrices preserve lengths, so they are harmless. A tiny singular value amplifies noise in its direction by 1/s.
  4. 4. What does ridge regression do to the filter factor 1/s?

    For large s the new factor is almost 1/s, so strong directions are barely changed. For tiny s it goes to zero instead of exploding.
  5. 5. Two nearly identical features get plain least-squares weights of -22 and +25. What is the most likely explanation?

    When two columns are almost equal, only their sum is well determined. The individual weights can be huge and opposite without hurting the fit, so noise decides them.

Summary

  • A design matrix turns curve fitting into X @ w; the model only has to be linear in the weights.
  • The normal equations, QR and SVD all solve least squares; the normal equations square the condition number and can lose every digit on hard problems.
  • np.linalg.lstsq (SVD based) and QR work on X directly and survive polynomial-style ill-conditioning.
  • Collinear columns make weights huge and unstable; ridge adds lambda * I, or equivalently filters singular values with s / (s^2 + lambda).
  • Standardize features, leave the intercept unpenalized, and pick lambda on held-out data.

Next: practice what you have learned in Practice: Vectors and Matrices.