COM4509/6509
Machine Learning and
Adaptive Intelligence
Lecture 4: Linear Regression
Mike Smith* and Matt Ellis
*[Link]@[Link]
Detour: Inner and Outer Products
Detour: Inner and Outer Products
ACTIVITY:
Compute these!
Detour: Inner and Outer Products
Detour: Inner and Outer Products
Linear Regression
ACTIVITY: What
does this equal?
ACTIVITY: Check this is
equivalent to the sum of
squares error.
(and other rules we have learnt about transposes etc)
ACTIVITY: Have a go at finding the value of
w that minimises this error function, E! We
need to differentiate E wrt w, then set to zero.
Here are some hints:
1. Move the transpose inside the bracket,
e.g. by noting that (Xw)T=wTXT.
2. Multiply out the brackets.
3. Differentiate each term wrt w.
4. Set equal to zero.
5. Multiply both sides by (XTX)-1 and cancel
any constants on both sides etc.
(moving the
transpose inside
the bracket).
Move the transpose inside the
bracket, e.g. by noting that
(Xw)T=wTXT.
Multiply out the brackets.
Differentiate each term wrt w.
Set equal to zero.
Multiply both sides by (XTX)-1 and
cancel any constants on both
sides etc.
(multiplying
out the
brackets)
Multiply out the brackets.
Differentiate each term wrt w.
Set equal to zero.
Multiply both sides by (XTX)-1 and
cancel any constants on both
sides etc.
Differentiate each term wrt w.
Set equal to zero.
Multiply both sides by (XTX)-1 and
cancel any constants on both
sides etc.
Set equal to
zero to find
minimum
Set equal to zero.
Multiply both sides by (XTX)-1 and
cancel any constants on both
sides etc.
Multiply both sides by (XTX)-1 and
cancel any constants on both
sides etc.
Multiply both sides by (XTX)-1 and
cancel any constants on both
sides etc.
Iterative Optimisation
For the case of linear regression, we’ve just seen it’s got a closed form solution. I.e. we can set the
gradient to zero, rearrange, and get the answer.
For most problems we can’t do this. But we might be able to still compute the gradient (and use a
gradient descent algorithm)
Side note:
Even though linear regression has a closed form solution, it might
be too tricky to compute. ACTIVITY: What size is (XTX)?
X is (N x D), so XTX is (D x D).
It takes roughly O(D3) time to compute the inverse, and uses
approximately O(D2) memory. If our data is high-dimensional (i.e.
D is big) then both of these complexities can be a problem.
So we might still need to use gradient descent…
Iterative Optimisation
For the case of linear regression, we’ve just seen it’s got a closed form solution. I.e. we can set the
gradient to zero, rearrange, and get the answer.
For most problems we can’t do this. But we might be able to still compute the gradient (and use a
gradient descent algorithm)
Side note:
Even though linear regression has a closed form solution, it might
be too tricky to compute. ACTIVITY: What size is (XTX)?
X is (N x D), so XTX is (D x D).
It takes roughly O(D3) time to compute the inverse, and uses
approximately O(D2) memory. If our data is high-dimensional (i.e.
D is big) then both of these complexities can be a problem.
So we might still need to use gradient descent…
Iterative Optimisation
For the case of linear regression, we’ve just seen it’s got a closed form solution. I.e. we can set the
gradient to zero, rearrange, and get the answer.
For most problems we can’t do this. But we might be able to still compute the gradient (and use a
gradient descent algorithm)
Side note:
Even though linear regression has a closed form solution, it might
be too tricky to compute. ACTIVITY: What size is (XTX)?
X is (N x D), so XTX is (D x D).
It takes roughly O(D3) time to compute the inverse, and uses
approximately O(D2) memory. If our data is high-dimensional (i.e.
D is big) then both of these complexities can be a problem.
So we might still need to use gradient descent…
Iterative Optimisation
For the case of linear regression, we’ve just seen it’s got a closed form solution. I.e. we can set the
gradient to zero, rearrange, and get the answer.
For most problems we can’t do this. But we might be able to still compute the gradient (and use a
gradient descent algorithm)
Side note:
Even though linear regression has a closed form solution, it might
be too tricky to compute. ACTIVITY: What size is (XTX)?
X is (N x D), so XTX is (D x D).
It takes roughly O(D3) time to compute the inverse, and uses
approximately O(D2) memory. If our data is high-dimensional (i.e.
D is big) then both of these complexities can be a problem.
So we might still need to use gradient descent…
Let’s code an example!
This is the method that
computes a prediction for
a given value of w and x.
This is the method that
computes a prediction for
Build the design
a given value of w and x.
matrix X from our
vector x. This has
two columns (two
regressors). The
first is full of xs, the
second full of 1s.
This is the method that
computes a prediction for
Build the design
Our prediction a given value of w and x.
matrix X from our
is Xw. In
vector x. This has
numpy matrix
two columns (two
multiplication is
regressors). The
with the @
first is full of xs, the
symbol.
second full of 1s.
Let’s plot the predictions
for different values of x,
with w equal to [-1,4]T.
Let’s plot the predictions
for different values of x,
with w equal to [-1,4]T.
Not a very
good fit!
Let’s write the cost function. This
returns the sum squared error.
For w = [-1,4]T, E = 53.
For w = [0.5,4]T, E = 33.5.
For w = [0.5,4]T, E = 33.5.
Ooh, the error is less, it seemed like increasing
the first term (the gradient) from -1 to +0.5
helped improved our predictions.
If only there was a way of finding out how much
E changes depending on w…
Ah! Here’s the gradient of
E wrt w! We worked this
out in the last section!
This says -2XTy + 2XTXw
Which is what we found the
gradient (dE/dw) to be:
Ah! Here’s the gradient of
E wrt w! We worked this
out in the last section!
This says -2XTy + 2XTXw
Which is what we found the
gradient (dE/dw) to be:
For complicated functions we use
autodiff frameworks (TensorFlow,
PyTorch, Keras, Theano, JAX, etc).
E.g. if the getprediction implemented
a deep neural network.
Off topic: To check I’ve coded my
gradient correctly, I’m computing it
numerically too…
Ok, so we’ve got our
gradient, how do we use it
to optimise w?
The simplest/most obvious approach is
Gradient Descent gradient (steepest) descent.
Here we simply subtract (a proportion of) the gradient from the current value of w.
We need to do this in small increments defined by the learning rate, η. In this case
I’ve chosen η=0.01.
The simplest/most obvious approach is
Gradient Descent gradient (steepest) descent.
Here we simply subtract (a
proportion of) the gradient
from the current value of w.
We need to do this in small
increments defined by the
learning rate (aka step
“The new value of w (at iteration k+1)
size), η [eta]. In this case I’ve equals the old value of w (at iteration
chosen η=0.01. k) minus eta (the learning rate) times
the gradient of the error E wrt w, at the
old value of w.”
Gradient Descent From Mauricio’s slide
Here we simply subtract (a
proportion of) the gradient
from the current value of w.
We need to do this in small
increments defined by the
learning rate (aka step
size), η [eta]. In this case I’ve
chosen η=0.01.
Gradient Descent From Mauricio’s slide
Line Search:
One solution is to pick a
direction, and find a point
along it where we’ve reduced
the function the most…
Alternative approaches to Gradient Descent
Gradient descent can make really
slow progress (e.g. along a ridge)...
(gradient ascent in
this example).
Alternative approaches to Gradient Descent
Gradient descent can make really
slow progress (e.g. along a ridge)...
(gradient ascent in
this example).
Alternative approaches to Gradient Descent
Gradient descent can make really
slow progress (e.g. along a ridge)...
(gradient ascent in
this example).
Alternative approaches to Gradient Descent
Gradient descent can make really
slow progress (e.g. along a ridge)...
(gradient ascent in
this example).
Alternative approaches to Gradient Descent
Gradient descent can make really
slow progress (e.g. along a ridge)...
(gradient ascent in
this example).
Alternative approaches to Gradient Descent
Gradient descent can make really
slow progress (e.g. along a ridge)...
(gradient ascent in
this example).
Alternative approaches to Gradient Descent
Gradient descent can make really
slow progress (e.g. along a ridge)...
(gradient ascent in
this example).
Alternative approaches to Gradient Descent
Gradient descent can make really
slow progress (e.g. along a ridge)...
(gradient ascent in
this example).
Alternative approaches to Gradient Descent
Gradient descent can make really
slow progress (e.g. along a ridge)...
(gradient ascent in
this example).
Alternative approaches to Gradient Descent
Newton’s method [not examinable!] will get to a minima quite quickly as it takes
into account the 2nd order derivatives:
At each iteration, it amounts to the fitting of a parabola to the graph at
the trial value, and then proceeding to the maximum or minimum of
that parabola (in higher dimensions, this may also be a saddle point).
– wikipedia
The problems is that this requires finding the Hessian (matrix of 2nd order partial
derivatives), which is really expensive. But approximations to the true Hessian
exist. For example the BFGS algorithm.
Alternative approaches to Gradient Descent
- Newton’s approach takes too much computation per step
- Steepest descent ends up with many many small steps
An intermediate approach is conjugate gradient descent.
Other tricks
- The example gradient descent we computed found the gradient using all the
data.
- This is called batch gradient descent.
- If you have a large dataset, or the function you are trying to minimise maybe
has a high time/space complexity: consider mini-batch gradient descent.
- This leads to stochastic gradient descent (SGD) - as the gradient will depend on the
sample chosen at each iteration.
Other tricks
- Choosing the learning rate (in SGD) is now more difficult. Typically some
decaying sequence is chosen. If it fulfills the Robbins-Monro conditions
(and the function we’re optimising is differentiable and convex) then, in the
limit, it is guaranteed to converge.
Two key conditions of Robbins-Monro.
Example sequences that
fulfill the conditions.
Typically though, we use a library optimisation algorithm, such as ADAM, which
will adjust the learning rate to help improve convergence.
Other tricks
- Choosing the learning rate (in SGD) is now more difficult. Typically some
decaying sequence is chosen. If it fulfills the Robbins-Monro conditions
(and the function we’re optimising is differentiable and convex) then, in the
limit, it is guaranteed to converge.
Two key conditions of Robbins-Monro.
Example sequences that
fulfill the conditions.
Snippet of a module I wrote for calibrating air pollution sensors.
Typically though, we use a library optimisation algorithm, such as ADAM, which
will adjust the learning rate to help improve convergence.
Other tricks
Finally note: Most optimisers will work better if the inputs (features) are
normalised.
break
Linear regression: try predicting the air
pollution in this example by manually
adjusting the parameters (weights) that
say how much to scale each feature.
Maximum Likelihood Estimation
We said that our noise (error) term was assumed to be Gaussian distributed.
If we assume this, then we can come at the problem from a different angle: Trying
to maximise the probability that the model generated the data, by adjusting model
parameters.
(I’ve added some extra text
to help with this slide)
Reminder: If we assume
conditional independence
exists between two Note: I should really have
variables A and B, given C said we assume the noise
then it means that we're added to each
saying that we believe observation is
p(A|C) P(B|C) = P(A,B|C). independent of the noise
added to other
So if we assume that y1 and y2 are
conditionally indpendent, given x1,x2,w observations. Or
and σ^2, then we can write that alternatively I could have
p(y1,y2|x1,x2,w,σ^2) [which is what we
want to know], is equal to p(y1|x1,x2,w, said that the data (or
σ^2) x p(y2|x1,x2,w,σ^2) [we also note observations) are
that we will assume that y1 is
conditionally indendent of x2 given x1, conditionally independent,
so p(y1|x1,x2) = p(y1|x1), so we can given our latent function.
remove the irrelevant terms from the
right of the |: giving us that the joint
probability density of p(y1,y2|x1,x2,w,
σ^2) = p(y1|x1,w,σ^2) x p(y2|x2,w,σ^2).
That product can extend over the
whole set of test points, given us the
Πp(yi|xi,w,σ^2).
Likelihood
Before, we wanted to minimise a cost function. Here we want to
maximise the probability that the data came from our model (by
adjusting our model). Because we are interested in this
probability as a function of w and σ2, it won’t integrate to one
over these parameters. So it’s not a probability distribution. We
instead call it the likelihood function,
Maximum likelihood estimation selects parameters (in this
case, w and σ2) to maximise the likelihood function.
The Normal Distribution
Looks tricky, but
let’s step
through how
you might work
this out from
scratch…
Looks tricky, but
let’s step
through how
you might work
this out from
scratch…
Looks tricky, but
let’s step
through how
you might work
this out from
scratch…
Looks tricky, but
let’s step
through how
you might work
this out from
scratch…
Looks tricky, but
let’s step
through how
you might work
this out from
scratch…
Make it
narrow or
wide
Looks tricky, but
let’s step
through how
you might work
this out from
scratch…
Need a normalising term:
E.g. If σ is big, then our
Gaussian is wide, so we
need to make it less tall.
Let’s go back now to our expression for the likelihood Remember we had assumed iid for
our noise, so we can say that the
joint probability of all the
observations is the product of the
individual probabilities.
Let’s go back now to our expression for the likelihood
Let’s go back now to our expression for the likelihood
Log Likelihood
We want to differentiate the likelihood with
respect to w and σ2, but in its current form
that is quite tricky.
The location of the maximum of L is in the
same place as the maximum of log L (as log
is monotonic).
So we first, find the log of the likelihood, then
differentiate that… An example function, and its log.
Log Likelihood
We want to differentiate the likelihood with
respect to w and σ2, but in its current form
that is quite tricky.
The location of the maximum of L is in the
same place as the maximum of log L (as log
is monotonic).
So we first, find the log of the likelihood, then
differentiate that… An example function, and its log, to
demonstrate that the maxima and
ACTIVITY: Compute the log likelihood.
minima are in the same places!
Hint: Start by thinking about how the log
product of things is the sum of the log of
things.
differentiate…
differentiate…
differentiate…
differentiate…
differentiate…
differentiate…
We can differentiate
and solve for σ2 in a
similar way.
Summary: Maximum Likelihood Estimation and Ordinary Least Squares
If we have Gaussian-distributed i.i.d. noise,
minimising the sum squared error (i.e.
“ordinary least squares”) is the maximum
likelihood estimator (for linear regression).
Basis Functions
We’ve already used a basis, the 1st-order polynomial had two bases: x1 and x0.
We could add another column, with the values of x2.
This will lead to a 2nd-order polynomial.
The solution is the same expression as before.
Our parameter vector would just need another
number (to describe the contribution of the quadratic
term).
From slide
16…
Basis Functions
We’ve already used a basis, the 1st-order polynomial had two bases: x1 and x0.
We could add another column, with the values of x2.
This will lead to a 2nd-order polynomial.
The solution is the same expression as before.
Our parameter vector would just need another
number (to describe the contribution of the quadratic
term).
From slide
16…
Basis Functions
We’ve already used a basis, the 1st-order polynomial had two bases: x1 and x0.
We could add another column, with the values of x2.
This will lead to a 2nd-order polynomial.
The solution is the same expression as before.
Our parameter vector would just need another
number (to describe the contribution of the quadratic
term).
From slide
16…
Example Basis Functions
- Polynomial
- Gaussian
- Fourier
- Sigmoid
ACTIVITY: Match the words to the
bases. One of them is a ‘random’ basis
(so not picked from a grid)
Example Basis Functions
- Polynomial
- Gaussian
- Fourier Polynomial
- Sigmoid
ACTIVITY: Match the words to the
bases. One of them is a ‘random’ basis
(so not picked from a grid)
Example Basis Functions
- Polynomial
- Gaussian
- Fourier Polynomial Gaussian
- Sigmoid
ACTIVITY: Match the words to the
bases. One of them is a ‘random’ basis
(so not picked from a grid)
Example Basis Functions
- Polynomial
- Gaussian
- Fourier Polynomial Gaussian
- Sigmoid
ACTIVITY: Match the words to the Sigmoid
bases. One of them is a ‘random’ basis
(so not picked from a grid)
Example Basis Functions
- Polynomial
- Gaussian
- Fourier Polynomial Gaussian
- Sigmoid
Random
fourier.
ACTIVITY: Match the words to the Sigmoid
bases. One of them is a ‘random’ basis
(so not picked from a grid)
ACTIVITY: Explore the effect of the
number of parameters: consider the
Regularisation score on the training and validation sets.
A common problem is ‘overfitting’. You can get parameter values that are very
large to explain data.
See the example.
ACTIVITY: Explore the effect of the
number of parameters: consider the
Regularisation score on the training and validation sets.
A common problem is ‘overfitting’. You can get parameter values that are very
large to explain data.
See the example.
To help avoid this we can add an additional term
to the cost function that penalises lots of large
parameters.
λ: Regulariser
parameter (maybe set
h(w) = E(w) + λR(w) using validation set?).
R: regulariser
E: Our original
cost function
l2 regularisation - also called
ridge regression.
In this toy example we can’t see
much benefit. But with many
2
bases (or parameters) this often
is absolutely necessary to make
the regression work.
2
2
l1 regularisation has the property
that it will push many of the
parameters to zero. This can be
useful if you think only a few
features are relevant.
l1 regularisation has the property
that it will push many of the
parameters to zero. This can be
useful if you think only a few
features are relevant.
l1 regularisation has the property
that it will push many of the
parameters to zero. This can be
useful if you think only a few
features are relevant.
Elastic net regularisation has
some l1 and some l2, mixed
together.
Other approaches exist.
Summary / Take home messages
- We can write the sum square cost function as
- We can differentiate, set to zero, and find a closed form solution for linear
regression.
- This is the same solution as when we use the maximum likelihood approach.
- If we don’t have a closed form solution, we need to optimise our parameters
iteratively.
- Steepest descent is simple but often is slow.
- Other options: line search, newton’s method, conjugate gradient descent.
- If we have too much data we could use mini-batching and stochastic gradient
descent.
- If the model overfits, try regularising.
Summary / Take home messages
- We can write the sum square cost function as
- We can differentiate, set to zero, and find a closed form solution for linear
regression.
- This is the same solution as when we use the maximum likelihood approach.
- If we don’t have a closed form solution, we need to optimise our parameters
iteratively.
- Steepest descent is simple but often is slow.
- Other options: line search, newton’s method, conjugate gradient descent.
- If we have too much data we could use mini-batching and stochastic gradient
descent.
- If the model overfits, try regularising.
Summary / Take home messages
- We can write the sum square cost function as
- We can differentiate, set to zero, and find a closed form solution for linear
regression.
- This is the same solution as when we use the maximum likelihood approach.
- If we don’t have a closed form solution, we need to optimise our parameters
iteratively.
- Steepest descent is simple but often is slow.
- Other options: line search, newton’s method, conjugate gradient descent.
- If we have too much data we could use mini-batching and stochastic gradient
descent.
- If the model overfits, try regularising.
Summary / Take home messages
- We can write the sum square cost function as
- We can differentiate, set to zero, and find a closed form solution for linear
regression.
- This is the same solution as when we use the maximum likelihood approach.
- If we don’t have a closed form solution, we need to optimise our parameters
iteratively.
- Steepest descent is simple but often is slow.
- Other options: line search, newton’s method, conjugate gradient descent.
- If we have too much data we could use mini-batching and stochastic gradient
descent.
- If the model overfits, try regularising.
Summary / Take home messages
- We can write the sum square cost function as
- We can differentiate, set to zero, and find a closed form solution for linear
regression.
- This is the same solution as when we use the maximum likelihood approach.
- If we don’t have a closed form solution, we need to optimise our parameters
iteratively.
- Steepest descent is simple but often is slow.
- Other options: line search, newton’s method, conjugate gradient descent.
- If we have too much data we could use mini-batching and stochastic gradient
descent.
- If the model overfits, try regularising.
Summary / Take home messages
- We can write the sum square cost function as
- We can differentiate, set to zero, and find a closed form solution for linear
regression.
- This is the same solution as when we use the maximum likelihood approach.
- If we don’t have a closed form solution, we need to optimise our parameters
iteratively.
- Steepest descent is simple but often is slow.
- Other options: line search, Newton’s method, conjugate gradient descent.
- If we have too much data we could use mini-batching and stochastic gradient
descent.
- If the model overfits, try regularising.
Summary / Take home messages
- We can write the sum square cost function as
- We can differentiate, set to zero, and find a closed form solution for linear
regression.
- This is the same solution as when we use the maximum likelihood approach.
- If we don’t have a closed form solution, we need to optimise our parameters
iteratively.
- Steepest descent is simple but often is slow.
- Other options: line search, Newton’s method, conjugate gradient descent.
- If we have too much data we could use mini-batching and stochastic gradient
descent.
- If the model overfits, try regularising.
Summary / Take home messages
- We can write the sum square cost function as
- We can differentiate, set to zero, and find a closed form solution for linear
regression.
- This is the same solution as when we use the maximum likelihood approach.
- If we don’t have a closed form solution, we need to optimise our parameters
iteratively.
- Steepest descent is simple but often is slow.
- Other options: line search, Newton’s method, conjugate gradient descent.
- If we have too much data we could use mini-batching and stochastic gradient
descent.
- If the model overfits, try regularising.