Все о градиентном спуске

Градиентный спуск (GD) — это итеративный алгоритм оптимизации, который использует производные первого порядка для обновления параметров, необходимых для нахождения локальных минимумов дифференцируемой функции. Он используется при решении нелинейных задач многомерной оптимизации. Алгоритм оптимизации градиентного спуска известен своей важной ролью в обучении моделей машинному обучению и глубокому обучению [1], [2]. Метод называется градиентным, так как определяет направление поиска с помощью отрицательного градиента.

p = -∇ f(x), где ∇ f(x) – градиент, а pобозначает направление поиска. Проще говоря, при градиентном спуске мы постепенно шагаем в направлении, противоположном градиенту, пока не встретим глобальный или локальный минимум целевой функции или функции потерь.

Согласно приведенному выше рис. 1, если мы возьмем целевую (стоимостную) функцию f(x), здесь используется градиентный спуск, чтобы найти вес, который является n-мерным вектором xпо минимальной цене.

Мы можем вычислить направление поиска из точки k (pᵏ)как -∇ f(xᵏ)и шаг постепенно в направлении поиска с размером шага αᵏ, пока мы не удовлетворим нашим критериям остановки или ∇ f(xᵏ) = 0. Это дает нам простой алгоритм:

Где x^(k+1) обозначает обновление с позиции xᵏ.

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

Варианты градиентного спуска

Есть три варианта градиентного спуска; а именно, пакетный градиентный спуск (BGD), стохастический градиентный спуск и мини-пакетный градиентный спуск. Эти варианты в основном различаются по объему данных, используемых для определения градиента целевой функции, поскольку объем используемых данных определяет компромисс в вариантах между точностью параметров и временем, затрачиваемым на выполнение обновления [1].

Пакетный градиентный спуск (BGD)

Также известный как Vanilla GD, BGD вычисляет градиент для всего набора обучающих данных. Если мы рассмотрим весь набор данных как D={d₁, d₂, … dₙ}, где dᵢ — точка данных, градиент целевой функции f(x) для всего набора обучающих данных D, что можно обозначить как ∇ f_D(x ) вычисляется. Таким образом, алгоритм каждого обновления выглядит следующим образом:

Где x^(k+1) — следующая позиция, xᵏтекущая позиция, αᵏ скорость обучения, определяющая размер шага, и ∇ f_D(xᵏ)градиент текущей позиции. Основное преимущество этого подхода заключается в том, что BGD может эффективно рассчитывать и указывать наиболее точное направление для обновления. Он также хорошо работает для небольших обучающих наборов данных [1]. Однако BGD является дорогостоящим методом, поскольку для нахождения градиента на каждом этапе требуется весь набор данных, а также требуется достаточно памяти для хранения всего набора обучающих данных.

Стохастический градиентный спуск (SGD)

Этот вариант называется стохастическим, поскольку он рассматривает не весь набор данных D для каждого обновления, а несколько случайно выбранных выборок с одной выборкой S⊂D и |S| = 1учитывается при определении направления поиска для каждой итерации. Таким образом, алгоритм в SGD меняется следующим образом:

Следовательно, по сравнению с BGD, стохастический градиентный спуск требует намного меньше вычислительного времени, поскольку он не выполняет обновления всего набора данных в целом. Благодаря своей скорости модель SGD может обновляться новыми примерами ad libitum. Однако, поскольку SGD вычисляет градиент для одного случайного примера для каждого шага, он менее точен, чем BGD, где мы учитывали весь D.

Стохастический градиентный спуск используется гораздо чаще, чем пакетный градиентный спуск, из-за его вычислительной дешевизны и того факта, что для больших наборов данных с избыточной информацией не получение наиболее точного направления может привести к лучшему решению. Кроме того, расчеты шума в направлении действительно могут помочь SGD найти глобальный оптимум для выпуклой целевой функции с несколькими локальными минимумами намного лучше, чем BGD [3].

Мини-пакетный градиентный спуск

В мини-пакетном градиентном спуске мы делим набор данных D на небольшие пакеты S, где | S|‹|D| и рассматривать каждую партию в каждом обновлении отдельно. Для каждой партии случайным образом выбирается другой набор образцов, подобно SGD [3]. Таким образом, алгоритм Mini Batch выглядит так:

Таким образом, Mini Batch GD обеспечивает золотую середину между пакетным методом и стохастическим градиентным спуском [4].

3 алгоритма градиентного спуска

Существуют различные типы алгоритмов оптимизации для GD, включая, помимо прочего, Momentum, Nesterov Accelerated Gradient, Adam, Nadam, Adagrad, AMSGrad, AdaMax и многие другие. В этом блоге мы подробно расскажем о трех из этих алгоритмов оптимизации; а именно Импульс, Ускоренный градиент Нестерова (NAG) и Адаград.

Импульс

Momentum используется с SGD для ускорения процесса обучения, поскольку выполнение одного примера за раз для расчета градиента увеличивает общее время выполнения алгоритма. Momentum очень хорошо работает со стабильными градиентами, небольшими, но шумными градиентами или эллиптическими контурами, где один только SGD может не сработать [1]. В то время как градиентный спуск сам по себе может идти зигзагами и для достижения глобального минимума может потребоваться гораздо больше времени, с использованием импульса можно получить лучшую уверенность в том, что локальные минимумы пропущены и что он сходится намного быстрее, чем SGD без импульса [5].

Алгоритм Momentum достигает этого, добавляя для каждой итерации t часть прошлого вектора скорости к текущему вектору следующим образом:

Где γ — дробь, равная 0,9, называемая импульсом. Этот термин уменьшает количество обновлений, когда градиенты в определенном измерении имеют изменяющиеся направления, например, при колебании, и увеличивает количество обновлений, когда градиенты в измерении направлены в одном и том же направлении. Здесь скорость vₜ означает обновление до x за временной шаг t. Теперь наш алгоритм выглядит следующим образом:

Это похоже на скатывание мяча по внутренней поверхности чаши, что очень похоже на двумерную функцию потерь. Достигнув дна чаши, он набирает скорость до тех пор, пока не достигнет предельной скорости при наличии сопротивления или трения γ. Таким образом, с Momentum модель может уменьшить количество колебаний и быстро достичь глобального оптимума. Для менее сложной модели с меньшим количеством функций лучше всего использовать Momentum.

Ускоренный градиент Нестерова (NAG)

Одним из недостатков алгоритма Momentum является то, что если импульс слишком велик, он может выйти за глобальный минимум [4]. Таким образом, NAG стремится добавить корректирующую меру к алгоритму Momentum, имея приблизительное представление о том, где должна быть следующая позиция. Таким образом, в Nesterov Accelerated Gradient мы добавляем скорость к параметрам и определяем градиент, как показано ниже:

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

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

Адаград

Алгоритм Adaptive Gradient Descent назван так потому, что скорость обучения адаптируется к ситуации положения, а это означает, что более низкая скорость обучения будет использоваться для более высокого градиента и более высокая скорость обучения для более низких градиентов без необходимости ручного вмешательства [7]. . Другими словами, Adagrad может реагировать на разреженность данных в наборе данных, выполняя небольшие обновления для частых параметров и большие обновления для нечастых параметров. В отличие от предыдущих алгоритмов, на каждом временном шаге t используется разная скорость обучения для каждого параметра xᵢ. Таким образом, градиент целевой функции для параметра xᵢв момент времени t равен:

Поскольку скорость обучения изменяется при каждом t для каждого xᵢ, алгоритм можно записать так:

Где,

представляет собой сумму квадратов градиентов gₜ,ᵢ до предыдущего временного шага, а ∈ представляет собой сглаживающий член, используемый для предотвращения деления на 0.

Это быстрый алгоритм, повышающий надежность стохастического градиентного спуска. Adagrad также полезен в задачах обработки естественного языка (NLP), как показано Pennington et al. для обучения встраиванию слов с помощью глобальных векторов для представления слов (GloVe) [8]. Однако скорость обучения снизится до микроскопических уровней после большого количества итераций с использованием Adagrad, что приведет к медленной сходимости. Тем не менее, Adagrad является подходящим алгоритмом, особенно для задач квадратичной простой оптимизации.

Проблемы

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

Выбор скорости обучения

Скорость обучения, обычно обозначаемая как α, сама по себе является сложной вещью для алгоритма, так как выбор малого значения α приведет к тому, что метод будет слишком медленным для сходимости и выбор большего значения α приведет к превышению алгоритма и еще большему отклонению от оптимального [4].

Настройка скорости обучения

Для большинства алгоритмов градиентного спуска использование фиксированной скорости обучения для всего процесса не подходит. На начальных этапах алгоритма мы ожидаем, что он будет делать более крупные шаги и уменьшать размер шага по мере того, как он постепенно достигает оптимальной точки, эти графики скорости обучения должны быть предварительно определены, поскольку они не могут подстраиваться в соответствии со свойствами набора данных [ 9].

Индивидуальные показатели обучения для функций

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

Локальные минимумы

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

Это одна из самых больших проблем, когда речь идет об анализе сходимости [10]. Согласно Дофину и соавт. (2014) наиболее сложная ситуация возникает, когда алгоритм застревает в седловой точке, так как близкий к нулю градиент в седловой точке делает практически невозможным выход из нее для SGD [11].

Преодоление проблемы поиска глобального минимума

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

Импульс Срок

Член импульса — это один из таких методов, используемых в алгоритме импульса, который помогает нам пропускать локальные минимумы и сходиться к оптимуму. Обычно он обозначается как 0‹γ‹1 и хорошо работает для импульсного алгоритма, когда γ = 0,9. Это не идеальное решение, как описано выше в алгоритме Momentum, поскольку алгоритм будет превышать минимум, если скорость обучения слишком высока [6].

Регуляризация

В регуляризации мы добавляем штрафной член к целевой функции, чтобы он наказывал большие веса. Этот штрафной термин называется регуляризатором. Регулятор добавлен так, что даже при ∇ f(x) = 0 веса обновляются, что повышает вероятность выхода алгоритма из локальных минимумов. При глобальном минимуме вес не будет обновляться. Lasso и Ridge — два используемых типа регуляризаторов [12].

Скорость обучения отжигу

Как видно выше из таких алгоритмов, как Adagrad, изменение скорости обучения (α) с каждым временным шагом приводит к лучшей оптимизации и сходимости к глобальному минимуму. Здесь уравнение отжига имеет вид:

Где временной шаг tможет увеличиваться, пока не дойдет до T, которое является конечным временем поиска, и α будет уменьшаться по мере увеличения t. Это также известно как график отжига «поиск, затем сходимость» [13].

Существуют также циклические скорости обучения, предложенные Лесли Н. Смитом в недавней литературе, где скорость обучения увеличивается и уменьшается циклическим образом, поскольку само по себе снижение скорости обучения не гарантирует, что вы не застрянете в локальных минимумах [14] , [15].

Обсуждение

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