Data fitting and optimization for machine learning · Lecture 23

Least Squares and Linear Regression

When there are more data points than unknowns, no curve passes through all of them. Least squares picks the curve that makes the total squared error smallest: the normal equations, their matrix form, how to judge a fit, and where the method breaks.

Md Mahbub E Noor · Assistant Professor
CSE-3107 Numerical Methods · B.Sc. 3rd Year 1st Semester
Department of CSE, University of Barishal

Why this lecture

The problem: predicting a delivery time

A food-delivery company records six orders: distance $x$ (km) and delivery time $y$ (minutes). How long will a 15 km order take?

The points lie almost on a line, but no line passes through all six
Interpolation (Lectures 16–18) forces a curve through every point: degree 5 here
That curve predicts 40.4 min at 12 km and 32.9 min at 13 km: a longer trip that is faster. Nonsense
Data have noise; we want the trend, not every wiggle

distance $x$ (km)	time $y$ (min)
2	14
4	21
5	24
7	30
9	37
11	42
15	?

Md Mahbub E Noor

Lecture 23: Least squares and linear regression

University of Barishal

2 / 24

Today's goals

Define the residual and the least-squares criterion
Derive and solve the normal equations for a straight line
Write least squares in matrix form $A^{T}A\mathbf{c} = A^{T}\mathbf{y}$ and fit models with several inputs
Judge a fit with $S$ , $R^2$ and the residual plot
Recognise when least squares misleads: outliers, extrapolation, ill-conditioning

Last time

Interpolation: a polynomial through every data point (Lectures 16–18); solving linear systems (Lectures 12–13).

Today

A simple curve that passes close to all points, chosen by minimising the sum of squared errors.

Data fitting and optimization for machine learning · you are here

L23 · Least Squares and Linear Regression→L24 · Polynomial, Exponential and Trigonometric Fitting→L25 · Numerical Optimization for Machine Learning

Builds on: L5, L13

Md Mahbub E Noor

Lecture 23: Least squares and linear regression

University of Barishal

3 / 24

Start here

The idea in one picture

Measured data never lie exactly on a line.Many lines look reasonable. Which one is "best"?We need a rule to score a line.Take a candidate line.For each dot, measure the vertical miss (the residual).Square each miss and add them up. Least squares picks the line with the smallest total.

In plain words

Real data are noisy: no line passes through every point
Score a line by its misses, squared and added
The line with the smallest score is the least-squares line

New words today

residual: measured y − y predicted by the line
least squares: make the sum of squared residuals smallest
normal equations: the small linear system that gives a and b
regression: fitting a model to data
QR factorisation: a safer way to solve them (A = QR)

Md Mahbub E Noor

Lecture 23: Least squares and linear regression

University of Barishal

4 / 24

Working principle: make the squared residuals as small as possible

Model, and the residual of point i (vertical distance from the line)

\hat y = a + bx, \qquad e_i = y_i - (a + bx_i)

Least-squares criterion: choose a and b to minimise

S(a, b) = \sum_{i=1}^{n} e_i^2 = \sum_{i=1}^{n} \big(y_i - a - bx_i\big)^2

$n$ equations $a + bx_i = y_i$ , only 2 unknowns: overdetermined, no exact solution
Why squares? Positive and negative errors cannot cancel, big errors count more, and $S$ is smooth, so calculus finds its minimum
Sum of $|e_i|$ is more robust but has no simple formula
Gauss (1795) and Legendre (1805) invented it to fit planetary orbits

Md Mahbub E Noor

Lecture 23: Least squares and linear regression

University of Barishal

5 / 24

The normal equations for a straight line

Set both partial derivatives of S to zero

\frac{\partial S}{\partial a} = -2\sum (y_i - a - bx_i) = 0, \quad \frac{\partial S}{\partial b} = -2\sum x_i(y_i - a - bx_i) = 0

Normal equations: a 2 × 2 linear system

\begin{aligned} na + b\textstyle\sum x_i &= \textstyle\sum y_i \\ a\textstyle\sum x_i + b\textstyle\sum x_i^2 &= \textstyle\sum x_iy_i \end{aligned}

Solution

b = \frac{n\sum x_iy_i - \sum x_i\sum y_i}{n\sum x_i^2 - (\sum x_i)^2}, \qquad a = \bar y - b\,\bar x

Only four sums are needed: $\sum x$ , $\sum y$ , $\sum x^2$ , $\sum xy$
The fitted line always passes through the mean point $(\bar x, \bar y)$
The denominator is zero only if all $x_i$ are equal
$S$ is a convex bowl in $(a, b)$ : this stationary point is the minimum

Md Mahbub E Noor

Lecture 23: Least squares and linear regression

University of Barishal

6 / 24

The method, step by step

Fitting a straight line, step by step

Tabulate $x_i$ , $y_i$ , $x_i^2$ , $x_iy_i$ and add each column
Write the two normal equations with these sums
Solve for $b$ , then $a = (\sum y - b\sum x)/n$
Compute the residuals $e_i = y_i - a - bx_i$ and $S = \sum e_i^2$
Check: $\sum e_i \approx 0$ ; look at the residual pattern; predict $\hat y = a + bx$

Pseudocode

input x[1..n], y[1..n]
Sx ← Σ x;   Sy ← Σ y
Sxx ← Σ x²; Sxy ← Σ x·y
D ← n·Sxx − Sx²
b ← (n·Sxy − Sx·Sy) / D
a ← (Sy − b·Sx) / n
S ← Σ (y − a − b·x)²
R² ← 1 − S / Σ (y − ȳ)²
return a, b, S, R²

One pass over the data: $O(n)$ work.

Md Mahbub E Noor

Lecture 23: Least squares and linear regression

University of Barishal

7 / 24

Problem 1: the table of sums for the delivery data

Fit

y = a + bx

to the six orders. First build the table of sums.

$i$	$x_i$	$y_i$	$x_i^2$	$x_iy_i$
1	2	14	4	28
2	4	21	16	84
3	5	24	25	120
4	7	30	49	210
5	9	37	81	333
6	11	42	121	462
$\sum$	38	168	296	1237

Normal equations

$6a + 38b = 168$
$38a + 296b = 1237$

$n = 6$ . Every number on the right comes from the bottom row of the table.

Md Mahbub E Noor

Lecture 23: Least squares and linear regression

University of Barishal

8 / 24

Problem 1 (continued): solve, check and predict

1

D = n\sum x^2 - (\sum x)^2 = 6(296) - 38^2 = 1776 - 1444 = 332

2

b = \dfrac{6(1237) - 38(168)}{332} = \dfrac{7422 - 6384}{332} = \dfrac{1038}{332} = 3.126506

3

a = \dfrac{168 - 38(3.126506)}{6} = \dfrac{168 - 118.8072}{6} = 8.198795

4

Residuals:

-0.45,\ 0.30,\ 0.17,\ -0.08,\ 0.66,\ -0.59

(sum 0);

\;S = 1.1145

5

Prediction:

\hat y(15) = 8.1988 + 3.1265(15) = 55.10

min

y = 8.20 + 3.13x

: about 8 minutes to collect the order plus 3.1 minutes per km.

R^2 = 0.998

.

Md Mahbub E Noor

Lecture 23: Least squares and linear regression

University of Barishal

9 / 24

Explore: edit the data, watch the best line and its residuals

Red dashed segments are the residuals; the line minimises the sum of their squares
Change one $y$ value and see the whole line move
Outlier preset: one wrong value tilts the line from slope 3.1 to 5.5
Curved data: a line gives a pattern in the residuals (+, −, −, −, −, +)

Md Mahbub E Noor

Lecture 23: Least squares and linear regression

University of Barishal

10 / 24

Matrix form: any model that is linear in its coefficients

n equations, k unknown coefficients (n > k): A c ≈ y

\underbrace{\begin{bmatrix} 1 & x_1 \\ 1 & x_2 \\ \vdots & \vdots \\ 1 & x_n \end{bmatrix}}_{A\;(n\times 2)} \begin{bmatrix} a \\ b \end{bmatrix} \approx \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{bmatrix}

Minimise ‖y − Ac‖²: the normal equations

A^{T}A\,\mathbf{c} = A^{T}\mathbf{y}

$A^{T}A$ is $k \times k$ , symmetric and positive definite: solve by Cholesky (Lecture 13)
Geometry: $A\mathbf{c}$ is the projection of $\mathbf{y}$ onto the columns of $A$ ; the residual is perpendicular to every column
More inputs = more columns: $y = \beta_0 + \beta_1x_1 + \beta_2x_2$ (multiple regression)
Columns may be any functions of $x$ : $x^2$ , $\cos x$ , … (Lecture 24)

Md Mahbub E Noor

Lecture 23: Least squares and linear regression

University of Barishal

11 / 24

Problem 2: multiple regression for house prices

Five flats: size

x_1

(m²) = 50, 70, 80, 100, 120; rooms

x_2

= 1, 2, 2, 3, 3; price

y

(lakh Tk) = 30, 42, 47, 60, 68. Fit

y = \beta_0 + \beta_1x_1 + \beta_2x_2

.

1

Rows of

A

:

(1, x_1, x_2)

, e.g.

(1, 50, 1)

; five rows, three columns

2

A^{T}A = \begin{bmatrix} 5 & 420 & 11 \\ 420 & 38200 & 1010 \\ 11 & 1010 & 27 \end{bmatrix}, \quad A^{T}\mathbf{y} = \begin{bmatrix} 247 \\ 22360 \\ 592 \end{bmatrix}

3

Solve the 3 × 3 system by Gaussian elimination or Cholesky

4

\beta_0 = 4.179

,

\;\beta_1 = 0.4282

per m²,

\;\beta_2 = 4.205

per room

Price

\approx 4.18 + 0.428x_1 + 4.21x_2

; a 90 m², 3-room flat: 55.3 lakh Tk.

R^2 = 0.9994

.

Md Mahbub E Noor

Lecture 23: Least squares and linear regression

University of Barishal

12 / 24

How good is the fit?

Residual sum of squares, and its spread around the mean

S = \sum e_i^2, \qquad S_t = \sum (y_i - \bar y)^2

Coefficient of determination and standard error (k coefficients)

R^2 = 1 - \frac{S}{S_t}, \qquad s = \sqrt{\frac{S}{n - k}}

$R^2$ : fraction of the variation in $y$ explained by the model ( $0 \le R^2 \le 1$ )
Delivery data: $R^2 = 0.998$ , $s = 0.53$ min: typical prediction error about half a minute
High $R^2$ is not proof: curved data fitted with a line still gives $R^2 = 0.93$
Always plot the residuals: random scatter = good model; a pattern = wrong model

Md Mahbub E Noor

Lecture 23: Least squares and linear regression

University of Barishal

13 / 24

Classical vs numerical

Same question, two approaches

Algebra

Classical (hand formula)

Straight line: two sums formulas for $a$ and $b$
Delivery data: $y = 8.20 + 3.13x$ in five minutes
One input variable, small $n$

vs

Algorithm

Numerical (linear algebra)

Build $A$ , solve $A^{T}A\mathbf{c} = A^{T}\mathbf{y}$ or use QR
Any number of inputs and basis functions
Same code for 6 points or 6 million

When the classical approach cannot work

Predicting a house price from 80 features and 1.5 million sales

There is no hand formula for 81 coefficients. Numerically: an 81 × 81 system $A^{T}A\mathbf{c} = A^{T}\mathbf{y}$ , or a QR factorisation of $A$ , solved in well under a second. This is linear regression as used in industry.

Md Mahbub E Noor

Lecture 23: Least squares and linear regression

University of Barishal

14 / 24

Linear regression in code

Accumulates the four sums in one loop
Solves the normal equations; prints $a$ , $b$
Residuals, $S$ , $R^2$ and a prediction
Lab: multiple regression with Gaussian elimination

Md Mahbub E Noor

Lecture 23: Least squares and linear regression

University of Barishal

15 / 24

When least squares misleads

Limitations shown failing

Outliers: squaring gives a wrong point huge weight; one typo changes the 15 km prediction from 55 to 80 min
Extrapolation: the line says nothing about traffic beyond 11 km
Wrong model: a line through curved data leaves a residual pattern
Ill-conditioning: forming $A^{T}A$ squares the condition number (next slide)

Md Mahbub E Noor

Lecture 23: Least squares and linear regression

University of Barishal

16 / 24

When least squares misleads

Limitation: the normal equations square the condition number

Fit sales against the year

x = 2015, 2016, \dots, 2020

. The columns of

A

are

(1, \dots, 1)

and

(2015, \dots, 2020)

: almost parallel.

matrix	condition number	digits lost (of 16)
$A$ (years as given)	$2.4\times10^{6}$	about 6
$A^{T}A$ (normal equations)	$5.7\times10^{12}$	about 13
$A^{T}A$ with centred $x - 2017.5$	2.9	none

Fixes: centre and scale the inputs, or solve by QR ( $A = QR$ , then $R\mathbf{c} = Q^{T}\mathbf{y}$ ), which works with cond( $A$ ) instead of its square. Library routines (numpy.linalg.lstsq) use QR or the SVD.

Why centring helps

Years as given:

$A^{T}A = \begin{bmatrix} 6 & 12105 \\ 12105 & 24421855 \end{bmatrix}$

determinant $105$ out of numbers near $10^{8}$ : nearly singular.

Centred, $x - 2017.5 = -2.5, \dots, 2.5$ :

$A^{T}A = \begin{bmatrix} 6 & 0 \\ 0 & 17.5 \end{bmatrix}$

Md Mahbub E Noor

Lecture 23: Least squares and linear regression

University of Barishal

17 / 24

Practice

Practice problem

Problem 3"Fit a straight line

y = a + bx

to the data

x

: 1, 2, 3, 4, 5 and

y

: 3, 5, 6, 9, 11 by the method of least squares. Estimate

y

at

x = 6

."

How to write a complete answer

Make the table: $\sum x = 15$ , $\sum y = 34$ , $\sum x^2 = 55$ , $\sum xy = 122$
Normal equations: $5a + 15b = 34$ , $\;15a + 55b = 122$
Solve: $b = \dfrac{5(122) - 15(34)}{5(55) - 225} = \dfrac{100}{50} = 2$ , $\;a = \dfrac{34 - 30}{5} = 0.8$
Answer $y = 0.8 + 2x$ ; $\;y(6) = 12.8$ ; residuals $0.2, 0.2, -0.8, 0.2, 0.2$ add to 0 (a quick check)

Md Mahbub E Noor

Lecture 23: Least squares and linear regression

University of Barishal

18 / 24

When to use it

Linear least squares: method profile

Best case

Many noisy measurements, a model linear in its coefficients
Errors roughly equal in size and independent (then least squares is statistically optimal)
Closed-form answer: one linear solve, no iteration

Worst case

Outliers or heavy-tailed errors
Nearly parallel columns (ill-conditioning)
Models nonlinear in the parameters, e.g. $ae^{bx}$ fitted directly

Best suited for

Calibration of sensors and instruments
Trend lines in economics and science
Linear regression in machine learning (the first model to try)

Avoid when

Exact data with no noise (interpolate instead)
Predictions far outside the data range
Data with gross errors (use robust regression)

Rule of thumb: fit, then look at the residuals before trusting $R^2$ ; solve by QR, not by forming $A^{T}A$ , when columns are nearly dependent.

Md Mahbub E Noor

Lecture 23: Least squares and linear regression

University of Barishal

19 / 24

Comparative analysis: interpolation vs least squares, and ways to solve it

Approach	Passes through points?	Work ( $n$ points, $k$ coefficients)	Accuracy	Use when
Interpolation (L16–18)	yes, all	$O(n^2)$	exact at data	data exact, few points
Least-squares line by sums	no	$O(n)$	sums may cancel	one input, by hand
Normal equations + Cholesky	no	$nk^2 + k^3/3$	loses $\log_{10}\text{cond}(A)^2$ digits	well-conditioned, $n \gg k$
QR factorisation	no	$2nk^2$	loses $\log_{10}\text{cond}(A)$ digits	default in libraries
Gradient descent (L25)	no	per pass $O(nk)$	iterative	huge $n$ and $k$

Interpolation trusts every point; least squares trusts the trend. With noisy data, least squares predicts better.

Md Mahbub E Noor

Lecture 23: Least squares and linear regression

University of Barishal

20 / 24

Roadmap

Limitations, and where we fix them

Least squares is the foundation of data fitting. Its weak points lead to the last two lectures.

What it does well (keep this)

Closed form: one linear solve
Works for any model linear in its coefficients
Statistical meaning: best fit under random errors
Matrix form scales to many inputs

LimitationHow it is overcomeWhere

Data follow a curve, not a line

→

Polynomial least squares (more columns)

Lecture 24 →

Growth and power laws:

ae^{bx}

,

ax^b

→

Linearise with logarithms

Lecture 24 →

Too many coefficients fit the noise

→

Overfitting; choose the degree by test error

Lecture 24 →

Parameters inside a nonlinear model

→

Gauss–Newton iteration

Lecture 25 →

Millions of rows or features; robust losses

→

Gradient descent on

S

Lecture 25 →

Md Mahbub E Noor

Lecture 23: Least squares and linear regression

University of Barishal

21 / 24

Applications

Where this method runs in the real world

Click a card to see least squares at work.

Md Mahbub E Noor

Lecture 23: Least squares and linear regression

University of Barishal

22 / 24

Checkpoint

Checkpoint · think, then discuss with your neighbourFor the points

(0, 1)

,

(1, 3)

,

(2, 4)

, what is the slope

b

of the least-squares line?

A

1.5

B

1.5\overline{6}

C

2

D

1.25

A.

n = 3

,

\sum x = 3

,

\sum y = 8

,

\sum x^2 = 5

,

\sum xy = 11

:

\;b = \dfrac{3(11) - 3(8)}{3(5) - 9} = \dfrac{9}{6} = 1.5

,

\;a = \dfrac{8 - 4.5}{3} = 1.1\overline{6}

.

Md Mahbub E Noor

Lecture 23: Least squares and linear regression

University of Barishal

23 / 24

Summary

Key points

Residual $e_i = y_i - \hat y_i$ ; least squares minimises $S = \sum e_i^2$
Line: $na + b\sum x = \sum y$ , $\;a\sum x + b\sum x^2 = \sum xy$
Matrix form $A^{T}A\mathbf{c} = A^{T}\mathbf{y}$ ; any number of inputs; QR when ill-conditioned
Judge with $R^2$ , $s$ and the residual plot; beware outliers and extrapolation

Opening problem: solved

Least squares gives $y = 8.20 + 3.13x$ ( $R^2 = 0.998$ ), so a 15 km order takes about 55 minutes, an extrapolation to be checked with new data. The degree-5 interpolant's 32.9 min at 13 km shows why we do not interpolate noisy data.

Homework

Fit $y = a + bx$ to $x$ : 0, 1, 2, 3 and $y$ : 1.1, 2.9, 5.2, 6.8. Find $S$ and $R^2$ .
A spring: $F$ = 0, 1, 2, 3, 4 N, $L$ = 10.0, 10.9, 12.1, 13.0, 13.9 cm. Fit $L = L_0 + cF$ and find the length at 2.5 N.
Show that the least-squares line passes through $(\bar x, \bar y)$ and that $\sum e_i = 0$ .
Write $A$ , $A^{T}A$ and $A^{T}\mathbf{y}$ for fitting $y = \beta_0 + \beta_1x_1 + \beta_2x_2$ to four data points of your choice, and solve it in the lab.

Next lecture

Lecture 24: polynomial, exponential and trigonometric fitting. Curved trends, growth laws, periodic data, and the danger of too many coefficients.

Md Mahbub E Noor

Lecture 23: Least squares and linear regression

University of Barishal

24 / 24

Least Squares and Linear Regression

The problem: predicting a delivery time

Today's goals

The idea in one picture

Working principle: make the squared residuals as small as possible

The normal equations for a straight line

Fitting a straight line, step by step

Problem 1: the table of sums for the delivery data

Problem 1 (continued): solve, check and predict

Explore: edit the data, watch the best line and its residuals

Matrix form: any model that is linear in its coefficients

Problem 2: multiple regression for house prices

How good is the fit?

Same question, two approaches

Classical (hand formula)

Numerical (linear algebra)

Predicting a house price from 80 features and 1.5 million sales

Linear regression in code

Limitations shown failing

Limitation: the normal equations square the condition number

Practice problem

Linear least squares: method profile

Comparative analysis: interpolation vs least squares, and ways to solve it

Limitations, and where we fix them

Where this method runs in the real world

🤖 Linear regression in machine learning

⚖️ Calibrating a sensor

🛰️ GPS positioning

📈 Trend lines in science and economics

Checkpoint

Summary