Medium End-to-End

Polynomial Regression

A polynomial model predicts an output by adding weighted powers of its input. For example, weights [2, -3, 1] describe 2 - 3*x + x**2. The coefficients are supplied in this exercise: compute predictions and their mean squared error without fitting or updating the weights.

Your task

Implement polynomial_regression(x, w, y) for floating-point inputs:

x has shape (N,), with N >= 1.
w has shape (d + 1,), with at least one coefficient.
y contains targets of shape (N,).

Infer d from the length of w; there is no separate degree argument. Coefficients are ordered by increasing power: w[0] is the constant term, w[1] multiplies x, and w[d] multiplies x**d.

Build a feature matrix phi of shape (N, d + 1). Row i is [1, x[i], x[i]**2, ..., x[i]**d]. Its first column is always one, including when x[i] is zero. Then compute:

prediction = phi @ w
loss = mean((prediction - y)**2)

Return a dictionary with "prediction" of shape (N,) and "loss" as a scalar number. Average over all N examples, with no square root or one-half factor. Preserve the inputs.

Example

For x = [-1, 0, 2] and w = [2, -3, 1], predictions are [6, 2, 0]. With targets [5, 4, 0], squared errors are [1, 4, 0], so the loss is 5/3.

The constant term already acts as an intercept; do not add another bias. If w contains only one value, every prediction is that value. Although powers allow a curved relationship with x, the prediction remains linear in the coefficients: each coefficient multiplies one fixed feature.

Understand the ideas behind this exercise. The Problem tab contains the exact implementation requirements.

Predict a numerical value

Regression predicts a number, such as a price or a temperature. A linear model combines the input features using weights and a bias:

$$\hat y=Xw+b.$$

Mean squared error (MSE) averages the squared differences between predictions and targets. For N examples with one target each,

$$L=\frac{1}{N}\sum_i(\hat y_i-y_i)^2.$$

Squaring makes larger errors count more. An error of 4 contributes 16 to the sum, while an error of 2 contributes 4.

The gradient with respect to each prediction is 2 * (prediction - target) / N. For several outputs per example, check whether the loss averages over examples only or over all output elements. The denominator, and therefore the gradient, will differ.

More features can represent curves

Polynomial regression uses features such as [1, x, x²]. The predicted curve can be nonlinear in x while remaining linear in its learned coefficients. Large powers can create very different feature scales, making the fitting problem more sensitive to numerical error and learning-rate choices.

Regularization discourages large weights

Adding the penalty lambda * sum(w²) adds 2 * lambda * w to the weight gradient. Some definitions include a factor of one half, so follow the stated loss rather than assuming a convention.

This penalty is used in ridge regression. It can make fitting more stable when features are strongly correlated, but feature scaling still matters: rescaling a feature changes the coefficient needed to represent the same prediction.

Why squared error favors the mean

For targets [1, 3], predicting 2 for both gives squared errors [1, 1] and MSE 1. Predicting 1 for both gives errors [0, 4] and MSE 2. The mean minimizes squared error for a constant prediction. More generally, when the relevant expectations exist, the best prediction under expected squared loss is the target's conditional mean given the input.

Large outliers can strongly affect this mean and the fitted model. Evaluate on held-out data to check whether a low training loss carries over to new examples.

Detecting runtime…