Skip to main content
Data Science

Return to Answer

added 8594 characters in body
Source Link
JahKnows
JahKnows
  • 9.1k
  • 30
  • 45

Supplemental

2D gradient descent of a function

$y = x_1^2 - x_1 + x_2^2 - 3x_2$

The partial derivatives are

$\frac{\partial y}{\partial x_1} = 2x_1 - 1$

$\frac{\partial y}{\partial x_2} = 2x_2 - 3$

Thus,

$\nabla y = (2x_1 - 1, 2x_2 - 3)$.

Our update rule with a learning rate $\nu = 0.1$ will then be

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.0 \\ 0.0 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.0 - 1 \\ 2 * 0.0 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.1 \\ 0.3 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.1 \\ 0.3 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.1 - 1 \\ 2 * 0.3 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.18 \\ 0.54 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.18 \\ 0.54 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.18 - 1 \\ 2 * 0.54 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.24 \\ 0.73 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.24 \\ 0.73 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.24 - 1 \\ 2 * 0.73 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.29 \\ 0.88 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.29 \\ 0.88 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.29 - 1 \\ 2 * 0.88 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.33 \\ 1.00 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.33 \\ 1.00 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.33 - 1 \\ 2 * 1.00 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.36 \\ 1.10 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.36 \\ 1.10 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.36 - 1 \\ 2 * 1.10 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.39 \\ 1.18 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.39 \\ 1.18 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.39 - 1 \\ 2 * 1.18 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.41 \\ 1.24 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.41 \\ 1.24 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.41 - 1 \\ 2 * 1.24 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.43 \\ 1.29 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.43 \\ 1.29 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.43 - 1 \\ 2 * 1.29 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.44 \\ 1.33 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.44 \\ 1.33 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.44 - 1 \\ 2 * 1.33 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.45 \\ 1.37 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.45 \\ 1.37 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.45 - 1 \\ 2 * 1.37 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.46 \\ 1.39 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.46 \\ 1.39 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.46 - 1 \\ 2 * 1.39 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.47 \\ 1.41 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.47 \\ 1.41 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.47 - 1 \\ 2 * 1.41 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.47 \\ 1.43 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.47 \\ 1.43 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.47 - 1 \\ 2 * 1.43 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.48 \\ 1.44 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.48 \\ 1.44 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.48 - 1 \\ 2 * 1.44 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.48 \\ 1.45 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.48 \\ 1.45 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.48 - 1 \\ 2 * 1.45 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.48 \\ 1.46 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.48 \\ 1.46 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.48 - 1 \\ 2 * 1.46 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.47 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.47 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.49 - 1 \\ 2 * 1.47 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.47 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.47 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.49 - 1 \\ 2 * 1.47 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.48 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.48 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.49 - 1 \\ 2 * 1.48 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.48 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.48 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.49 - 1 \\ 2 * 1.48 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.48 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.48 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.49 - 1 \\ 2 * 1.48 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.49 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.49 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.49 - 1 \\ 2 * 1.49 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.49 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.49 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.49 - 1 \\ 2 * 1.49 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.49 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.49 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.49 - 1 \\ 2 * 1.49 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.49 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.49 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.49 - 1 \\ 2 * 1.49 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.49 \end{array}\right)$

And we have convergence in 2D at those points above!

Supplemental

2D gradient descent of a function

$y = x_1^2 - x_1 + x_2^2 - 3x_2$

The partial derivatives are

$\frac{\partial y}{\partial x_1} = 2x_1 - 1$

$\frac{\partial y}{\partial x_2} = 2x_2 - 3$

Thus,

$\nabla y = (2x_1 - 1, 2x_2 - 3)$.

Our update rule with a learning rate $\nu = 0.1$ will then be

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.0 \\ 0.0 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.0 - 1 \\ 2 * 0.0 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.1 \\ 0.3 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.1 \\ 0.3 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.1 - 1 \\ 2 * 0.3 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.18 \\ 0.54 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.18 \\ 0.54 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.18 - 1 \\ 2 * 0.54 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.24 \\ 0.73 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.24 \\ 0.73 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.24 - 1 \\ 2 * 0.73 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.29 \\ 0.88 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.29 \\ 0.88 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.29 - 1 \\ 2 * 0.88 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.33 \\ 1.00 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.33 \\ 1.00 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.33 - 1 \\ 2 * 1.00 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.36 \\ 1.10 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.36 \\ 1.10 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.36 - 1 \\ 2 * 1.10 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.39 \\ 1.18 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.39 \\ 1.18 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.39 - 1 \\ 2 * 1.18 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.41 \\ 1.24 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.41 \\ 1.24 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.41 - 1 \\ 2 * 1.24 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.43 \\ 1.29 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.43 \\ 1.29 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.43 - 1 \\ 2 * 1.29 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.44 \\ 1.33 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.44 \\ 1.33 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.44 - 1 \\ 2 * 1.33 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.45 \\ 1.37 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.45 \\ 1.37 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.45 - 1 \\ 2 * 1.37 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.46 \\ 1.39 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.46 \\ 1.39 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.46 - 1 \\ 2 * 1.39 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.47 \\ 1.41 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.47 \\ 1.41 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.47 - 1 \\ 2 * 1.41 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.47 \\ 1.43 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.47 \\ 1.43 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.47 - 1 \\ 2 * 1.43 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.48 \\ 1.44 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.48 \\ 1.44 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.48 - 1 \\ 2 * 1.44 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.48 \\ 1.45 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.48 \\ 1.45 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.48 - 1 \\ 2 * 1.45 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.48 \\ 1.46 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.48 \\ 1.46 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.48 - 1 \\ 2 * 1.46 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.47 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.47 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.49 - 1 \\ 2 * 1.47 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.47 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.47 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.49 - 1 \\ 2 * 1.47 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.48 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.48 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.49 - 1 \\ 2 * 1.48 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.48 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.48 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.49 - 1 \\ 2 * 1.48 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.48 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.48 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.49 - 1 \\ 2 * 1.48 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.49 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.49 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.49 - 1 \\ 2 * 1.49 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.49 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.49 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.49 - 1 \\ 2 * 1.49 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.49 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.49 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.49 - 1 \\ 2 * 1.49 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.49 \end{array}\right)$

$ \left(\begin{array}{cc} x_1^{new} \\ x_2^{new} \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.49 \end{array}\right) - 0.1 \left(\begin{array}{cc} 2 * 0.49 - 1 \\ 2 * 1.49 - 3 \end{array}\right) = \left(\begin{array}{cc} 0.49 \\ 1.49 \end{array}\right)$

And we have convergence in 2D at those points above!

added 757 characters in body
Source Link
JahKnows
JahKnows
  • 9.1k
  • 30
  • 45

$C = \sum_{i=0}^{N}(\hat{y} - y)^2$$C = \frac{1}{N} \sum_{i=0}^{N}(\hat{y} - y)^2$.

$\hat{\text{x}_1}$ and $\hat{\text{x}_2}$ are the two dimensions that we are optimizing over. So in our analogy we will go down this 2D surface a bit in the $x_1$ dimension and the $x_2$ dimension. Kind of like going down the mountain in the North-West direction. A bit in front and a bit to our left. That's a 2D direction!

The total size of the step that we take across all dimensions is then described by

$\Delta y = \frac{\partial y}{\partial x_1} \Delta x_1 + \frac{\partial y}{\partial x_2} \Delta x_2$.

Relating all this to your question

Change our function $y(x_1, x_2)$ by $C(v_1, v_2)$. The size of the step we are taking is defined by

$\Delta C = \frac{\partial C}{\partial v_1} \Delta v_1 + \frac{\partial C}{\partial v_2} \Delta v_2$.

At each gradient descent iteration we will update $v$ as

$v^{new} = v^{old} - \nu \nabla C$

where

$\nabla C = \frac{\partial C}{\partial v_1} \hat{\textbf{v}_1} + \frac{\partial C}{\partial v_2} \hat{\textbf{v}_2} = (\frac{\partial C}{\partial v_1}, \frac{\partial C}{\partial v_2})^T$

$C = \sum_{i=0}^{N}(\hat{y} - y)^2$.

$\hat{\text{x}_1}$ and $\hat{\text{x}_2}$ are the two dimensions that we are optimizing over. So in our analogy we will go down this 2D surface a bit in the $x_1$ dimension and the $x_2$ dimension. Kind of like going down the mountain in the North-West direction. A bit in front and a bit to our left. That's a 2D direction!

$C = \frac{1}{N} \sum_{i=0}^{N}(\hat{y} - y)^2$.

$\hat{\text{x}_1}$ and $\hat{\text{x}_2}$ are the two dimensions that we are optimizing over. So in our analogy we will go down this 2D surface a bit in the $x_1$ dimension and the $x_2$ dimension. Kind of like going down the mountain in the North-West direction. A bit in front and a bit to our left. That's a 2D direction!

The total size of the step that we take across all dimensions is then described by

$\Delta y = \frac{\partial y}{\partial x_1} \Delta x_1 + \frac{\partial y}{\partial x_2} \Delta x_2$.

Relating all this to your question

Change our function $y(x_1, x_2)$ by $C(v_1, v_2)$. The size of the step we are taking is defined by

$\Delta C = \frac{\partial C}{\partial v_1} \Delta v_1 + \frac{\partial C}{\partial v_2} \Delta v_2$.

At each gradient descent iteration we will update $v$ as

$v^{new} = v^{old} - \nu \nabla C$

where

$\nabla C = \frac{\partial C}{\partial v_1} \hat{\textbf{v}_1} + \frac{\partial C}{\partial v_2} \hat{\textbf{v}_2} = (\frac{\partial C}{\partial v_1}, \frac{\partial C}{\partial v_2})^T$

Source Link
JahKnows
JahKnows
  • 9.1k
  • 30
  • 45

What's the point?

First, it is good to understand what we are doing that leads us to need these tools. When we are trying to apply machine learning we want to infer some meaning from data. This means that given an instance we want to put it through our model and then we can have some output that tell us something about this data.

Let's look at the example where we try to label whether an image contains a cat or a dog. If we have a perfect model, we can give the model a picture and it will tell us if it is a cat or a dog. However, no model is perfect and it will make mistakes.

When we train our model to be able to infer meaning from input data we want to minimize the amount of mistakes it makes. So we use a training set, this data contains a lot of pictures of dogs and cats and we have the ground truth label associated with that image. Each time we run a training iteration of the model we calculate the cost (the amount of mistakes) of the model. We will want to minimize this cost.

Many cost functions exist each serving their own purpose. A common cost function that is used is the quadratic cost which is defined as

$C = \sum_{i=0}^{N}(\hat{y} - y)^2$.

This is the square of the difference between the predicted label and the ground truth label for the $N$ images that we trained over. We will want to minimize this in some way. The cost is also commnly called the loss function.

So we have a minimization problem on our hands!

Indeed most of machine learning is simply a family of frameworks which are capable of determining a distribution by minimizing some cost function. The question we can ask is "how can we minimize a function"?

Let's minimize the following function

$y = x^2-4x+6$.

If we plot this we can see that there is a minimum at $x = 2$. To do this analytically we can take the derivative of this function as

$\frac{dy}{dx} = 2x - 4 = 0$

$x = 2$.

However, often times finding a global minimum analytically is not feasible. So instead we use some optimization techniques. Here as well many different ways exist such as : Newton-Raphson, grid search, etc. Among these is gradient descent.

How does gradient descent work?

Let's use a famously used analogy to understand this. Imagine a 2D minimization problem. This is equivalent of being on a mountainous hike in the wilderness. You want to get back down to the village which you know is at the lowest point. Even if you do not know the cardinal directions of the village. All you need to do is continuously take the steepest way down, and you will eventually get to the village. So we will descend down the surface based on the steepness of the slope.

Let's take our function

$y = x^2-4x+6$

we will determine the $x$ for which $y$ is minimized. Gradient descent algorithm first says we will pick a random value for $x$. Let us initialize at $x=8$. Then the algorithm will do the following iteratively until we reach convergence.

$x^{new} = x^{old} - \nu \frac{dy}{dx}$

where $\nu$ is the learning rate, we can set this to whatever value we will like. However there is a smart way to choose this. Too big and we will never reach our minimum value, and too large we will waste soooo much time before we get there. It is analogous to the size of the steps you want to take down the steep slope. Small steps and you will die on the mountain, you'll never get down. Too large of a step and you risk over shooting the village and ending up the other side of the mountain.

$\frac{dy}{dx} = 2x - 4$

$\nu = 0.1$

Iteration 1:

$x^{new} = 8 - 0.1(2 * 8 - 4) = 6.8 $
$x^{new} = 6.8 - 0.1(2 * 6.8 - 4) = 5.84 $
$x^{new} = 5.84 - 0.1(2 * 5.84 - 4) = 5.07 $
$x^{new} = 5.07 - 0.1(2 * 5.07 - 4) = 4.45 $
$x^{new} = 4.45 - 0.1(2 * 4.45 - 4) = 3.96 $
$x^{new} = 3.96 - 0.1(2 * 3.96 - 4) = 3.57 $
$x^{new} = 3.57 - 0.1(2 * 3.57 - 4) = 3.25 $
$x^{new} = 3.25 - 0.1(2 * 3.25 - 4) = 3.00 $
$x^{new} = 3.00 - 0.1(2 * 3.00 - 4) = 2.80 $
$x^{new} = 2.80 - 0.1(2 * 2.80 - 4) = 2.64 $
$x^{new} = 2.64 - 0.1(2 * 2.64 - 4) = 2.51 $
$x^{new} = 2.51 - 0.1(2 * 2.51 - 4) = 2.41 $
$x^{new} = 2.41 - 0.1(2 * 2.41 - 4) = 2.32 $
$x^{new} = 2.32 - 0.1(2 * 2.32 - 4) = 2.26 $
$x^{new} = 2.26 - 0.1(2 * 2.26 - 4) = 2.21 $
$x^{new} = 2.21 - 0.1(2 * 2.21 - 4) = 2.16 $
$x^{new} = 2.16 - 0.1(2 * 2.16 - 4) = 2.13 $
$x^{new} = 2.13 - 0.1(2 * 2.13 - 4) = 2.10 $
$x^{new} = 2.10 - 0.1(2 * 2.10 - 4) = 2.08 $
$x^{new} = 2.08 - 0.1(2 * 2.08 - 4) = 2.06 $
$x^{new} = 2.06 - 0.1(2 * 2.06 - 4) = 2.05 $
$x^{new} = 2.05 - 0.1(2 * 2.05 - 4) = 2.04 $
$x^{new} = 2.04 - 0.1(2 * 2.04 - 4) = 2.03 $
$x^{new} = 2.03 - 0.1(2 * 2.03 - 4) = 2.02 $
$x^{new} = 2.02 - 0.1(2 * 2.02 - 4) = 2.02 $
$x^{new} = 2.02 - 0.1(2 * 2.02 - 4) = 2.01 $
$x^{new} = 2.01 - 0.1(2 * 2.01 - 4) = 2.01 $
$x^{new} = 2.01 - 0.1(2 * 2.01 - 4) = 2.01 $
$x^{new} = 2.01 - 0.1(2 * 2.01 - 4) = 2.00 $
$x^{new} = 2.00 - 0.1(2 * 2.00 - 4) = 2.00 $
$x^{new} = 2.00 - 0.1(2 * 2.00 - 4) = 2.00 $
$x^{new} = 2.00 - 0.1(2 * 2.00 - 4) = 2.00 $
$x^{new} = 2.00 - 0.1(2 * 2.00 - 4) = 2.00 $

And we see that the algorithm converges at $x = 2$!

Where do partial derivatives come into this?

We just minimized $y$ for $x$. But if we had a multi-dimensional $x$ then we will need to identify where is the steepest slope in each dimension. To do this we will take the derivative across each dimension. In 2 dimensions gradient descent is performed using the gradient of the function $\nabla y$.

For the function

$y = 2x_1^2 + 5x_1 - 4x_2^2$

we will take the gradient in both dimensions defined as

$x^{new} = x^{old} - \nu \nabla y$.

The operator $\nabla$ is called the gradient it is defined as

$\nabla y = \frac{\partial y}{\partial x_1} \hat{\textbf{x}_1} + \frac{\partial y}{\partial x_2} \hat{\textbf{x}_2}$.

$\hat{\text{x}_1}$ and $\hat{\text{x}_2}$ are the two dimensions that we are optimizing over. So in our analogy we will go down this 2D surface a bit in the $x_1$ dimension and the $x_2$ dimension. Kind of like going down the mountain in the North-West direction. A bit in front and a bit to our left. That's a 2D direction!