Applying gradient descent – primer / refresher

Every so often a problem arises where it’s appropriate to use gradient descent, and it’s fun (and / or easier) to apply it manually. Recently I’ve applied it optimising a basic recommender system to ‘unsuppressing’ suppressed tabular data. I thought I’d do a series of posts about how I’ve used gradient descent, but figured it was worth while starting with the basics as a primer / refresher.

Linear regression

To understand how this works gradient descent is applied we’ll use the classic example, linear regression.

A simple linear regression model is of the form

    \[\textbf{y} = \textbf{X}\boldsymbol{\beta}+\boldsymbol{\epsilon}\]

where

    \[\boldsymbol{\beta} = (\beta_0, \beta_1)^T\]

The objective is to find the parameters \boldsymbol{\beta} such that they minimise the mean squared error.

    \[MSE(\hat{y}) = \frac{1}{n}\sum_{i=1}^{n} (y_i-\hat{y}_i)^2\]

This is a good problem since we know the analytical solution and can check our results.

    \[\boldsymbol{\beta} = (\textbf{X}^{T}\textbf{X})^{-1}\textbf{X}^{T}\textbf{y}\]

In practice you would never use gradient descent to solve a regression problem, but it is useful for learning the concepts.

Example data

Set up

The analytical solution is given by

And just to convince ourselves this is correct

plot of chunk unnamed-chunk-3

Gradient descent

The objective is to achieve the same result using gradient descent. It works by updating the parameters with each iteration in the direction of negative gradient to minimise the mean squared error i.e.

    \[\boldsymbol{\hat{\beta}}_{t+1} = \boldsymbol{\hat{\beta}}_{t} -\gamma \nabla F(\boldsymbol{\hat{\beta}_t})\]

where \gamma is the learning rate. Here F(\boldsymbol{\hat{\beta}_t}) is the MSE with respect to the regression parameters. Firstly, we find the partial derivatives of F.

    \[\begin{aligned} \nabla F(\boldsymbol{\hat{\beta}_t}) &= \biggl( \frac{\partial F}{\partial \beta_0}, \frac{\partial F}{\partial \beta_1} \biggr) \\ &= -\frac{2}{n} \biggl(\sum_{i=1}^{n} \boldsymbol{x}_{i,0}(y_{i}-\boldsymbol{x}_{i}^{T}\boldsymbol{\hat{\beta}}_{t}), \sum_{i=1}^{n} \boldsymbol{x}_{i,1}(y_{i}-\boldsymbol{x}_{i}^{T}\boldsymbol{\hat{\beta}}_{t}) \biggr) \\ &= -\frac{2}{n} \textbf{X}^T (\textbf{y}-\textbf{X}\boldsymbol{\hat{\beta}}_{t}) \end{aligned}\]

The learning rate is to ensure we don’t jump too far with each iteration and rather some proportion of the gradient, otherwise we could end up overshooting the minimum and taking much longer to converge or not find the optimal solution at all.

Applying this to the problem above, we’ll initialise our values for \boldsymbol{\beta} to something sensible e.g. \boldsymbol{\beta} = (1,1)^T. I’ll choose a learning rate of \gamma=0.01. This is a slow burn, a learning rate of 0.1-0.2 is more appropriate for this problem but we’ll get to see the movement of the gradient better. It’s worth trying different values of \gamma to see how it changes convergence. The algorithm is setup as

plot of chunk unnamed-chunk-4

As expected we obtain the same result. The lines show the gradient and how the parameters converge to the optimal values. A less reasonable set of starting values still converges quickly to the optimal solution showing how well graident descent works on linear regression.

plot of chunk unnamed-chunk-5

Takeaways

They are the basics of applying gradient descent. In practice there is no need to use gradient descent to solve a regression problem, but once you know how to apply it you’ll find real-world applications elsewhere that are more complicated (and interesting). If you can define the objective function and it is differentiable, you can apply gradient descent. In later posts i’ll demonstrate how I’ve applied it to real world problems. Stay tuned!

Follow me on social media: