4.3. Ещё лучше катимся

Главная проблема градиентного спуска - много разных ям

Например, на картинке видно функцию, у которой есть две ямы, одна из которых выше другой

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

Математически это описывается через понятие выпуклости
Функция выпуклая (вниз), если она лежит над своей касательной
Или, что тоже самое, что он лежит под своей секущей (секущая в данном случае - отрезок между любыми двумя точками)

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

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

Что с этим делать?
Есть два классических подхода.

Первый - использовать название прошлого урока: "катимся с горки".
Если скатить с прошлого графика мячик, то он, скорее всего, найдёт правильный минимум, потому что у него есть инерция.
С помощью неё он "перелетает" локальную яму, попадая в главную яму.

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

Теперь введём понятие скорости, которую мы уже будем считать таким же образом:
$v_t = \beta v_{t-1} + \eta \nabla L(\theta_t)$
Здесь $\beta$ - коэффициент инерции, он показывает, насколько скорость сейчас зависит от прошлой скорости.
Дальше мы уже вычитаем из координат эту скорость и алгоритм готов.

На видео показан пример спуска с инерцией, решающей проблему локального минимума.

Второй подход (который, на самом деле, решает ещё кучу проблем) - стохастический градиентный спуск
Главная идея - случайность

Сначала нужно понять, в каких задачах обычно используется градиентный спуск
Самый частый вариант - улучшение работы какой-нибудь предсказательной модели (например, нейросети)
У нас есть какой-то набор данных (допустим, их 100 000), и, допустим, мы хотим, чтобы наша модель распознавала цифры на фотографиях
Функция, которую нужно минимизировать через спуск - функция ошибки
То есть, при каждой измерении мы модель прогоняем через 100 000 картинок (а это ну очень долго)
Идея стохастического спуска в том, чтобы прогонять модель каждый раз через одну случайную картинку и на основе и пытаться минимизировать эту достаточно случайную функцию

Это решает сразу две проблемы:
1. Проблему с ямами, с которой мы начали
Учитывая, что функция получается достаточно случайной, она как бы постоянно колеблется 
Из-за этого небольшие ямы часто сглаживаются и градиентный спуск их проскакивает
При этом, главный минимум, всё равно, будет примерно там, где и в изначальном случае

2. Проблема скорости
Проверить спуск на одном объекте во много раз быстрее, чем на 100 000 объектах
Поэтому, можно сделать сильно больше шагов
И даже если иногда мы будем отступать немного не туда, в среднем мы будем двигаться к минимуму

Так получается, что случайность и шум помогают нам улучшить нашу модель