[K-MOOC] Introductory Mathematics for Artificial Intelligence
Translated by
Sang-Gu LEE with Youngju NIELSEN, Yoonmee HAM
from the original Korean text written by
Sang-Gu LEE with Jae Hwa LEE, Yoonmee HAM, Kyung-Eun PARK
Part Ⅲ. AI and Optimal solution(Calculus)
9. Gradient descent method
For any differentiable function 
that has the local minimum value at 
, then 
. Therefore, we need to find all points that satisfy 
,
critical points, first and then determine which of them will be the optimal solution. However, when the function is complicated,
it is not easy to solve the equation 
to find critical points. In such cases, the critical point can be obtained by a numerical method,
which is called the gradient descent method. The gradient descent method is also the core algorithm for updating the weights in deep learning.
9.1 Gradient descent method
*9.2 Application (least-square problem)
9.1. Gradient Descent Method
http://matrix.skku.ac.kr/math4ai/gradient_descent/
We now introduce the Gradient Descent Method to obtain an approximate solution to the least-squares problem numerically.
There is a problem of finding the minimum value of a one-variable function 
that can be differentiated as follows.
Then, the point 
giving the minimum value of the function (it is called the optimal solution) by [Fermat's critical point theorem] satisfies the following.
Therefore, we can determine which of the solutions satisfying the equation 
is the optimal solution.
However, when the function is complex, it is not easy to find a critical point by solving the equation. In this case, the critical point is obtained numerically.
In this section, we look at the gradient descent method, which is the most popular numerical optimization method to find the minimum value
of a given function. The basic idea of the gradient descent method is to find the slope of the function, move it toward downhill,
and repeat it until it reaches the extreme value.
|
[Gradient Descent Method] Algorithm [Step 1] Set an initial iterate rate [Step 2] Compute [Step 3] Set |
Let's explain this GDM algorithm. Set 
and compute 
. If 
(it satisfies the critical point theorem within the margin of error we allow),
then the algorithm stops and will give 
as the optimal solution. Here, 
(epsilon, tolerance) satisfies 
.
A notation ‘
’ in this inequality means that the epsilon is much smaller than 1. Hence, we give a small tolerance epsilon 
,
which is very close to zero, and with a learning rate 
. And let the iteration number 
be 1. If 
, 
is determined using the formula.
Then 
is calculated to determine whether or not the critical point theorem is satisfied. If the critical point theorem is not satisfied,
then 
is determined similarly. In this way, we create 
, 
, 
(
). If the value of 
is within a given tolerance
after some repeated steps 
, then the algorithm stops. We expect some 
or the limit 
to satisfy 
.
Let's see how the GDM works in detail. Suppose the slope of the tangent line to the function 
is negative at the approximate solution 
after the 
-th iteration. It is 
as shown in the figure below. This means the function decreases when 
moves from left to right,
so we can expect 
is located on the right side of 
. If 
moves from the left to the right, then 
is closer to the optimal value 
.
Therefore, we move from 
to 
with 
direction.
Similarly, the slope of the tangent line to the function 
is positive at the approximate solution 
after the 
-th iteration.
It is 
as shown in the figure below. It means the function is increasing when 
moves from left to right,
so we can expect 
is located on the left side of 
. If 
moves the right to the left, then 
is closer to the optimal value 
.
Therefore, we move from 
to 
with 
direction. If we repeat the process until 
moves to 
,
then 
will converge to 0. In this way, we get the approximate solution 
.
This shows that the GDM will find 
, 
, 
, 
that satisfy 
. Here, 
determines the magnitude of movements.
We call this 
the ‘learning rate.’ If the learning rate is too large, 
can pass over 
, or even the function value may increase.
So we should be careful to choose a reasonable learning rate 
.
Do not converge Too slow
☞ Note It is important to determine the appropriate learning rate, but we leave the detail of this issue for the next stage.
It is usual to set 
in (
, 
). As an initial learning rate, 
or 
is usually chosen.
Find the minimum of 
. Take, 
,
, and 
in the following code.
Solution. From 
, the critical point becomes 
and 
is convex downward.
So the minimum value 
can be obtained at 
.
In the above example, the points created by the gradient descent method 
, 
, 
, 
are shown
on the coordinate plane along with the graph of the function 
as follows. From the figure, it is easy to see that it is intuitively converged
to the point 
on the curve with the minimum value. It can be seen that the sequence converges to the optimal solution
.
|
◩ Open Problem 3 |
Find the minimum value of 
. Use 
, 
, and 
with the above GDM code.
So far, the algorithm and the principle of GDM have been explained using simple examples. The GDM is a key algorithm that is used to update weights
in Deep Learning. When we introduced the GDM algorithm, we assumed a convex down function on the domain.
However, if we have a function that contains both convex down and convex up in an interval (non-convex), the GDM algorithm may not work well,
as you can see in the figure below. Under this circumstance, the algorithm may converge to different points. It might be another local minimum
or might not even an extreme or a critical point. It depends on where the starting point 
is given.
|
◩ Open Problem 4 |
Draw graphs for various differentiable functions, as shown in the figure above. Determine a small interval
containing the local minimum identified from the figure (by your eye), and apply the GDM code to each interval with a reasonable 
. Discuss your output.
■ In addition to the gradient descent method, you can use Newton's method to find the optimal solution. It is not in the scope of our book.
Please refer to the following for more information on Newton's method and Taylor series. Visit the following link for more information on Newton's method.
[Math4 AI Book] http://matrix.skku.ac.kr/math4ai/Math4AI.pdf
[AI and Optimal solution] http://matrix.skku.ac.kr/math4ai/part2/
[Newton's method] http://matrix.skku.ac.kr/Cal-Book1/Ch4/
[Taylor series] http://matrix.skku.ac.kr/Cal-Book1/Ch9/
*9.2. Application of the Gradient Descent Method
The GDM introduced in the first session is for minimizing a function 
of one variable. Let's generalize the algorithm for minimizing a function
of several variables. The least-squares problem we learned is a multivariate function 
with at least two independent variables.
The least-squares problem was solved using the error function 
transformed using multiple variables. The least-squares problem can also be solved
by the gradient descent method(GDM).
|
[GDM Algorithm for minimizing a multi-variable function] [Step 1] Set an initial iterate rate [Step 2] Compute [Step 3] Set |
All the steps of the GDM algorithm for minimizing a multi-variable function are the same as for a one-variable function.
■ One variable function ⟷ Multi-variable function
① Scalar 
⟷ Vector, 
② Absolute value 
⟷ Norm of vector, 
③ Derivative 
⟷ Gradient, 
.
Let 
be independent variables and 
be a third variable. Now we can consider a function 
, which is dependent on 
and 
.
Functions of several variables can be defined in the same manner.
In a 3-dimensional (coordinate) space, 
can be considered as a point 
. As 
and 
move, the graph of 
becomes a surface.
For example, the graph of a two-variable function 
can be drawn using the codes as follows.
The graph of 
in the figure above intuitively shows that 
has a local maximum value at the peak and a local minimum value at the valley.
To find those critical points, the notion of a 'gradient of a multi-variable function' is required.
The gradient of a function of two variables 
is defined as follows:
grad 
.
The gradient of 
is a 2×1 vector, where 
means the partial derivative of 
with respect to 
. The partial derivative with respect to 
considers
other variables except 
is constant. Similarly, 
means the partial derivative
of 
with respect to y.
Answer : grad
■
◆ Gradient of multi-variable function
Similarly, the gradient of a multi-variable function with three or more variables 
can be obtained. In general,
the gradient of the 
-variable function 
is as following;
grad 
.
◆ In [Section 5.2], the first example of the least-squares problem was as follows. For each data 
, let's say 
is the value obtained
by substituting 
in a linear function 
. So we have, 
. If this equation's solution does not exist, it is possible
to find 
, 
where the square of error 
is minimized. The error function 
, which is the sum of squared errors 
, is defined as follows:
(The reason we multiplied it by 
at the front of the error expression is only for computational convenience, so it doesn't affect
anything on the conclusion.)
Let's use the GDM to get the approximate solution 
that minimizes 
. Set an initial iterate 
, tolerance 
,
and initial learning rate 
.
The solution is the same as that obtained from QR decomposition. The least-square line is 
.
Therefore, the line we get from the least-squares solution is 
. ■
As we found earlier, we found the <least-square line> by algorithm from the given data. The least-squares solution is obtained with the algorithm.
The least-squares line 
was obtained with the answer as a coefficient. We can also find a quadratic function 
that best fits the given data. In this case, the error function 
is as follows.
We can use the same GDM code to find the best fit for the below quadratic function 
. Take an initial value 
, tolerance 
and learning rate 
.
Hence, the least square quadratic curve is 
since the output has 
. After 4207 iterations,
we now have the least square curve. It means that we can always have the best fit least-square quadratic curve that passes through four or more points. ■
[Web resources]
[GDM Lab] http://matrix.skku.ac.kr/math4ai-intro/W9/
[GDM Lab 2] http://matrix.skku.ac.kr/math4ai/gradient_descent/
[GDM lecture] https://youtu.be/BME4lOvnE-U (New)
[Calculus and Optimal solution] http://matrix.skku.ac.kr/math4ai/part2/
|
◩ Open Problem 1 |
Find the third derivative for the differentiable function from the textbook.
|
◩ Open Problem 2 |
Find a complicated twice differentiable function in other textbooks, and use the code to find the local maximum,
the local minimum, the absolute maximum, and the absolute minimum of the function.
|
◩ Open Problem 3 |
Find the minimum value of 
.
Use 
, 
, and 
using the above GDM code.
|
◩ Open Problem 4 |
Draw a graph for various differentiable functions, as shown in the figure above. Determine a small interval containing the local minimum
identified from the figure (by your eye), and apply the GDM code to each interval with a reasonable starting point 
. Discuss your output.
Copyright @ 2021 SKKU Matrix Lab. All rights reserved.
Made by Manager: Prof. Sang-Gu Lee and Dr. Jae Hwa Lee
, 
, initial 
(eta) and iteration number 
.
. If 
, then stop.
, 
and go to [Step 2].
, tolerance 
, initial learning 
(eta), and iteration number 
.
. If 
, then stop.
, 
and go to [Step2].