Катимся с горки

Шаг 1

Разберёмся с понятием производной, она нам сейчас будет критически нужна

Производную можно ввести как линейное приближение функции в точке (что?)

Мы не просто так 100 лет работали с линейной алгеброй

Это самый изученный раздел математики

Поэтому неудивительно, что у людей появляется желание любую другую науку свести к линейной

Так вот производная - попытка заменить обычную функцию на линейную

Но только в одной точке и только локально (в маленькой окрестности)

Из этого становится понятно, почему производная определяет касательную к графику

Ведь касательная прямая это та прямая, которая лучше всего приближает функцию (это можно брать за определение касательной)

Внимательно посмотрите на картинку

Прямая рядом с функцией практически от этой функции не отличается

Это и есть приближение

Более аналитически это вводится так:

$f(x + \Delta x) - f(x) = l(\Delta x) + o(\Delta x)$,

где $o(\Delta x)$ - это поправка, которая стремится к нулю сильно быстрее, чем само $\Delta x$ (для придирчивых математиков формула: $\lim_{\Delta x\rightarrow 0}\frac{o(\Delta x)}{\Delta x} = 0$)

l(x) - линейная функция

То есть, разница между близкими точками функции хорошо (наилучшим образом из возможных) приближается линейной функцией

Так как в одномерном случае линейная функция это просто умножение на число, то $l(x) = k*\Delta x$

Шаг 2

А что в многомерном случае?

В целом, почти всё тоже самое

По каждому из направлений есть обычная производная с касательной прямой

Только там линейная функция будет уже не умножение на число, а умножение на число каждой из координаты и их сложение:

$l(x) = l_1x^1 + \dots l_nx^n$

То есть, саму функцию можно задать в виде набора из n чисел, то есть, тоже вектор

(Из этого мы сделали вывод, что линейные функции тоже вектора)

Такой вектор называется градиентоми обозначается перевёрнутой дельтой: $\nabla f$

Получается, что можно l(x) можно представить через скалярное произведение в ортонормированном базисе:

$l(x) = <\nabla f, x>$

Мы помним, что скалярное произведение тем больше, чем ближе друг к другу вектора (на этом основано косинусное сходство)

А это значит, что чтобы функция росла больше всего, направление движение****должно совпадать с градиентом(тогда их скалярное произведение максимально, а значит максимален и рост функции)

Получается, что градиент это вектор, указывающий направление наибольшего роста функции (это самое важное, на этом будет построен будущий алгоритм)

В одномерном случае вместо градиента производная, но она тоже показывает направление роста, только обычным знаком

Если она положительная, то при движении в положительную сторону функция будет расти

Это соотносится с касательной плоскостью

Если коэффициент прямой больше нуля, то прямая как бы идёт вверх (иначе, вниз)

А на этой картинке виден вектор градиента в точке и можно понять, что он указывает на направление, куда нужно пойти, чтобы функция росла

Шаг 3

В одномерном случае мы приближали функцию прямой

А в многомерном случае как?

Во втором уроке третьего модуля мы обсуждали, что гладкие поверхности это такие поверхности, которые локально выглядят как обычные n-мерные пространства

Например, в случае с двумерными поверхностями как плоскость

Так вот это как раз и есть их приближение!

“Хорошая” функция от n переменных задаёт гладкую поверхность своим графиком и локально они похожи на пространства

Поэтому, например, в случае двух переменных линейно приближать можно касательной плоскостью

В общем случае это называется касательным пространством

Шаг 4

Вернёмся к изначальной проблеме

Нам нужен минимум функции

Как его найти?

Раз градиент показывает, куда идти, чтобы функция росла, то чтобы она уменьшалась нужно идти в противоположную сторону

Этот подход называется “градиентным спуском”

Подробно он работает так:

1. Выбирается случайная точка и оценивается градиент у функции в этой точке (условный наклон холма)

2. Делается шаг, пропорциональный градиенту в противоположную от него сторону

Чем больше градиент, тем более резкий спуск и тем (скорее всего) мы дальше от нужной ямы

А если градиент совсем маленький, значит, скорее всего, мы прямо у ямы

В центре самой ямы градиент равен нулю(иначе, если он не равен нулю, можно пойти в противоположную сторону и ещё уменьшить значение функции)

Ещё, это можно понять через то, что касательное пространство в центре ямы параллельно “полу” и мы куда ни пойдём, вначале практически не будем ощущать наклона

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

Этот метод похож на то, как мы мячик искал яму в лесу

Он бы просто катился туда, куда идёт спуск и в какой-то момент пришёл бы к яме

Главное, за чему нужно следить - выбор размера шага

Обычно длину градиента умножают на какой-то коэффициент $\eta$:

Если $\eta$ слишком большая, то есть шанс “перескочить” яму (причём, пойдя потом обратно тоже перескочить, так и не подойдя близко к точке минимума

Если $\eta$ слишком маленькая, то может потребоваться слишком много шагов

Шаг 5

Разберём простой пример для функции двух переменных

$f(x,y)=x^2 + y^2$

Её градиент в точке (x, y) равна: $\nabla f = (2x, 2y)$

(нам сейчас не так важно, как это вычисляется)

Будем делать вид, что мы не знаем, как выглядит сама функция (иначе очев, что минимум в нуле), а будем работать просто по принципу: выбрали точку -> получили её значение и градиент в этой точке

Возьмём начальную точку (3, 4) и коэффициент для шага $\eta = 0.1$

Изначальное значение функции: $f(3, 4) = 25$

Шаг 1:

$\nabla f(3, 4) = (6, 8)$

Получается, нам нужно пройти на 6 * 0.1 = 0.6 в минус по координате x и на 8*0.1 = 0.8 в минус по координате y

Новые координаты: (3 - 0.6, 4 - 0.8) = (2.4, 3.2)

$f(2.4, 3.2) = 16$ (значение уменьшилось, значит мы на правильном пути)

Шаг 2:

$\nabla f(2.4, 3.2) = (4.2, 6.4)$

Идём на -0.42 по x и на -0.64 по y

Новые координаты: (1.92, 2.56)

f(1.92, 2.56) = 10.24 (ещё уменьшилось)

Далее менее подробно:

Шаг 3: $\nabla f = (3.072, 4.096) → (1.2288, 1.6384) → f = 6.5536$

Шаг 4: $∇f = (1.96608, 2.62144) → (0.786432, 1.048576) → f = 2.6844$

Шаг 5:

$∇f = (1.572864, 2.097152) → (0.6291456, 0.8388608) → f = 1.7180$

Видно, что после каждого шага функция уменьшается

А значит, алгоритм работает

Далее мы разберём разновидности и проблемы градиентного спуска

А ещё, сейчас будет видео, где как раз визуализированы наши шаги градиентного спуска

Шаг 6

Шаг 7

Вы стоите в точке на склоне холма (график функции двух переменных). Вычислив градиент в этой точке, вы получили вектор, указывающий на северо-восток и имеющий большую длину. Что это означает геометрически?

• Это направление, в котором функция убывает быстрее всего.
• Это направление, в котором функция растёт быстрее всего, причём крутизна подъёма большая.
• Это направление касательной к линии уровня функции.
• Это направление, в котором функция вообще не меняется.