Стохастический градиентный спуск. Варианты реализации

где f i – функция, подсчитанная на i-м батче, i выбирается случайным образом;

Шаг обучения является гиперпараметром; при слишком больших значениях алгоритм обучения будет расходиться, при слишком маленьких – будет сходиться медленно.

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

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

(14)
(15)

Как несложно догадаться, гиперпараметр инерции μ имеет такое название из-за того, что, подобно так называемой ньютоновой силе инерции, т.е. силе противодействия, «сопротивляется» изменениям градиента и смягчает изменения весовых коэффициентов на протяжении обучения. Такой алгоритм обучения называется стохастическим градиентным спуском с инерцией или SGDМ (stochastic gradient descent with momentum).

Метод адаптивного градиента

Метод адаптивного градиента (Adagrad – от англ. «adaptive gradient algorithm») основан на идее масштабирования. Он перемасштабирует скорость обучения для каждого настраиваемого параметра в отдельности, при этом учитывая историю всех прошлых градиентов для этого параметра. Для этого каждый элемент градиента делится на квадратный корень от суммы квадратов предыдущих соответствующих элементов градиента. Такой подход эффективно уменьшает скорость обучения для тех весовых коэффициентов, которые имеют большое значение градиента, а также со временем снижает скорость обучения для всех параметров, так как сумма квадратов неуклонно увеличивается для всех параметров при каждой итерации. При задании нулевого начального масштабирующего параметра g = 0 формула для пересчета весовых коэффициентов имеет вид (деление выполняется поэлементно).

Итак, у вас есть задача предсказать какое-то значение вроде стоимости дома по его размеру. Или время обработки какого-то запроса вашей системой. Да мало ли что.

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

  1. Batch Gradient Descent (общий градиентный спуск)
  2. Stochastic Gradient Descent (стохастический градиентный спуск)
  3. Normal Equations (нормальные уравнения)
  4. Newton’s Method (метод Ньютона)

Сегодня мы поговорим о двух видах градиентного спуска.

Gradient Descent

Что вообще такое градиентный спуск?

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

Зеленая линия показывает, что в этой точке производная будет положительной, красная – отрицательной.

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

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

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

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

Вы можете представить эту функцию как «чашку» в трехмерном пространстве:

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

Наша функция стоимости имеет вид:

Ее градиент обозначается как и будет вычисляться по такой формуле:

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

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

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

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

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


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

Чем ближе вы подбираетесь к минимуму функции стоимости (чем меньше разница между предсказанной ценой и реальной), тем лучше ваша прямая описывает ваши исторические данные:

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

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

В псевдокоде stochastic gradient descent выглядит так:

Until Cost Function change is small: {

For j:= 1 to m {

Напоследок, особенности схождения алгоритма: batch gradient descent всегда сходится к минимуму при условии, что используется достаточно маленькое значение . Stochastic gradient descent в общем виде не сходится к минимуму, но есть его модификации, которые позволяют добиться сходимости.

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

В этом посте вы найдете объяснение градиентного спуска с небольшим количеством математики. Краткое содержание:

  • Смысл ГС — объяснение всего алгоритма;
  • Различные вариации алгоритма;
  • Реализация кода: написание кода на языке Phyton.

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

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

Итак, градиентный спуск нужен для минимизации функции потерь.

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


Поиск минимума функции

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

На рисунке мы видим график функции потерь (названный «Ошибка» с символом «J») с одним весом. Теперь, если мы вычислим наклон (обозначим это dJ/dw) функции потерь относительно одного веса, то получим направление, в котором нужно двигаться, чтобы достичь локальных минимумов. Давайте пока представим, что наша модель имеет только один вес.

Функция потерь

Важно: когда мы перебираем все учебные данные, мы продолжаем добавлять значения dJ/dw для каждого веса. Так как потери зависят от примера обучения, dJ/dw также продолжает меняться. Затем делим собранные значения на количество примеров обучения для получения среднего. Потом мы используем это среднее значение (каждого веса) для настройки каждого веса.

Также обратите внимание: Функция потерь предназначена для отслеживания ошибки с каждым примером обучениям, в то время как производная функции относительного одного веса – это то, куда нужно сместить вес, чтобы минимизировать ее для этого примера обучения. Вы можете создавать модели даже без применения функции потерь. Но вам придется использовать производную относительно каждого веса (dJ/dw).

Теперь, когда мы определили направление, в котором нужно подтолкнуть вес, нам нужно понять, как это сделать. Тут мы используем коэффициент скорости обучения, его называют гипер-параметром. Гипер-параметр – значение, требуемое вашей моделью, о котором мы действительно имеем очень смутное представление. Обычно эти значения могут быть изучены методом проб и ошибок. Здесь не так: одно подходит для всех гипер-параметров. Коэффициент скорости обучения можно рассматривать как «шаг в правильном направлении», где направление происходит от dJ/dw.

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

Подробнее о градиентах

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

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

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

Коэффициент скорости обучения

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

Однако проблема у большинства моделей возникает с коэффициентом скорости обучения. Давайте взглянем на обновленное выражение для каждого веса (j лежит в диапазоне от 0 до количества весов, а Theta-j это j-й вес в векторе весов, k лежит в диапазоне от 0 до количества смещений, где B-k — это k-е смещение в векторе смещений). Здесь alpha – коэффициент скорости обучения. Из этого можно сказать, что мы вычисляем dJ/dTheta-j (градиент веса Theta-j), и затем шаг размера alpha в этом направлении. Следовательно, мы спускаемся по градиенту. Чтобы обновить смещение, замените Theta-j на B-k.

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

Использование градиентного спуска

Что ж, вот и всё. Это всё, что нужно знать про градиентный спуск. Давайте подытожим всё в псевдокоде.

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

От i = 0 до «количество примеров обучения»

1. Вычислите градиент функции потерь для i-го примера обучения по каждому весу и смещению. Теперь у вас есть вектор, который полон градиентами для каждого веса и переменной, содержащей градиент смещения.

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

3. Подобно ситуации с весами, добавьте градиент смещения к аккумулятивной переменной.

Теперь, ПОСЛЕ перебирания всех примеров обучения, выполните следующие действия:

1. Поделите аккумулятивные переменные весов и смещения на количество примеров обучения. Это даст нам средние градиенты для всех весов и средний градиент для смещения. Будем называть их обновленными аккумуляторами (ОА).

2. Затем, используя приведенную ниже формулу, обновите все веса и смещение. Вместо dJ / dTheta-j вы будете подставлять ОА (обновленный аккумулятор) для весов и ОА для смещения. Проделайте то же самое для смещения.

Это была только одна итерация градиентного спуска.

Повторите этот процесс от начала до конца для некоторого количества итераций. Это означает, что для 1-й итерации ГС вы перебираете все примеры обучения, вычисляете градиенты, потом обновляете веса и смещения. Затем вы проделываете это для некоторого количества итераций ГС.

Различные типы градиентного спуска

Существует 3 варианта градиентного спуска:

1. Мini-batch : тут вместо перебирания всех примеров обучения и с каждой итерацией, выполняющей вычисления только на одном примере обучения, мы обрабатываем n учебных примеров сразу. Этот выбор хорош для очень больших наборов данных.

2. Стохастический градиентный спуск : в этом случае вместо использования и зацикливания на каждом примере обучения, мы ПРОСТО ИСПОЛЬЗУЕМ ОДИН РАЗ. Есть несколько вещей замечаний:

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

3. Серия ГС : это то, о чем написано в предыдущих разделах. Цикл на каждом примере обучения.


Картинка, сравнивающая 3 попадания в локальные минимумы

Пример кода на python

Применимо к cерии ГС, так будет выглядеть блок учебного кода на Python.

Def train(X, y, W, B, alpha, max_iters): """ Performs GD on all training examples, X: Training data set, y: Labels for training data, W: Weights vector, B: Bias variable, alpha: The learning rate, max_iters: Maximum GD iterations. """ dW = 0 # Weights gradient accumulator dB = 0 # Bias gradient accumulator m = X.shape # No. of training examples for i in range(max_iters): dW = 0 # Reseting the accumulators dB = 0 for j in range(m): # 1. Iterate over all examples, # 2. Compute gradients of the weights and biases in w_grad and b_grad, # 3. Update dW by adding w_grad and dB by adding b_grad, W = W - alpha * (dW / m) # Update the weights B = B - alpha * (dB / m) # Update the bias return W, B # Return the updated weights and bias.

Вот и всё. Теперь вы должны хорошо понимать, что такое метод градиентного спуска.

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

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

Если в качестве взять орты, т. то эта оценка при как легко заметить из (3.3.22), дает точное значение градиента.

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

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

где - по-прежнему единичный случайный -мерный вектор. Это известный градиентный алгоритм случайного поиска . Второй алгоритм имеет вид (3.3.23), но оценка градиента вычисляется по формуле

При как легко заметить, оба алгоритма вырождаются, в градиентный алгоритм поиска (3.3.21).

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

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

Так, алгоритм случайного поиска с линейной тактикой (3.3.12) является стохастической моделью алгоритма наискорейшего спуска:

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

оператор случайного шага заменяет громоздкий оператор оценки градиента, например, по формуле (3.3.22).

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

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

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

Цель - минимизировать функцию F в пространстве все возможных точек. График F представляет собой параболическую поверхность, и у неё должен быть один-единственный минимум. А вопрос о том, как исправлять точки так, чтобы двигаться в сторону этого минимума, давным-давно решён в математическом анализе. Для этого нужно двигаться в направлении, противоположном градиенту - вектору, вдоль которого производная максимальна. Градиент вычисляется следующим образом:

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

Таким образом, чтобы определить, как правильно исправлять координаты точек, мы должны вычислить градиент и отнять вектор какой-нибудь наперёд заданной длины (в нашем случае этой длинной выступает заданный шаг а) от имеющегося вектора точек:

Чтобы реализовать это программно, нужно научиться дифференцировать функцию F:

Пример 1 - алгоритм градиентного спуска для одной точки.

GradientDescent()

  • 1. Инициализировать маленькими случайными значениями.
  • 2. Повторить Number_of_Steps раз:
    • а) Для всех i от 1 до n
    • б) Для всех j от 1 до m :
      • (i) Для всех i от 1 до n
  • 3. выдать значения.

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

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

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

Похожие статьи