Least Squares
The polynomial is nonlinear as a function of the original input x, but it is linear in its coefficients. That distinction is what allows linear regression and least squares to be used after the input transformation.
Try it: Least-Squares Line
How least squares fits a line: the slope and intercept that minimise the mean squared error come from solving the normal equations, and no hand-drawn line can do better.
How it works
- Each point's residual is y − ŷ, the vertical gap to the line; its square is the squared error.
- Add up n, Σx, Σy, Σx² and Σxy.
- Write the normal equations (XᵀX)w = Xᵀy for w = (slope a, intercept b) and solve the 2×2 system.
- Measure every residual of the fitted line and average the squares (MSE).
- Compare with your own line: its MSE is always at least the least-squares MSE.
Default run (13 steps): 8 points (x, y). Your line ŷ = 0.2x + 4 has mean squared error 1.78. Least squares finds the line with the smallest possible MSE. … MSE = 1.744 / 8 = 0.218. Your line: 1.78 — 1.562 worse. No other line can beat least squares on this data.
Simplified: One input feature and at most 12 points; the 2×2 system is solved in closed form. If every x is equal the system is singular and the lab stops.
Loading the simulation…
Beyond Straight Lines
A straight-line predictor is useful when the relationship in the training data can be described linearly. Some learning tasks require a predictor that can respond to powers of the input instead. Polynomial regression provides that extra flexibility. The important idea is that changing the predictor to a polynomial does not require abandoning linear regression methods: the input can first be transformed, and least squares can then learn the polynomial coefficients.
A degree-n polynomial predictor uses the input powers from 1 through xⁿ and has n + 1 coefficients. The constant term accounts for the first coefficient, so the complete feature representation contains 1, x, x², through xⁿ.
The polynomial is nonlinear as a function of the original input x, but it is linear in its coefficients. That distinction is what allows linear regression and least squares to be used after the input transformation.
Building Polynomial Features
For a scalar input x, construct the transformed feature vector ψ(x) = (1, x, x², ..., xⁿ). Each position records one polynomial degree: the first position is the constant feature, the next is the first power of x, and the final position is the nth power. A coefficient vector w can then combine these transformed features to produce the polynomial prediction.
A Degree-2 Transformation
Construct the polynomial feature vector for a scalar input x using a degree-2 model.
- 1Identify the degrees
A degree-2 polynomial uses degree 0, degree 1, and degree 2 features.
- 2Write each feature
The corresponding features are 1, x, and x².
- 3Assemble the vector
Place the features in degree order to obtain ψ(x) = (1, x, x²).
The transformed input is ψ(x) = (1, x, x²), containing three features and therefore three coefficient positions.
Linearizing the Predictor
The feature mapping changes the representation of the input, not the fact that the prediction is formed as a linear combination of coefficients. After replacing x with ψ(x), the learning problem becomes: find the coefficient vector w that combines the transformed features most effectively. Thus, polynomial regression can be reorganized as a linear regression problem in the transformed feature space.
The word linear refers here to the coefficients being combined linearly. The presence of x² or higher powers in the transformed features does not prevent the use of linear regression methods.
Least Squares and Empirical Risk
Empirical risk minimization chooses the predictor with the smallest loss on the training data. For linear regression with squared loss, least squares performs this search by minimizing the squared-loss objective. In the polynomial setting, the same process is applied after the inputs have been transformed into polynomial feature vectors.
From Objective to Aw = b
Least squares minimizes an objective that depends on the regression weights. To locate an optimal set of weights, calculate the gradient of that objective and set the gradient equal to zero. This condition identifies a stationary point of the squared-loss objective and is the mathematical step used to derive the equations for the weights.
In A w = b, A and b are determined by the problem formulation, while w is the vector of regression weights that must be found. This compact system is the central computational form of the least-squares problem after the gradient condition has been rewritten.
Solving for the Weights
| Matrix A | Meaning for solving A w = b | Tool described in the source |
|---|---|---|
| Invertible | The system has the corresponding direct linear-algebra solution for the weights. | Solve the system under the invertible-matrix case. |
| Not invertible | A direct inverse is unavailable. The training instances may not span the entire space of R d. | Use eigenvalue decomposition as a needed linear-algebra tool. |
The two matrix cases that arise after the gradient condition is converted into A w = b.
Eigenvalue Decomposition
When A is not invertible, the direct invertible-matrix route cannot be used. Eigenvalue decomposition supplies the needed linear-algebra tools for analyzing this case. It helps expose the directions represented by the matrix and clarifies why some directions cannot be handled by ordinary inversion. The key point is not to force an inverse where one is unavailable, but to use the decomposition to reason about the structure of A and the resulting weight system.
Treat the cases in order: first identify that the gradient condition produces A w = b, then determine whether A is invertible. Only after identifying the non-invertible case should eigenvalue decomposition become the relevant tool.
Common Reasoning Errors
Common mistake Assuming polynomial regression must use a completely different learning algorithm from linear regression.
What it looks likeTreating the powers x, x², and higher powers as proof that linear regression cannot be used.
Why it failsThe transformed feature vector makes the prediction a linear combination of the coefficients.
Do this insteadApply the mapping ψ(x) = (1, x, x², ..., xⁿ), then use linear regression and least squares to learn the polynomial coefficients.
Common mistake Leaving out the constant feature.
What it looks likeUsing (x, x², ..., xⁿ) instead of (1, x, x², ..., xⁿ).Why it failsA degree-n polynomial has n + 1 coefficients, including the constant-term coefficient.
Do this insteadBegin the feature mapping with 1, which represents degree 0.
Common mistake Treating A w = b as the starting point without explaining where it comes from.
What it looks likeWriting the linear system without mentioning the squared-loss objective or its gradient.
Why it failsThe system is obtained by differentiating the objective and setting the gradient equal to zero.
Do this insteadTrace the derivation from squared loss to gradient, from zero gradient to the linear system.
Common mistake Using the direct invertible-matrix route when A is not invertible.
What it looks likeAssuming every matrix in A w = b can be inverted.
Why it failsThe non-invertible case requires different linear-algebra tools.
Do this insteadUse eigenvalue decomposition to analyze the non-invertible case.
Practice Check
Explain the full route from a scalar input x to the coefficient vector for a degree-n polynomial regression model. Your explanation should include the feature mapping, the role of squared loss, the zero-gradient condition, the system A w = b, and the difference between the invertible and non-invertible cases.
Hints
- Start by listing the features in ψ(x) in degree order.
- Explain why the transformed problem is linear in the coefficients.
- Connect least squares to empirical risk minimization with squared loss.
- State what is checked about A after deriving A w = b.
Tracing the Complete Method
Describe how least squares would be organized for a degree-2 polynomial predictor.
- 1Transform the input
Replace each scalar input x with ψ(x) = (1, x, x²).
- 2Form the learning problem
Use the transformed features in a linear regression model whose coefficients are the polynomial coefficients.
- 3Choose the objective
Use squared loss and seek the predictor with the smallest empirical risk on the training data.
- 4Derive the equations
Calculate the gradient of the objective, set it equal to zero, and rewrite the resulting condition as A w = b.
- 5Handle the matrix
If A is invertible, use the corresponding direct solution. If A is not invertible, use eigenvalue decomposition as the relevant linear-algebra tool.
Polynomial regression has been converted into a least-squares linear regression problem in transformed features, with A w = b as its central computational form.
Key Takeaways
- 1A degree-n polynomial uses the features 1, x, x², through xⁿ and has n + 1 coefficients.
- 2The mapping ψ(x) = (1, x, x², ..., xⁿ) turns the original input into a feature vector suitable for linear regression methods.
- 3Least squares minimizes empirical risk when the loss is squared loss.
- 4Setting the gradient of the objective equal to zero produces the central system A w = b.
- 5An invertible A has the corresponding direct solution, while a non-invertible A calls for eigenvalue decomposition and related linear-algebra tools.
At a glance
- Polynomial regression can represent relationships that a straight-line predictor cannot, while still being linear in its coefficients after feature transformation.
- The feature mapping ψ(x) = (1, x, x², ..., xⁿ) packages the required powers of the input.
- Least squares solves the empirical risk minimization problem for linear regression with squared loss.
- Differentiating the objective and setting its gradient to zero leads to A w = b.
- The solution strategy depends on whether A is invertible; eigenvalue decomposition provides tools for the non-invertible case.