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

Шаг 1

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

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

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

А значит, особо не выполнит свою работу

Математически это описывается через понятие выпуклости

Функция **выпуклая (вниз),**если она лежит надсвоей касательной

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

В прошлом уроке мы рассматривали выпуклые функции

Наш пример, на котором ломается спуск - невыпуклая функция

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

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

Шаг 2

Шаг 3

Что с этим делать?

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

Первый - использовать название прошлого урока: “катимся с горки”.

Если скатить с прошлого графика мячик, то он, скорее всего, найдёт правильный минимум, потому что у него есть инерция.

С помощью неё он “перелетает” локальную яму, попадая в главную яму.

Остаётся это прописать в алгоритме самого градиентного спуска.

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

Теперь введём понятие скорости, которую мы уже будем считать таким же образом:

$v_t = \beta v_{t-1} + \eta \nabla L(\theta_t)$

Здесь $\beta$ - коэффициент инерции, он показывает, насколько скорость сейчас зависит от прошлой скорости.

Дальше мы уже вычитаем из координат эту скорость и алгоритм готов.

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

Шаг 4

Шаг 5

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

Главная идея - случайность

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

Самый частый вариант - улучшение работы какой-нибудь предсказательной модели (например, нейросети)

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

Функция, которую нужно минимизировать через спуск - функция ошибки

То есть, при каждой измерении мы модель прогоняем через 100 000 картинок (а это ну очень долго)

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

Это решает сразу две проблемы:

1. Проблему с ямами, с которой мы начали

Учитывая, что функция получается достаточно случайной, она как бы постоянно колеблется

Из-за этого небольшие ямы часто сглаживаются и градиентный спуск их проскакивает

При этом, главный минимум, всё равно, будет примерно там, где и в изначальном случае

2. Проблема скорости

Проверить спуск на одном объекте во много раз быстрее, чем на 100 000 объектах

Поэтому, можно сделать сильно больше шагов

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

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