[Из песочницы] Конспект по «Машинному обучению». Математический анализ. Градиентный спуск03.11.2019 21:35

Вспомним математический анализ

Непрерывность функции и производная

Пусть $inline$E \subseteq \mathbb{R}$inline$, $inline$a$inline$ — предельная точка множества $inline$E$inline$ (т.е. $inline$a \in E, \forall \varepsilon > 0 \space\space |(a — \varepsilon, a + \varepsilon) \cap E| = \infty$inline$), $inline$f \colon E \to \mathbb{R}$inline$.

Определение 1 (предел функции по Коши):

Функция $inline$f \colon E \to \mathbb{R}$inline$ стремится к $inline$A$inline$ при $inline$x$inline$, стремящемся к $inline$a$inline$, если

$$display$$\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).$$display$$

Обозначение: $inline$\lim\limits_{E \ni x \to a}f (x) = A$inline$.
Определение 2:

Интервалом $inline$ab$inline$ называется множество $inline$]a, b[ \space:= \{x \in \mathbb{R}| a < x < b\}$inline$;
Интервал, содержащий точку $inline$x \in \mathbb{R}$inline$, называется окрестностью этой точки.
Проколотой окрестностью точки называется окрестность точки, из которой исключена сама эта точка.

Обозначение:

$inline$V (x)$inline$ или $inline$U (x)$inline$ — окрестность точки $inline$x$inline$;
$inline$\overset{\circ}{U}(x)$inline$ — проколотая окрестность точки $inline$x$inline$;
$inline$U_E (x) := E \cap U (x), \\ \overset{\circ}{U}_E (x) := E \cap \overset{\circ}{U}(x)$inline$

Определение 3 (предел функции через окрестности):

$$display$$\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)).$$display$$

Определения 1 и 3 равносильны.

Определение 4 (непрерывность функции в точке):

$inline$f \colon E \to \mathbb{R}$inline$непрерывна в $inline$a \in E:=$inline$
$$display$$= \forall V (f (a)) \space\space \exists U_E (a) \space\space (f (U_E (a)) \subset V (f (a)));$$display$$
$inline$f \colon E \to \mathbb{R}$inline$непрерывна в $inline$a \in E:=$inline$
$$display$$\forall \varepsilon > 0 \space\space \exists \delta > 0 \space\space \forall x \in E \space\space (|x-a| < \delta \Rightarrow |f(x)-f(a)| < \varepsilon).$$display$$

Из определений 3 и 4 видно, что
($inline$f \colon E \to \mathbb{R}$inline$ непрерывна в $inline$a \in E$inline$, где $inline$a$inline$ — предельная точка $inline$E$inline$) $inline$\Leftrightarrow$inline$
$inline$ \Leftrightarrow (\lim\limits_{E \ni x \to a}f (x) = f (a)).$inline$

Определение 5:

Функция $inline$f \colon E \to \mathbb{R}$inline$ называется непрерывной на множестве $inline$E$inline$, если она непрерывна в каждой точке множества $inline$E$inline$.

Определение 6:

Функция $inline$f \colon E \to \mathbb{R}$inline$, определённая на множестве $inline$E \subset \mathbb{R}$inline$, называется дифференцируемой в точке $inline$a \in E$inline$, предельной для множества $inline$E$inline$, если существует такая линейная относительно приращения $inline$x-a$inline$ аргумента функция $inline$A \cdot (x-a)$inline$ [дифференциал функции $inline$f$inline$ в точке $inline$a$inline$], что приращение $inline$f (x)-f (a)$inline$ функции $inline$f$inline$ представляется в виде
$$display$$f (x)-f (a)=A\cdot (x-a) + o (x-a) \quad при \space x\to a, \space x\in E.$$display$$
Величина
$$display$$f'(a) = \lim\limits_{E \ni x \to a} \frac{f (x)-f (a)}{x-a}$$display$$

называется производной функции $inline$f$inline$ в точке $inline$a$inline$.

Также

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

Определение 7:

Точка $inline$x_0 \in E \subset \mathbb{R}$inline$ называется точкой локального максимума (минимума), а значение функции в ней — локальным максимумом (минимумом) функции $inline$f \colon E \to \mathbb{R}$inline$, если $inline$\exists U_E (x_0)$inline$:
$$display$$\forall x \in U_E (x_0) \space\space f (x) \leq f (x_0)(соответственно, f (x) \geq f (x_0)).$$display$$
Точки локального максимума и минимума называются точками локального экстремума, а значения функции в них — локальными экстремумами функции.
Точка $inline$x_0 \in E$inline$ экстремума функции $inline$f \colon E \to \mathbb{R}$inline$ называется точкой внутреннего экстремума, если $inline$x_0$inline$ является предельной точкой как для множества $inline$E_-=\{x\in E | x < x_0\}$inline$, так и для множества $inline$E_+=\{x\in E | x > x_0\}$inline$.

Лемма 1 (Ферма):

Если функция $inline$f \colon E \to \mathbb{R}$inline$ дифференцируема в точке внутреннего экстремума $inline$x_0 \in E$inline$, то её производная в этой точке равна нулю: $inline$f'(x_0)=0$inline$.

Утверждение 1 (теорема Ролля):
Если функция $inline$f \colon [a, b] \to \mathbb{R}$inline$ непрерывна на отрезке $inline$[a, b]$inline$, дифференцируема в интервале $inline$]a, b[$inline$ и $inline$f (a)=f (b)$inline$, то найдётся точка $inline$\xi \in ]a, b[$inline$ такая, что $inline$f'(\xi)=0$inline$.

Теорема 1 (теорема Лагранжа о конечном приращении):

Если функция $inline$f\colon[a, b] \to \mathbb{R}$inline$ непрерывна на отрезке $inline$[a, b]$inline$ и дифференцируема в интервале $inline$]a, b[$inline$, то найдётся точка $inline$\xi \in ]a, b[$inline$ такая, что

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

Следствие 1 (признак монотонности функции):
Если в любой точке некоторого интервала производная функции неотрицательная (положительная), то функция не убывает (возрастает) на этом интервале.

Следствие 2 (критерий постоянства функции):
Непрерывная на отрезке $inline$[a, b]$inline$ функция постоянна не нём тогда и только тогда, когда её производная равна нулю в любой точке отрезка $inline$[a, b]$inline$ (или хотя бы интервала $inline$]a, b[$inline$).

Частная производная функции многих переменных

Через $inline$\mathbb{R}^m$inline$ обозначают множество:

$$display$$\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}\}.$$display$$

Определение 8:

Функция $inline$f \colon E \to \mathbb{R}$inline$, определённая на множестве $inline$E \subset \mathbb{R}^m$inline$, называется дифференцируемой в точке $inline$x \in E$inline$, предельной для множества $inline$E$inline$, если

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

где $inline$L (x) \colon \mathbb{R}^m \to \mathbb{R}$inline$ — линейная относительно $inline$h$inline$ функция [дифференциал функции $inline$f$inline$ в точке $inline$x$inline$ (обозн. $inline$df (x)$inline$ или $inline$f'(x)$inline$)], а $inline$\alpha (x; h) = o (h)$inline$ при $inline$h \to 0, x+h \in E$inline$.

Соотношение (1) можно переписать в следующем виде:

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

или

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

Если перейти к координатной записи точки $inline$x = (x^1, …, x^m)$inline$, вектора $inline$h = (h^1, …, h^m)$inline$ и линейной функции $inline$L (x)h = a_1(x)h^1 + … + a_m (x)h^m$inline$, то равенство (1) выглядит так

$$display$$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 при \space\space h \to 0, \qquad (2)$$display$$

где $inline$a_1(x), …, a_m (x)$inline$ — связанные с точкой $inline$x$inline$ вещественные числа. Необходимо найти эти числа.

Обозначим

$$display$$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,$$display$$

где $inline$\{e_1, …, e_m\}$inline$ — базис в $inline$\mathbb{R}^m$inline$.

При $inline$h=h_i$inline$ из (2) получаем

$$display$$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 при \space\space h^i \to 0. \qquad (3)$$display$$

Из (3) получаем

$$display$$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)$$display$$

Определение 9:
Предел (4) называется частной производной функции $inline$f (x)$inline$ в точке $inline$x = (x^1, …, x^m)$inline$ по переменной $inline$x^i$inline$. Обозначается:

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

Пример 1:

$$display$$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.$$display$$

Градиентный спуск

Пусть $inline$f \colon \mathbb{R}^n \to \mathbb{R}$inline$, где $inline$\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}\}$inline$.

Определение 10:

Градиентом функции $inline$f \colon \mathbb{R}^n \to \mathbb{R}$inline$ называется вектор, $inline$i$inline$-й элемент которого равен $inline$\frac{\partial f}{\partial \theta_i}$inline$:

$$display$$\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).$$display$$

Градиент — это то направление, в котором функция быстрее всего возрастает. А значит, направление, в котором она быстрее всего убывает, — это и есть направление, обратное градиенту, то есть $inline$-\bigtriangledown_{\theta}f$inline$.

Целью метода градиентного спуска является поиск точки экстремума (минимума) функции.

Обозначим через $inline$\theta_t$inline$ вектор параметров функции на шаге $inline$t$inline$. Вектор обновления параметров на шаге $inline$t$inline$:

$$display$$u_t = -\eta\bigtriangledown_{\theta}f (\theta_{t-1}), \quad \theta_t = \theta_{t-1} + u_t.$$display$$

В формуле выше параметр $inline$\eta$inline$ — это скорость обучения, которая регулирует размер шага, который мы делаем в направлении склона-градиента. В частности, могут возникать две противоположные друг другу проблемы:

если шаги будут слишком маленькими, то обучение будет слишком долгим, и повышается вероятность застрять в небольшом неудачном локальном минимуме по дороге (первое изображение на картинке ниже);
если слишком большие, можно бесконечно прыгать через искомый минимум взад-вперёд, но так и не прийти в самую нижнюю точку (третье изображение на картинке ниже).

Список используемой литературы:

«Математический анализ. Часть 1», В.А. Зорич, Москва, 1997;
«Глубокое обучение. Погружение в мир нейронных сетей», С. Никуленко, А. Кадурин, Е. Архангельская, ПИТЕР, 2018.