Demonstrate under- vs over-fitting: fit polynomials of degree 1, 3, and 9 (least squares) to noisy training points and compare TRAIN error to TEST error. Pure Python, deterministic.

Answer

# True pattern is roughly quadratic; train points carry small fixed noise. train_x = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] train_y = [0.0, 1.2, 3.8, 9.1, 15.8, 25.2, 35.9, 49.1, 63.8, 81.2] test_x = [0.5, 2.5, 4.5, 6.5, 8.5] test_y = [0.25, 6.25, 20.25, 42.25, 72.25] def fit_poly(xs, ys, degree): # Solve the least-squares normal equations by Gaussian elimination. n = degree + 1 A = [[sum(x ** (i + j) for x in xs) for j in range(n)] for i in range(n)] b = [sum(ys[k] * (xs[k] ** i) for k in range(len(xs))) for i in range(n)] for col in range(n): piv = max(range(col, n), key=lambda r: abs(A[r][col])) A[col], A[piv] = A[piv], A[col] b[col], b[piv] = b[piv], b[col] for r in range(n): if r != col and A[col][col] != 0: f = A[r][col] / A[col][col] A[r] = [A[r][j] - f * A[col][j] for j in range(n)] b[r] -= f * b[col] return [b[i] / A[i][i] for i in range(n)] def evaluate(coeffs, x): return sum(c * (x ** i) for i, c in enumerate(coeffs)) def mse(coeffs, xs, ys): return sum((evaluate(coeffs, x) - y) ** 2 for x, y in zip(xs, ys)) / len(xs) for d in (1, 3, 9): c = fit_poly(train_x, train_y, d) tr = mse(c, train_x, train_y) te = mse(c, test_x, test_y) print(f"deg{d}: train={tr:5.2f} test={te:6.2f}") print("underfit: deg1 high train+test | good: deg3 | overfit: deg9 ~0 train, large test")