Метод градиентного спуска реферат

Обновлено: 02.07.2024

Метод градиентного спуска
[pic]
[pic]
Рис.1 Геометрическая интерпретация метода градиентного спуска с постоянным шагом. На каждом шаге мы сдвигаемся по вектору антиградиента, "уменьшенному в [pic]раз".

Основная идея метода заключается в том, чтобы осуществлять оптимизацию в направлении наискорейшего спуска, а это направление задаётся антиградиентом [pic]:
[pic]
где[pic]выбирается
• постоянной, в этом случае метод может расходиться;
• дробным шагом, т.е. длина шага в процессе спуска делится на некое число;
• наискорейшим спуском: [pic]

Критерии остановки процесса приближенного нахождения минимума могут быть основаны на различных соображениях. Некоторые из них:
1. [pic]
2. [pic]
Здеcь [pic]- значение, полученное после [pic]-го шага оптимизации. [pic]- наперед заданное положительное число.

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

Теорема 1 о сходимости метода градиентногоспуска спуска с постоянным шагом.
Пусть [pic], функция [pic]дифференцируема, ограничена снизу. Пусть выполняется условие Липшица для градиента [pic]: [pic]. Пусть [pic].
Тогда [pic]при любом выборе начального приближения.
В условиях теоремы градиентный метод обеспечивает сходимость [pic]либо к точной нижней грани [pic](если функция [pic]не имеет минимума) либо к значению [pic]Существуют примеры, когдав точке [pic]реализуется седло, а не минимум. Тем не менее, на практике методы градиентного спуска обычно обходят седловые точки и находят локальные минимумы целевой функции.
Определение. Дифференцируемая функция [pic]называется сильно выпуклой (с константой [pic]), если для любых [pic]и [pic]из [pic]справедливо
[pic]
Теорема 2 о сходимости метода градиентного спуска спуска с постояннымшагом.
Пусть функция [pic]дифференцируема, сильно выпукла с константой [pic]. Пусть выполняется условие Липшица для градиента [pic]: [pic]. Пусть [pic].
Тогда [pic]при любом выборе начального приближения.

Выбор оптимального шага

[pic]
[pic]
Рис.2 Ситуация, когда метод гардиентного спуска сходится плохо.
Константа [pic], фигурирующая в теореме 2 и характеризующая скорость сходимостиметода, зависит от шага [pic]. Нетрудно видеть, что величина [pic]минимальна, если шаг [pic]выбирается из условия [pic], т. е. если [pic].
При таком выборе шага оценка сходимости будет наилучшей и будет характеризоваться величиной:
[pic].
В качестве [pic]и [pic]могут выступать равномерные по x оценки сверху и снизу собственных значений оператора [pic]. Если [pic], то [pic]и метод сходится оченьмедленно. Геометрически случай [pic]соответствует функциям с сильно вытянутыми линиями уровня (см. рис. 2). Простейшим примером такой функции может служить функция на [pic], задаваемая формулой:
[pic].
Поведение итераций градиентного метода для этой функции изображено на рис. 2 — они, быстро спустившись на "дно оврага", затем медленно "зигзагообразно" приближаются к точке минимума. Число[pic](характеризующее, грубо говоря, разброс собственных значений оператора [pic]) называют числом обусловленности функции [pic]. Если [pic], то функции называют плохо обусловленными или овражными. Для таких функций градиентный метод сходится медленно.
Но даже для хорошо обусловленных функций проблема выбора шага нетривиальна в силу отсутствия априорной информации о минимизируемой функции. Если шаг выбираетсямалым (чтобы гарантировать сходимость), то метод сходится медленно. Увеличение же шага (с целью ускорения сходимости) может привести к расходимости метода. Далее будут описаны два алгоритма автоматического выбора шага, позволяющие частично обойти указанные трудности.

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

Рубрика	Программирование, компьютеры и кибернетика
Вид	реферат
Язык	русский
Дата добавления	25.12.2018
Размер файла	405,5 K

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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

КЫРГЫЗСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ

Факультет: Математики и информатики

Проверила: ст. пр. Саркелова Ж.Ж.

1. Метод градиентного спуска

1.3 Критерий останова

1.4 Сходимость градиентного спуска с постоянным шагом

1.5 Выбор оптимального шага

1.6 Градиентный метод с дроблением шага

1.7 Метод наискорейшего спуска

2. Числовые примеры

2.1 Метод градиентного спуска с постоянным шагом

2.2 Градиентный метод с дроблением шага

2.3 Метод наискорейшего спуска

3. Рекомендации программисту

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

В работе рассматривается задача поиска минимума функции , записываемая в виде:

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

В статье приведены теоремы сходимости метода градиентного спуска, а также рассмотрена его варианты:

Метод градиентного спуска с постоянным шагом

Метод градиентного спуска с дроблением шага

Метод наискорейшего спуска

1. Метод градиентного спуска

Рис.1 Геометрическая интерпретация метода градиентного спуска с постоянным шагом. На каждом шаге мы сдвигаемся по вектору антиградиента, "уменьшенному в раз".

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

где выбирается постоянной, в этом случае метод может расходиться;

дробным шагом, т.е. длина шага в процессе спуска делится на некое число;

Выход: найденная точка оптимума

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

1.3 Критерий останова

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

Здесь - значение, полученное после -го шага оптимизации. - наперед заданное положительное число.

1.4 Сходимость градиентного спуска с постоянным шагом

Теорема 1 о сходимости метода градиентного спуска с постоянным шагом.

Пусть , функция дифференцируема, ограничена снизу. Пусть выполняется условие Липшица для градиента : . Пусть .

Тогда при любом выборе начального приближения.

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

Определение. Дифференцируемая функция называется сильно выпуклой (с константой ), если для любых и из справедливо

Теорема 2 о сходимости метода градиентного спуска спуска с постоянным шагом.

Пусть функция дифференцируема, сильно выпукла с константой . Пусть выполняется условие Липшица для градиента : . Пусть .

Тогда при любом выборе начального приближения.

1.5 Выбор оптимального шага

Рис.2 Ситуация, когда метод гардиентного спуска сходится плохо.

Константа , фигурирующая в теореме 2 и характеризующая скорость сходимости метода, зависит от шага . Нетрудно видеть, что величина минимальна, если шаг выбирается из условия , т. е. если .

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

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

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

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

1.6 Градиентный метод с дроблением шага

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

где - некоторая заранее выбранная константа.

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

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

1.7 Метод наискорейшего спуска

Рис.3 Геометрическая интерпретация метода наискорейшего спуска. На каждом шаге выбирается так, чтобы следующая итерация была точкой минимума функции на луче L.

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

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

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

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

2. Числовые примеры

2.1 Метод градиентного спуска с постоянным шагом

Для исследования сходимости метода градиентного спуска с постоянным шагом была выбрана функция:

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

Решается задача минимизации функции j(x) на всём пространстве E_n. Методы спуска состоят в следующей процедуре построения последовательности k>. Â качестве начального приближения выбирается любая точка x₀ÎE_n. Последовательные приближения x₁, x₂, … строятся по следующей схеме:

1) в точке x_k выбирают направление спуска — S_k;

Направление S_k выбирают таким образом, чтобы обеспечить неравенство j(x_k+1) 0.

В случае, если =0, полагают x_k+1=x_k и переходят к следующей итерации.

Нужна помощь в написании реферата?

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

Опишем первый цикл метода, состоящий из n итераций. В произвольной точке x₀ выбирают S₀=±e, и определяет величину b₀ способом удвоения так, чтобы было j(x₁)=j(x₀-b₀S₀) 2 +y 2 -xy-3y c точностью e, используя описанные выше методы.

Нахождение минимума моей функции с помощью метода покоординатного спуска.

Для получения результата программой было выполнено 24 итерации.

Нужна помощь в написании реферата?

Нахождение минимума с помощью метода градиентного спуска.

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

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

Итак, взяв те же начальные условия я получил следующие результаты:

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

Нужна помощь в написании реферата?

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

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

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

Рассмотрим функцию f, считая для определенности, что она зависит от трех переменных x, y, z. Вычислим ее частные производные дf/дх, дf/ду, дf/дz и образуем с их помощью вектор, который называют градиентом функции: Отметим, что при таких расчетах gi, нельзя брать слишком малым, а значения функции нужно вычислять с достаточно высокой степенью точности, иначе при вычислении разности. На рис1… Читать ещё >

решение задачи многомерной оптимизации при помощи компьютера

Метод градиентного спуска ( реферат , курсовая , диплом , контрольная )

grad f (x, у, z) = дf (х, у, z) /дх*i+дf (x, у, z)/ду*j+дf (x, y, z)/дг*k.

Здесь i, j, k — единичные векторы, параллельные координатным осям. Частные производные характеризуют изменение функции f по каждой независимой переменной в отдельности. Образованный с их помощью вектор градиента дает общее представление о поведении функции в окрестности точки (х, у, z). Направление этого вектора является направлением наиболее быстрого возрастания функции в данной точке. Противоположное ему направление, которое часто называют антиградиентным, представляет собой направление наиболее быстрого убывания функции. Модуль градиента.

grad (х, у, z)|—=Ц—(дf/дх (х, у, z))2 +(дf/ду (x, у, z))2+(дf/дг (x, y, z))2.

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

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

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

Для оценки частных производных используются разностные методы:

где g_i — пробный шаг по i-й переменной, выбираемый достаточно малым для разностной оценки производной.

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

будет допущена большая ошибка.

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

На рис1. изображены линии уровня функции двух переменных u= f (х, у),, и приведена траектория поиска ее минимума с помощью метода градиентного спуска.

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

Примечание от автора

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

Постановка задачи

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

Немного математики

Еще в 17 веке Пьером Ферма был придуман критерий, который позволял решать простые задачи оптимизации, а именно, еcли — точка минимума , то

где — производная . Этот критерий основан на линейном приближении

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

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

Стоит отметить, что указанные условия являются необходимыми, но не достаточными, самый простой пример — 0 для и

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

Квадратичные функции

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

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

Зачем я об этом рассказываю? Дело в том, что квадратичные функции важны в оптимизации по двум причинам:

Они тоже встречаются на практике, например при построении линейной регрессии методом наименьших квадратов
Градиент квадратичной функции — линейная функция, в частности для функции выше

Или в матричной форме

Полезные свойства градиента

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

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

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

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

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

Градиентный спуск

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

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

для всех , то гарантирует убывание .

Анализ для квадратичных функций

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

где — единичная матрица, т.е. для всех . Если же , то получится

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

Модификации градиентного спуска

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

Инерционные или ускоренные градиентные методы

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

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

Метод Чебышева

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

где — некоторый многочлен степени . Почему бы не попробовать подобрать таким образом, чтобы было поменьше? Один уз универсальных многочленов, которые меньше всего отклоняются от нуля — многочлен Чебышева. Метод Чебышева по сути заключается в том, чтобы подобрать параметры спуска так, чтобы был многочленом Чебышева. Есть правда одна небольшая проблема: для обычного градиентного спуска это просто невозможно. Однако для инерционных методов это оказывается возможным. В основном это происходит из-за того, что многочлены Чебышева удовлетворяют рекуррентному соотношению второго порядка

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

Метод сопряженных градиентов

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

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

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

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

Метод Нестерова

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

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

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

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

Если принимает значения равновероятно, то как раз в среднем — это градиент . Этот пример показателен еще и следующим: сложность вычисления градиента в раз больше, чем сложность вычисления . Это позволяет стохастическому градиентному спуску делать за одно и то же время в раз больше итераций. Несмотря на то, что стохастический градиентный спуск обычно сходится медленней обычного, за счет такого большого увеличения числа итераций получается улучшить скорость сходимости на единицу времени. Насколько мне известно — на данный момент стохастический градиентный спуск является базовым методом обучения большинства нейронных сетей, реализован во всех основных библиотеках по ML: tensorflow, torch, caffe, CNTK, и т.д.

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

Субградиентный спуск

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

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

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

Допустим мы начали из точки .
Шаг субградиентного спуска:

Где обычно или . На практике я часто видел успешное применение шагов , хоть и для таких шагов вообще говоря не будет сходимости.

Proximal методы

Заключение

На этом заканчиваются основные известные мне вариации градиентного метода. Пожалуй под конец я бы отметил, что все указанные модификации (кроме разве что метода сопряженных градиентов) могут легко взаимодействовать друг с другом. Я специально не стал включать в эту перечень метод Ньютона и квазиньютоновские методы (BFGS и прочие): они хоть и используют градиент, но при этом являются более сложными методами, требуют специфических дополнительных вычислений, которые обычно более вычислительно затратны, нежели вычисление градиента. Тем не менее, если этот текст будет востребован, я с удовольствием сделаю подобный обзор и по ним.

Читайте также: