Understanding ML - the Gradient Descent from Math perspective

The Gradient Descent

The Gradient Descent is basically an optimization algorithm for finding a local minimum of a differentiable function.

• Gradient descent is simply used to find the values of a function’s parameters (coefficients) that minimize a cost function as far as possible.
• Our goal is to find the minimum of this function using the gradient descent methodology.

The simplest and the most fundamental optimization algorithm is the gradient descent.

• the gradient is the multivariate generalization of the derivative concept.

The basic idea - 1 parameter GD

A easy example, only show on 1 variate (1-parameter):

Let there is a formula

$$f(x) = 5x^2 + 2x - 1$$

We want to use Gradient descent to find the minimum point. To find the minimum point, we need to make use of the slope since the minimum point is basically slope = 0.

First we take a first the derivative (find the slope of the curve in a given particular point $x$):

$$f'(x) = \frac{df(x)}{dx} = 10x + 2$$

Then we choose any arbitrary number to represent $x$.

This “choose any arbitrary number” is called Initialization, the process in which we set the initial values of weights.

• If $f'(x)$ is +ve, It means the slope is / and we want to move left to slide to minimum point.
• If $f'(x)$ is -ve, It means the slope is \ and we want to move right to slide to minimum point.

The update rule is like this:

$$\mathrm{x}_{\mathrm{k}+1}=\mathrm{x}_{\mathrm{k}}-\eta \mathrm{f}^{\prime}\left(\mathrm{x}_{\mathrm{k}}\right)$$

where $\eta$ is the learning rate. the learning rate allow us to adjust how much do we want to slide.

Some people will notate as this:

$x = x + \Delta x$

where $\Delta$ means changes.

\text{new weight} = \text{existing_weight} - \text{learning_rate} \times \text{gradient}

Let our inital x value $x_0 = 3$ , learning rate $\eta = 0.06$

The 1st iteration: $x_1 = 3 - 32 \times 0.06 = 1.08$ ($f'(x_k)$ is +ve -> Slope is / -> Point goes left)

The 2nd iteration: $x_2 = 1.08 - 12.8 \times 0.06 = 0.312$ ($f'(x_k)$ is +ve -> Slope is / -> Point goes left)

The 3rd iteration: $x_3 = 0.312 - 5.12 \times 0.06 = 0.0048$ ($f'(x_k)$ is +ve -> Slope is / -> Point goes left)

The 4th iteration: $x_4 = 0.0048 - 2.048 \times 0.06 = -0.11808$ ($f'(x_k)$ is +ve -> Slope is / -> Point goes left)

The 5th iteration: $x_5 = -0.11808 - 0.8192 \times 0.06 = -0.167232$ ($f'(x_k)$ is -ve -> Slope is / -> Point goes left)

…

• If $x_{k+1}$ is smaller than $x_k$, $x_{k+1}$ will be the left side of $x_k$.
• If $x_{k+1}$ is larger than $x_k$, $x_{k+1}$ will be the right side of $x_k$.

The process goes on and on, eventually the value will stop updating.

• because the first derivative of the function will be very close to 0 when we have reached the minimum.
• Usually, we iterate until overall loss stops changing or at least changes extremely slowly. When that happens, we say that the model has converged.

Let’s visualize it. I coded a simple one using matplotlib.

The 1st iteration:

The 3rd iteration:

We can see the point is running towards to minimum point.

The 10th iteration:

It is reaching the minimum point.

To conclude, We can start from any arbitrary point and descend to the minimum. And the speed of minimization depends on the learning rate $\eta$.

# Just quickly hardcode a program to check will it really be stop updating
learning_rate = 0.06

x = 3

for i in range(50):
  diff = (10 * x) + 2
  x = x - (diff * learning_rate)

  print(x)
  # x will stuck at around -0.19999999999999998

How do we initialize the starting $x$ ?

As we mentioned , the initial $x$ is chosen arbitrarily, as it will slide during GD.

Pick $x$ arbitrarily is good enough in this case, but not for all cases. An inappropriate initialization would cause in unoptimized model. There are other ways of initializing the weight such as Xavier Initialization (will be explained in the future).

GD initialization is stuck

If Gradient Descent gets initialized in such a way that it starts at a local maximum (or a saddle point, or a local minimum) with gradient zero, then it will simply stay stuck there. Variations of GD, such as Stochastic GD and Mini-batch GD try to work around this by adding an element of randomness to the search, but even those aren’t guaranteed to escape a zero gradient region if the shape of the gradient is weird enough.

In practice the only way to solve this is to reinitialize your search with new weights or parameters that start in a completely new region of the search space. This won’t be hard to do, since if you do get stuck in such a zero-gradient area you will notice very quickly that the error in your training isn’t changing at all, and you would know that you need to start over.

How about learning rate?

How to choose the learning rate?

Reducing Loss: Learning Rate

TLDR:

• If you pick a learning rate that is too small, learning will take too long.
• If you pick a learning rate that is too large, it may totally overshoots the minimum, or result in oscillation and never reach the minimum.
• Generally, we want the learning rate to be high enough so we can reach the closest minimum in a rational amount of time, but low enough so it will not oscillate around the minimum.
• The ideal learning rate in one-dimension is $\frac{1}{f(x)^{\prime \prime}}$ (the inverse of the second derivative of $f(x)$ at $x$ .
• The ideal learning rate for 2 or more dimensions is the inverse of the Hessian (matrix of second partial derivatives).

If you have large but not too large learning rate, the point could descend like this:

It will also reach the minimum point eventually.

The interactive visualizer in this image: Reducing Loss: Optimizing Learning Rate - Graph Visualizer by Google Developers

The ML approach - N parameters GD

Video : The mathematics behind Linear Regression with Gradient Descent

Now moving to a ML approach.

In Machine Learning, the problem is often contains more parameters. In this example we will take a look into a linear model is using a 2-parameters GD.

$$y = w_1x + w_0$$

• For 2 model parameters, we only need to solve 2 simultaneous equations.
• For n model parameters, we need to solve n simultaneous equations.
  • e.g. $y = w_2x_2+w_1x_1 + w_0$ -> 3 simultaneous equations

To make it clearer to see, I use $m$ for $w_1$ and $b$ for $w_0$ .

Lets look at this linear model.

the formula $\hat{y} = mx + b$

$y = \text{true value}$

$\hat{y} = \text{predicted value}$

$$\text{Loss function} = L = (y-\hat{y})^2$$

• For simplicity, Lets just assume we only have 1 point data here. (Data point $N = 1$)
• So the Loss function will simply equal to $(y-\hat{y})^2$

Further reading : Objective function, cost function, loss function: are they the same thing?

We want to minimize the loss function. (find minima)

This bring us to the Gradient Descent.

The Update rule:

$$\begin{array}{l} \mathbf{m}_{i+1}=\mathbf{m}_{i}-\eta \nabla_{m} L\\ \mathbf{b}_{i+1}=\mathbf{b}_{i}-\eta \nabla_{b} L \end{array}$$

Some people will notate as this:

$m = m + \Delta m$

$b = b + \Delta b$

where $\Delta$ means changes.

So I want to know what is a way that I could change the value of $m$ in $y = mx + b$ in order to make the error less.

Our final goal is to solve for $m$ and $b$ by considering $\Delta m = 0$ and $\Delta b = 0$, just like what we did in the .

Lets substitute Error $E$ to $y - \hat{y}$

$$\text{Error} = E = y - \hat{y} = y - (mx+b)$$

So now our Loss function $L$ looks like:

$$L = (E)^2$$

Now we want to find the derivatives of $L$ relative to $b$.

Power rule is used here. $x^2 \rightarrow 2x$

Then Chain rule occur.

Since $L$ is a function of Error $E$, and Error $E$ is a function of $m$ and $b$.

$\frac{\partial L}{\partial b} = \frac{\partial L}{\partial E} \times \frac{\partial E}{\partial b}$

$$\frac{\partial L}{\partial b} = 2E \times \frac{\partial E}{\partial b}$$

Since $E = y - mx - b$

$\frac{\partial E}{\partial b} = -1$

Therefore:

$$\frac{\partial L}{\partial b} = 2E \times -1$$

Then multiple with a learning rate $\eta$

$$\frac{\partial L}{\partial b}\times \eta = E \times -1 \times \eta \times 2$$

Since we are multiplying with a constant learning rate $\eta$, it is pointless to have 2 here.

$$\Delta b = \frac{\partial L}{\partial b}\times \eta = E \times -\eta$$

$$\Delta b = -\eta E$$

Now we do the same on $m$. find the derivatives of $L$ relative to $m$ ($m$ is $w_1$).

Power rule is used here. $x^2 \rightarrow 2x$

Then Chain rule occur.

Since $L$ is a function of Error $E$, and Error $E$ is a function of $m$ and $b$.

$\frac{\partial L}{\partial m} = \frac{\partial L}{\partial E} \times \frac{\partial E}{\partial m}$

$$\frac{\partial L}{\partial m} = 2E \times \frac{\partial L}{\partial m}$$

Since $E = y - mx - b$

$\frac{\partial E}{\partial m} = -x$

Therefore:

$$\frac{\partial L}{\partial m} = 2E \times -x$$

Then multiple with a learning rate $\mu$

$$\frac{\partial L}{\partial m}\times \mu = E \times -x \times \mu \times 2$$

Since we are multiplying with a constant learning rate $\mu$, it is pointless to have 2 here.

$$\Delta m = \frac{\partial L}{\partial m}\times \mu = E \times -x \times \mu$$

$$\Delta m = -\mu xE$$

Therefore, during the training:

$$m_{k+1} = m_k - \mu xE$$

$$b_{k+1} = b_k - \eta E$$

In code representation (from https://youtu.be/L-Lsfu4ab74?t=1199)

function gradientDescent(){
  var learning_rate = 0.05;
  
  for (var i = 0; i < data.length; i++){
    var x = data[i].x;
    var y = data[i].y;
    var guess = m * x + b;
    var error = y - guess;
    m = m + (error * x) * learning_rate;
    b = b + (error) * learning_rate;
  }
}

Now lets look at a practical example.

Gradient Descent in Linear / Logistic regression

Linear relationship:

$$\hat{y}=ax+b$$

Cost function: mean-square error (MSE)

• Square difference between the observed data (y) and the predicted data (ax+b)
• Lets assume our data is not 1 point only but multiple points (N points)

$$\text{Cost function} =\frac{1}{N} \sum_{i=0}^{N-1}(y_i-a x_i-b)^{2}$$

Let $J$ be the Cost function.

Problem definition:

Find a and b so that Cost function is minimized

$$J_{(a,b)} =\frac{1}{N} \sum_{i=1}^{N}\left(y_{i}-a x_{i}-b\right)^{2}$$

To minimize the cost function, we solve for a and b by considering

$$\frac{\partial J}{\partial a}=0, \frac{\partial J}{\partial b}=0$$

In other words, to find a point where slope = 0. That minimum is where the cost function converges.

• For 2 model parameters, we only need to solve 2 simultaneous equations.
• For n model parameters, we need to solve n simultaneous equations.
  • e.g. $y = w_2x_2+w_1x_1 + w_0$ -> 3 simultaneous equations

First look at $b$ :

b is ($w_0$)

How do we do Derivative with summation operator?

It is a finite sum, just differentiate each term and sum up!

the idea is like this:

$\frac{d}{d t} \sum_{n=0}^{k-1} f_{n}(t)=\frac{d}{d t}\left(f_{0}(t)+\cdots+f_{k-1}(t)\right)=\frac{d f_{0}}{d t}+\cdots+\frac{d f_{k-1}}{d t}=\sum_{n=0}^{k-1} \frac{d f_{n}}{d t}$

$\sum\left(f_{n}(t)+g_{n}(t)\right)=\sum f_{n}(t)+\sum g_{n}(t)$

Therefore we need not worry about the summation operator, just do the differentiation first.

$$\frac{\partial J}{\partial b} = \frac{1}{N}\sum_{i=1}^{N}(2\left(y_{i}-a x_{i}-b\right)\times(-1))$$

To solve for $b$:

$$\frac{2}{N}\sum_{i=1}^{N}(\left(y_{i}-a x_{i}-b\right)\times(-1)) = 0$$

$$\sum_{i=1}^{N}(-y_{i}+a x_{i}+b) = -\sum_{i=1}^{N}y_{i} + a\sum_{i=1}^{N}x_{i} + Nb = 0$$

$$b = \frac{1}{N}(\sum_{i=1}^{N}y_{i} - a\sum_{i=1}^{N}x_{i})$$

Then multply with a learning rate $\eta$.

$$\Delta b = \frac{\partial J}{\partial b}\times \mu = \mu \times \frac{2}{N}\sum_{i=1}^{N}(\left(y_{i}-a x_{i}-b\right)\times(-1))$$

Then look at $a$:

a is $(w_1)$

$$\frac{\partial J}{\partial a} = \frac{1}{N}\sum_{i=1}^{N}(2\left(y_{i}-a x_{i}-b\right)\times(-x_i))$$

To solve for $a$:

$$\frac{2}{N}\sum_{i=1}^{N}(\left(y_{i}-a x_{i}-b\right)\times(-x_i)) = 0$$

$$\sum_{i=1}^{N}(y_{i}x_i -a x_{i}^2-bx_i) = \sum_{i=1}^{N}y_{i}x_i - a\sum_{i=1}^{N}x_{i}^2-b\sum_{i=1}^{N}x_i = 0$$

$$a\sum_{i=1}^{N}x_{i}^2 = \sum_{i=1}^{N}y_{i}x_i -b\sum_{i=1}^{N}x_i$$

Since $b = \frac{1}{N}(\sum_{i=1}^{N}y_{i} - a\sum_{i=1}^{N}x_{i})$

substitute it into the formula

$$a\sum_{i=1}^{N}x_{i}^2 = \sum_{i=1}^{N}y_{i}x_i -(\frac{1}{N}(\sum_{i=1}^{N}y_{i} - a\sum_{i=1}^{N}x_{i}))\sum_{i=1}^{N}x_i$$

$$a\sum_{i=1}^{N}x_{i}^2 = \sum_{i=1}^{N}y_{i}x_i -\frac{1}{N}\sum_{i=1}^{N}y_{i}\sum_{i=1}^{N}x_i +\frac{1}{N} a(\sum_{i=1}^{N}x_{i})^2$$

$$a(\sum_{i=1}^{N}x_{i}^2 - \frac{1}{N}(\sum_{i=1}^{N}x_{i})^2) = \sum_{i=1}^{N}y_{i}x_i -\frac{1}{N}\sum_{i=1}^{N}y_{i}\sum_{i=1}^{N}x_i$$

$$a = \frac{\sum_{i=1}^{N}y_{i}x_i -\frac{1}{N}\sum_{i=1}^{N}y_{i}\sum_{i=1}^{N}x_i}{\sum_{i=1}^{N}x_{i}^2 - \frac{1}{N}(\sum_{i=1}^{N}x_{i})^2 }$$

$$a = \frac{\sum_{i=1}^{N}y_{i}x_i -\frac{1}{N}\sum_{i=1}^{N}y_{i}\sum_{i=1}^{N}x_i}{\sum_{i=1}^{N}x_{i}^2 - \frac{1}{N}(\sum_{i=1}^{N}x_{i})^2 } \times \frac{N}{N}$$

$$a = \frac{N\sum_{i=1}^{N}y_{i}x_i -\sum_{i=1}^{N}y_{i}\sum_{i=1}^{N}x_i}{N\sum_{i=1}^{N}x_{i}^2 - (\sum_{i=1}^{N}x_{i})^2 }$$

Then multply with a learning rate $\eta$.

$$\Delta a = \frac{\partial J}{\partial a}\times \eta = \eta \times \frac{2}{N}\sum_{i=1}^{N}(\left(y_{i}-a x_{i}-b\right)\times(-x_i))$$

Therefore, during the training stage:

$$\begin{array}{c} a_{k+1}=a_{k}+\Delta a \\ b_{k+1}=b_{k}+\Delta b \end{array}$$

where

$$\begin{array}{l} \Delta a=-\mu \frac{\partial J}{\partial a} \\ \Delta b=-\mu \frac{\partial J}{\partial b} \end{array}$$