Least Squares
A polynomial predictor can represent relationships that require more than a straight-line predictor.
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.
Identify the degrees: A degree-2 polynomial uses degree 0, degree 1, and degree 2 features.
Write each feature: The corresponding features are 1, x, and x².
Assemble 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.
Empirical risk = average squared loss over the training dataFrom 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.
A w = bIn 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. |
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
Assuming polynomial regression must use a completely different learning algorithm from linear regression.
The transformed feature vector makes the prediction a linear combination of the coefficients.
Fix:
Apply the mapping ψ(x) = (1, x, x², ..., xⁿ), then use linear regression and least squares to learn the polynomial coefficients.Leaving out the constant feature.
A degree-n polynomial has n + 1 coefficients, including the constant-term coefficient.
Fix:
Begin the feature mapping with 1, which represents degree 0.Treating A w = b as the starting point without explaining where it comes from.
The system is obtained by differentiating the objective and setting the gradient equal to zero.
Fix:
Trace the derivation from squared loss to gradient, from zero gradient to the linear system.Using the direct invertible-matrix route when A is not invertible.
The non-invertible case requires different linear-algebra tools.
Fix:
Use 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.
Transform the input: Replace each scalar input x with ψ(x) = (1, x, x²).
Form the learning problem: Use the transformed features in a linear regression model whose coefficients are the polynomial coefficients.
Choose the objective: Use squared loss and seek the predictor with the smallest empirical risk on the training data.
Derive the equations: Calculate the gradient of the objective, set it equal to zero, and rewrite the resulting condition as A w = b.
Handle 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
- A degree-n polynomial uses the features 1, x, x², through xⁿ and has n + 1 coefficients.
- The mapping ψ(x) = (1, x, x², ..., xⁿ) turns the original input into a feature vector suitable for linear regression methods.
- Least squares minimizes empirical risk when the loss is squared loss.
- Setting the gradient of the objective equal to zero produces the central system A w = b.
- An invertible A has the corresponding direct solution, while a non-invertible A calls for eigenvalue decomposition and related linear-algebra tools.
Key Takeaways
- 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.