Fit a linear model by least squares
Medium14 min10 hidden tests
A delivery team predicts how many minutes a route takes from its distance in km and its number of stops. They want a linear model, minutes = b + w1 * km + w2 * stops, with the weights that make the squared errors on past routes as small as possible. Write fit_least_squares(X, y) that returns the intercept b followed by one weight per feature.
Set the weights, or solve
minutes = b + w1 · km + w2 · stopsminutes = 0 + 4 × km + 2 × stops. Squared errors: 25 + 64 + 1 + 64 + 16 = 170. Solving the normal equations, AᵀA θ = Aᵀy, gives the weights with the smallest sum.
Sum of squared errors 170.
Examples
These routes follow 4 minutes plus 3 per km plus 5 per stop exactly
fit_least_squares([[2, 1], [5, 3], [3, 0], [8, 4], [6, 2]], [15, 34, 13, 48, 32])
returns [4, 3, 5]
No line passes through all three points, so the fit is the one with the smallest squared error
fit_least_squares([[0], [1], [2]], [1, 2, 6])
returns [0.5, 2.5]
Requirements
Xis a 2-D list or array of shape (n, d), andyis a list or 1-D array of n targets. The columns of X plus a column of ones are linearly independent, so the answer is unique.- Return a 1-D float array of length d + 1: the intercept first, then the d weights in column order.
- The coefficients minimize the sum of squared errors, the sum of (y_i - b - X_i . w)^2.
- Leave
Xandyunchanged.
The idea behind it
Linear regression predicts y as b + w_1 x_1 + ... + w_d x_d. Least squares picks the coefficients that make the sum of squared errors on the training rows as small as possible.
Writing the intercept as a weight on a constant feature turns the whole model into one matrix product. Put a column of ones in front of X to get A, and the predictions are A @ c with c = [b, w_1, ..., w_d]. The best c solves the normal equations, A^T A c = A^T y.
Solving them with an explicit inverse works on small, clean data but loses accuracy when features are nearly collinear (almost copies of each other). np.linalg.lstsq uses a more stable method based on the singular value decomposition, and it is what you should reach for in practice.
Fitting each feature on its own gives the same answer only when features are uncorrelated. Real features rarely are: longer routes usually have more stops, so the joint fit has to split the credit between them.