Оптимизаторы. Часть 2
Обозначения
Для начала вспомним обозначения из нашей прошлой статьи: \( θ \) — веса модели;
\( η \) — learning rate;
\( ∇J(θ) \) — градиент loss функции по весам;
EWMA — Exponentially Weighted Moving Average.
Еще мы будем использовать обозначение \( ∝ \) — равенство размерностей (в физическом смысле). Например, \( m∝кг \).
Adadelta
Теперь давайте обратимся к формуле обновления весов для ADAGRAD и RMSprop. Разница между ними только в расчете \( G \).
Для ADAGRAD мы берем сумму квадратов градиентов:
\( G=G+∇J^2(θ) \)
А для RMSprop — EWMA квадратов градиентов:
\( G=rG+(1-r)∇J^2(θ) \)
Концептуальная проблема этих двух оптимизаторов — неправильная размерность обновления весов.
Давайте считать \( p \) размерностью весов. Подставляем ее в формулу и получаем:
\( \Deltaθ= \frac{η}{\sqrt{G +\epsilon}}∇J(θ)∝\frac{1}{\sqrt{{p’^2} +0}}p’∝\frac{p’}{p’}∝1 \) \( (2) \)
Хотя на самом деле \( \Deltaθ∝p \), а значит, размерности не совпадают.
Посмотрим, как создатели Adadelta решают эту проблему.
Для этого вспомним о методе Ньютона — методе оптимизации второго порядка (то есть в данном методе используются вторые производные).
Выглядит он так:
\( \Deltaθ= -H(J)^{-1}∇J(θ)\) \( (3) \)
\( H(J) \) — это гессиан, определитель матрицы вида:
\( \begin{matrix} \dfrac{\partial^2 J}{\partial^2θ_1} & …&\dfrac{\partial^2 J}{\partial x_1 \partial θ_j}&… & \dfrac{\partial^2 J}{\partial θ_1 \partial θ_n}\\ … & … &… & …&… \\\dfrac{\partial^2 J}{\partial θ_n \partial θ_1} & …&\dfrac{\partial^2 J}{\partial θ_n \partial θ_j}&… & \dfrac{\partial^2 J}{\partial^2θ_n}\\ \end{matrix} \) \( (4) \)
Для оптимизации мы могли бы использовать именно эту формулу. Но есть одна большая проблема: нам нужно высчитать \( n^2 \) частных производных второго порядка, а потом еще и найти обратную матрицу! Это очень затратные операции, кроме того, процесс их обучения требует более тщательной настройки, поэтому они почти не применяются в машинном обучении.
Авторы предлагают рассмотреть следующее выражение:
\( \Deltaθ ∝ — H(J)^{−1} ∇J(θ) ∝ \frac{\frac{∂J}{∂θ}} {\frac{∂^2J}{∂θ^2}} \) \( (5) \)
А эта формула поможет понять размерность величины, стоящей вместо гессиана:
\( \Deltaθ =\frac{\frac{∂J}{∂θ}}{\frac{∂^2J}{∂θ^2}}⇒H(J)∝\frac{1}{\frac{∂^2J}{∂θ^2}}=\frac{∆θ}{\frac{∂J}{∂θ}}\) \( (6) \)
Теперь введем простое обозначение для RMS — Root Mean Square:
\( RMS(X)=\sqrt{EWMA(x^2)+eps} \) \( (7) \)
Авторы предлагают использовать для обновления весов формулу, в которой множитель перед \( ∇J(θ) \) заменен на выражение из формулы \( (6) \). Стоит отметить, что такая подстановка не совсем честная, ведь в формуле \( (6) \) мы использовали еще не известную нам \( ∆θ \). Именно поэтому мы будем применять \( ∆θ \) из предыдущего шага и предполагать, что за счет использования \( EWMA \) значения на соседних шагах не будут сильно различаться.
\( \Deltaθ = −\frac{RMS(∆θ)}{RMS(∇J(θ))} ∇J(θ)\) \( (8) \)
Кстати, отметим, что в формуле \( (8) \) нет гиперпараметра \( η \). Почему? Об этом подробнее можно почитать здесь.
Также, в отличие от предыдущих алгоритмов, в этом у нас будет 3 шага:
- накопление квадрата градиента;
- обновление весов;
- обновление \( RMS(∆θ) \).
Adam
Adam — это, наверное, самый популярный алгоритм для обучения нейросетей. Таким известным он стал за счет быстрой сходимости, простых операций “под капотом”.
Adam — алгоритм, сочетающий в себе идеи слабого обновления типичных признаков (как в Adadelta, RMSprop и ADAGRAD) и накопления (как в алгоритмах с momentum).
Первая часть Adam — множитель из RMSprop. Он позволяет адаптировать размер шага:
\( u=RMS(∇J(θ)) \)
Вторая часть Adam — немного измененный импульс. Он помогает выбираться из локальных минимумов:
\( m=EWMA(∇J(θ)) \)
Отметим, что в отличие от momentum, мы не включаем в \( EWMA \) параметр \( η \).
С точки зрения статистики, \( m \) — оценка первого момента, а \( u \) — второго.
Мы помним, что в \( RMS \) встроен \( EWMA \) , а в \( EWMA \) есть гиперпараметр \( \beta \). Получается, этот гиперпараметр нужно будет различать для обоих частей. Для \( m \) мы назовем его \( \beta_1 \), а для \( u \) — \( \beta_2. \) Авторы советуют использовать следующие значения:
\( β_1=0.9 \) \( , β_2=0.999 \)
А сейчас давайте посмотрим, как будет выглядеть множитель \( m \) на произвольном шаге:
\( m_0=0 \)
\( m_1= β_1*m_0 + (1 − β_1)∇J(θ)_1=(1 − β_1)∇J(θ)_1 \)
\( m_2= β_1m_1 + (1 − β_1)∇J(θ)_2=β_1(1 − β_1)∇J(θ)_1 + (1 − β_1)∇J(θ)_2 \)
\( m_3=β_1^2(1-β_1)∇J(θ)_1+β_1(1-β_1)∇J(θ)_2+(1-β_1)∇J(θ)_3 \)
\( m_t=(1-b_1)\sum_{i=0}^{t}{\beta_1^{t-i}∇J(θ)_i} \)
Мы используем \( EWMA(x) \) для оценки \( x \). Строго говоря, выходит так:
\( E[EWMA(x)_t]=E[x_t] \)
Но в этом случае наша оценка получается смещенной. Сейчас станет понятно почему:
\( E[m_t]=E[(1-b_1)\sum_{i=0}^{t}{\beta_1^{t-i}∇J(θ)_i}] \)
Мы можем апроксимировать \( J_i \) с помощью \( J_t \) :
\( E[m_t]=E∇J(θ)_t\sum_{i=0}^{t}{\beta_1^{t-i}}=E∇J(θ)_t\sum_{i=0}^{t}{\beta_1^{t-i}} \)
А теперь посчитать частичную сумму геометрической прогрессии. В нашем случае q — это \( b_1 \), a \( r_1=1 \):
\( S_n=r_1\frac{(1-q^n)}{(1-q)} \)
и соответственно:
\( \sum_{i=0}^{t}{\beta_1^{t-i}}=\frac{1-\beta_1^t}{1-b_1} \)
После подстановки получаем следующее:
\( E∇J(θ)_t*\frac{1-\beta_1^t}{1-b_1}=E∇J(θ)_t \)
\( E[m_t]=E∇J(θ)_t \)
Мы видим, что оценка смещена. Для решения этой проблемы авторы предлагают использовать метод коррекции смещения (bias correction):
\( \overline m=\frac{m}{1-\beta_1^t} \)
Для \( u \) этот метод тоже используется:
\( \overline u=\frac{u}{1-\beta_2^t} \)
Алгоритм будет корректным и без применения метода коррекции смещения. Но коррекция ошибок позволяет значительно улучшить движение на первых шагах (на последних шагах она уже почти не значима).
Итак, собираем все вместе и получаем самый популярный оптимизатор — Adam:
\( u=RMS(∇J(θ)) \)
\( m=EWMA(∇J(θ)) \)
\( \overline m=\frac{m}{1-\beta_1^t} \)
\( \overline u=\frac{u}{1-\beta_2^t} \)
\( θ= θ−\frac{η}{\overline u}\overline m \)
Хотя Adam и является очень популярным оптимизатором, но на некоторых задачах он дает результаты худшие чем, например Sgd. Поэтому существует множество методов, которые стоит попробовать, если Adam дает плохие результаты. Мы рассмотрим несколько из них.
AdamW
У Adam есть проблема, связанная с тем, что L2 регуляризация для него не эквивалентна weight decay.
На самом деле, в общем случае L2 != weight decay.
Разница между этими двумя методиками заключается в том, что в случае L2 регуляризации, мы изменяем loss функцию, добавляя к ней норму весов \( \lambda\sum w^2 \).
В в случае weight decay — меняем правило обновления весов, вычитая на каждом шаге из весов \( η\lambda w \).
Для SGD применение этих двух методик будет эквивалентным, так как
\( \frac{∂\lambda\sum w^2} {∂w}= 2\lambda\sum w \).
Правда, \( \lambda \) должна различаться в 2 раза, для получения идентичного поведения алгоритма.
В случае \( Adam \) различия между этими методиками будут сильно отличаться:
В случае L2 изменятся компонента, отвечающая за моментум:
\( m=EWMA(∇J(θ)+∇\lambda\sum w^2)=EWMA(∇J(θ)+2\lambda\sum w) \)
и компонента, отвечающая за адаптивность:
\( u=RMS(∇J(θ)+∇\lambda\sum w^2)=RMS(∇J(θ)+2\lambda\sum w) \).
В случае weight decay изменится только правило изменения весов:
\( θ= θ−\frac{η}{\overline u}\overline m- η\lambda w \)
Авторы статьи предлагают использовать именно weight decay и называют получившийся оптимизатор AdamW. Авторы, также утверждают, что такой оптимизатор обладает лучшей обобщающей способностью, и критикуют использование l2 нормализации, поскольку она вносит возмущение в накопленный моментум.
SWATS
В статье авторы обнаружили, что Adam быстрее сходится, но полученная модель хуже генерализируется, чем уступает обычному Sgd.
Авторы предлагают простое решение — переключаться на Sgd при выполнении условия:
\( \lvert\frac{\lambda_t}{1 − β_2^t}-\gamma_t \rvert<\epsilon \),
где
\( \gamma_k = \frac{p^Tp}{p^T∇J(θ)} \), \( p=\frac{η}{\overline u}\overline m \)
А \( \lambda_t \) это \( EWMA(\gamma_k) \), с весом \( β_2 \).
В Sgd после переключения предлагается использовать \( η=\gamma_k \).
Авторы получили улучшение относительно Adam на тех датасетах, на которых он классически показывал худшие результаты.
Одним из возможных улучшений этого алгоритма является идея изменять оптимизатор не глобально для всех весов, а в локально, проверяя условие для каждого веса по отдельности.
Warmup
Адаптивные методы накапливают статистики градиентов, но на первом шаге у нас нет истории предыдущих шагов. Из-за этого, на первом шаге мы можем шагнуть в неверном направлении, так как мы еще не успели накопить информацию о ландшафте loss функции.
Поэтому зачастую используется метод “прогрева” адаптивных алгоритмов. На первых итерациях берется очень маленький \( η \) и постепенно увеличивается, пока не достигнет нормальных значений. Благодаря этому оптимизатор вначале исследует ландшафт, и накопив информацию о нем, гораздо лучше сходится.
Также эту проблему пытались решить в RAdam с помощью эвристического правила.
