Optimising linear regression: A guide to applying gradient descent
Tags: machinelearning, beginners
Published: 2023-02-26 14:48:47

Linear regression is a statistical technique that helps us understand and predict relationships between variables. It is widely used in data science and machine learning.

At its core, linear regression involves finding the best-fitting line through a set of data points, allowing us to make predictions about future values based on past observations.

![Linear regression](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/0kvd1w8k3hy8n09du0cc.png)

Finding the line can be a complex and computationally-intensive task, especially when dealing with large datasets.

Enter gradient descent... an optimisation algorithm that we can use to find the best-fitting line by iteratively adjusting its parameters.

It's worth noting that linear regression is a form of supervised learning where our algorithm is trained on "labelled" data. This simply reflects the fact that, within the available data, the inputs have corresponding outputs or labels.

In this blog, we will look at the maths, specifically the partial derivatives, involved in applying gradient descent to linear regression.

## Model

Given a training set, our aim is to model the relationship so that our hypothesis {% katex inline %}\hat{y}{% endkatex %} is a good predicator for the corresponding value of {% katex inline %}y{% endkatex %}.

For simple or univariate linear regression, our model can be expressed as:

{% katex %}
\hat{y} = \theta_0 + \theta_1{x_1}
{% endkatex %}

And for multivariate linear regression:

{% katex %}
\hat{y} = \theta_0 + \theta_1{x_1} + \theta_2{x_2} + ... + \theta_j{x_j}
{% endkatex %}

## Loss function

We can measure the accuracy of our hypothesis {% katex inline %}\hat{y}{% endkatex %} by calculating the mean squared error - including a {% katex inline %}\frac{1}{2}{% endkatex %} to simplify the derivatives that follow later.

{% katex %}
{Loss, l} = \frac{1}{2m}\sum_{i=1}^{m}(\hat{y} - y)^2
{% endkatex %}

![Mean squared error](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/irfkytv52t76wfna8vjm.png)

## Gradient descent

We need to minimise the loss to ensure that {% katex inline %}\hat{y}{% endkatex %} is a good predicator of {% katex inline %}y{% endkatex %}.

Gradient descent is well described elsewhere but the principle is that we adjust the {% katex inline %}\theta{% endkatex %} parameters until the loss is at the very bottom of the curve.

![Gradient descent](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ae29onnp7nq04tle3gf7.png)

The adjustment is achieved by repeatedly taking the derivative of the loss function (the tangent line) to infer a movement to the right (gradient is negative) or the left (gradient is positive).

The size of each step is relative to a fixed hyper parameter {% katex inline %}\alpha{% endkatex %} which is called the learning rate. Typical values for {% katex inline %}\alpha{% endkatex %} are 0.1, 0.01 and 0.001. 

This approach can be articulated as:

{% katex %}
\theta_j = \theta_j - \alpha\dfrac{\mathrm{d}l}{\mathrm{d}\theta_j}
{% endkatex %}

There are three types of gradient descent:

1. Batch gradient descent: Update the {% katex inline %}\theta{% endkatex %} parameters using the entire training set; slow but guaranteed to converge to the global minimum
2. Stochastic gradient descent: Update the {% katex inline %}\theta{% endkatex %} parameters using each training example; faster but may not converge to the global minimum due to randomness
3. Mini batch gradient descent: Update the {% katex inline %}\theta{% endkatex %} parameters using a small batch of training examples; compromise between efficiency and convergence

## Gradient descent derivatives

Imagine we have the following training data:

| x<sub>1</sub> | x<sub>2</sub> | y |
|---|---|---|
| 5 | 6 | 31.7 |
| 10 | 12 | 63.2 |
| 15 | 18 | 94.7 |
| 20 | 24 | 126.2 |
| ... | ... | ... |
| ... | ... | ... |
| 35 | 42 | 220.7 |

Our model will be:

{% katex %}
\hat{y} = \theta_0 + \theta_1{x_1} + \theta_2{x_2}
{% endkatex %}

Let's say we want to apply stochastic gradient descent.

Here are the steps we need to follow:

1. Set {% katex inline %}\alpha{% endkatex %} to 0.001 (say) and {% katex inline %}\theta_0{% endkatex %}, {% katex inline %}\theta_1{% endkatex %} and {% katex inline %}\theta_2{% endkatex %} to random values between -1 and 1
2. Take the first training example and use gradient descent to update {% katex inline %}\theta_0{% endkatex %}, {% katex inline %}\theta_1{% endkatex %} and {% katex inline %}\theta_2{% endkatex %} 
3. Repeat step 2 for each of the remaining training examples
4. Repeat the process from step 2 another 1000 times

Let's look at the expressions and derivatives needed, starting with the loss.

When we consider just one training example at a time, as with stochastic gradient descent, {% katex inline %}m = 1{% endkatex %}.

As such, the loss between our hypothesis {% katex inline %}\hat{y}{% endkatex %} and {% katex inline %}y{% endkatex %} can be described as:

{% katex %}
{Loss, l} = \frac{1}{2}(\hat{y} - y)^2
{% endkatex %}

Our gradient descent equation is:

{% katex %}
\theta_j = \theta_j - \alpha\dfrac{\mathrm{d}l}{\mathrm{d}\theta_j}
{% endkatex %}

To apply it, we need to determine:

{% katex %}
\dfrac{\mathrm{d}l}{\mathrm{d}\theta_j}
{% endkatex %}

Using the chain rule, we can say that:

{% katex %}
\dfrac{\mathrm{d}l}{\mathrm{d}\theta_j} = 
\dfrac{\mathrm{d}l}{\mathrm{d}(\hat{y} - y)}
.
\dfrac{\mathrm{d}(\hat{y} - y)}{\mathrm{d}\theta_j} 
{% endkatex %}

One of the linearity rules of derivatives tells us that when differentiating the addition or subtraction of two functions, we can differentiate the functions individually and then add or subtract them.

This means we can say:

{% katex %}
\dfrac{\mathrm{d}l}{\mathrm{d}\theta_j} = 
\dfrac{\mathrm{d}l}{\mathrm{d}(\hat{y} - y)}
.
\left[
\dfrac{\mathrm{d}\hat{y}}{\mathrm{d}\theta_j}-
\dfrac{\mathrm{d}y}{\mathrm{d}\theta_j}
\right]
{% endkatex %}

Since {% katex inline %}y{% endkatex %} does not change with respect to {% katex inline %}\theta{% endkatex %}:

{% katex %}
\dfrac{\mathrm{d}y}{\mathrm{d}\theta_j} = 0
{% endkatex %}

Therefore:

{% katex %}
\dfrac{\mathrm{d}l}{\mathrm{d}\theta_j} = 
\dfrac{\mathrm{d}l}{\mathrm{d}(\hat{y} - y)}
.
\dfrac{\mathrm{d}\hat{y}}{\mathrm{d}\theta_j}
{% endkatex %}

Let's now consider the two parts to this derivative, starting with the first:

{% katex %}
\dfrac{\mathrm{d}l}{\mathrm{d}(\hat{y} - y)}
{% endkatex %}

We can reduce this down:

{% katex %}
\dfrac{\mathrm{d}l}{\mathrm{d}(\hat{y} - y)} =
2.\frac{1}{2}(\hat{y} - y) = 
(\hat{y} - y)
{% endkatex %}

Now let's consider the second part of the derivative:

{% katex %}
\dfrac{\mathrm{d}\hat{y}}{\mathrm{d}\theta_j}
{% endkatex %}

We can this simplify this for {% katex inline %}\theta_0{% endkatex %}, {% katex inline %}\theta_1{% endkatex %} and {% katex inline %}\theta_2{% endkatex %} as follows:

{% katex %}
\dfrac{\mathrm{d}\hat{y}}{\mathrm{d}\theta_0} =
\dfrac{\mathrm{d}(\theta_0 + \theta_1{x_1} + \theta_2{x_2})}{\mathrm{d}\theta_0} = 1
{% endkatex %}

{% katex %}
\dfrac{\mathrm{d}\hat{y}}{\mathrm{d}\theta_1} =
\dfrac{\mathrm{d}(\theta_0 + \theta_1{x_1} + \theta_2{x_2})}{\mathrm{d}\theta_1} = x_1
{% endkatex %}

{% katex %}
\dfrac{\mathrm{d}\hat{y}}{\mathrm{d}\theta_2} =
\dfrac{\mathrm{d}(\theta_0 + \theta_1{x_1} + \theta_2{x_2})}{\mathrm{d}\theta_2} = x_2
{% endkatex %}

Let's now combine what we've worked out.

We found that:

{% katex %}
\theta_j = \theta_j - \alpha\dfrac{\mathrm{d}l}{\mathrm{d}\theta_j}
{% endkatex %}

Where:

{% katex %}
\dfrac{\mathrm{d}l}{\mathrm{d}\theta_j} = 
\dfrac{\mathrm{d}l}{\mathrm{d}(\hat{y} - y)}
.
\dfrac{\mathrm{d}\hat{y}}{\mathrm{d}\theta_j}
{% endkatex %}

And:

{% katex %}
\dfrac{\mathrm{d}l}{\mathrm{d}(\hat{y} - y)} =
(\hat{y} - y)
{% endkatex %}

Therefore we can say:

{% katex %}
\theta_0 = \theta_0 - \alpha\dfrac{\mathrm{d}l}{\mathrm{d}\theta_0} = \theta_0 - \alpha(\hat{y} - y)
{% endkatex %}

{% katex %}
\theta_1 = \theta_1 - \alpha\dfrac{\mathrm{d}l}{\mathrm{d}\theta_1} = \theta_1 - \alpha(\hat{y} - y)x_1
{% endkatex %}

{% katex %}
\theta_2 = \theta_2 - \alpha\dfrac{\mathrm{d}l}{\mathrm{d}\theta_2} = \theta_2 - \alpha(\hat{y} - y)x_2
{% endkatex %}

We now have all of the expressions needed to apply gradient descent. Over 1000 iterations, we might expect to see the total loss per iteration decrease like this.

![Total loss per iteration](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zwxf81oavhybn6whxewx.png)

In this post, we looked at the maths, specifically the partial derivatives, involved in applying gradient descent to linear regression.

For more information, check out Andrew Ng's Stanford CS229 lecture on [Linear Regression and Gradient Descent](https://www.youtube.com/watch?v=4b4MUYve_U8).