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

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

Производную можно ввести как линейное приближение функции в точке (что?)
Мы не просто так 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$

А что в многомерном случае?
В целом, почти всё тоже самое 

По каждому из направлений есть обычная производная с касательной прямой
Только там линейная функция будет уже не умножение на число, а умножение на число каждой из координаты и их сложение:
$l(x) = l_1x^1 + \dots l_nx^n$
То есть, саму функцию можно задать в виде набора из n чисел, то есть, тоже вектор
(Из этого мы сделали вывод, что линейные функции тоже вектора)

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

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

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

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

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

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

Так вот это как раз и есть их приближение!
"Хорошая" функция от n переменных задаёт гладкую поверхность своим графиком и локально они похожи на пространства
Поэтому, например, в случае двух переменных линейно приближать можно касательной плоскостью
В общем случае это называется касательным пространством

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

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

2. Делается шаг, пропорциональный градиенту в противоположную от него сторону
Чем больше градиент, тем более резкий спуск и тем (скорее всего) мы дальше от нужной ямы
А если градиент совсем маленький, значит, скорее всего, мы прямо у ямы 
В центре самой ямы градиент равен нулю (иначе, если он не равен нулю, можно пойти в противоположную сторону и ещё уменьшить значение функции)
Ещё, это можно понять через то, что касательное пространство в центре ямы параллельно "полу" и мы куда ни пойдём, вначале практически не будем ощущать наклона

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

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

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

Обычно длину градиента умножают на какой-то коэффициент $\eta$:
Если $\eta$ слишком большая, то есть шанс "перескочить" яму (причём, пойдя потом обратно тоже перескочить, так и не подойдя близко к точке минимума
Если $\eta$ слишком маленькая, то может потребоваться слишком много шагов

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

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

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

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

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