Pull to refresh

Конспект по «Машинному обучению». Математический анализ. Градиентный спуск

Reading time 3 min
Views 9.8K


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


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


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

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

Функция $f \colon E \to \mathbb{R}$ стремится к $A$ при $x$, стремящемся к $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).$


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

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

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

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

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

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


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


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

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

  1. $f \colon E \to \mathbb{R}$ непрерывна в $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}$ непрерывна в $a \in E :=$

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


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

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

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

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

  1. Функция $f \colon E \to \mathbb{R}$, определённая на множестве $E \subset \mathbb{R}$, называется дифференцируемой в точке $a \in E$, предельной для множества $E$, если существует такая линейная относительно приращения $x-a$ аргумента функция $A \cdot (x-a)$ [дифференциал функции $f$ в точке $a$], что приращение $f(x)-f(a)$ функции $f$ представляется в виде

    $f(x)-f(a)=A\cdot (x-a) + o(x-a) \quad при \space x\to a, \space x\in E.$

  2. Величина

    $f'(a) = \lim\limits_{E \ni x \to a} \frac{f(x)-f(a)}{x-a}$


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

Также

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



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

  1. Точка $x_0 \in E \subset \mathbb{R}$ называется точкой локального максимума (минимума), а значение функции в ней — локальным максимумом (минимумом) функции $f \colon E \to \mathbb{R}$, если $\exists U_E(x_0)$:

    $\forall x \in U_E(x_0) \space\space f(x) \leq f(x_0)(соответственно, f(x) \geq f(x_0)).$

  2. Точки локального максимума и минимума называются точками локального экстремума, а значения функции в них — локальными экстремумами функции.
  3. Точка $x_0 \in E$ экстремума функции $f \colon E \to \mathbb{R}$ называется точкой внутреннего экстремума, если $x_0$ является предельной точкой как для множества $E_-=\{x\in E | x < x_0\}$, так и для множества $E_+=\{x\in E | x > x_0\}$.

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

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

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

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

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

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


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

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

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


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

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



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

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

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

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

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

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

или

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


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

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

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

Обозначим

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

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

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

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



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

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


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

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



Пример 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.$





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


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

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

Градиентом функции $f \colon \mathbb{R}^n \to \mathbb{R}$ называется вектор, $i$-й элемент которого равен $\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).$


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

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

Обозначим через $\theta^{(t)}$ вектор параметров функции на шаге $t$. Вектор обновления параметров на шаге $t$:

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


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

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


Пример:
Рассмотрим пример работы метода градиентного спуска в простейшем случае ($n=1$). То есть $f \colon \mathbb{R} \to \mathbb{R}$.
Пусть $f(x)=x^2, \quad\theta^{(0)} = 3,\quad \eta=1$. Тогда:

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

В случае, когда $\eta=1$, получается ситуация, как на третьем изображении картинки выше. Мы постоянно перепрыгиваем точку экстремума.
Пусть $\eta=0.8$. Тогда:

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

Видно, что итеративно мы приближаемся к точке экстремума.
Пусть $\eta=0.5$. Тогда:

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

Точка экстремума найдена за 1 шаг.

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


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

Tags:
Hubs:
If this publication inspired you and you want to support the author, do not hesitate to click on the button
+9
Comments 12
Comments Comments 12

Articles