📘

Polynomial Regression Error

MediumOptimization 📚 CV: Model Fitting and Optimization

Implement a polynomial regression error calculator to evaluate the goodness of fit for a given polynomial model. The task involves computing the mean squared error between observed data points and predicted values based on the polynomial coefficients.

The concept of polynomial regression is a form of least squares optimization, where a polynomial function of degree $n$ is fitted to a set of data points $(x_i, y_i)$ . The polynomial function can be represented as $p(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n$ , where $a_i$ are the coefficients of the polynomial. The goal is to find the best fit polynomial that minimizes the difference between observed and predicted values.

To compute the error, follow these steps:

Evaluate the polynomial at each data point $x_i$ using the given coefficients.
Compute the squared difference between the observed value $y_i$ and the predicted value $p(x_i)$ .
Average the squared differences over all data points.

MSE = \frac{1}{n}\sum_i (y_i - p(x_i))^2

This technique is widely used in data analysis and machine learning for model evaluation and optimization.

Example:

Input:

poly_mse([0, 1], [(0,0), (1,1), (2,2)])

Output:

0.0

Reasoning:

The coefficients [0, 1] define the polynomial $p(x) = 0 + 1x = x$ .
Evaluate $p(x)$ $p (x)$ at each $x_i$ $x_{i}$ :
- $x=0 \Rightarrow p(0)=0$
- $x=1 \Rightarrow p(1)=1$
- $x=2 \Rightarrow p(2)=2$
Compare to the given points $(x_i, y_i)$ : predicted $p(x_i)$ equals actual $y_i$ for all three points, so each error $(y_i - p(x_i))$ is $0$ and each squared error is $0$ .
Compute MSE: $\text{MSE} = \frac{1}{3}(0^2 + 0^2 + 0^2) = 0.0$ .

Constraints:

Return MSE rounded to 4 decimal places

More from CV: Model Fitting and Optimization

RANSAC Homography EstimationMedium RANSAC Line FittingMedium RANSAC Line FitHard Line from Two PointsEasy Count InliersEasy

You’re given a polynomial’s coefficients, some data points $(x_i, y_i)$ , and asked to compute the mean squared error (MSE) between the polynomial’s predictions and the observed targets.

1. Background Knowledge

In polynomial regression, we model the relationship between an input $x$ and an output $y$ using a polynomial

p(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_k x^k,

where the $a_j$ values are the coefficients of the polynomial. The polynomial is often found by least squares, which chooses coefficients that minimize the sum of squared differences between predictions $p(x_i)$ and true values $y_i$ .

The mean squared error (MSE) measures how well the model fits the data:

\text{MSE} = \frac{1}{n} \sum_{i=1}^{n} \left( y_i - p(x_i) \right)^2.

It is the average squared residual, where each residual is $y_i -$ \hat{y} $_i$ and $\hat{y}_i = p(x_i)$ . A smaller MSE indicates that predictions are closer to the true values in a least-squares sense.

In this problem, the coefficients are already given; you are not doing the fitting. Your job is purely to evaluate the polynomial at each input and then compute the MSE between those predictions and the given targets.

2. Algorithm / General Approach

The general pattern:

For each data point $x_i$ , compute the polynomial value $p(x_i)$ using the coefficient list.
Compute the squared error $(y_i - p(x_i))^2$ for that point.
Accumulate (sum) these squared errors over all points.
Divide the total by $n$ (the number of points) to get the MSE.

The main subroutine you need is: evaluate a polynomial given coefficients and an input value.

3. Step-by-Step Strategy

Assume:

coeffs = [a0, a1, a2,..., aK]
xs = list/array of inputs [x0, x1,..., x_{n-1}]
ys = list/array of targets [y0, y1,..., y_{n-1}]

A. Polynomial evaluation

Naive method (direct formula):

def poly_value(coeffs, x):
 value = 0.0
 # coeffs[j] corresponds to a_j
 for power, a in enumerate(coeffs):
 value += a * (x ** power)
 return value

More numerically stable and efficient is Horner’s method:

def poly_value(coeffs, x):
 value = 0.0
 # iterate from highest degree down to constant term
 for a in reversed(coeffs):
 value = value * x + a
 return value

B. MSE computation

def mse(coeffs, xs, ys):
 n = len(xs)
 total_sq_error = 0.0
 for x, y in zip(xs, ys):
 y_pred = poly_value(coeffs, x)
 diff = y - y_pred
 total_sq_error += diff * diff
 return total_sq_error / n

Conceptually:

Initialize total_sq_error = 0.
Loop over all points:

Compute y_pred = p(x_i).
Compute error e = y_i - y_pred.
Add e**2 to total_sq_error.

Return total_sq_error / n.

4. Common Pitfalls

Incorrect power indexing: Ensure coeffs[j] multiplies $x^j$ , not $x^{j+1}$ or similar off-by-one errors.
Integer division: In some languages, sum / n may perform integer division if both are integers. Force floating-point division.
Numerical overflow: If degrees are high and $x$ is large, x**power can overflow or lose precision. Horner’s method reduces this risk.
Empty or mismatched input lengths: Ensure xs and ys have the same non-zero length; otherwise MSE is undefined.
Using RMSE instead of MSE: The problem asks for MSE, so do not take the square root.

5. Time & Space Complexity

Let:

$n$ = number of data points
$k$ = degree of the polynomial (number of coefficients is $k+1$ )
Per evaluation:
Naive polynomial evaluation: $O(k)$ (loop over all coefficients).
Horner’s method: also $O(k)$ .
Total MSE computation:
You evaluate the polynomial for each of the $n$ points: $O(nk)$ time.
Space: $O(1)$ extra space (just a few scalar variables), assuming input arrays are given and reused.

This pattern—loop over data, compute model prediction, aggregate a scalar loss—is a standard template for evaluating regression errors.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.