Стохастический градиентный спуск (, SGD) — итерационный метод для оптимизации целевой функции с подходящими свойствами гладкости (например, дифференцируемость или субдифференцируемость). Его можно расценивать как стохастическую аппроксимацию оптимизации методом градиентного спуска, поскольку он заменяет реальный градиент, вычисленный из полного набора данных, оценкой, вычисленной из случайно выбранного подмножества данных. Это сокращает задействованные вычислительные ресурсы и помогает достичь более высокой скорости итераций в обмен на более низкую скорость сходимости. Особенно большой эффект достигается в приложениях, связанных с обработкой больших данных.
Хотя базовая идея стохастической аппроксимации восходит к алгоритму Роббинса-Монро 1950-х годов, стохастический градиентный спуск стал важным оптимизационным методом в машинном обучении.
Предпосылки
И статистическая , и машинное обучение рассматривают задачу минимизации целевой функции, имеющей форму суммы
где параметр , минимизирующий , следует оценить. Каждый член суммы обычно ассоциируется с -ым в наборе данных, использованном для обучения.
В классической статистике задачи минимизации суммы возникают в методе наименьших квадратов и методе максимального правдоподобия (для независимых наблюдений). Общий класс оценок, возникающих в виде минимизации сумм, называется . Однако еще в конце XX века было замечено, что требование даже локальной минимизации слишком ограничительно для некоторых задач метода максимального правдоподобия. Поэтому современные теоретики-статистики часто рассматривают стационарные точки функции правдоподобия (или нули её производной, и другие ).
Задача минимизации суммы возникает также при минимизации эмпирического риска. В этом случае является значением функции потерь на -ом примере, а является эмпирическим риском.
При использовании для минимизации вышеприведённой функции, стандартный (или «пакетный») метод градиентного спуска осуществляет следующие итерации:
где является размером шага, называемым скоростью обучения в машинном обучении.
Во многих случаях суммируемые функции имеют простую форму, что позволяет осуществить малозатратные вычисления для суммы функций и градиента суммы. Например, в статистике использование позволяет произвести экономичное вычисление функции и градиента.
Однако в других случаях вычисление градиента суммы может потребовать дорогих расчетов градиентов для всех суммируемых функций. На большом тренировочном множестве в отсутствие простых формул вычисление сумм градиентов становится очень дорогим, поскольку вычисление градиента суммы требует вычисления градиентов отдельных членов суммы. Для уменьшения объема вычислений стохастический градиентный спуск отбирает подмножество суммируемых функций на каждой итерации алгоритма. Этот подход особенно эффективен для больших задач машинного обучения.
Итеративный метод
В стохастическом («онлайновом») градиентном спуске истинный градиент аппроксимируется градиентом одного тренировочного примера
Пробегая через тренировочное множество, алгоритм осуществляет приведённый выше пересчёт для каждого тренировочного примера. Для достижения сходимости алгоритма может потребоваться несколько проходов по тренировочному набору данных. Перед каждым новым проходом данные в наборе перемешиваются для устранения возможности зацикливания алгоритма. Типичные реализации могут использовать скорость обучения для улучшения сходимости.
В псевдокоде стохастический градиентный спуск можно представить следующим образом: Выбрать начальный вектор параметров и скорость обучения . Повторять до достижения приблизительного минимума: Случайным образом перемешать примеры в тренировочном множестве. Для выполнить
Компромиссом между вычислением истинного градиента и градиента по одному тренировочному примеру может быть вычисление градиента по более чем одному тренировочному примеру, называемому «минипакетом», на каждом шаге. Это может быть существенно лучше, чем описанный «истинный» стохастический градиентный спуск, поскольку код может использовать библиотеки вместо отдельных вычислений на каждом шаге. Это может также привести к более гладкой сходимости, так как градиент, вычисляемый на каждом шаге, усредняется по большему числу тренировочных примеров.
Сходимость стохастического градиентного спуска анализировалась с помощью теорий выпуклой минимизации и стохастической аппроксимации. В упрощенном виде результат можно представить так: при убывании скоростью обучения с подходящей скоростью с учётом относительно слабых предположений, стохастический градиентный спуск сходится почти наверняка к глобальному минимуму, если целевая функция выпукла или псевдовыпукла, в противном случае метод сходится почти наверняка к локальному минимуму. Фактически, это следствие теоремы Роббинса — Сигмунда.
Пример Предположим, что мы хотим приблизить прямую тренировочным набором с множеством наблюдений и соответствующих ответов с помощью метода наименьших квадратов. Целевой функцией для минимизации будет
Последняя строка в вышеприведённом псевдокоде для задачи превращается в
Заметим, что на каждой итерации (которая называется также пересчётом), вычисляется только градиент в одной точке вместо вычисления на множестве всех выборок.
Ключевое различие по сравнению со стандартным (пакетным) градиентным спуском в том, что только одна часть данных из всего множества используется на каждом шаге и эта часть выбирается на каждом шаге случайно.
Известные приложения Стохастический градиентный спуск является популярным алгоритмом для обучения широкого ряда моделей в машинном обучении, в частности в (линейном) методе опорных векторов, в логистической регрессии (см. например, ) и в графовых вероятностных моделях. Когда метод комбинируется с алгоритмом обратного распространения ошибки, он является де факто стандартным алгоритмом для обучения искусственных нейронных сетей. Его применение было также замечено в геофизическом сообществе, особенно для приложений Full Waveform Inversion (FWI).
Стохастический градиентный спуск конкурирует с алгоритмом , который также широко используется. Стохастический градиентный спуск использовался по меньшей мере с 1960 года для обучения моделей линейной регрессии под именем .
Другой стохастический алгоритм градиентного спуска является адаптивным (, LMS).
Разновидности и модификации Существует множество модификаций алгоритма стохастического градиентного спуска. В частности, в машинном обучении проблемой является выбор скоростью обучения (размера шага): при большом шаге алгоритм может расходиться, а при маленьком — сходимость слишком медленная. Для решения этой проблемы можно использовать расписание скорости обучения, при котором скорость убывает с увеличением номера итерации . При этом на первых итерациях значения параметров изменяются значительно, а на более поздних итерациях — только лишь уточняются. Такие расписания известны со времён работы Мак-Куина по кластеризации методом -средних. Некоторые практические рекомендации по выбору шага в некоторых вариантах SGD даны в секциях 4.4, 6.6 и 7.5 статьи Сполла (2003).
Не выраженные явно изменения (ISGD) Как упомянуто ранее, классический стохастический градиентный спуск обычно чувствителен к скорости обучения . Быстрая сходимость требует большой скорости обучения, но это может вызвать численную неустойчивость. Задача может быть главным образом решена путём рассмотрения неявного изменения, когда стохастический градиент пересчитывается на следующей итерации, а не на текущей
Это равенство неявное, поскольку появляется на обеих сторонах равенства. Это стохастическая форма проксимального градиентного метода, поскольку пересчёт может быть выражен в виде
В качестве примера рассмотрим метод наименьших квадратов со свойствами и наблюдениями . Мы хотим решить:
где означает скалярное произведение.
Заметим, что может иметь «1» в качестве первого элемента. Классический стохастический градиентный спуск работает следующим образом
где равномерно распределено между 1 и . Хотя теоретически эта процедура сходится при относительно мягких предположениях, на практике процедура может оказаться сильно нестабильной. В частности, если неверно задана, то имеют большие абсолютные собственные значения с большой вероятностью и процедура может расходиться за несколько итераций. Для контраста, явный стохастический градиентный спуск (, ISGD) может быть выражен в виде формулы
Процедура будет оставаться численно устойчивой почти для всех , поскольку скоростью обучения теперь нормализована. Такое сравнение между классическим и явным стохастическим градиентным спуском в методе наименьших квадратов очень похоже на сравнение между (, LMS) и (, NLMS).
Хотя решение в аналитическом виде для ISGD возможно только в методе наименьших квадратов, процедуру можно эффективно реализовать в широкий ряд моделей. В частности, предположим, что зависит от только как линейная комбинация свойств , так что мы можем записать , где вещественнозначная функция может зависеть от , но не от непосредственно, лишь через . Метод наименьших квадратов удовлетворяет этому условию, а потому удовлетворяют этому условию логистическая регрессия и большинство обобщённых линейных моделей. Например, в методе наименьших квадратов , а в логистической регрессии , где является логистической функцией. В , и так далее.
В таких условия ISGD легко реализовать следующим образом. Пусть , где является числом. Тогда ISGD эквивалентен
Масштабный множитель можно найти методом деления отрезка пополам, поскольку в большинстве моделей, таких как вышеупомянутые обобщённые линейные модели, функция убывает, а тогда границами поиска для будут .
Импульс Более поздние разработки включают метод импульса, который появился в статье Румельхарта, Хинтона и Уильямса об обучении с обратным распространением ошибки. Стохастический градиентный спуск с импульсом запоминает изменение на каждой итерации и определяет следующее изменение в виде линейной комбинации градиента и предыдущего изменения:
что приводит к
где параметр , который минимизирует , следует оценить, а является размером шага (иногда называется скоростью обучения в машинном обучении).
Название «импульс» берёт начало от импульса в физике — вектор весов , понимаемый как трасса частицы по пространству параметров, испытывает ускорение от градиента функции потерь («силы»). В отличие от классического стохастического градиентного спуска, метод пытается сохранить продвижение в том же направлении, предотвращая колебания. Импульс использовался успешно специалистами по информатике для обучения искусственных нейронных сетей в течение нескольких десятилетий.
Усреднение Усреднённый стохастический градиентный спуск, разработанный независимо Руппертом и Поляком в конце 1980-х годов, является обычным стохастическим градиентным спуском, который записывает среднее вектора параметров. То есть пересчёт тот же, что и в обычном методе стохастического градиентного спуска, но алгоритм также отслеживает
.
Когда оптимизация завершена, вектор средних параметров занимает место .
AdaGrad AdaGrad (адаптивный градиентный алгоритм, ), опубликованный в 2011, является модификацией стохастического алгоритма градиентного спуска с отдельной для каждого параметра скоростью обучения. Неформально говоря, это увеличивает скорость обучения для параметров с редкими данными и уменьшает скорость обучения для параметров с менее редкими. Эта стратегия увеличивает скорость сходимости по сравнению со стандартным стохастическим методом градиентного спуска в условиях, когда данные редки и соответствующие параметры более информативны. Примерами таких приложений являются обработка естественных языков и распознавание образов. Алгоритм имеет базовую скорость обучения , но она умножается на элементы вектора , который является диагональю матрицы внешнего произведения
где , градиент на итерации . Диагональ задаётся выражением
.
Этот вектор обновляется после каждой итерации. Формула пересчёта
или, записывая как пересчёт по параметрам,