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

отмена правки 113584685 участника VCarik (обс.) Пожалуйста, сделайте нормальные правки. То, что вы поправили никуда не годится.
(отмена правки 113584017 участника Jumpow (обс.) Моя правка содержит исправления многочисленных стилевых и лексических неточностей автоматического перевода с английского, в частности пресловутое «обучение машин». Пожалуйста, исправьте отдельно те моменты, которые кажутся Вам совершенно неприемлемыми.)
Метки: отмена Задача для новичков отменено
(отмена правки 113584685 участника VCarik (обс.) Пожалуйста, сделайте нормальные правки. То, что вы поправили никуда не годится.)
Метка: отмена
'''Стохастический градиентный спуск''' ({{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}}.
 
== Предпосылки ==
И [[Статистика|статистическая]] {{не переведено 5|M-оценка|оценка||M-estimation}}, и [[машинное обучение]] рассматривают задачу [[Оптимизация (математика)|минимизации]] [[Функция потерь|целевой функции]], имеющей форму суммы
: <math>Q(w)=\frac{1}{n}\sum_{i=1}^n Q_i(w),</math>
где [[Параметрическая статистика|параметр]] <math>w</math>, минимизирующий <math>Q(w)</math>, следует [[Статистическая оценка|оценить]]. Каждый член суммы <math>Q_i</math> обычно ассоциируется с <math>i</math>-ым {{не переведено 5|Наблюдение (статистика)|наблюдением||Observation (statistics)}} в {{не переведено 5|Набор данных|наборе данных||data set}}, (использованном для обучения).
 
В классической статистике задачи минимизации суммы возникают в [[Метод наименьших квадратов|методе наименьших квадратов]] и [[Метод максимального правдоподобия|методе максимального правдоподобия]] (для независимых наблюдений). Общий класс оценок, возникающих в виде минимизации сумм называется {{не переведено 5|M-оценка|M-оценками||M-estimator}}. Однако, в статистике давно признали, что требование даже локальной минимизации слишком ограничительно для некоторых задач метода максимального правдоподобия{{sfn|Ferguson|1982|с=831–834}}. Поэтому современные теоретики-статистики часто рассматривают [[Критическая точка (математика)|стационарные точки]] [[Функция правдоподобия|функции правдоподобия]] (или нули её производной, {{не переведено 5|Количественный показатель (статистика)|функцию количественной оценки||Score (statistics)}} и другие {{не переведено 5|Метод оценочных уравнений|методы оценочных уравнений||estimating equations}}).
Задача минимизации суммы возникает также при [[Минимизация эмпирического риска|минимизации эмпирического риска]]. В этом случае <math>Q_i(w)</math> является значением [[Функция потерь|функции потерь]] на <math>i</math>-ом примере, а <math>Q(w)</math> является эмпирическим риском.
 
ПриКогда используется для минимизации вышеприведённой функции <math>Q</math>, стандартный (или «пакетный») метод [[Градиентный спуск|градиентного спуска]] заключается в выполненииосуществляет итерационнойследующие процедурыитерации
: <math>w := w - \eta \nabla Q(w)=w - \eta \sum_{i=1}^n \nabla Q_i(w)/n,</math>
где <math>\eta</math> является размером шага (называемого {{не переведено 5|скорость обучения|''скоростью обучения''||learning rate}} в машинномпри обучении машин).
 
ЧастоВо многих случаях суммируемые функции имеют простую форму, что позволяет осуществить малозатратные вычисления суммирующейдля функциисуммы функций и градиента суммы. Например, в статистике {{не переведено 5|Экспоненциальное семейство|однопараметрические экспоненциальные семейства||exponential families}} позволяют реализовать экономичное вычисление функцийфункции и градиента.
 
Однако, в других случаях, вычисление градиента суммы может потребовать затратныхдорогих вычислений градиентов для всех суммируемых функций. Когда тренировочное множество огромно и нет простых выражений для вычисляемых функцийформул, вычисление сумм градиентов становится очень затратнымдорогим, поскольку вычисление градиента суммы требует вычисления градиентов отдельных членов суммы. Чтобы сэкономить на вычислениях на каждой итерации, стохастический градиентный спуск [[Семплирование (математическая статистика)|отбирает]] подмножество суммируемых функций на каждом шаге алгоритма. Это очень эффективный подход прив решениислучае широкомасштабныхбольших задач в машинномпри обучении машин{{sfn|Bottou, Bousquet|2008|с=161–168}}.
 
== Итеративный метод ==
[[Файл:stogra.png|thumb|right|Флуктуации целевой функции по мере работы алгоритма]]
 
В стохастическом (или «онлайновом») градиентном спуске истинный градиент функции <math>Q(w)</math> аппроксимируется градиентом одного тренировочного примера
: <math>w := w - \eta \nabla Q_i(w).</math>
Пробегая через тренировочное множество, алгоритм осуществляет приведённый выше пересчёт для каждого тренировочного примера. Через тренировочный набор может быть осуществлено несколько проходов, прежде чем алгоритм сойдётся. ДанныеЕсли перемешиваютсятакие проходы происходят, данные перетряхиваются перед каждым таким проходом, чтобы избежать [[Бесконечный цикл|зацикливания]]. Типичные реализации могут использовать {{не переведено 5|скорость обучения|адаптивную скорость обучения||learning rate}}, длячтобы сходимостиалгоритм алгоритмасходился.
 
НаВ [[Псевдокод (язык описания алгоритмов)|псевдокоде]] стохастический градиентный спуск можно представить следующим образом
<div style="margin-left: 35px; width: 600px">
{{Начало коробки|blue}}
* Выбираем начальный вектор параметров <math>w</math> и скорость обучения <math>\eta</math>.
* Повторяем пока не получим приблизительный минимум:
** Случайным образом перемешиваемтасуем примеры в тренировочном множестве.
** Для <math> i=1, 2, ..., n</math> выполняем
*** <math>\! w := w - \eta \nabla Q_i(w).</math>
</div>
 
Компромиссом между вычислением истинного градиента и градиента по одному тренировочному примеру может быть вычисление градиента по более чем одному тренировочному примеру (называемому «минипакетом») на каждом шаге. Это может работатьбыть существенно лучше, чем описанный «истинный» стохастический градиентный спуск, поскольку вкод коде можноможет использовать библиотеки {{не переведено 5|Преобразование в векторную форму|векторных форм||Vectorization (mathematics)}}, а не вычислять каждый шаг отдельно. Это может также привести к более гладкой сходимости, так как градиент, вычисляемый на каждом шаге, усредняется по большему числу тренировочных примеров.
 
Сходимость стохастического градиентного спуска анализировалась с помощью теорий [[Выпуклое программирование|выпуклой минимизации]] и [[Стохастическая аппроксимация|стохастической аппроксимации]]. Если коротко, когда {{не переведено 5|скорость обучения|скорости обучения||learning rate}} <math>\eta</math> убывают с подходящей скоростью, с учётом относительно слабых предположений, стохастический градиентный спуск сходится [[Почти достоверное событие|почти наверняка]] к глобальному минимуму, если целевая функция [[Выпуклая функция|выпукла]] или [[Псевдовыпуклая функция|псевдовыпукла]], в противном случае метод сходится почти наверняка к локальному минимуму{{sfn|Bottou|1998}}{{sfn|Kiwiel|2001|с=1–25}}. Фактически, это следствие теоремы Роббинса — Сигмунда{{sfn|Robbins, Siegmund|1971}}.
 
== Пример ==
Предположим, что мы хотим приблизитьподогнать прямую <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>Q(w)=\sum_{i=1}^n Q_i(w)=\sum_{i=1}^n \left(\hat{y_i}-y_i\right)^2=\sum_{i=1}^n \left(w_1 + w_2 x_i - y_i\right)^2.</math>
 
- \eta \begin{bmatrix} 2 (w_1 + w_2 x_i - y_i) \\ 2 x_i(w_1 + w_2 x_i - y_i) \end{bmatrix}.</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|Фильтр наименьших квадратов|фильтром наименьших квадратов||Least mean squares filter}} ({{lang-en|least mean squares adaptive filter}}, LMS)]].
Стохастический градиентный спуск использовался по меньшей мере с 1960 года для обучения моделей [[Линейная регрессия|линейной регрессии]] под именем {{не переведено 5|ADALINE|||ADALINE}}{{r|APf}}.
 
== ОбобщенияРазновидности и модификации ==
Другой стохастический алгоритм градиентного спуска является адаптивным {{не переведено 5|Фильтр наименьших квадратов|фильтром наименьших квадратов||Least mean squares filter}} ({{lang-en|least mean squares adaptive filter}}, LMS).
Существует множество модификаций алгоритма стохастического градиентного спуска. В частности, в машинном обучении проблемой является выбор {{не переведено 5|Скорость обучения|скорости обучения||learning rate}} (размера шага): при большом шаге алгоритм может расходиться, а при маленьком — сходимость слишком медленная. Для решения этой проблемы можно использовать {{Не переведено 5|расписание скорости обучения|||Learning_rate#Learning_rate_schedule}}, при котором скорость обучения <math>\eta_t</math> убывает с увеличением номера итерации <math>t</math>. При этом на первых итерациях значения параметров изменяются значительно, а на более поздних итерациях — только лишь уточняются. Такие расписания известны со времён работы Мак-Куина по [[Метод k-средних|кластеризации методом {{mvar|k}}-средних]]{{sfn|Darken, Moody|1990}}. Некоторые практические рекомендации по выбору шага в некоторых вариантах SGD даны в секциях 4.4, 6.6 и 7.5 статьи Сполла (2003){{sfn|Spall|2003}}.
 
== Обобщения и модификации ==
Существует множество модификаций алгоритма стохастического градиентного спуска. В частности, в машинном обучении проблемой является выбор {{не переведено 5|Скорость обучения|скорости обучения||learning rate}} (размера шага): при большом шаге алгоритм может расходиться, а при маленьком — сходимость слишком медленная. Для решения этой проблемы можно использовать {{Не переведено 5|расписание скорости обучения|||Learning_rate#Learning_rate_schedule}}, при котором скорость обучения <math>\eta_t</math> убывает с увеличением номера итерации <math>t</math>. При этом на первых итерациях значения параметров изменяются значительно, а на более поздних итерациях — лишь уточняются. Такие расписания известны со времён работы Мак-Куина по [[Метод k-средних|кластеризации методом k-средних]]{{sfn|Darken, Moody|1990}}. Некоторые практические рекомендации по выбору шага в некоторых вариантах SGD даны в секциях 4.4, 6.6 и 7.5 статьи Сполла (2003){{sfn|Spall|2003}}.
 
=== Не выраженные явно изменения (ISGD) ===
Как упомянуто ранее, классический стохастический градиентный спуск обычно чувствителен к {{не переведено 5|скорость обучения|скорости обучения||learning rate}} <math>\eta</math>. Быстрая сходимость требует быстрой большой скорости обучения, но это может вызвать численную неустойчивостьнестабильность. Задача может быть главным образом решена{{sfn|Toulis, Airoldi|2017|с=1694–1727}} путём рассмотрения ''неявного изменения'', когда стохастический градиент пересчитывается на следующей итерации, а не на текущей
:<math>w^{new} := w^{old} - \eta \nabla Q_i(w^{new}).</math>
 
:<math>w^{new} := \arg\min_w \{ Q_i(w) + \frac{1}{2\eta}||w - w^{old}||^2 \}.</math>
 
В качестве примера рассмотрим метод наименьших квадратов ссо переменнымисвойствами <math>x_1, \ldots, x_n \in\mathbb{R}^p</math> и наблюдениями <math>y_1, \ldots, y_n\in\mathbb{R}</math>. Мы хотим решить:
<math>y_1, \ldots, y_n\in\mathbb{R}</math>. Мы хотим решить:
:<math>\min_w \sum_{j=1}^n (y_j - x_j'w)^2,</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>x</math> может иметь "1" в качестве первого элемента. Классический стохастический градиентный спуск работает следующим образом
:<math>w^{new}=w^{old} + \eta (y_i - x_i'w^{old}) x_i</math>
 
где <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>w^{new}=w^{old} + \frac{\eta}{1 + \eta||x_i||^2} (y_i - x_i'w^{old}) x_i.</math>
 
Процедура будет оставаться численно устойчивойстабильной почтивиртуально для всех <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).
{{не переведено 5|Фильтр наименьших квадратов|нормированным фильтром наименьших квадратов||Least mean squares filter}} ({{lang-en|normalized least mean squares filter}}, NLMS).
 
Хотя решение в аналитическом виде для ISGD возможно только в методе наименьших квадратов, процедуру можно эффективно реализовать в широкий ряд моделей. В частности, предположим, что <math>Q_i(w)</math> зависит от <math>w</math> только как линейная комбинация свойств <math>x_i</math>, так что мы можем записать <math>\nabla_w Q_i(w)=-q(x_i'w) x_i</math>, где
<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 эквивалентен
Тогда ISGD эквивалентен
:<math>w^{new}=w^{old} + \xi^\ast x_i,~\text{where}~\xi^\ast=f(\xi^\ast).</math>
 
МасштабирующийМасштабный множитель <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 := w - \eta \nabla Q_i(w) + \alpha \Delta w </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}} величину.
 
:<math>\bar{w}=\frac{1}{t} \sum_{i=0}^{t-1} w_i</math>.
 
Когда оптимизация завершена, усреднённый вектор средних параметров занимает место {{mvar|w}}.
 
=== AdaGrad ===
''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=\sum_{\tau=1}^t g_\tau g_\tau^\mathsf{T}</math>
:<math>G_{j,j}=\sum_{\tau=1}^t g_{\tau,j}^2</math>.
 
Этот вектор обновляется после каждой итерации. Формула обновления:пересчёта
 
:<math>w := w - \eta\, \mathrm{diag}(G)^{-\frac{1}{2}} \circ g</math>{{efn|<math>\circ</math> является [[Произведение Адамара|поэлементным произведением]].}}
:<math>w_j := w_j - \frac{\eta}{\sqrt{G_{j,j}}} g_j.</math>
 
Каждый элемент <math>\{G_{(i,i)}\}</math> даёт множитель для скорости обучения, применяемый к одному параметру <math>w_i</math>. Поскольку знаменатель в этом множителе, <math>\sqrt{G_i}=\sqrt{\sum_{\tau=1}^t g_\tau^2}</math>, является [[Норма (математика)#Линейные нормированные пространства|нормой ''ℓ''<mathsub>l_{2}</mathsub>]] предыдущей производной, большие изменения параметра ослабляются, в то время как параметры, получающие малые изменения получают более высокие скорости обучения{{r|Zeiler}}.
 
Хотя алгоритм разрабатывался для [[Выпуклое программирование|выпуклых задач]], AdaGrad успешно применяется для невыпуклой оптимизации{{sfn|Gupta, Bengio, Weston|2014|с=1461–1492}}.
 
=== RMSProp ===
''RMSProp'' (от {{lang-en|Root Mean Square Propagation}}) — это метод, в котором {{не переведено 5|скорость обучения|||learning rate}} настраивается для каждого параметра. Идея заключается в делении скорости обучения для весов на [[Скользящая средняя|скользящиесгруппированные средние]] значения недавних градиентов для этого веса{{r|TTHG}}. Таким образом, первое скользящеесгруппированное среднее вычисляется в терминах среднеквадратичного
 
:<math>v(w,t):=\gamma v(w,t-1)+(1-\gamma)(\nabla Q_i(w))^2</math>
:<math>w:=w-\frac{\eta}{\sqrt{v(w,t)}}\nabla Q_i(w)</math>
 
RMSProp показал хорошуюпрекрасную адаптацию скорости обучения в различных приложениях. RMSProp можно рассматривать как обобщение {{не переведено 5|Rprop|||Rprop}}. Методи метод можетспособен работать с минипакетами, а не только с полными пакетами {{r|Hinton}}.
 
=== Adam ===
''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>m_w ^ {(t+1)} \leftarrow \beta_1 m_w ^ {(t)} + (1 - \beta_1) \nabla _w L ^ {(t)} </math>
:<math>w ^ {(t+1)} \leftarrow w ^ {(t)} - \eta \frac{\hat{m}_w}{\sqrt{\hat{v}_w} + \epsilon} </math>
 
где <math>\epsilon</math> является малаямалой добавкадобавкой, используемаяиспользуемой для предотвращения деления на ноль0, а <math>\beta_1</math> и <math>\beta_2</math> являются коэффициентыкоэффициентами забывания для градиентов и вторых моментов градиентов соответственно. Возведение в квадрат и квадратный корень вычисляются поэлементно.
 
=== Естественный градиентный спуск и kSGD ===
Основанный на фильтре Калмана стохастический градиентный спуск ({{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 является серьёзным улучшениемулучшение популярного естественного метода градиентного спуска.
 
Преимущества kSGD по сравнению с другими методами:
 
# Нечувствителен к числу условий задачи{{efn|Для задачи линейной регрессии, kSGD's отклонение целевой функции (то есть полная ошибка и дисперсия) на итерации <math>k</math> равно <math>{\frac {1+\epsilon }{k}}p\sigma ^{2}</math> с вероятностью, стремящейся к 1 со скоростью, зависящей от <math>\epsilon \in (0,1)</math>, где <math>\sigma ^{2}</math> является дисперсией остатков. Более того, для конкретного выбора <math>\gamma _{1},\gamma _{2}</math>, может быть показано, что kSGD's отклонение целевой функции на итерации <math>k</math> равно <math>\frac {(1+\epsilon )^{2}}{2k^{2}}\Vert w(0)-w_{*}\Vert _{2}^{2}</math> с вероятностью, стремящейся к 1 со скоростью, зависящей от <math>\epsilon \in (0,1)</math>, где <math>w_{*}</math> является оптимальным параметром.}}.
# Имеет робастный выбор гиперпараметров.
# Имеет условие остановки.
 
Преимущества kSGD по сравнению с другими методами:
#: Нечувствителен(1) Он нечувствителен к числу условий задачи,{{efn|Для задачи линейной регрессии, kSGD's отклонение целевой функции (то есть полная ошибка и дисперсия) на итерации <math>k</math> равно <math>{\frac {1+\epsilon }{k}}p\sigma ^{2}</math> с вероятностью, стремящейся к 1 со скоростью, зависящей от <math>\epsilon \in (0,1)</math>, где <math>\sigma ^{2}</math> является дисперсией остатков. Более того, для конкретного выбора <math>\gamma _{1},\gamma _{2}</math>, может быть показано, что kSGD's отклонение целевой функции на итерации <math>k</math> равно <math>\frac {(1+\epsilon )^{2}}{2k^{2}}\Vert w(0)-w_{*}\Vert _{2}^{2}</math> с вероятностью, стремящейся к 1 со скоростью, зависящей от <math>\epsilon \in (0,1)</math>, где <math>w_{*}</math> является оптимальным параметром.}}.
#: Имеет(2) он имеет робастный выбор гиперпараметров.
: (3) он имеет условие останова.
Недостатком 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>\nabla_w Q_i(w)=\frac{Y_i - \mu(X_i,w)}{V(\mu(X_i,w))} \nabla_w \mu(X_i,w)</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> p=\nabla_w \mu(X_{t+1},w(t)) </math>
:<math> M(t+1)=M(t) - \frac{1}{s} v v^\mathsf{T} </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). В частности, оптимальность второго порядка асимптотически достижима без непосредственного вычисления матриц Гессе членов суммы в эмпирической функции риска.
 
== Комментарии ==