Problem 651197 · medium · Level 06 Heuristics & Optimization

Mileage or Age?

multiple regression · normal equations · Gaussian elimination · matrix inverse · standard error · confounding

A used-car dealer wants to know how much each thousand kilometres on the clock lowers a car's price. Older cars tend to have more kilometres, so the dealer fits a regression with several inputs,

price ≈ b0 + b1 * x1 + b2 * x2 + ... + bk * xk,

choosing the coefficients that minimise the sum of squared residuals, and wants to know how precisely each coefficient is determined.

Write regression_table(rows, prices). rows[i] is the list of the k inputs of car i (no leading 1: add the intercept yourself). Return a list of k + 1 tuples (coefficient, standard_error), the intercept first. With X the table whose rows are [1] + rows[i], n cars and p = k + 1 coefficients:

  • the coefficients solve the linear system (XᵀX) b = Xᵀy;
  • s² = RSS / (n - p), where RSS is the sum of squared residuals;
  • the standard error of coefficient j is sqrt(s² * C[j][j]), where C is the inverse of the matrix XᵀX.

Solve and invert with your own code (no libraries). The setup provides car_sales(n, seed), which returns (rows, prices) for n simulated cars with inputs [km in thousands, age in years, previous owners, engine size in litres] and prices in hundreds of pounds.

Examples

Input:  rows = [[20, 1], [45, 2], [60, 5], [80, 4], [110, 8], [130, 7], [150, 10]]
        prices = [182, 160, 131, 128, 92, 95, 60]
Output: [(193.22036882179478, 3.1757416927301407), (-0.3630650059416396, 0.1063146521280083),
         (-7.7978081950618385, 1.5423796631816244)]
Explanation: among cars of the same age, each 1000 km lowers the price by about 36
(hundred pounds per thousand km: £36); each year of age, at equal mileage, by about 780.

Input:  the same cars with only the mileage: rows = [[20], [45], [60], [80], [110], [130], [150]]
Output: [(195.446227929374, 7.647139478597603), (-0.8741573033707866, 0.08002260097601964)]
Explanation: on its own, mileage also carries the effect of age, so its slope more than doubles.

Constraints

  • 1 <= k <= 8, k + 2 <= n <= 5000
  • the inputs are linearly independent (the columns of X are not redundant)
  • floats are compared with a tolerance of 1e-6

Goals

  • Fit a regression with several inputs by solving the normal equations
  • Write Gaussian elimination by hand and use it to invert a matrix
  • Attach a standard error to every coefficient and read a coefficient as 'with the other inputs held fixed'
Starting Python…