Реализация и сравнение трех основных вариантов градиентного спуска
1. Введение
Алгоритм градиентного спуска - это итерационный метод оптимизации первого порядка для поиска локального минимума функции (в идеале - глобального). Его базовую реализацию и поведение я описал в другой статье. В нем рассматриваются три основных варианта с точки зрения количества данных, которые алгоритм использует для вычисления градиента и выполнения шагов.
Эти 3 варианта:
- Пакетный градиентный спуск (BGD)
- Стохастический градиентный спуск (SGD)
- Мини-пакетный градиентный спуск (mBGD)
В этой статье мы увидим их производительность в простой задаче линейной регрессии.
Подведем итоги - одномерная линейная функция определяется как:
Параметризуется двумя коэффициентами:
- a0 - смещение
- a1 - наклон функции.
В демонстрационных целях мы определяем следующую линейную функцию:
Где σ - белый (гауссов) шум. Приведенный ниже код генерирует 100 точек для набора данных, с которым мы будем работать.
Функция стоимости (метрика), которую мы хотим минимизировать, - это Среднеквадратичная ошибка, определяемая как:
В случае одномерной функции ее можно явно записать как:
В приведенном ниже коде рассчитывается стоимость MSE для заданного набора из двух параметров.
Обратите внимание, что для нашего исходного коэффициента из-за случайной ошибки (белого шума) функция минимальной стоимости не равна 0 (она будет меняться при каждом запуске), а на этот раз равна:
Визуализация ниже показывает эту функцию вблизи оптимальной точки. Мы видим, что он имеет форму вытянутой чаши.
Чтобы использовать любой алгоритм градиентного спуска, мы должны вычислить градиент этой функции. Поскольку для одномерной линейной регрессии наш алгоритм минимизирует 2 коэффициента, мы должны вычислять производные для каждого из них отдельно. Заметим, что:
Теперь, используя цепное правило, получаем следующий результат:
Следующий раздел посвящен самим алгоритмам. Используемый код доступен в моем репозитории GitHub.
2. Пакетный градиентный спуск
В Batch GD весь набор данных используется на каждом этапе для вычисления градиента (помните: мы не вычисляем саму функцию стоимости). На графике ниже показано, как он себя ведет в процессе оптимизации. Для нахождения глобального оптимума (в пределах заданного допуска) требуется 86 итераций.
Траектория пакетного градиентного спуска выглядит хорошо - с каждым шагом она приближается к оптимальной, а поперечные колебания со временем становятся все меньше. Это причина того, что у него хорошая скорость сходимости.
Чтобы точно определить скорость его сходимости, нам нужно провести некоторые математические вычисления. Чтобы не усложнять, предположим, что наша функция стоимости сильно выпукла (дважды дифференцируема) и имеет липшицевский градиент с L> 0, определяемым как:
Второе предположение ограничивает скорость изменения градиента.
Если вы можете рассчитать L, вы можете получить так называемую «границу гарантированного прогресса», которая представляет собой размер шага (скорость обучения), гарантирующий сходимость:
Однако не следует использовать это значение на практике, потому что оно очень мало и сходится медленно. Поиск наилучшей скорости обучения - это огромная тема, которую стоит посвятить отдельной статье - просто проверьте такие вещи, как, например, поиск по строке с обратным прослеживанием, условие Armijo или условие Вульфа ».
При фиксированном размере шага скорость сходимости зависит от выпуклости функции.
Для простых (слабых) выпуклых функций скорость сходимости равна [1]:
где k - количество итераций. Эта скорость называется «сублинейной сходимостью», и для заданного допуска ε требуется следующее количество итераций для сходимости [1]:
Для сильно выпуклых функций коэффициент равен [1]:
где 0 ‹γ‹ 1, k - количество итераций. Эта скорость называется «линейной сходимостью» и означает, что Batch GD работает экспоненциально быстро. Для заданного допуска ε требуется следующее количество итераций для схождения [1]:
Плюсы и минусы пакетного градиентного спуска:
Плюсы:
- Простой алгоритм, которому просто нужно вычислить градиент
- Во время обучения можно использовать фиксированную скорость обучения, и можно ожидать, что BGD сойдется
- Очень быстрое отношение сходимости к глобальному минимуму, если функция потерь выпуклая (и к локальному минимуму для невыпуклых функций)
Минусы:
- Даже с векторизованной реализацией это может быть медленным, когда наборы данных огромны (в случае больших данных).
- Не все задачи являются выпуклыми, поэтому алгоритмы градиентного спуска не универсальны.
Типичные варианты использования:
- Небольшие базы данных, которые помещаются в память компьютера
- Проблемы с выпуклыми функциями стоимости (например, OLS, логистическая регрессия и т. Д.)
3. Стохастический градиентный спуск.
Идея стохастического градиентного спуска заключается не в использовании всего набора данных для расчета градиента, а только в одном образце. Задача - ускорить процесс. При отборе пробы есть два основных правила:
- рандомизированное правило - произвольно выбранная выборка (возможны повторы)
- циклическое правило - каждая выборка один раз (отсутствие или минимальное количество повторений)
Рандомизированное правило встречается гораздо чаще.
- На графике ниже показано, как SGD сходится к окончательному решению (примерный запуск). Красная точка указывает образец, выбранный для данного шага вычислений.
Из-за своей стохастической природы каждый прогон требует разного количества шагов для достижения глобального минимума. Ниже гистограмма итераций, необходимых для 100 прогонов с той же начальной точкой (0,0) и одинаковой скоростью обучения (0,05).
В отличие от Batch GD, он не сходится напрямую к решению, потому что он использует только 1 образец на итерацию, а это означает, что шаги довольно шумные. Однако он намного эффективнее - меньше нагрузка на CPU / GPU. Этот эффект едва заметен для небольших баз данных (например, этой), но оказывает огромное влияние на производительность при работе с большими данными.
Ниже график, показывающий траекторию шагов SGD из приведенного выше примера.
Скорость сходимости для стохастического градиентного спуска с фиксированным размером шага [1]:
Это означает, что у SGD нет линейной скорости сходимости, как у пакетного градиентного спуска - просто это означает, что ему нужно больше итераций (но не обязательно вычислительного времени).
Плюсы и минусы стохастического градиентного спуска:
Плюсы:
- Сходится быстрее (меньше времени), чем Batch GD для огромных наборов данных
- Может выходить из локальных минимумов
Минусы:
- Шаги более шумные - SGD может потребоваться больше итераций, чтобы сойтись с ограничениями
- Он может "колебаться" вокруг глобального оптимума - для этого может потребоваться больший допуск, чем у Batch GD.
Типичный вариант использования:
- Является основой более совершенных стохастических алгоритмов, используемых при обучении искусственных нейронных сетей.
4. Мини-пакетный градиентный спуск.
Мини-пакетный градиентный спуск - это подход к поиску точного баланса между чистым SGD и пакетным градиентным спуском. Идея состоит в том, чтобы использовать подмножество наблюдений для обновления градиента. Количество точек, используемых для каждого размера, называется размером пакета, а каждая итерация пакета называется эпохой. На анимации ниже показан процесс сходимости с использованием точек на каждом шаге (размер пакета 10).
Траектория по-прежнему шумная, но все более уверенно приближается к минимуму.
Коэффициент сходимости этого алгоритма находится где-то между BGD и mBGD и составляет [1]:
где b - размер партии.
Плюсы и минусы мини-пакетного градиентного спуска:
Плюсы:
- Хороший баланс между BGD и SGD с точки зрения эффективности
- Легко помещается в память компьютера
- Может уйти от локальных минимумов
Минусы:
- Он все еще может «колебаться» вокруг глобального оптимума - для этого может потребоваться больший допуск, чем у Batch GD, но меньший, чем SGD.
- Еще один гиперпараметр для оптимизации - размер партии.
Типичный вариант использования:
- Это очень распространенный алгоритм обучения глубоких нейтральных сетей.
5. Резюме
Мы рассмотрели 3 основных варианта алгоритмов градиентного спуска. В современном ML используются более продвинутые и эффективные версии, но при этом используются фундаментальные идеи, описанные здесь. Дальнейшие модификации включают в себя такие вещи, как адаптивная скорость обучения, различные импульсы (например, Нестерова), усреднение и т. Д.
Некоторые очень популярные реализации:
В настоящее время ведутся исследования по их дальнейшему совершенствованию для невыпуклых функций (глубокие нейронные сети), которые включают различные идеи для обработки данных.
Если вы хотите узнать больше о темах в этой статье, я настоятельно рекомендую вам ознакомиться со следующими материалами:
- Стохастический градиентный спуск, Райан Тибширани из Калифорнийского университета в Беркли
- Выпуклая оптимизация Райана Тибширани из Калифорнийского университета в Беркли
- Ускорение обучения глубоких нейронных сетей с непоследовательным стохастическим градиентным спуском
- Несходимость стохастического градиентного спуска при обучении глубоких нейронных сетей
- Анализ сходимости распределенного стохастического градиентного спуска с перетасовкой
