Synopsis on “Machine Learning”. Mathematical analysis. Gradient descent

Recall the mathematical analysis

Function Continuity and Derivative

Let $$$E \ subseteq \ mathbb {R}$ , $$$a$ Is the limit point of the set $$$E$ (those. $$$a \ in E, \ forall \ varepsilon> 0 \ space \ space | (a - \ varepsilon, a + \ varepsilon) \ cap E | = \ infty$ ), $$$f \ colon E \ to \ mathbb {R}$ .



Definition 1 (Cauchy function limit):



Function $$$f \ colon E \ to \ mathbb {R}$ committed to $$$A$ at $$$x$ seeking to $$$a$ , if a

$$

$$\ forall \ varepsilon> 0 \ space \ space \ exists \ delta> 0 \ space \ space \ forall x \ in E \ space \ space (0 <| x- a | <\ delta \ Rightarrow | f (x) - A | <\ varepsilon).$$

Designation: $$$\ lim \ limits_ {E \ ni x \ to a} f (x) = A$ .



Definition 2:

1. Interval $$$ab$ called set $$$] a, b [\ space: = \ {x \ in \ mathbb {R} | a <x <b \}$ ;
2. Point Interval $$$x \ in \ mathbb {R}$ is called the neighborhood of this point.
3. A punctured neighborhood of a point is a neighborhood of a point from which this point itself is excluded.

Designation:

1. $$$V (x)$ or $$$U (x)$ - neighborhood of a point $$$x$ ;
2. $$$\ overset {\ circ} {U} (x)$ - punctured neighborhood of a point $$$x$ ;
3. $$$U_E (x): = E \ cap U (x), \\ \ overset {\ circ} {U} _E (x): = E \ cap \ overset {\ circ} {U} (x)$

Definition 3 (function limit through neighborhoods):

$$

$$\ lim \ limits_ {E \ ni x \ to a} f (x) = A: = \ forall V_R (A) \ space \ exists \ overset {\ circ} {U} _E (a) \ space \ space ( f (\ overset {\ circ} {U} _E (a)) \ subset V_R (A)).$$

Definitions 1 and 3 are equivalent.



Definition 4 (continuity of a function at a point):

1. $$$f \ colon E \ to \ mathbb {R}$ continuous in $$$a \ in E: =$
   
   
   
   
   

   $$

   $$= \ forall V (f (a)) \ space \ space \ exists U_E (a) \ space \ space (f (U_E (a)) \ subset V (f (a)));$$
   
   
   
   
   
2. $$$f \ colon E \ to \ mathbb {R}$ continuous in $$$a \ in E: =$
   
   
   
   
   

   $$

   $$\ forall \ varepsilon> 0 \ space \ space \ exists \ delta> 0 \ space \ space \ forall x \ in E \ space \ space (| xa | <\ delta \ Rightarrow | f (x) -f (a) | <\ varepsilon).$$
   
   
   
   
   

Definitions 3 and 4 show that

( $$$f \ colon E \ to \ mathbb {R}$ continuous in $$$a \ in E$ where $$$a$ - limit point $$$E$ ) $$$\ Leftrightarrow$

$$$\ Leftrightarrow (\ lim \ limits_ {E \ ni x \ to a} f (x) = f (a)).$



Definition 5:



Function $$$f \ colon E \ to \ mathbb {R}$ called continuous on the set $$$E$ if it is continuous at each point of the set $$$E$ .



Definition 6:

1. Function $$$f \ colon E \ to \ mathbb {R}$ defined on the set $$$E \ subset \ mathbb {R}$ is called differentiable at the point $$$a \ in E$ limiting for the set $$$E$ if there is such a linear with respect to the increment $$$x-a$ argument function $$$A \ cdot (x-a)$ [function differential $$$f$ at the point $$$a$ ] that increment $$$f (x) -f (a)$ the functions $$$f$ represented as
   
   
   
   
   

   $$

   $$f (x) -f (a) = A \ cdot (x-a) + o (x-a) \ quad for \ space x \ to a, \ space x \ in E.$$
   
   
   
   
   
2. Value
   
   
   
   
   
   
   

   $$

   $$f '(a) = \ lim \ limits_ {E \ ni x \ to a} \ frac {f (x) -f (a)} {x-a}$$
   
   
   
   
   
   
   called derivative function $$$f$ at the point $$$a$ .

Also

$$

$$f '(x) = \ lim _ {\ substack {h \ to 0 \\ x + h, x \ in E}} \ frac {f (x + h) -f (x)} {h}.$$

Definition 7:

1. Dot $$$x_0 \ in E \ subset \ mathbb {R}$ is called the point of local maximum (minimum) , and the value of the function in it is called the local maximum (minimum) of the function $$$f \ colon E \ to \ mathbb {R}$ , if a $$$\ exists U_E (x_0)$ :
   
   
   
   
   

   $$

   $$\ forall x \ in U_E (x_0) \ space \ space f (x) \ leq f (x_0) (respectively, f (x) \ geq f (x_0)).$$
   
   
   
   
   
2. The points of local maximum and minimum are called points of local extremum , and the values ​​of the function in them are called local extrema of the function .
3. Dot $$$x_0 \ in E$ extremum function $$$f \ colon E \ to \ mathbb {R}$ called an internal extremum point if $$$x_0$ is the limit point as for the set $$$E _- = \ {x \ in E | x <x_0 \}$ , and for the set $$$E _ + = \ {x \ in E | x> x_0 \}$ .

Lemma 1 (Fermat):



If the function $$$f \ colon E \ to \ mathbb {R}$ differentiable at the point of internal extremum $$$x_0 \ in E$ , then its derivative at this point is zero: $$$f '(x_0) = 0$ .



Proposition 1 (Roll's theorem):

If the function $$$f \ colon [a, b] \ to \ mathbb {R}$ continuous on a segment $$$[a, b]$ differentiable in the interval $$$] a, b [$ and $$$f (a) = f (b)$ then there is a point $$$\ xi \ in] a, b [$ such that $$$f '(\ xi) = 0$ .



Theorem 1 (Lagrange finite increment theorem):



If the function $$$f \ colon [a, b] \ to \ mathbb {R}$ continuous on a segment $$$[a, b]$ and differentiable in the interval $$$] a, b [$ then there is a point $$$\ xi \ in] a, b [$ such that

$$

$$f (b) -f (a) = f '(\ xi) (b-a).$$

Corollary 1 (a sign of monotonicity of a function):

If at any point of a certain interval the derivative of the function is non-negative (positive), then the function does not decrease (increases) on this interval.



Corollary 2 (criterion for the constancy of a function):

Continuous on a cut $$$[a, b]$ a function is not constant if and only if its derivative is zero at any point in the interval $$$[a, b]$ (or at least the interval $$$] a, b [$ )

Partial derivative of a function of many variables

Across $$$\ mathbb {R} ^ m$ denote the set:

$$

$$\ mathbb {R} ^ m = \ underbrace {\ mathbb {R} \ times \ mathbb {R} \ times \ cdots \ times \ mathbb {R}} _ m = \ {(\ omega_1, \ omega_2, ... , \ omega_m), \ space \ omega_i \ in \ mathbb {R} \ space \ forall i \ in \ overline {1, m} \}.$$

Definition 8:



Function $$$f \ colon E \ to \ mathbb {R}$ defined on the set $$$E \ subset \ mathbb {R} ^ m$ is called differentiable at the point $$$x \ in E$ limiting for the set $$$E$ , if a

$$

$$f (x + h) -f (x) = L (x) h + \ alpha (x; h), \ qquad (1)$$

Where $$$L (x) \ colon \ mathbb {R} ^ m \ to \ mathbb {R}$ - linear with respect to $$$h$ function [function differential $$$f$ at the point $$$x$ (reference $$$df (x)$ or $$$f '(x)$ )], but $$$\ alpha (x; h) = o (h)$ at $$$h \ to 0, x + h \ in E$ .



Relation (1) can be rewritten as follows:

$$

$$f (x + h) -f (x) = f '(x) h + \ alpha (x; h)$$

or

$$

$$\ bigtriangleup f (x; h) = df (x) h + \ alpha (x; h).$$

If we go to the coordinate record of the point $$$x = (x ^ 1, ..., x ^ m)$ , vector $$$h = (h ^ 1, ..., h ^ m)$ and linear function $$$L (x) h = a_1 (x) h ^ 1 + ... + a_m (x) h ^ m$ , then equality (1) looks like this

$$

$$f (x ^ 1 + h ^ 1, ..., x ^ m + h ^ m) -f (x ^ 1, ..., x ^ m) = \\ = a_1 (x) h ^ 1 + ... + a_m (x) h ^ m + o (h) \ quad for \ space \ space h \ to 0, \ qquad (2)$$

Where $$$a_1 (x), ..., a_m (x)$ - associated with point $$$x$ real numbers. You need to find these numbers.



We denote

$$

$$h_i = h ^ ie_i = 0 \ cdot e_1 + ... + 0 \ cdot e_ {i-1} + h ^ i \ cdot e_i + 0 \ cdot e_ {i + 1} + ... + 0 \ cdot e_m,$$

Where $$$\ {e_1, ..., e_m \}$ - basis in $$$\ mathbb {R} ^ m$ .



At $$$h = h_i$ from (2) we obtain

$$

$$f (x ^ 1, ..., x ^ {i-1}, x ^ i + h ^ i, x ^ {i + 1}, ..., x ^ m) -f (x ^ 1, ..., x ^ i, ..., x ^ m) = \\ = a_i (x) h ^ i + o (h ^ i) \ quad for \ space \ space h ^ i \ to 0. \ qquad (3)$$

From (3) we obtain

$$

$$a_i (x) = \ lim_ {h_i \ to 0} \ frac {f (x ^ 1, ..., x ^ {i-1}, x ^ i + h ^ i, x ^ {i + 1} , .., x ^ m) -f (x ^ 1, ..., x ^ i, ..., x ^ m)} {h ^ i}. \ qquad (4)$$

Definition 9:

The limit (4) is called the partial derivative of the function $$$f (x)$ at the point $$$x = (x ^ 1, ..., x ^ m)$ by variable $$$x ^ i$ . It is designated:

$$

$$\ frac {\ partial f} {\ partial x ^ i} (x), \ quad \ partial_if (x), \ quad f '_ {x ^ i} (x).$$

Example 1:

$$

$$f (u, v) = u ^ 3 + v ^ 2 \ sin u, \\ \ partial_1f (u, v) = \ frac {\ partial f} {\ partial u} (u, v) = 3u ^ 2 + v ^ 2 \ cos u, \\ \ partial_2 f (u, v) = \ frac {\ partial f} {\ partial v} (u, v) = 2v \ sin u.$$

Gradient descent

Let $$$f \ colon \ mathbb {R} ^ n \ to \ mathbb {R}$ where $$$\ mathbb {R} ^ n = \ underbrace {\ mathbb {R} \ times \ mathbb {R} \ times \ cdots \ times \ mathbb {R}} _ n = \ {(\ theta_1, \ theta_2, ... , \ theta_n), \ space \ theta_i \ in \ mathbb {R} \ space \ forall i \ in \ overline {1, n} \}$ .



Definition 10:



Gradient Function $$$f \ colon \ mathbb {R} ^ n \ to \ mathbb {R}$ called a vector, $$$i$ whose element is equal to $$$\ frac {\ partial f} {\ partial \ theta_i}$ :

$$

$$\ bigtriangledown _ {\ theta} f = \ left (\ begin {array} {c} \ frac {\ partial f} {\ partial \ theta_1} \\\ frac {\ partial f} {\ partial \ theta_2} \\ \ vdots \\\ frac {\ partial f} {\ partial \ theta_n} \ end {array} \ right), \ quad \ theta = (\ theta_1, \ theta_2, ..., \ theta_n).$$

Gradient is the direction in which the function increases most rapidly. This means that the direction in which it decreases most rapidly is the direction opposite to the gradient, i.e. $$$- \ bigtriangledown _ {\ theta} f$ .



The aim of the gradient descent method is to find the extremum (minimum) point of the function.



Denote by $$$\ theta ^ {(t)}$ function parameter vector in step $$$t$ . Parameter update vector in step $$$t$ :

$$

$$u ^ {(t)} = - \ eta \ bigtriangledown _ {\ theta} f (\ theta ^ {(t-1)}), \ quad \ theta ^ {(t)} = \ theta ^ {(t- 1)} + u ^ {(t)}.$$

In the formula above, the parameter $$$\ eta$ Is the learning speed that controls the size of the step that we take in the direction of the gradient slope. In particular, two opposing problems may arise:

• if the steps are too small, the training will be too long, and the likelihood of getting stuck in a small unsuccessful local minimum along the road increases (the first image in the picture below);
• if they are too large, you can endlessly jump over the desired minimum back and forth, but never reach the lowest point (the third image in the picture below).

Example:

Consider the example of the gradient descent method in the simplest case ( $$$n = 1$ ) I.e $$$f \ colon \ mathbb {R} \ to \ mathbb {R}$ .

Let $$$f (x) = x ^ 2, \ quad \ theta ^ {(0)} = 3, \ quad \ eta = 1$ . Then:

$$

$$\ frac {\ partial f} {\ partial x} (x) = 2x \ quad \ Rightarrow \ quad \ bigtriangledown f_ \ theta (x) = 2x; \\ \ theta ^ {(1)} = \ theta ^ {(0)} - 1 \ cdot f_ \ theta (\ theta ^ {(0)}) = 3 - 6 = -3; \\ \ theta ^ {(2)} = \ theta ^ {(1)} - 1 \ cdot f_ \ theta (\ theta ^ {(1)}) = - 3 + 6 = 3 = \ theta ^ {(0 )}.$$

In the case when $$$\ eta = 1$ , the situation turns out, as in the third image of the picture above. We constantly jump over the extreme point.

Let $$$\ eta = 0.8$ . Then:

$$

$$\ theta ^ {(1)} = \ theta ^ {(0)} - 0.8 \ times f_ \ theta (\ theta ^ {(0)}) = 3 - 0.8 \ times6 = 3 - 4.8 = -1.8; \\ \ theta ^ {(2)} = \ theta ^ {(1)} - 0.8 \ times f_ \ theta (\ theta ^ {(1)}) = - 1.8 + 0.8 \ times3.6 = -1.8 + 2.88 = 1.08; \\ \ theta ^ {(3)} = \ theta ^ {(2)} - 0.8 \ times f_ \ theta (\ theta ^ {(2)}) = 1.08 - 0.8 \ times2.16 = 1.08 - 1.728 = - 0.648; \\ \ theta ^ {(4)} = \ theta ^ {(3)} - 0.8 \ times f_ \ theta (\ theta ^ {(3)}) = - 0.648 + 0.8 \ times1.296 = -0.648 + 1.0368 = 0.3888; \\ \ theta ^ {(5)} = \ theta ^ {(4)} - 0.8 \ times f_ \ theta (\ theta ^ {(4)}) = 0.3888 - 0.8 \ times0.7776 = 0.3888 - .62208 = -0.23328; \\ \ theta ^ {(6)} = \ theta ^ {(5)} - 0.8 \ times f_ \ theta (\ theta ^ {(5)}) = - 0.23328 + 0.8 \ times0.46656 = -0.23328 + 0.373248 = \\ = 0.139968.$$

It is seen that iteratively we are approaching the point of extremum.

Let $$$\ eta = 0.5$ . Then:

$$

$$\ theta ^ {(1)} = \ theta ^ {(0)} - 0.5 \ times f_ \ theta (\ theta ^ {(0)}) = 3 - 0.5 \ times6 = 3 - 3 = 0; \\ \ theta ^ {(2)} = \ theta ^ {(1)} - 0.5 \ times f_ \ theta (\ theta ^ {(1)}) = 0 - 0.5 \ times0 = 0.$$

The extremum point was found in 1 step.

Bibliography:

• "Mathematical analysis. Part 1 ", V.A. Zorich, Moscow, 1997;
• “Deep learning. Immersion in the world of neural networks ”, S. Nikulenko, A. Kadurin, E. Arkhangelskaya, PETER, 2018.