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

'''Стохастический градиентный спуск''' ({{lang-en|Stochastic gradient descent}}, '''SGD''') — это [[методИтерация итерации(математика)|итерационный]] дляметод [[Оптимизация (математика)|оптимизации]] некоторой [[Функция потерь|целевой функции]] с подходящими свойствами [[Гладкая функция|гладкости]] (например, [[Дифференцируемая функция|дифференцируемостьдифференцируемой]] или [[Субдифференциал|субдифференцируемостьсубдифференцируемой]])., Егокоторый можно расценивать как [[Стохастическая аппроксимация|стохастическую аппроксимацию]] оптимизации методом [[Градиентный спуск|градиентного спуска]], поскольку он заменяет реальный [[Градиент|градиент,]] (вычисленный изпо полногополному {{не переведено 5|Набор данных|наборанабору данных||data set}}), путёмего оценкиоценкой, такового (вычисленноговычисленной из случайно выбранного [[Подмножество|подмножества]] данных){{sfn|Taddy|2019|с=303–307}}. Особенно вВ приложениях, связанных с обработкиобработкой [[Большие данные|больших данных]], этоиспользование стохастического градиентного спуска сокращает [[Вычислительная сложность|вычислительные ресурсы]], достигаяи болеепомогает быстрыедостичь более итерациибыстрого ввыполнения обменитераций напри более низкуюнизкой скоростьскорости сходимости{{sfn|Bottou, Bousquet|2012|с=351–368}}.

Хотя базовуюосновную идею стохастической аппроксимации можно отследить назадвплоть кдо {{не переведено 5|Алгоритм Роббинса — Монро|алгоритмуалгоритма Роббинса — Монро||Robbins–Monro algorithm}}, созданного в 1950-хе годовгоды{{sfn|Mei|2018|с=E7665–E7671}}, стохастический градиентный спуск стал важным оптимизационным методом в [[Машинное обучение|машинном обучении]]{{sfn|Taddy|2019|с=303–307}}.

где [[Параметрическая статистика|параметр]] <math>w</math>, минимизирующий <math>Q(w)</math>, следует [[Статистическая оценка|оценить]]. Каждый член суммы <math>Q_i</math> обычно ассоциируется с <math>i</math>-ым {{не переведено 5|Наблюдение (статистика)|наблюдением||Observation (statistics)}} в {{не переведено 5|Набор данных|наборе данных||data set}}, (использованном для обучения).

Когда используется дляПри минимизации вышеприведённой функции, <math>Q</math> стандартный (или «пакетный») метод [[Градиентный спуск|градиентного спуска]] осуществляетзаключается в выполнении следующиеитерационной итерациипроцедуры

где <math>\eta</math> является размером шага (называемого {{не переведено 5|скорость обучения|''скоростью обучения''||learning rate}} прив обучениимашинном машинобучении).

Во многих случаяхЧасто суммируемые функции имеют простую форму, что позволяет осуществить малозатратные вычисления длясуммирующей суммы функцийфункции и градиента суммы. Например, в статистике {{не переведено 5|Экспоненциальное семейство|однопараметрические экспоненциальные семейства||exponential families}} позволяют реализовать экономичное вычисление функциифункций и градиента.

Однако, в других случаях, вычисление градиента суммы может потребовать дорогихзатратных вычислений градиентов для всех суммируемых функций. Когда тренировочное множество огромно и нет простых формулвыражений для вычисляемых функций, вычисление сумм градиентов становится очень дорогимзатратным, поскольку вычисление градиента суммы требует вычисления градиентов отдельных членов суммы. Чтобы сэкономить на вычислениях на каждой итерации, стохастический градиентный спуск [[Семплирование (математическая статистика)|отбирает]] подмножество суммируемых функций на каждом шаге алгоритма. Это очень эффективный подход впри случаерешении большихширокомасштабных задач прив обучениимашинном машинобучении{{sfn|Bottou, Bousquet|2008|с=161–168}}.

В стохастическом (или «онлайновом») градиентном спуске истинный градиент функции <math>Q(w)</math> аппроксимируется градиентом одного тренировочного примера

Пробегая через тренировочное множество, алгоритм осуществляет приведённый выше пересчёт для каждого тренировочного примера. Через тренировочный набор может быть осуществлено несколько проходов, прежде чем алгоритм сойдётся. ЕслиДанные такие проходы происходят, данные перетряхиваютсяперемешиваются перед каждым таким проходом, чтобы избежать [[Бесконечный цикл|зацикливания]]. Типичные реализации могут использовать {{не переведено 5|скорость обучения|адаптивную скорость обучения||learning rate}}, чтобыдля алгоритмсходимости сходилсяалгоритма.

ВНа [[Псевдокод (язык описания алгоритмов)|псевдокоде]] стохастический градиентный спуск можно представить следующим образом

** Случайным образом тасуемперемешиваем примеры в тренировочном множестве.

Компромиссом между вычислением истинного градиента и градиента по одному тренировочному примеру может быть вычисление градиента по более чем одному тренировочному примеру (называемому «минипакетом») на каждом шаге. Это может бытьработать существенно лучше, чем описанный «истинный» стохастический градиентный спуск, поскольку кодв можеткоде можно использовать библиотеки {{не переведено 5|Преобразование в векторную форму|векторных форм||Vectorization (mathematics)}}, а не вычислять каждый шаг отдельно. Это может также привести к более гладкой сходимости, так как градиент, вычисляемый на каждом шаге, усредняется по большему числу тренировочных примеров.

Предположим, что мы хотим подогнатьприблизить прямую <math>\hat{y}=\! w_1 + w_2 x</math> подтренировочным тренировочный наборнабором с множеством наблюденийнаблюдениями <math> (x_1, x_2, \ldots, x_n)</math> и соответствующихсоответствующими им ответовоценками <math> (\hat{y_1}, \hat{y_2}, \ldots, \hat{y_n})</math> с помощью [[Метод наименьших квадратов|метода наименьших квадратов]]. Целевой функцией для минимизации будет

Заметим, что на каждой итерации (которая называется также пересчётомобновлением), вычисляется только градиент в одной точке <math> x_i </math> вместо вычисления на множестве всех [[Выборка|выборок]].

Стохастический градиентный спуск является популярным алгоритмом для обучения широкого ряда моделей в [[Машинное обучение|обучениимашинном машинобучении]], в частности в (линейном) [[Метод опорных векторов|методе опорных векторов]], в [[Логистическая регрессия|логистической регрессии]] (см. например, {{не переведено 5|Vowpal Wabbit|||Vowpal Wabbit}}) и в [[Графовая вероятностная модель|графовых вероятностных моделях]]{{sfn|Finkel, Kleeman, Manning|2008}}. Когда метод комбинируется с алгоритмом [[Метод обратного распространения ошибки|обратного распространения ошибки]], он является ''де факто'' стандартным алгоритмом для обучения [[Искусственная нейронная сеть|искусственных нейронных сетей]]{{sfn|LeCun и др.|2012|с=9-48}}. Его применение былоМетод также замеченоприменяется в области [[Геофизика|геофизическомгеофизики]] сообществе, особенно для приложений Full Waveform Inversion (FWI){{sfn|Díaz, Guitton|2011|с=2804-2808}}.

СтохастическийОсновным градиентныйконкурентом спускстохастического градиентного конкурируетспуска сявляется алгоритмомалгоритм {{не переведено 5|Алгоритм L-BFGS ограниченной памяти|L-BFGS||limited-memory BFGS}}, который также широко используется. Стохастический градиентный спуск использовался по меньшей мере с 1960 года для обучения моделей [[Линейная регрессия|линейной регрессии]] под именем {{не переведено 5|ADALINE|||ADALINE}}{{r|APf}}.

Как упомянуто ранее, классический стохастический градиентный спуск обычно чувствителен к {{не переведено 5|скорость обучения|скорости обучения||learning rate}} <math>\eta</math>. Быстрая сходимость требует быстрой большой скорости обучения, но это может вызвать численную нестабильностьнеустойчивость. Задача может быть главным образом решена{{sfn|Toulis, Airoldi|2017|с=1694–1727}} путём рассмотрения ''неявного изменения'', когда стохастический градиент пересчитывается на следующей итерации, а не на текущей

В качестве примера рассмотрим метод наименьших квадратов сос свойствамипеременными <math>x_1, \ldots, x_n \in\mathbb{R}^p</math> и наблюдениями <math>y_1, \ldots, y_n\in\mathbb{R}</math>. Мы хотим решить:

где <math>x_j' w=x_{j1} w_1 + x_{j, 2} w_2 + ... + x_{j,p} w_p</math> означает скалярное произведение. Заметим, что <math>x</math> может иметь "1" в качестве первого элемента. Классический стохастический градиентный спуск работает следующим образом

где <math>i</math> равномерно распределено между 1 и <math>n</math>. Хотя теоретически эта процедура сходится при относительно мягкихслабых предположениях, на практике процедура может оказаться сильно нестабильной. В частности, если <math>\eta</math> неверно задана, то <math>I - \eta x_i x_i'</math> имеют большие абсолютные собственные значения с большой вероятностью и процедура может расходиться за несколько итераций. Для контраста, ''явный стохастический градиентный спуск'' ({{lang-en|implicit stochastic gradient descent}}, ISGD) может быть выражен в виде формулы

Процедура будет оставаться численно стабильнойустойчивой виртуальнопочти для всех <math>\eta</math>, поскольку {{не переведено 5|скорость обучения|||learning rate}} теперь нормализована. Такое сравнение между классическим и явным стохастическим градиентным спуском в методе наименьших квадратов очень похоже на сравнение между {{не переведено 5|Фильтр наименьших квадратов|фильтром наименьших квадратов||Least mean squares filter}} ({{lang-en|least mean squares}}, LMS) и {{не переведено 5|Фильтр наименьших квадратов|нормированным фильтром наименьших квадратов||Least mean squares filter}} ({{lang-en|normalized least mean squares filter}}, NLMS).

<math>q() \in\mathbb{R}</math> может зависеть от <math>x_i, y_i</math>, но не от <math>w</math> непосредственно, лишь через <math>x_i'w</math>. Метод наименьших квадратов удовлетворяет этому условию, атак потомуже, удовлетворяюткак этому условию doesи [[Логистическая регрессия|логистическая регрессия]] и большинство [[обобщённая линейная модель|обобщённых линейных моделей]]. Например, в методе наименьших квадратов <math>q(x_i'w)=y_i - x_i'w</math>, а в логистической регрессии <math>q(x_i'w)=y_i - S(x_i'w)</math>, где <math>S(u)=e^u/(1+e^u)</math> является [[Логистическое уравнение|логистической функцией]]. В {{не переведено 5|Регрессия Пуассона|регрессии Пуассона||Poisson regression}} <math>q(x_i'w)=y_i - e^{x_i'w}</math>, и так далее.

В таких условия ISGD легко реализовать следующим образом. Пусть <math>f(\xi)=\eta q(x_i'w^{old} + \xi||x_i||^2)</math>, где <math>\xi</math> является— числомскаляр. Тогда ISGD эквивалентен

МасштабныйМасштабирующий множитель <math>\xi^\ast\in\mathbb{R}</math> можно найти [[Метод бисекции|методом деления отрезка пополам]], поскольку в большинстве моделей, таких как вышеупомянутые обобщённые линейные модели, функция <math>q()</math> убывает, а тогда границами поиска для <math>\xi^\ast</math> будут <math>[\min(0, f(0)), \max(0, f(0))]</math>.

где [[Параметрическая статистика|параметр]] <math>w</math>, который минимизирует <math>Q(w)</math>, следует [[Статистическая оценка|оценить]], а <math>\eta</math> является размером шага (иногда называемаяв машинном обучении называется {{не переведено 5|скорость обучения|''скоростью обучения''||learning rate}} при обучении машин).

Название «импульс» берёт началопроисходит от понятия [[импульс]]а в физике — вектор весов <math>w</math>, понимаемый как трасса частицы по пространству параметров{{sfn|Rumelhart, Hinton, Williams|1986|с=533–536}}, испытывает ускорение от градиента функции потерь («[[Сила|силы]]»). В отличие от классического стохастического градиентного спуска, метод пытается сохранить продвижение в том же направлении, предотвращая колебания. Импульс использовался успешно специалистами по информатике для обучения [[Искусственная нейронная сеть|искусственных нейронных сетей]] в течение нескольких десятилетий{{r|Zeiler}}.

''Усреднённый стохастический градиентный спуск'', разработанный независимо Руппертом и Поляком в конце 1980-х годов, является обычным стохастическим градиентным спуском, который записывает среднее вектора параметров. То есть пересчётобновление тотпроисходит так же, чтокак и в обычном методе стохастического градиентного спуска, но алгоритм также отслеживает{{sfn|Polyak, Juditsky|1992|с=838–855}}. величину

Когда оптимизация завершена, векторусреднённый среднихвектор параметров занимает место {{mvar|w}}.

''AdaGrad'' (адаптивный градиентный алгоритм, {{lang-en|adaptive gradient algorithm}}) является модификацией стохастического алгоритма градиентного спуска с отдельной для каждого параметра {{не переведено 5|скорость обучения|скоростью обучения||learning rate}}. Алгоритм был опубликован в 2011{{sfn|Duchi, Hazan, Singer|2011|с=2121–2159}}{{r|Perla}}. Неформально, этоМетод увеличивает скорость обучения для параметров с редкими данными и уменьшает скорость обучения для параметров с менее редкими. Эта стратегия увеличивает скорость сходимости по сравнению со стандартным стохастическим методом градиентного спуска в условиях, когда данные редки и соответствующие параметры более информативны. Примерами такихприложений приложенияметода являются обработка [[Естественный язык|естественных языков]] и [[Теория распознавания образов|распознавание образов]]{{sfn|Duchi, Hazan, Singer|2011|с=2121–2159}}. Алгоритм имеет базовую скорость обучения <math>\eta</math>, но она умножается на элементы вектора <math>\{G_{j,j}\}</math>, который является диагональю матрицы [[Внешнее произведение|внешнего произведения]]

Этот вектор обновляется после каждой итерации. Формула пересчётаобновления:

Каждый элемент <math>\{G_{(i,i)}\}</math> даёт множитель для скорости обучения, применяемый к одному параметру <math>w_i</math>. Поскольку знаменатель в этом множителе, <math>\sqrt{G_i}=\sqrt{\sum_{\tau=1}^t g_\tau^2}</math>, является [[Норма (математика)#Линейные нормированные пространства|нормой ''ℓ''<submath>l_{2}</submath>]] предыдущей производной, большие изменения параметра ослабляются, в то время как параметры, получающие малые изменения получают более высокие скорости обучения{{r|Zeiler}}.

''RMSProp'' (от {{lang-en|Root Mean Square Propagation}}) — это метод, в котором {{не переведено 5|скорость обучения|||learning rate}} настраивается для каждого параметра. Идея заключается в делении скорости обучения для весов на сгруппированные[[Скользящая средняя|скользящие средние]] значения недавних градиентов для этого веса{{r|TTHG}}. Таким образом, первое сгруппированноескользящее среднее вычисляется в терминах среднеквадратичного

RMSProp показал прекраснуюхорошую адаптацию скорости обучения в различных приложениях. RMSProp можно рассматривать как обобщение {{не переведено 5|Rprop|||Rprop}}. и методМетод способенможет работать с минипакетами, а не только с полными пакетами {{r|Hinton}}.

''Adam''{{r|DeBa}} (сокращение от «метод Адаптивнойадаптивной Оценкиоценки Моментовмоментов», {{lang-en|Adaptive Moment Estimation}}) — это обновление оптимизатора ''RMSProp'' оптимизатора. В этом оптимизационном алгоритме используются сгруппированныескользящие средние как градиентов, так и вторых моментов градиентов. Если даны параметры <math> w^ {(t)} </math>, аи функция потерь <math> L ^ {(t)} </math>, где <math> t </math> отражает индекс текущей итерации (отчёт начинается с <math> 0 </math>), пересчётобновление параметра алгоритмом Adam задаётся формулами

где <math>\epsilon</math> является— малоймалая добавкойдобавка, используемойиспользуемая для предотвращения деления на 0ноль, а <math>\beta_1</math> и <math>\beta_2</math> являются— коэффициентамикоэффициенты забывания для градиентов и вторых моментов градиентов соответственно. Возведение в квадрат и квадратный корень вычисляются поэлементно.

Основанный на фильтре Калмана стохастический градиентный спуск ({{lang-en|Kalman-based Stochastic Gradient Descent}}, kSGD){{sfn|Patel|2016|с=2620–2648}} является онлайновым и офлайновым алгоритмом для параметров обучения для статистических задач для моделей {{не переведено 5|Квазиправдоподобие|квазиправдоподобия||quasi-likelihood}}, куда входят [[Линейная регрессия|линейные модели]], [[Нелинейная регрессия|нелинейные модели]], [[обобщённая линейная модель|обобщённые линейные модели]], и [[Искусственная нейронная сеть|нейронные сети]] с {{не переведено 5|Среднеквадратичная ошибка|среднеквадратичными потерями||Mean squared error}} как специальныйчастный случай. Для онлайновых задач обучения kSGD является специальнымчастным случаем [[Фильтр Калмана|фильтра Калмана]] для задач линейной регрессии, специальныйчастным случайслучаем {{не переведено 5|Расширенный фильтр Калмана|расширенного фильтра Калмана||Extended Kalman filter}} для задач нелинейной регрессии и может рассматриваться как инкрементальный метод [[Алгоритм Гаусса — Ньютона|Гаусса — Ньютона]]. Более того, ввиду связи kSGD с фильтром Калмана и связи естественного градиентного спуска{{sfn|Cichocki, Chen, Amari|1997|с=1345–1351}} с фильтром Калмана{{r|Yann}}, kSGD является серьёзным улучшениеулучшением популярного естественного метода градиентного спуска.

Для описания алгоритма предположим, что для <math>Q_i(w)</math>, где <math>w \in \mathbb{R}^p</math>, определена <math>(Y_i,X_i)\in \mathbb{R} \times \mathbb{R}^d</math> так, что

где <math>\mu(X_i,w)</math> — функция усреднения (то есть ожидаемое[[математическое значениеожидание]] <math>Y_i</math> от <math>X_i</math>), а <math>V(\mu(X_i,w))</math> является— функциейфункция дисперсии (то есть дисперсия <math>Y_i</math> для <math>X_i</math>). Тогда, пересчётобновление параметра <math> w(t+1) </math> и пересчёт ковариантной матрицы <math> M(t+1) </math> задаётсязадаются следующими выражениями

где <math>\gamma_1,\gamma_2</math> являются гиперпараметрами. Пересчёт <math>M(t)</math> может привести к тому, что ковариантная матрица станет неопределённой, что можно избежать за счёт умножения матрицы на матрицу. <math>M(0)</math> может быть любой [[Положительно определённая матрица|положительно определённой]] [[Симметричная матрица|симметричной]] матрицей, но обычно берётся [[единичная матрица]]. Как заметил Патель{{sfn|Patel|2016|с=2620–2648}}, для всех задач, не считая линейной регрессии, требуются повторные прогоны для обеспечения сходимости алгоритма, но в его работе не приведены теоретические детали или детали реализации. В тесно связанном офлайновом мультипакетном методе для нелинейной регрессии, проанализированным Бертсекасом{{sfn|Bertsekas|1996|с=807–822}}, для доказательства сходимости использовался коэффициент забывания при пересчёте ковариантной матрицы.

Известно, что стохастический аналог стандартного (детерминированного) [[Метод Ньютона#Метод Ньютона — Рафсона|алгоритма Ньютона — РэпсонаРафсона]] (метод «второго порядка») даёт асимптотически оптимальноеоптимальный или почти оптимальный вид итеративной оптимизации в условиях стохастической аппроксимации. Метод, который использует прямое вычисление [[Гессиан функции|матриц Гессе]] членов суммы в эмпирической функции риска, разрабатывали Бёрд, Хансен, Носедаль и Сингер{{sfn|Byrd, Hansen, Nocedal, Singer|2016|с=1008–1031}}. Однако, прямое определение требующихся матриц ХессеГессе для оптимизации может оказаться невозможным на практике. Практические и теоретически выглядящие методы для версии второго порядка алгоритма SGD, который не требует прямой информации о гессиане, дали Сполл и другие{{sfn|Spall|2000|с=1839−1853}}{{sfn|Spall|2009|с=1216–1229}}{{sfn|Bhatnagar, Prasad, Prashanth|2013}} (Менее эффективный метод, основанный на конечных разностях вместо одновременного пересчёта, дал Рупперт{{sfn|Ruppert|1985|с=236–245}}). Эти методы, не требуя напрямую информацию о гессиане, базируются либо на значениях членов суммы в эмпирической функции риска, приведённой выше, либо значениях градиентов членов суммы (то есть ввода SGD). В частности, оптимальность второго порядка асимптотически достижима без непосредственного вычисления матриц Гессе членов суммы в эмпирической функции риска.