The Hong Kong University of Science and Technology · FACULTY OF COMPUTER SCIENCE

MAIE5421 Chap.2 Linear, Polynomial and Regularised Regression

- one subject, every graph, every model, every mark
8 Chapters5-page Bible
Our own words - no uploaded lecturer files
Updated for this semester
Chapter 2 of 10 · MAIE5421

Linear, Polynomial and Regularised Regression

From one input to many

The regression lecture works through a family of models in increasing flexibility. Simple linear regression relates one input to one output with a slope, an intercept and an error term, and the lecture's running example predicts salary from years of working experience.

Multiple linear regression adds further inputs, each with its own partial coefficient, illustrated with a house price that depends on floor area, bedrooms, bathrooms, age and distance to the city centre.

Polynomial regression lets one input enter as a sum of its powers so that the fitted curve can follow a non-linear relationship.

One fitting principle throughout

All three are estimated by ordinary least squares, which chooses the coefficients that minimise the sum of squared residuals between observed and predicted values.

For a single input this gives a slope equal to the sum of paired deviation products over the sum of squared input deviations, and an intercept that makes the line pass through the point of means. With several inputs the same condition is written in matrix form, with a column of ones carrying the intercept, and solved with the normal equations.

The lecture stresses that the polynomial solution has exactly the same form, with a feature matrix built from powers of the input.

Flexibility has a price

A high-degree polynomial can thread every training point and still generalise badly, and the lecture links that failure to coefficients that grow very large in both directions. Two remedies are taught.

Cross-validation chooses the degree that predicts held-out data best.

Regularisation keeps the degree but adds a penalty on coefficient size: ridge regression penalises the squared L2 norm and has a closed-form solution, while lasso penalises the L1 norm, has no closed-form solution in general and is solved iteratively by coordinate descent.

Why lasso can select features

The L1 penalty produces sparse solutions, in which a few coefficients are large and the rest are exactly zero.

That is how lasso can recognise that a feature such as the age of a house owner adds nothing to a price model and remove it, which ridge cannot do because it only shrinks. The strength of either penalty is a tuning parameter: small values stay close to ordinary least squares and risk high variance, large values add bias or sparsity, and the lecture recommends choosing the value by cross-validation.

In this chapter

What this chapter covers

  • 01

    Regression with single and multi-dimensional inputs and outputs

  • 02

    Simple linear regression and ordinary least squares

  • 03

    Multiple linear regression in matrix form

  • 04

    Polynomial regression and the choice of degree

  • 05

    Overfitting and the role of large coefficients

  • 06

    Ridge regression and the L2 penalty

  • 07

    Lasso regression, the L1 penalty and sparse solutions

  • 08

    Choosing the tuning parameter by cross-validation

Worked example · free

Fit and check a least-squares calibration line for exposure time

Q [7 marks]. AskSia-authored practice. A grey card photographed at exposure times of 1, 2, 3, 4 and 5 ms gives mean brightness readings of 3, 5, 6, 8 and 10. Fit the least-squares line of brightness on exposure time, confirm two properties every such fit must have, and predict the reading at 2.5 ms. The marks shown are an AskSia study allocation and are not the University's marking scheme.
Five measurements and their least-squares line.Five measurements and their least-squares line. Each dot is one exposure setting, the blue line is the fitted model, and each dashed orange segment is a residual whose square enters the sum being minimised.12345100y = 1.7x+1.3residualExposure time (ms)Mean brightness
Five measurements and their least-squares line. Each dot is one exposure setting, the blue line is the fitted model, and each dashed orange segment is a residual whose square enters the sum being minimised.
  • 2Means: 3 ms and 6.4; the paired deviation products sum to 17 and the squared time deviations sum to 10.
  • 2Slope 17 / 10 = 1.7 and intercept 6.4 - 1.7 × 3 = 1.3, so brightness = 1.7 × time + 1.3.
  • 2Checks: the line passes through (3, 6.4), and the residuals 0, 0.3, -0.4, -0.1, 0.2 sum to zero.
  • 1Prediction at 2.5 ms: 1.7 × 2.5 + 1.3 = 5.55.
The fitted calibration is brightness = 1.7 × time + 1.3, so each extra millisecond adds 1.7 brightness units over this range. Two checks confirm the arithmetic: substituting the mean time of 3 ms returns the mean reading of 6.4, and the five residuals cancel exactly. Their squares sum to 0.30, a small error relative to readings between 3 and 10. At 2.5 ms the line predicts 5.55, an interpolation inside the measured range and therefore a safe use of the model.
Sia tip — After fitting, substitute the mean input. If the line does not return the mean output, the intercept is wrong.
Glossary

Key terms

Residual
The difference between an observed value and the value the fitted model predicts for it.
Sum of Squared Residuals
The total of the squared residuals over a dataset, the quantity ordinary least squares minimises.
Normal Equations
The matrix condition whose solution gives the least-squares coefficients for several features at once.
Polynomial Regression
Regression in which one input enters as a sum of its powers, letting the fitted curve bend.
Ridge Regression
Linear regression with a penalty on the squared L2 norm of the coefficients, which shrinks every weight towards zero.
Tuning Parameter
The weight on a regularisation penalty, which controls how strongly coefficient size is punished relative to fitting error.
Sparse Solution
A coefficient vector in which only a few entries are large and the rest are zero or very close to zero.
FAQ

Linear, Polynomial and Regularised Regression FAQ

When should I use ridge rather than lasso?

Use ridge when you expect most features to carry some signal and you want to stop any of them dominating, because it shrinks every coefficient while keeping all of them. Use lasso when you suspect several features are irrelevant, because its L1 penalty can set coefficients exactly to zero and so performs feature selection. In both cases, choose the strength of the penalty by cross-validation.

Why does a high-degree polynomial overfit?

Because with enough terms the curve can pass through, or very near, every training point, including the noise in them. Achieving those extra bends needs large positive and negative coefficients on the higher powers, and those coefficients make the curve swing wildly between and beyond the training points. The result is a small training error and a large error on new data.

Does polynomial regression need a different fitting method?

No. The model is non-linear in the input but still linear in its coefficients, so ordinary least squares applies directly. You build a feature matrix whose columns are the input raised to successive powers, plus a column of ones, and solve the same normal equations used for multiple linear regression. Only the definition of the matrix changes.

Study strategy

Assessment move

Fit one five-point line completely by hand, writing the means, deviations, products, slope, intercept and residuals in a table, then repeat the fit in a few lines of NumPy and confirm the numbers match. Next, compute a ridge and a lasso estimate for one coefficient at two values of the tuning parameter, so that the difference between shrinking and zeroing is something you have calculated rather than read.

Working through Linear, Polynomial and Regularised Regression in MAIE5421? Sia is AskSia’s AI Computer Science tutor — ask any MAIE5421 Linear, Polynomial and Regularised Regression question and get a clear, step-by-step explanation grounded in how MAIE5421 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.

A+Everything unlocked
Unlocks this Bible + all 13 of your subjects at The Hong Kong University of Science and Technology, plus 1,000+ more Bibles across the AskSia library.
Sia - your MAIE5421 tutor, unlimited, worked the way the exam marks it
The full 5-page Bible + practice bank with worked solutions
Chrome extension - sync your LMS so Sia knows your deadlines
Bilingual EN / Chinese on every Bible and every Sia answer
$0.99 Trial
30-day money-back · cancel in one tap · how it works