CSE 403: Machine Learning

Chapter 3: Linear Regression

Md Atikuzzaman
Lecturer
Department of Computer Science & Engineering
atik@[Link]
 Outline
1 Motivation and Problem Setup

2 Model: Hypothesis Function

3 Loss Function and Objective

4 Training Method: Gradient Descent

5 Evaluation and Interpretation

6 Training Method 2: Normal Equation

7 Other Loss Functions for Regression

8 Summary

9 References

Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 1 / 35
 Why Linear Regression?

Many real-world tasks require predicting a continuous value.

Examples: house price, salary, temperature, demand forecasting.
Linear regression provides a simple, interpretable baseline.

Linear regression is often the first model to try: fast to train, easy to debug, easy to
explain.

Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 2 / 35
 Supervised Learning View

Data
We are given labeled examples:

D = {(x (i) , y (i) )}m

i=1

where y (i) ∈ R is continuous.

Goal
Learn a function fθ (x) that predicts ŷ ≈ y for unseen inputs.

Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 3 / 35
 Simple Linear Regression (1 Feature)

Hypothesis (Model)

ŷ = fθ (x) = θ0 + θ1 x

θ0 : intercept (bias)
θ1 : slope (effect of x on y )
The model assumes a linear relationship between input x and target y .

Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 4 / 35
 Example Dataset: House Prices

Rooms Price ($1000)

2 18
3 22
4 26
5 28
6 30

x = Rooms, y = Price

Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 5 / 35
 How Do We Measure Error?

Residual (Prediction Error)

For one example (x (i) , y (i) ):
e(i) = ŷ (i) − y (i)

If e(i) > 0: model overestimates

If e(i) < 0: model underestimates

Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 6 / 35
 Squared Loss (MSE)

Loss for One Example

ℓ(ŷ , y ) = (ŷ − y )2

Empirical Risk (Mean Squared Error)

1 ∑(
m
)2
J(θ) = fθ (x (i) ) − y (i)
m
i=1

Squaring penalizes large errors more strongly and gives a smooth objective for
optimization.

Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 7 / 35
 Learning Objective

Optimization Problem

θ̂ = arg min J(θ)

θ∈Θ

Choose parameters θ that minimize the average squared error.

Two common training approaches:
Closed-form solution (Normal Equation)
Iterative optimization (Gradient Descent)

Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 8 / 35
 Gradient Descent: Idea

Start with an initial guess θ(0) .

Compute gradient of J(θ).
Update parameters in the direction that reduces the loss.

Initialize Compute gradient Update

θ(0) ∇J(θ) θ ← θ − α∇J(θ)

Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 9 / 35
 Gradient Descent Update Rule

Vector Update

θ(t+1) = θ(t) − α∇θ J(θ(t) )

For Linear Regression (MSE)

2 ⊤
∇θ J(θ) = X (X θ − y )
m

α: learning rate
Repeat until convergence or early stopping

Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 10 / 35
 Goal: Fit a Line to the Data

Given Dataset
We model Price (y ) from Rooms (x):

(x, y ) ∈ {(2, 18), (3, 22), (4, 26), (5, 28), (6, 30)}, y in $1000

Hypothesis (Simple Linear Regression)

ŷ = hθ (x) = θ0 + θ1 x

Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 11 / 35
 Loss Function and Objective

Squared Loss (per example)

ℓ(ŷ , y ) = (ŷ − y )2

Mean Squared Error (MSE) Objective

1 ∑( )2
m
J(θ0 , θ1 ) = θ0 + θ1 x (i) − y (i)
m
i=1

m = 5 (number of training examples)

Training means: minimize J(θ0 , θ1 )
Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 12 / 35
 Gradient Descent: Core Idea

We update parameters iteratively

θ ← θ − α∇J(θ)

Start with an initial guess (θ0 , θ1 )

Compute gradients (direction of steepest increase)
Move opposite direction to reduce loss
Repeat until the loss stops improving

Gradient descent is an optimization method, not a machine learning model.

Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 13 / 35
 Gradients for Simple Linear Regression
Define the error (residual)

( )
e(i) = ŷ (i) − y (i) = θ0 + θ1 x (i) − y (i)

Partial derivatives of MSE

2 ∑ (i) 2 ∑ (i) (i)

m m
∂J ∂J
= e = e x
∂ θ0 m ∂ θ1 m
i=1 i=1

Update rules

∂J ∂J
θ0 ← θ0 − α , θ1 ← θ1 − α
∂ θ0 ∂ θ1
Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 14 / 35
 Gradient Descent Algorithm (Step-by-Step)

Algorithm (Batch Gradient Descent)

1 Initialize θ0 , θ1 (e.g., 0) and choose learning rate α
2 Repeat for t = 0, 1, 2, . . . until convergence:
1 Compute predictions: ŷ (i) = θ0 + θ1 x (i)
2 Compute errors: e(i) = ŷ (i) − y (i)
3 Compute gradients:
2 ∑ (i) 2 ∑ (i) (i)
m m
g0 = e , g1 = e x
m m
i=1 i=1

4 Update:
θ0 ← θ0 − αg0 , θ1 ← θ1 − αg1

Note: Batch GD uses all m examples in every iteration.

Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 15 / 35
 Worked Example: Initialization

Dataset

(2, 18), (3, 22), (4, 26), (5, 28), (6, 30)

Choose

θ0 = 0, θ1 = 0, α = 0.01, m = 5

We will do one full batch update to show the process.

Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 16 / 35
 Iteration 1: Predictions and Errors

Predictions with θ0 = 0, θ1 = 0

ŷ (i) = θ0 + θ1 x (i) = 0 ⇒ ŷ = [0, 0, 0, 0, 0]

Errors e(i) = ŷ (i) − y (i)

e = [−18, −22, −26, −28, −30]

Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 17 / 35
 Iteration 1: Compute Gradients

Gradient w.r.t. θ0

2 ∑ (i) 2 (
m
) 2
g0 = e = − 18 − 22 − 26 − 28 − 30 = (−124) = −49.6
m 5 5
i=1

Gradient w.r.t. θ1

2 ∑ (i) (i) 2 (
m
)
g1 = e x = (−18)2 + (−22)3 + (−26)4 + (−28)5 + (−30)6
m 5
i=1

2( ) 2
= − 36 − 66 − 104 − 140 − 180 = (−526) = −210.4
5 5
Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 18 / 35
 Iteration 1: Parameter Update

Update with α = 0.01

θ0 ← 0 − 0.01(−49.6) = 0.496
θ1 ← 0 − 0.01(−210.4) = 2.104

New model after 1 iteration

ŷ = 0.496 + 2.104x

After the first step, the line moves upward and starts fitting the data trend.

Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 19 / 35
 Check: New Predictions (After 1 Update)

Compute ŷ = 0.496 + 2.104x

ŷ (2) = 4.704, ŷ (3) = 6.808, ŷ (4) = 8.912, ŷ (5) = 11.016, ŷ (6) = 13.120

True outputs are [18, 22, 26, 28, 30].

Predictions are still low, but closer than 0.
Repeating iterations will keep reducing the loss.

Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 20 / 35
 Effect of Learning Rate α
Too Small α Too Large α
Very slow convergence Oscillation
Many iterations required May diverge

J(θ) J(θ)

θ θ
Choose α carefully for stable and fast convergence.

Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 21 / 35
 Stopping Criteria

Common Stopping Rules Loss

Loss improvement is very small:

|J (t+1) − J (t) | < ϵ

Maximum iterations reached

Stop
Validation loss stops improving (Early
Stopping)
Iterations
Goal: Stop training when further updates
provide negligible improvement.

Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 22 / 35
 Optimization Methods: Gradient Descent Variants
Batch GD Stochastic GD Mini-batch GD
Uses all m samples 1 sample at a time Small batches (e.g., 32)
Smooth convergence Noisy updates Stable + Efficient
Computationally heavy Fast for large data Most commonly used
Loss Batch (smooth)
Mini-batch (stable)
Stochastic (noisy)

Iterations
Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 23 / 35
 How Do We Evaluate a Regression Model?
∑
MSE: 1
m (ŷ − y )2
√
RMSE: MSE (same unit as y )
∑
MAE: 1
m |ŷ − y |
R 2 : proportion of variance explained

Always report metrics on a held-out test set to estimate generalization performance.

Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 24 / 35
 Interpretation: Coefficients

Meaning of Parameters
In ŷ = θ0 + θ⊤ x:
θ0 shifts predictions up/down (baseline)
θj is the expected change in y when xj increases by 1 unit, holding other features
fixed

Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 25 / 35
 Multiple Linear Regression (d Features)

Vector Form
Let x ∈ Rd and θ ∈ Rd .
ŷ = fθ (x) = θ0 + θ⊤ x

x = [x1 , . . . , xd ]⊤
θ = [ θ1 , . . . , θd ] ⊤
Each coefficient θj measures the contribution of feature xj

Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 26 / 35
 Closed-Form Solution (Normal Equation)

Design Matrix
Let X ∈ Rm×(d+1) include a column of ones:
 
1 (x (1) )⊤  
1 (x (2) )⊤  y (1)
   
X = . .. , y =  ... 
 .. . 
y (m)
1 (x (m) )⊤

Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 27 / 35
 Normal Equation

Solution
If X ⊤ X is invertible:
θ̂ = (X ⊤ X )−1 X ⊤ y

Fast and exact for small to medium feature sizes.

Can be expensive when (d + 1) is very large.
If X ⊤ X is not invertible, use:
θ̂ = X † y
where X † is the pseudoinverse.

Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 28 / 35
 Why Use Different Loss Functions?

Different loss functions measure prediction error differently.

Choice of loss function affects:
Sensitivity to outliers
Model robustness
Optimization behavior
Mean Squared Error (MSE) is common, but not always the best choice.

Selecting an appropriate loss function can significantly improve model performance.

Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 29 / 35
 Mean Absolute Error (MAE)

Definition

L(y , ŷ ) = |y − ŷ |

Measures the absolute difference between prediction and true value.

Less sensitive to outliers than MSE.
All errors contribute linearly.
Empirical Loss

1 ∑ (i)
m
J(θ) = |y − ŷ (i) |
m
i=1

Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 30 / 35
 Huber Loss

Definition
{
1
2 (y− ŷ )2 , |y − ŷ | ≤ δ
L(y , ŷ ) = 2
δ|y − ŷ | − δ2 , |y − ŷ | > δ

Combines advantages of MSE and MAE.

Quadratic for small errors (smooth optimization).
Linear for large errors (robust to outliers).

Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 31 / 35
 Quantile Loss (Pinball Loss)

Definition
For quantile τ ∈ (0, 1):
{
τ(y − ŷ ), y ≥ ŷ
Lτ (y , ŷ ) =
(1 − τ)(ŷ − y ), y < ŷ

Used in quantile regression.

Estimates conditional quantiles instead of the mean.
Useful when prediction uncertainty is important.

Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 32 / 35
 Comparison of Common Loss Functions
Loss Function Formula Type Outlier Sensitivity
MSE Squared Error High
MAE Absolute Error Medium
Huber Hybrid Low
Quantile Asymmetric Error Task-dependent

MSE penalizes large errors heavily.

MAE is more robust to extreme values.
Huber provides a balance between both.

Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 33 / 35
 Key Takeaways
Problem: Linear regression models a continuous target using labeled data (x (i) , y (i) ).
Model: Predictions are linear in features:
ŷ = θ0 + θ⊤ x
Training objective: Learn parameters by minimizing an empirical loss (commonly
MSE, but alternatives exist for robustness).
Optimization choices:
Gradient Descent (batch/SGD/mini-batch): scalable and widely used
Normal Equation / Pseudoinverse: exact for small to medium feature sizes
Evaluation: Use a held-out test set and report metrics such as MSE/RMSE, MAE,
and R 2 .
Interpretation: Each coefficient θj represents the expected change in y per one-unit
increase in xj , holding other features fixed.
A good workflow: choose a loss, train with a suitable optimizer, validate on test data, and
interpret coefficients.
Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 34 / 35
 References

1 T. Hastie, R. Tibshirani, J. Friedman, The Elements of Statistical Learning, Springer.

2 C. M. Bishop, Pattern Recognition and Machine Learning, Springer.
3 I. Goodfellow, Y. Bengio, A. Courville, Deep Learning, MIT Press.

Department of Computer Science & Engineering Chapter 3: Linear Regression CSE 403: Machine Learning 35 / 35