Gradient Descent

Posted on by

the Diploma thesis learning –

Machine learning has multiple methods to gradually improve solution by moving closer with intermediate result. One of more sophisticated methods is the Gradient Descent. Gradient descent is functional approach where you often approximate the result with some regard to difference of real (eg. measured) value and the predicted (function) value. In the statistics the difference is called error or the residual and is often used as cost function. The Gradient Descent tries to minimize the cost function.

There are two main types of functions – the loss function and the cost function. The loss function is function which displays the loss on one sample, one element, whereas the cost function is total of all the individual loss functions combined.

For example for linear regression we can use as cost function the Mean Squared Error (MSE). MSE displays how far from actual value the predicted value is. In other words how bad was the guess. The equation for Mean Squared Error is

 (1)    \begin{equation*}  MSE = \frac{1}{m} \sum_{i=1}^{m}{(\hat{y}_{i} - y_{i})^2} \end{equation*}

or vectorized MSE = \frac{1}{m}(\hat{y} - y)^T(\hat{y} - y) where \hat{y} is predicted value of model based on some parameters X, y is real value for the parameters and m is a number of measurements.

If we are looking on linear regression and our model \hat{y} is equal to \hat{y_i} = \beta_0 + \beta_1 X_i for any X_i from vector X (that is vector of size (1\times m)) and X^*_i is simplified version for multiplying the vectors in \hat{y} = X^* \times \theta to create \hat{y_i} = \beta_0 + \beta_1 X_i.

  
 (2)    \begin{align*}     X &= \begin{bmatrix}            x_{1} \\            x_{2} \\            \vdots \\            x_{m}          \end{bmatrix}, &     X^* &= \begin{bmatrix}            1  & x_{1} \\            1  & x_{2} \\            \vdots & \vdots \\            1  & x_{m}          \end{bmatrix}, &    \theta =          \begin{bmatrix}            \beta_0 \\            \beta_1          \end{bmatrix}, & &     y &= \begin{bmatrix}            y_{1} \\            y_{2} \\            \vdots \\            y_{m}          \end{bmatrix}   \end{align*}

Expanding the calculation based on MSE = \frac{1}{m}(\hat{y} - y)^T(\hat{y} - y) for \hat{y} = X^* \times \theta and y. First we are counting the loss function \hat{y} - y.

  
 (3)    \begin{align*}     (\hat{y} - y) &=     \Bigg(    \begin{bmatrix}            1  & x_{1} \\            1  & x_{2} \\            \vdots & \vdots \\            1  & x_{m}          \end{bmatrix}    \times    \begin{bmatrix}            \beta_0 \\            \beta_1          \end{bmatrix} -     \begin{bmatrix}            y_{1} \\            y_{2} \\            \vdots \\            y_{m}          \end{bmatrix}   \Bigg)\\     &=    \Bigg(    \begin{bmatrix}            \beta_0  + \beta_1 x_{1} \\            \beta_0  + \beta_1 x_{2} \\            \vdots & \vdots \\            \beta_0  + \beta_1 x_{m}          \end{bmatrix} -     \begin{bmatrix}            y_{1} \\            y_{2} \\            \vdots \\            y_{m}          \end{bmatrix}   \Bigg)\\    &=         \begin{bmatrix}            \beta_0  + \beta_1 x_{1} - y_{1}\\            \beta_0  + \beta_1 x_{2} - y_{2}\\            \vdots  \\            \beta_0  + \beta_1 x_{m} - y_{m}          \end{bmatrix}   \end{align*}

where again MSE = \frac{1}{m} (\hat{y} - y)^T(\hat{y} - y) is equal to

  
 (4)    \begin{align*}     MSE &= \frac{1}{m}           \times \begin{bmatrix}            \beta_0  + \beta_1 x_{1} - y_{1} &            \beta_0  + \beta_1 x_{2} - y_{2} &            \hdots  &            \beta_0  + \beta_1 x_{m} - y_{m}          \end{bmatrix}    \times         \begin{bmatrix}            \beta_0  + \beta_1 x_{1} - y_{1}\\            \beta_0  + \beta_1 x_{2} - y_{2}\\            \vdots  \\            \beta_0  + \beta_1 x_{m} - y_{m}          \end{bmatrix} \\     &= \frac{1}{m}{           \times (            (\beta_0  + \beta_1 x_{1} - y_{1})(\beta_0  + \beta_1 x_{1} - y_{1}) +            \hdots           )} \\     &= \frac{1}{m}           \times (            (\beta_0^2 + \beta_0\beta_1 x_{1} - \beta_0 y_{1}) + (\beta_0 \beta_1 x_{1}  + \beta_1^2 x_{1}^2 - \beta_1 x_{1} y_{1}) + (-\beta_0 y_{1} - \beta_1 x_{1} y_{1} + y_{1}^2) +            \hdots           ) \\     &= \frac{1}{m}           \times (            (\beta_0^2 + 2 \beta_0\beta_1 x_{1} - 2 \beta_0 y_{1} + \beta_1^2 x_{1}^2 - 2 \beta_1 x_{1} y_{1} + y_{1}^2) +            \hdots           )\\     &= \frac{1}{m}           \times             \sum_{i=1}^{m}{(\beta_0^2 + 2 \beta_0\beta_1 x_{i} - 2 \beta_0 y_{i} + \beta_1^2 x_{i}^2 - 2 \beta_1 x_{i} y_{i} + y_{i}^2)}   \end{align*}

The Mean Squared Errror is great in telling how far from real values our prediction is, but it has problem of not telling us which way to go (as it is squared, so it is always positive). That is why it is necessary to create partial derivation of MSE (gradient).

To simplify the equations we will halve the MSE. Using \frac{MSE}{2} does not really matter as we are changing the cost function by a scalar while searching for the minimum of the function.

  
 (5)    \begin{align*}     MSE &= \frac{1}{2m}           \times             \sum_{i=1}^{m}{(\beta_0^2 + 2 \beta_0\beta_1 x_{i} - 2 \beta_0 y_{i} + \beta_1^2 x_{i}^2 - 2 \beta_1 x_{i} y_{i} + y_{i}^2)}   \end{align*}

The cost function (in this case \frac{MSE}{2}) can be partially derived for each parameter of \theta (in this case [\beta_0 \beta_1]).

  
 (6)    \begin{align*}     \frac{df}{d\beta_0} &= \frac{1}{2m}           \times             \sum_{i=1}^{m}{(2\beta_0 + 2 \beta_1 x_{i} - 2 y_{i})}\\        &= \frac{1}{m}           \times             \sum_{i=1}^{m}{(\beta_0 + \beta_1 x_{i} - y_{i})}   \end{align*}
  
 (7)    \begin{align*}     \frac{df}{d\beta_1} &= \frac{1}{2m}           \times             \sum_{i=1}^{m}{(2 \beta_0 x_{i} + 2 \beta_1 x_{i}^2 - 2 x_{i} y_{i})}\\       &= \frac{1}{m}           \times             \sum_{i=1}^{m}{x_{i} (\beta_0 + \beta_1 x_{i} - y_{i})}   \end{align*}

Using differentiation we can approach the local minimum using slope of the function (the slope is described by the first derivative). Having MSE function we can do partial derivation for each of the parameters and subtract the part of the slope of the previous solution to better approximate the function. 

 (8)    \begin{align*}     \theta_{new} &= \theta_{old} - \alpha \frac{df}{d\theta}   \end{align*}

Now having the partial derivatives it is time to use them to improve the parameters. Only thing remaining is choosing the correct step size \alpha. It is important to choose proper size. Choose too big steps and it would mean jumping too far a back. Choose too small step size and it will take close to infinite amount of time to improve the parameters.. Often simple 1% change (\alpha = 0.01) in time seems like a good fit as it is simple enough to not complicate the counting yet big enough to make change in time.

 (9)    \begin{align*}     \theta_{new} &= \theta_{old} - \alpha \frac{df}{d\theta}\\     \begin{bmatrix}            \beta_0\\            \beta_1       \end{bmatrix}_{new} &= \begin{bmatrix}            \beta_0\\            \beta_1       \end{bmatrix}_{old} - \alpha \begin{bmatrix}            \frac{df}{d\beta_0}\\\            \frac{df}{d\beta_1}\       \end{bmatrix}   \end{align*}

And this is one iteration of Gradient Descent. Now few hundred, maybe thousands (depending on model and initial guess), to converge to local minimum.