How Much Bend Is Enough?

Polynomial regression bends a straight line by giving it extra columns. From a single input $x$ it builds the row

and fits an ordinary linear model on those columns:

The degree $d$ is the dial from Polynomial Regression. Set it too low and the curve misses the bend; set it too high and the curve chases the noise. To tell which is happening, fit on training points, then measure the error on points the fit never saw.

Fitting. In Linear Regression the coefficients came from gradient descent, which creeps toward the best fit without ever landing exactly on it. The tests here expect the exact best fit, so jump straight to it with the normal equations from Linear Algebra. Put the expanded training rows into a table $X$, with one row per training point and $d + 1$ columns, and put the training answers into $y$. The coefficients $b = (b_0, \dots, b_d)$ that give the smallest possible mean squared error on the training points solve

You never need $X$ itself. Each entry is a plain sum over the training points $(x, y)$, with $i$ and $j$ running from $0$ to $d$:

That is $d + 1$ linear equations in $d + 1$ unknowns. Solve them either way:

• With numpy (already imported in the starter): build A and c as arrays, and np.linalg.solve(A, c) returns $b_0, \dots, b_d$ in that order. Turn your two final answers into plain floats with float(...).
• By elimination, as in Solving by Elimination: for each column in turn, subtract the right multiple of that column's row from every row below it, until every entry under the diagonal is 0. The last equation then has one unknown. Solve it, and work back up, one new unknown per row. Because the training set has at least $d + 1$ different $x$ values, the diagonal number you divide by is never 0, so no row swaps are needed.

Task: write degree_check(train, test, degree).

• train and test are lists of (x, y) pairs.
• Fit the coefficients on train only, for the given degree. A degree of $0$ means the constant column alone.
• Return a tuple (train_mse, test_mse): the mean squared error of that one fitted curve on the training points and on the test points. Round each to 4 decimal places and return them as plain Python floats.