Polynomial Features and Overfitting

A straight line can't fit a curve, but linear regression on polynomial features can. For one input column $x$, degree $d$ gives the columns $[1, x, x^2, \dots, x^d]$.

Implement:

• poly_features(x, degree): shape (n, degree + 1), starting with the column of ones.
• fit_poly(x, y, degree): least-squares coefficients via np.linalg.lstsq on those features.
• predict_poly(x, coef).
• train_test_mse(x_train, y_train, x_test, y_test, degree): returns (train_mse, test_mse), so you can watch overfitting happen as the degree grows.