Chapter 9.
Linear Regression
0
Equivalent to 1 slot. Lecturers can use extra materials for other slots in the chater
FPT University Chapter 9. Linear Regression 1 / 14
Chapter 9. Linear Regression
1 9.1 Problem Formulation
2 9.2 Parameter Estimation
3 9.3 Bayesian Linear Regression
4 9.4 Maximum Likelihood as Orthogonal Projection
FPT University Chapter 9. Linear Regression 2 / 14
9.1 Problem Formulation
Consider a regression problem with the likelihood function
p(y ∣x) = N (y ∣f (x), σ 2 ), (1)
where x ∈ RD are inputs and y ∈ R are noisy function values (targets).
The relation between x and y is given by
y = f (x) + with ∼ N (0, σ 2 ), σ 2 is known. (2)
Our object is to find a function that is close to the unknown function f
that generated the data and that generalizes well.
FPT University Chapter 9. Linear Regression 3 / 14
We choose a parametrized function and parameters θ that work well for
modeling the data.
In the linear regression, we consider the parameter θ appear linearly in our
model. An exapmle,
p(y ∣x, θ) = N (y ∣x T θ, σ 2 ) (3)
⇔ y = x T θ + , ∼ N (0, σ 2 ). (4)
Example
For x, θ ∈ R, the linear regression model in (4) describes straight lines and
the parameter θ is the slope of the line.
FPT University Chapter 9. Linear Regression 4 / 14
9.2 Parameter Estimation
Consider the linear regression setting in (4) and a training set
D ∶= {(x1 , y1 ), . . . , (xN , yN )}
consisting of N inputs xn ∈ RD and corresponding targets yn ∈ R.
The likelihood:
p(Y∣X , θ) = p(y1 , . . . , yN ∣x1 , . . . , xN , θ) (5)
N N
= ∏ p(yn ∣xn , θ) = ∏ N (yn ∣xnT θ, σ 2 )
n=1 n=1
where
X ∶= {x1 , . . . , xN } ∶ training inputs set
Y ∶= {y1 , . . . , yN } ∶ corresponding targets set.
We shall discuss how to find optimal parameter θ⋆ ∈ RD for the model (4):
p(y⋆ ∣x⋆ , θ⋆ ) = N (y⋆ ∣x⋆T θ⋆ , σ 2 ).
FPT University Chapter 9. Linear Regression 5 / 14
9.2.1 Maximum likelihood Estimation
Find the maximum likelihood estimation
θML = arg max p(Y∣X , θ).
θ
To find θML , we can perform gradient ascent (or gradient descent on the
negative likelihood).
However, in practice, we apply the log-transformation to the likelihood
function and minimize the negative log-likelihood
N
− log p(Y∣X , θ) = − ∑ log p(yn ∣xn , θ). (6)
n=1
In the model (4), the likelihood is Gaussian
1
log p(yn ∣xn , θ) = − (yn − xnT θ) + const.
2σ 2
FPT University Chapter 9. Linear Regression 6 / 14
Substitute to (6) (ignoring the constant term)
1 N
L(θ) ∶= 2 ∑ (yn − xn θ)
T 2
(7)
2σ n=1
1 1
= 2
(y − X θ)T (y − X θ) = 2 ∥y − X θ∥2
2σ 2σ
where
T
X ∶= [x1 ⋯xN ] ∈ RN×D
T
y ∶= [y1 . . . yN ] ∈ RN .
FPT University Chapter 9. Linear Regression 7 / 14
The gradient of L w.r.t θ
dL 1 d
= 2 (∥y − X θ∥2 )
dθ 2σ dθ
1 d
= 2 (y T y − 2y T X θ + θT X T X θ) (8)
2σ dθ
1
= 2 (−y T X + θT X T X ) ∈ R1×D .
σ
Find θML by solving dL
dθ = 0:
dL
= 0 ⇔ θML
T
XT X = yT X
dθ
⇔ θML
T
= y T X (X T X )−1 (9)
−1
⇔ θML = (X X ) X y .T T
(10)
FPT University Chapter 9. Linear Regression 8 / 14
Maximum Likelihood Estimation with Features
Straight lines are not sufficiently expressive when it comes to fitting more
interesting data. We can perform a nonlinear transformation Φ(x) of the
inputs x and then linearly combine the components of this transformation.
The corresponding linear regression model is
p(y ∣x, θ) = N (y ∣φT (x)θ, σ 2 ) (11)
K
⇔ y = φT (x)θ + = ∑ θk φk (x) + ,
k=1
where φ ∶ R → R is a transformation of inputs x and φk ∶ RD → R is the
D K
k th component of the feature vector φ.
Consider training inputs xn ∈ RD and targets yn ∈ R, define the feature
matrix
⎡ φT (x1 ) ⎤ ⎡ φ1 (x1 ) ⋯ φK (x1 ) ⎤
⎢ ⎥ ⎢ ⎥
⎢ ⎥ ⎢ ⎥
Φ ∶= ⎢ ⋮ ⎥=⎢ ⋮ ⋱ ⋮ ⎥. (12)
⎢ T ⎥ ⎢ ⎥
⎢φ (xN )⎥ ⎢φ1 (xN ) ⋯ φK (xN )⎥
⎣ ⎦ ⎣ ⎦
FPT University Chapter 9. Linear Regression 9 / 14
The negative log-likelihood for the model (11):
1
− log p(Y∣X , θ) = (y − Φθ)T (y − Φθ) + const. (13)
2σ 2
The maximum likelihood estimate:
−1
θML = (ΦT Φ) ΦT y
for the linear regression problem (11).
FPT University Chapter 9. Linear Regression 10 / 14
Estimating the Noise Variance
We assumed that the noise variance σ 2 is known. However, we can obtain
2
the maximum likelihood estimator σML for the noise variance:
N
log p(Y∣X , θ, σ 2 ) = ∑ log N (yn ∣φT (xn )θ, σ 2 )
n=1
N
1 1 1
= ∑ (− log(2π) − log σ 2 − 2 (yn − φT (xn )θ)2 )
n=1 2 2 2σ
N 1 N
=− log σ 2 − 2 ∑ (yn − φT (xn )θ)2 + const.
2 2σ n=1
Solving
∂ log p(Y∣X , θ, σ 2 )
= 0,
∂σ 2
we get
1 N
2
σML = ∑ (yn − φ (xn )θ) .
T 2
N n=1
FPT University Chapter 9. Linear Regression 11 / 14
9.2.3 Maximum A Posteriori Estimation
Given a data set X , Y, the maximum a posteriori (MAD) estimation is a
procedure that instead of maximizing the likelihood, we seek parameters
that maximize the posterior distribution
p(Y∣X , θ)p(θ)
p(θ∣X , Y) = . (14)
p(Y∣X )
We have
log p(θ∣X , Y) = log p(Y∣X , θ) + log p(θ) + const, (15)
where the constant is independent of θ.
d log p(θ∣X , Y) d log p(Y∣X , θ) d log p(θ)
− =− − . (16)
dθ dθ dθ
With p(θ) = N (0, b 2 I )
1 1
− log p(θ, X , Y) = (y − Φθ)T (y − Φθ) + 2 θT θ + const. (17)
2σ 2 2b
FPT University Chapter 9. Linear Regression 12 / 14
Hence
d log p(θ∣X , Y) 1 1
− = 2 (θT ΦT Φ − y T Φ) + 2 θT . (18)
dθ σ b
Find θMAP ∈ arg minθ {− log p(Y∣X , θ) − log p(θ)} by solving
d log p(θ∣X , Y)
− =0
dθ
1 T T 1
⇒ 2
(θ Φ Φ − y T Φ) + 2 θT = 0
σ b
1 T 1 1
⇔θ ( 2 Φ Φ + 2 I ) − 2 y T Φ = 0
T
σ b σ
−1
σ2
⇔θT = y T Φ (ΦT Φ + I) .
b2
Hence
−1
σ2
θMAP = (Φ Φ + 2 I )
T
ΦT y .
b
FPT University Chapter 9. Linear Regression 13 / 14
Summary
We have discussed linear regression for
Gaussian likelihoods;
conjugate Gaussian priors on the parameters of the model.
FPT University Chapter 9. Linear Regression 14 / 14