10 алгоритмов оптимизации стохастического градиентного спуска + шпаргалка

Алгоритмы оптимизации стохастического градиентного спуска, которые вы должны знать для глубокого обучения

(Я веду шпаргалку этих оптимизаторов, включая RAdam, в моем блоге здесь.)

Журналы изменений:
4 мая 2020 г .: исправление опечатки в формуле Надам в Приложении 2.
21 марта 2020 г .: заменить V и S на m и v соответственно. Обновлены мертвые ссылки. Рассмотрена идея скорости обучения и компонентов градиента. Обновленная интуиция.
6 октября 2019 г .: улучшена идея EMA градиентов.
22 сентября 2019 г .: изменился порядок появления оптимизаторов и удалена «карта эволюции».

Градиентный спуск - это метод оптимизации для поиска минимума функции. Он обычно используется в моделях глубокого обучения для обновления весов нейронной сети посредством обратного распространения ошибки.

В этом посте я обобщу общие алгоритмы оптимизации градиентного спуска, используемые в популярных фреймворках глубокого обучения (например, TensorFlow, Keras, PyTorch). Цель этого поста - упростить чтение и усвоение формул с использованием согласованной номенклатуры, поскольку таких резюме не так много. В конце этого поста находится шпаргалка для справки.

Этот пост предполагает, что читатель имеет некоторые знания о градиентном спуске / стохастическом градиентном спуске.

(Для демонстрации задачи линейной регрессии с использованием оптимизаторов градиентного спуска, таких как SGD, Momentum и Adam, нажмите здесь.)

Что делают оптимизаторы стохастического градиентного спуска?

Напомним, что стандартный стохастический градиентный спуск (SGD) обновляет веса, вычитая текущий вес на коэффициент (т.е. α, скорость обучения) своего градиента.

Вариации в этом уравнении широко известны как оптимизаторы стохастического градиентного спуска. Есть 3 основных различия, которыми они отличаются:

  1. Адаптируйте компонент градиента ( ∂L / ∂w )
    вместо использования только одного градиента, как в стохастическом ванильном градиенте спуска, чтобы обновить вес, возьмите совокупность нескольких градиентов. В частности, эти оптимизаторы используют экспоненциальную скользящую среднюю градиентов.
  2. Адаптируйте «компонент скорости обучения» ( α )
    Вместо того, чтобы поддерживать постоянную скорость обучения, адаптировать скорость обучения в соответствии с величиной градиента (ов).
  3. И (1), и (2)
    Адаптируйте как компонент градиента, так и компонент скорости обучения.

Как вы увидите позже, эти оптимизаторы пытаются улучшить объем информации, используемой для обновления весов, в основном за счет использования предыдущих (и будущих) градиентов, а не только текущего доступного градиента.

Ниже приведена таблица, в которой обобщается, какие «компоненты» адаптируются:

‹Журнал изменений 22 сентября 2019 г .: удалена карта эволюции›

Содержание

  1. Стохастический градиентный спуск
  2. Импульс
  3. АдаГрад
  4. RMSprop
  5. Ададелта
  6. НАГ
  7. Адам
  8. AdaMax
  9. Надам
  10. AMSGrad

Приложение 1: Шпаргалка

Приложение 2: интуиция

Приложение 3: Планировщики скорости обучения и оптимизаторы стохастического градиентного спуска

Обозначения

  • t - временной шаг
  • w - вес / параметр, который мы хотим обновить, где нижний индекс t индексирует вес на временном шаге t.
  • α - скорость обучения
  • ∂L / ∂w - градиент L, функция потерь, которую необходимо минимизировать, относительно к w
  • Я также стандартизировал обозначения и греческие буквы, используемые в этом посте (следовательно, они могут отличаться от документов), чтобы мы могли исследовать, как оптимизаторы «развиваются» по мере того, как мы прокручиваем.

1. Стохастический градиентный спуск

Как мы видели ранее, ванильный SGD обновляет текущий вес, используя текущий градиент ∂L / ∂w, умноженный на некоторый коэффициент, называемый скоростью обучения, α.

2. Импульс

Вместо зависимости только от текущего градиента для обновления веса, градиентный спуск с импульсом (Поляк, 1964) заменяет текущий градиент на m (импульс), который является совокупностью градиентов. Этот агрегат представляет собой экспоненциальную скользящую среднюю текущих и прошлых градиентов (то есть до времени t). Позже в этом посте вы увидите, что это обновление импульса становится стандартным обновлением компонента градиента для большинства оптимизаторов.

куда

и m инициализируется значением 0.

Общее значение по умолчанию:

  • β = 0.9

О происхождении импульса
Обратите внимание, что во многих статьях метод импульса ссылается на публикацию Ning Qian, 1999. Однако статья Суцкевер и др. приписал классический импульс гораздо более ранней публикации Поляка в 1964 году, как цитировалось выше. (Спасибо Джеймсу за указание на это.)

3. AdaGrad

Адаптивный градиент, или AdaGrad (Duchi et al., 2011), воздействует на компонент скорости обучения путем деления скорости обучения на квадратный корень из v, который представляет собой совокупную сумму текущего и прошлого квадраты градиентов (т.е. до времени t). Обратите внимание, что компонент градиента остается неизменным, как и в SGD.

куда

и v инициализировано значением 0.

Обратите внимание, что к знаменателю добавляется ε. Керас называет это фактором нечеткости, небольшим значением с плавающей запятой, чтобы гарантировать, что нам никогда не придется сталкиваться с делением на ноль.

Значения по умолчанию (от Keras):

  • α = 0.01
  • ε = 10⁻⁷

4. RMSprop

Среднеквадратичная опора или RMSprop (Hinton et al., 2012) - еще одна адаптивная скорость обучения, которая пытается улучшить AdaGrad. Вместо того, чтобы брать кумулятивную сумму квадратов градиентов, как в AdaGrad, мы берем экспоненциальную скользящую среднюю (опять же!) Этих градиентов. Подобно импульсу, мы постепенно увидим, что это обновление станет стандартным обновлением для компонента скорости обучения для большинства оптимизаторов.

куда

и v инициализировано значением 0.

Значения по умолчанию (от Keras):

  • α = 0.001
  • β = 0,9 (рекомендовано авторами статьи)
  • ε = 10⁻⁶

5. Ададелта

Как и RMSprop, Adadelta (Zeiler, 2012) также является еще одним усовершенствованием AdaGrad, сосредоточенным на компоненте скорости обучения. Adadelta, вероятно, является сокращением от адаптивной дельты, где дельта здесь означает разницу между текущим и недавно обновленным весом.

Разница между Adadelta и RMSprop заключается в том, что Adadelta полностью исключает использование параметра скорости обучения, заменяя его на D, экспоненциальное скользящее среднее квадратов дельт.

куда

с D и v, инициализированными 0, и

Значения по умолчанию (от Keras):

  • β = 0.95
  • ε = 10⁻⁶

6. Ускоренный градиент Нестерова (НАГ).

После того, как Поляк набрал обороты (каламбур 😬), подобное обновление было реализовано с помощью Nesterov Accelerated Gradient (Суцкевер и др., 2013). В этом обновлении используется m, экспоненциальная скользящая средняя того, что я бы назвал прогнозируемыми градиентами.

куда

и m инициализируется значением 0.

Последний член во втором уравнении - это прогнозируемый градиент. Это значение можно получить, перейдя «на шаг вперед», используя предыдущую скорость (уравнение 4). Это означает, что для этого временного шага t мы должны выполнить еще одно прямое распространение, прежде чем мы наконец сможем выполнить обратное распространение. Вот как это происходит:

  1. Обновите текущий вес w до прогнозируемого веса w *, используя предыдущую скорость.

2. Выполните прямое распространение, но используя этот прогнозируемый вес.

3. Получите спроецированный градиент ∂L / ∂w *.

4. Вычислите соответственно V и w.

Общее значение по умолчанию:

  • β = 0.9

О происхождении NAG
Обратите внимание, что исходная статья Нестерова по ускоренному градиенту (Нестеров, 1983) не касалась стохастического градиентного спуска и не использовала явно уравнение градиентного спуска. Следовательно, более подходящей ссылкой является упомянутая выше публикация Sutskever et al. в 2013 году, в котором описывалось применение NAG в стохастическом градиентном спуске. (Опять же, я хотел бы поблагодарить комментарий Джеймса к HackerNews за указание на это.)

7. Адам

Оценка адаптивного момента, или Адам (Kingma & Ba, 2014), - это просто комбинация импульса и RMSprop. Он действует на

  1. компонент градиента с помощью m, экспоненциального скользящего среднего градиентов (например, в импульсе), и
  2. компонент скорости обучения путем деления скорости обучения α на квадратный корень из v, экспоненциального скользящего среднего квадрата градиентов (как в RMSprop).

куда

поправки смещения, и

с m и v, инициализированными 0.

Предлагаемые авторами значения по умолчанию:

  • α = 0.001
  • β₁ = 0.9
  • β₂ = 0.999
  • ε = 10⁻⁸

8. AdaMax

AdaMax (Kingma & Ba, 2015) - это адаптация оптимизатора Adam от тех же авторов, использующая бесконечные нормы (отсюда max). m - экспоненциальное скользящее среднее градиентов, а v - экспоненциальное скользящее среднее прошлой p -нормы градиентов, приближенное к функции max. как показано ниже. Обратитесь к статье за ​​их доказательством сходимости.

куда

- поправка смещения для m и

с m и v, инициализированными 0.

Предлагаемые авторами значения по умолчанию:

  • α = 0.002
  • β₁ = 0.9
  • β₂ = 0.999

9. Надам

Надам (Дозат, 2015) - это аббревиатура от Нестерова и Адама оптимизатора. Однако компонент Нестерова является более эффективной модификацией, чем его первоначальная реализация.

Во-первых, я хотел бы показать, что оптимизатор Адама также можно записать как:

Надам использует Нестерова для обновления градиента на шаг вперед, заменяя предыдущий m_hat в приведенном выше уравнении на текущий m_hat:

куда

а также

с m и v, инициализированными 0.

Значения по умолчанию (взяты из Keras):

  • α = 0.002
  • β₁ = 0.9
  • β₂ = 0.999
  • ε = 10⁻⁷

10. AMSGrad

Другой вариант Адама - AMSGrad (Reddi et al., 2018). Этот вариант пересматривает компонент адаптивной скорости обучения в Адаме и изменяет его, чтобы гарантировать, что текущее v всегда больше, чем v с предыдущего временного шага .

куда

а также

с m и v, инициализированными 0.

Значения по умолчанию (взяты из Keras):

  • α = 0.001
  • β₁ = 0.9
  • β₂ = 0.999
  • ε = 10⁻⁷

Пожалуйста, свяжитесь со мной, если что-то не так или если что-то в этом посте можно улучшить! ✌🏼

Приложение 2: интуиция

Суть всего вышеперечисленного можно найти здесь. Изображение создано с помощью QuickLaTeX. (Спасибо, Рави, за указание на опечатку в обновлении Надама.)

Приложение 2: интуиция

Здесь я хотел бы поделиться с вами некоторой интуицией, почему оптимизаторы градиентного спуска используют экспоненциальное скользящее среднее для компонента градиента и среднеквадратичное значение для компонента скорости обучения.

Зачем использовать экспоненциальное скользящее среднее градиентов?

Напомним, что нам нужно обновить вес, и для этого нам нужно использовать какое-то значение. Единственное значение, которое у нас есть, - это текущий градиент, поэтому давайте просто воспользуемся этой информацией для обновления веса.

Но взять только текущее значение градиента недостаточно. Мы хотим, чтобы наши обновления были «более управляемыми». И это достигается за счет использования предыдущей информации о градиентах. Итак, давайте также включим предыдущие градиенты, объединяя текущий градиент и прошлые градиенты.

Один из способов агрегировать эти градиенты - взять простое среднее всех прошлых и текущих градиентов. Но подождите, это означает, что каждый из этих градиентов имеет одинаковый вес. Было бы это справедливо? Может быть. Может быть нет.

Что мы могли бы сделать, так это взять экспоненциальную скользящую среднюю, где прошлые значения градиента имеют более высокий вес (важность), чем текущее. Интуитивно, если не учитывать важность, придаваемую текущему градиенту, это гарантирует, что обновление веса не будет чувствительным к текущему градиенту.

Зачем делить скорость обучения на корень из среднего экспоненциального квадрата градиентов?

Цель адаптации скорости обучения - сделать оптимизатор «умнее» путем деления скорости обучения на среднеквадратическое значение нескольких градиентов. Итак, давайте зададим себе следующие вопросы:

  1. Зачем использовать несколько градиентов?
  2. Зачем делить?
  3. Зачем извлекать корень из экспоненциальной скользящей средней квадратов градиентов?

На первый вопрос был дан ответ из предыдущего раздела - помимо значения текущего градиента мы также хотим использовать информацию из прошлых градиентов.

Чтобы ответить на второй вопрос, сначала рассмотрим простой случай, когда средняя величина градиентов за последние несколько итераций была 0,01. Поскольку это значение близко к 0, это означает, что мы находились на приблизительно плоской поверхности (представьте себе плоский участок трехмерного ландшафта потерь). Там, где мы сейчас находимся, земля довольно плоская, поэтому мы довольно уверенно перемещаемся по этой местности. Фактически, мы хотим как можно быстрее выбраться из этой области и искать нисходящий уклон, который может привести нас к глобальным минимумам. (Вы можете найти в некоторых статьях упоминание, что это имеет эффект «ускорения».) Следовательно, мы хотим увеличить компонент скорости обучения (учиться быстрее), когда величина градиентов мала. Чтобы установить эту обратную пропорциональную зависимость, мы берем фиксированную скорость обучения α и делим ее на среднюю величину градиента. Эта адаптированная скорость обучения (которая теперь является большим значением) затем умножается на компонент градиента, что дает нам большое обновление веса по величине (независимо от того, положительное или отрицательное).

Интуиция верна и в обратном направлении. Предположим, что среднее значение наших градиентов было очень высоким, около 2,7. Это означает, что мы были на крутых склонах. Мы хотим двигаться с осторожностью, поэтому делаем меньшие шаги, и этого можно достичь, выполняя такое же деление.

В последнем вопросе причина, по которой мы берем экспоненциальную скользящую среднюю, была нам очевидна из предыдущего раздела. Причина, по которой мы берем квадрат градиента, заключается просто в том, что, имея дело с компонентом скорости обучения, мы озабочены его величиной. Естественный выбор «компенсировать» это - пустить корни. Возможно, за этим стоит математика, но давайте пока воспользуемся этой интуицией, чтобы убедить себя.

Приложение 3: Планировщики скорости обучения и оптимизаторы стохастического градиентного спуска

Некоторые из вас могут спросить - в чем разница между планировщиками скорости обучения и оптимизаторами стохастического градиентного спуска? Основное различие между ними заключается в том, что оптимизаторы стохастического градиентного спуска адаптируют компонент скорости обучения, умножая скорость обучения на коэффициент, который является функцией градиентов, тогда как планировщики скорости обучения умножают скорость обучения на коэффициент, который является функцией временной шаг (или даже постоянный).

использованная литература

Соответствующие документы, упомянутые выше для каждого оптимизатора

Обзор алгоритмов оптимизации градиентного спуска (ruder.io)

Почему Momentum действительно работает (distill.pub)

Связанные статьи о глубоком обучении

Анимированные РНН, ЛСТМ и ГРУ

Построчная реализация Word2Vec (о встраиваниях слов)

Пошаговое руководство по линейной регрессии со стохастическим градиентным спуском

Подсчет количества параметров в моделях глубокого обучения

Attn: Иллюстрированное внимание

Иллюстрировано: внимание к себе

Спасибо Ren Jie, Derek, William Tjhi, Chan Kai, Serene и James за идеи, предложения и исправления к этой статье.

Подписывайтесь на меня в Twitter @remykarem или LinkedIn. Вы также можете связаться со мной по [email protected]. Не стесняйтесь посетить мой сайт remykarem.github.io.