Стохастический градиентный спуск - Stochastic gradient descent

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

Хотя основная идея стохастической аппроксимации восходит к алгоритму Роббинса – Монро 1950-х годов, стохастический градиентный спуск стал важным методом оптимизации в машинном обучении .

Фон

И статистическая оценка и машинное обучение рассмотрят задачу минимизации в целевую функции , которая имеет вид суммы:

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

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

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

При использовании для минимизации вышеуказанной функции стандартный (или «пакетный») метод градиентного спуска будет выполнять следующие итерации:

где - размер шага (иногда называемый скоростью обучения в машинном обучении).

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

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

Итерационный метод

Колебания общей целевой функции выполняются в виде шагов градиента по отношению к минипакетам.

При стохастическом (или "оперативном") градиентном спуске истинный градиент аппроксимируется градиентом в одном примере:

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

В псевдокоде стохастический градиентный спуск можно представить следующим образом:

  • Выберите начальный вектор параметров и скорость обучения .
  • Повторяйте, пока не получите приблизительный минимум:
    • Случайным образом перемешайте примеры в обучающей выборке.
    • Для , сделайте:

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

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

Пример

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

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

Обратите внимание, что в каждой итерации (также называемой обновлением) только градиент оценивается в одной точке, а не в наборе всех выборок.

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

Известные приложения

Стохастический градиентный спуск - это популярный алгоритм для обучения широкого спектра моделей машинного обучения , включая (линейные) машины опорных векторов , логистическую регрессию (см., Например, Vowpal Wabbit ) и графические модели . В сочетании с алгоритмом обратного распространения ошибки это фактический стандартный алгоритм для обучения искусственных нейронных сетей . Об его использовании также сообщалось в сообществе геофизиков , особенно в приложениях Full Waveform Inversion (FWI).

Стохастический градиентный спуск конкурирует с алгоритмом L-BFGS , который также широко используется. Стохастический градиентный спуск используется по крайней мере с 1960 года для обучения моделей линейной регрессии , первоначально под названием ADALINE .

Другой алгоритм стохастического градиентного спуска - это адаптивный фильтр наименьших средних квадратов (LMS) .

Расширения и варианты

Было предложено и использовано множество улучшений основного алгоритма стохастического градиентного спуска. В частности, в машинном обучении необходимость установки скорости обучения (размера шага) была признана проблематичной. Установка слишком большого значения этого параметра может привести к отклонению алгоритма; установка слишком низкого значения замедляет схождение. Концептуально простое расширение стохастического градиентного спуска превращает скорость обучения в убывающую функцию η t номера итерации t , что дает график скорости обучения , так что первые итерации вызывают большие изменения параметров, а последующие - только точную настройку. . Такие расписания были известны со времен работы MacQueen над кластеризацией k- средних . Практическое руководство по выбору размера шага в нескольких вариантах SGD дает Сполл.

Неявные обновления (ISGD)

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

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

В качестве примера рассмотрим метод наименьших квадратов с характеристиками и наблюдениями . Мы хотим решить:

где указывает внутренний продукт. Обратите внимание, что в качестве первого элемента, включающего перехват , может быть «1». Классический стохастический градиентный спуск происходит следующим образом:

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

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

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

В таких настройках ISGD просто реализуется следующим образом. Пусть , где - скаляр. Тогда ISGD эквивалентен:

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

Импульс

Дальнейшие предложения включают метод импульса , который появился в статье Рамельхарта , Хинтона и Уильямса об обучении с обратным распространением. Стохастический градиентный спуск с импульсом запоминает обновление Δ w на каждой итерации и определяет следующее обновление как линейную комбинацию градиента и предыдущего обновления:

что приводит к:

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

Название «импульс» происходит от аналогии с импульсом в физике: вектор веса , рассматриваемый как частица, движущаяся через пространство параметров, вызывает ускорение из-за градиента потерь (« сила »). В отличие от классического стохастического градиентного спуска, он стремится продолжать движение в одном и том же направлении, предотвращая колебания. Momentum успешно используется компьютерными учеными при обучении искусственных нейронных сетей в течение нескольких десятилетий. Метод импульса тесно связан с underdamped динамики Ланжевенны , и может быть объединен с имитацией отжигом .

Усреднение

Усредненный стохастический градиентный спуск , изобретенный независимо Руппером и Поляком в конце 1980-х годов, представляет собой обычный стохастический градиентный спуск, который регистрирует среднее значение вектора параметров во времени. То есть обновление такое же, как и для обычного стохастического градиентного спуска, но алгоритм также отслеживает

.

Когда оптимизация выполнена, этот усредненный вектор параметров заменяет w .

АдаГрад

AdaGrad (для алгоритма адаптивного градиента ) - это модифицированный алгоритм стохастического градиентного спуска со скоростью обучения по параметрам , впервые опубликованный в 2011 году. Неформально это увеличивает скорость обучения для более разреженных параметров и снижает скорость обучения для менее разреженных. Эта стратегия часто улучшает производительность сходимости по сравнению со стандартным стохастическим градиентным спуском в условиях, когда данные разрежены, а разреженные параметры более информативны. Примеры таких приложений включают обработку естественного языка и распознавание изображений. Он по-прежнему имеет базовую скорость обучения η , но она умножается на элементы вектора { G j , j }, который является диагональю матрицы внешнего произведения

где градиент на итерации τ . Диагональ задается формулой

.

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

или, записанные как обновления для каждого параметра,

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

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

RMSProp

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

где, - коэффициент забвения.

И параметры обновляются как,

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

Адам

Adam (сокращение от Adaptive Moment Estimation) - это обновление оптимизатора RMSProp . В этом алгоритме оптимизации используются средние значения как градиентов, так и вторых моментов градиентов. Учитывая параметры и функцию потерь , где индексируется текущая итерация обучения (индексируется в ), обновление параметров Адама задается следующим образом:

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


Поиск строки с возвратом

Поиск строки с возвратом - это еще один вариант градиентного спуска. Все нижеперечисленное взято из указанной ссылки. Он основан на условии, известном как условие Армийо – Гольдштейна. Оба метода позволяют изменять скорость обучения на каждой итерации; однако способ изменения иной. Поиск строки с возвратом использует оценки функций для проверки состояния Armijo, и в принципе цикл в алгоритме для определения скорости обучения может быть длинным и заранее неизвестным. Adaptive SGD не нуждается в цикле при определении скорости обучения. С другой стороны, адаптивный SGD не гарантирует «свойства спуска», которым обладает поиск по строке с возвратом, а именно для всех n. Если градиент функции стоимости глобально непрерывен по Липшицу, с константой Липшица L и скорость обучения выбрана порядка 1 / L, то стандартная версия SGD является частным случаем поиска строки с возвратом.

Методы второго порядка

Стохастический аналог стандартного (детерминированного) алгоритма Ньютона – Рафсона (метод «второго порядка») обеспечивает асимптотически оптимальную или почти оптимальную форму итерационной оптимизации в условиях стохастической аппроксимации. Метод, который использует прямые измерения матриц Гессе слагаемых эмпирической функции риска, был разработан Бердом, Хансеном, Нокедалом и Зингером. Однако прямое определение требуемых матриц Гессе для оптимизации на практике может оказаться невозможным. Практические и теоретически обоснованные методы для версий SGD второго порядка, которые не требуют прямой гессенской информации, представлены Споллом и другими. (Менее эффективный метод, основанный на конечных разностях, а не на одновременных возмущениях, дан Руппером.) Эти методы, не требующие прямой гессенской информации, основаны либо на значениях слагаемых в приведенной выше эмпирической функции риска, либо на значениях градиентов слагаемых. (т.е. входы SGD). В частности, оптимальность второго порядка асимптотически достижима без прямого вычисления матриц Гессе слагаемых в эмпирической функции риска.

Примечания

Смотрите также

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

дальнейшее чтение

внешние ссылки