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

Информацию об аналитическом методе под названием «наискорейший спуск» см. в разделе « Метод наискорейшего спуска » .

Продолжительность: 14 секунд. 0:14

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

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

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

Градиентный спуск обычно приписывают Огюстену-Луи Коши , который впервые предложил его в 1847 году. Жак Адамар независимо предложил аналогичный метод в 1907 году. Его свойства сходимости для задач нелинейной оптимизации были впервые изучены Хаскеллом Карри в 1944 году: этот метод становится все более хорошо изученным и используется в последующие десятилетия.

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

Описание

Иллюстрация градиентного спуска на серии наборов уровней

Градиентный спуск основан на наблюдении, что если функция многих переменных $F(\mathbf {x} )$ определен дифференцируем и точки в окрестности $\mathbf {a}$, затем $F(\mathbf {x} )$ убывает, быстрее всего если перейти от $\mathbf {a}$ в направлении градиента отрицательного $F$ в $\mathbf {a} ,-\nabla F(\mathbf {a} )$. Отсюда следует, что если

$\mathbf {a} _{n+1}=\mathbf {a} _{n}-\gamma \nabla F(\mathbf {a} _{n})$

для достаточно небольшого размера шага или скорости обучения $\gamma \in \mathbb {R} _{+}$, затем $F(\mathbf {a_{n}} )\geq F(\mathbf {a_{n+1}} )$. Другими словами, термин $\gamma \nabla F(\mathbf {a} )$ вычитается из $\mathbf {a}$ потому что мы хотим двигаться против градиента, к локальному минимуму. Учитывая это наблюдение, можно начать с предположения. $\mathbf {x} _{0}$ за местный минимум $F$и рассматривает последовательность $\mathbf {x} _{0},\mathbf {x} _{1},\mathbf {x} _{2},\ldots$ такой, что

$\mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}\nabla F(\mathbf {x} _{n}),\ n\geq 0.$

Имеем монотонную последовательность

$F(\mathbf {x} _{0})\geq F(\mathbf {x} _{1})\geq F(\mathbf {x} _{2})\geq \cdots ,$

итак, надеюсь, последовательность $(\mathbf {x} _{n})$ сходится к желаемому локальному минимуму. Обратите внимание, что значение размера шага $\gamma$ разрешено изменять на каждой итерации.

к локальному минимуму можно Гарантировать сходимость при определенных предположениях на функцию $F$ (например, $F$ выпуклый и $\nabla F$ Липшиц ) и конкретный выбор $\gamma$. К ним относятся последовательность

$\gamma _{n}={\frac {\left|\left(\mathbf {x} _{n}-\mathbf {x} _{n-1}\right)^{T}\left[\nabla F(\mathbf {x} _{n})-\nabla F(\mathbf {x} _{n-1})\right]\right|}{\left\|\nabla F(\mathbf {x} _{n})-\nabla F(\mathbf {x} _{n-1})\right\|^{2}}}$

как и в методе Барзилаи-Борвейна , или последовательность $\gamma _{n}$ удовлетворяющие условиям Вульфа (которые можно найти с помощью поиска по строке ). Когда функция $F$ является выпуклым , все локальные минимумы также являются глобальными минимумами, поэтому в этом случае градиентный спуск может сходиться к глобальному решению.

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

Аналогия для

Туман в горах

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

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

Выбор размера шага и направления спуска

Поскольку использование размера шага $\gamma$ слишком маленький размер замедлит сближение, а $\gamma$ слишком большое значение приведет к перерегулированию и расхождению, поэтому необходимо найти хорошую настройку $\gamma$ является важной практической проблемой. Филип Вулф также выступал за использование на практике «умного выбора направления [спуска]». Хотя использование направления, которое отклоняется от направления самого крутого спуска, может показаться нелогичным, идея состоит в том, что меньший уклон можно компенсировать, сохраняя его на гораздо большем расстоянии.

Чтобы рассуждать об этом математически, рассмотрим направление $\mathbf {p} _{n}$ и размер шага $\gamma _{n}$ и рассмотрим более общее обновление:

$\mathbf {a} _{n+1}=\mathbf {a} _{n}-\gamma _{n}\,\mathbf {p} _{n}$.

Поиск хороших настроек $\mathbf {p} _{n}$ и $\gamma _{n}$ требует некоторого размышления. Прежде всего, нам бы хотелось, чтобы направление обновления было направлено вниз. Математически, позволяя $\theta _{n}$ обозначаем угол между $-\nabla F(\mathbf {a_{n}} )$ и $\mathbf {p} _{n}$, для этого требуется $\cos \theta _{n}>0.$ Более того, нам нужно больше информации о целевой функции, которую мы оптимизируем. При достаточно слабом предположении, что $F$ непрерывно дифференцируема, мы можем доказать, что:

$F(\mathbf {a} _{n+1})\leq F(\mathbf {a} _{n})-\gamma _{n}\|\nabla F(\mathbf {a} _{n})\|_{2}\|\mathbf {p} _{n}\|_{2}\left[\cos \theta _{n}-\max _{t\in [0,1]}{\frac {\|\nabla F(\mathbf {a} _{n}-t\gamma _{n}\mathbf {p} _{n})-\nabla F(\mathbf {a} _{n})\|_{2}}{\|\nabla F(\mathbf {a} _{n})\|_{2}}}\right]$ ( 1 )

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

В принципе неравенство ( 1 ) можно оптимизировать по $\mathbf {p} _{n}$ и $\gamma _{n}$ выбрать оптимальный размер и направление шага. Проблема в том, что для оценки второго члена в квадратных скобках требуется вычислить $\nabla F(\mathbf {a} _{n}-t\gamma _{n}\mathbf {p} _{n})$, а дополнительные оценки градиента обычно дороги и нежелательны. Некоторые способы решения этой проблемы:

• Откажитесь от преимуществ умного направления спуска, установив $\mathbf {p} _{n}=\nabla F(\mathbf {a_{n}} )$и воспользуйтесь поиском по строке , чтобы найти подходящий размер шага $\gamma _{n}$, например тот, который удовлетворяет условиям Вульфа . Более экономичный способ выбора скорости обучения — поиск по строке с возвратом — метод, который имеет как хорошие теоретические гарантии, так и экспериментальные результаты. Обратите внимание, что не нужно выбирать $\mathbf {p} _{n}$ быть градиентом; любое направление, имеющее положительное произведение пересечения с градиентом, приведет к уменьшению значения функции (при достаточно малом значении $\gamma _{n}$).
• Предполагая, что $F$ дважды дифференцируема, используйте его гессиан $\nabla ^{2}F$ оценить $\|\nabla F(\mathbf {a} _{n}-t\gamma _{n}\mathbf {p} _{n})-\nabla F(\mathbf {a} _{n})\|_{2}\approx \|t\gamma _{n}\nabla ^{2}F(\mathbf {a} _{n})\mathbf {p} _{n}\|.$Затем выберите $\mathbf {p} _{n}$ и $\gamma _{n}$ путем оптимизации неравенства ( 1 ).
• Предполагая, что $\nabla F$ является Липшицем , используйте его константу Липшица $L$ связывать $\|\nabla F(\mathbf {a} _{n}-t\gamma _{n}\mathbf {p} _{n})-\nabla F(\mathbf {a} _{n})\|_{2}\leq Lt\gamma _{n}\|\mathbf {p} _{n}\|.$ Затем выберите $\mathbf {p} _{n}$ и $\gamma _{n}$ путем оптимизации неравенства ( 1 ).
• Создайте собственную модель $\max _{t\in [0,1]}{\frac {\|\nabla F(\mathbf {a} _{n}-t\gamma _{n}\mathbf {p} _{n})-\nabla F(\mathbf {a} _{n})\|_{2}}{\|\nabla F(\mathbf {a} _{n})\|_{2}}}$ для $F$. Затем выберите $\mathbf {p} _{n}$ и $\gamma _{n}$ путем оптимизации неравенства ( 1 ).
• При более сильных предположениях на функцию $F$ такие как выпуклость более продвинутые методы . , могут быть возможны

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

Решение линейной системы

Алгоритм наискорейшего спуска, примененный к фильтру Винера

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

$A\mathbf {x} -\mathbf {b} =0$

переформулирована как задача квадратичной минимизации.Если системная матрица $A$ вещественно симметрична и положительно определена , целевая функция определяется как квадратичная функция с минимизацией

$F(\mathbf {x} )=\mathbf {x} ^{T}A\mathbf {x} -2\mathbf {x} ^{T}\mathbf {b} ,$

так что

$\nabla F(\mathbf {x} )=2(A\mathbf {x} -\mathbf {b} ).$

Для общей вещественной матрицы $A$, линейный метод наименьших квадратов определяет

$F(\mathbf {x} )=\left\|A\mathbf {x} -\mathbf {b} \right\|^{2}.$

В традиционных линейных методах наименьших квадратов на самом деле $A$ и $\mathbf {b}$ этом случае используется евклидова норма, в

$\nabla F(\mathbf {x} )=2A^{T}(A\mathbf {x} -\mathbf {b} ).$

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

Например, для вещественной симметричной и положительно определенной матрицы $A$, простой алгоритм может быть следующим:

${\begin{aligned}&{\text{repeat in the loop:}}\\&\qquad \mathbf {r} :=\mathbf {b} -\mathbf {Ax} \\&\qquad \gamma :={\mathbf {r} ^{\mathsf {T}}\mathbf {r} }/{\mathbf {r} ^{\mathsf {T}}\mathbf {Ar} }\\&\qquad \mathbf {x} :=\mathbf {x} +\gamma \mathbf {r} \\&\qquad {\hbox{if }}\mathbf {r} ^{\mathsf {T}}\mathbf {r} {\text{ is sufficiently small, then exit loop}}\\&{\text{end repeat loop}}\\&{\text{return }}\mathbf {x} {\text{ as the result}}\end{aligned}}$

Чтобы не умножать на $A$ дважды за итерацию,мы отмечаем, что $\mathbf {x} :=\mathbf {x} +\gamma \mathbf {r}$ подразумевает $\mathbf {r} :=\mathbf {r} -\gamma \mathbf {Ar}$, что дает традиционный алгоритм,

${\begin{aligned}&\mathbf {r} :=\mathbf {b} -\mathbf {Ax} \\&{\text{repeat in the loop:}}\\&\qquad \gamma :={\mathbf {r} ^{\mathsf {T}}\mathbf {r} }/{\mathbf {r} ^{\mathsf {T}}\mathbf {Ar} }\\&\qquad \mathbf {x} :=\mathbf {x} +\gamma \mathbf {r} \\&\qquad {\hbox{if }}\mathbf {r} ^{\mathsf {T}}\mathbf {r} {\text{ is sufficiently small, then exit loop}}\\&\qquad \mathbf {r} :=\mathbf {r} -\gamma \mathbf {Ar} \\&{\text{end repeat loop}}\\&{\text{return }}\mathbf {x} {\text{ as the result}}\end{aligned}}$

Этот метод редко используется для решения линейных уравнений, при этом метод сопряженных градиентов является одной из самых популярных альтернатив. Количество итераций градиентного спуска обычно пропорционально числу спектральных условий. $\kappa (A)$ системной матрицы $A$ (отношение максимального и минимального собственных значений $A^{T}A$) , тогда как сходимость метода сопряженных градиентов обычно определяется квадратным корнем из числа обусловленности, т. е. происходит намного быстрее. Оба метода могут извлечь выгоду из предварительной обработки , где градиентный спуск может потребовать меньше предположений в отношении предварительной обработки.

Решение нелинейной системы

Градиентный спуск также можно использовать для решения системы нелинейных уравнений . Ниже приведен пример, показывающий, как использовать градиентный спуск для решения трех неизвестных переменных: x ₁ , x ₂ и x ₃ . В этом примере показана одна итерация градиентного спуска.

Рассмотрим нелинейную систему уравнений

${\begin{cases}3x_{1}-\cos(x_{2}x_{3})-{\tfrac {3}{2}}=0\\4x_{1}^{2}-625x_{2}^{2}+2x_{2}-1=0\\\exp(-x_{1}x_{2})+20x_{3}+{\tfrac {10\pi -3}{3}}=0\end{cases}}$

Введем ассоциированную функцию

$G(\mathbf {x} )={\begin{bmatrix}3x_{1}-\cos(x_{2}x_{3})-{\tfrac {3}{2}}\\4x_{1}^{2}-625x_{2}^{2}+2x_{2}-1\\\exp(-x_{1}x_{2})+20x_{3}+{\tfrac {10\pi -3}{3}}\\\end{bmatrix}},$

где

$\mathbf {x} ={\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\\end{bmatrix}}.$

Теперь можно определить целевую функцию

${\begin{aligned}F(\mathbf {x} )&={\frac {1}{2}}G^{\mathrm {T} }(\mathbf {x} )G(\mathbf {x} )\\&={\frac {1}{2}}\left[\left(3x_{1}-\cos(x_{2}x_{3})-{\frac {3}{2}}\right)^{2}+\left(4x_{1}^{2}-625x_{2}^{2}+2x_{2}-1\right)^{2}+\right.\\&{}\qquad \left.\left(\exp(-x_{1}x_{2})+20x_{3}+{\frac {10\pi -3}{3}}\right)^{2}\right],\end{aligned}}$

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

$\mathbf {x} ^{(0)}=\mathbf {0} ={\begin{bmatrix}0\\0\\0\\\end{bmatrix}}.$

Мы знаем, что

$\mathbf {x} ^{(1)}=\mathbf {0} -\gamma _{0}\nabla F(\mathbf {0} )=\mathbf {0} -\gamma _{0}J_{G}(\mathbf {0} )^{\mathrm {T} }G(\mathbf {0} ),$

где матрица Якобиана $J_{G}$ дается

$J_{G}(\mathbf {x} )={\begin{bmatrix}3&\sin(x_{2}x_{3})x_{3}&\sin(x_{2}x_{3})x_{2}\\8x_{1}&-1250x_{2}+2&0\\-x_{2}\exp {(-x_{1}x_{2})}&-x_{1}\exp(-x_{1}x_{2})&20\\\end{bmatrix}}.$

Мы рассчитываем:

$J_{G}(\mathbf {0} )={\begin{bmatrix}3&0&0\\0&2&0\\0&0&20\end{bmatrix}},\qquad G(\mathbf {0} )={\begin{bmatrix}-2.5\\-1\\10.472\end{bmatrix}}.$

Таким образом

$\mathbf {x} ^{(1)}=\mathbf {0} -\gamma _{0}{\begin{bmatrix}-7.5\\-2\\209.44\end{bmatrix}},$

и

$F(\mathbf {0} )=0.5\left((-2.5)^{2}+(-1)^{2}+(10.472)^{2}\right)=58.456.$

Анимация, показывающая первые 83 итерации градиентного спуска, примененные к этому примеру. Поверхности – изоповерхности это $F(\mathbf {x} ^{(n)})$ по текущему предположению $\mathbf {x} ^{(n)}$, а стрелки показывают направление спуска. Из-за небольшого и постоянного размера шага сходимость происходит медленно.

Теперь подходящий $\gamma _{0}$ должно быть найдено такое, что

$F\left(\mathbf {x} ^{(1)}\right)\leq F\left(\mathbf {x} ^{(0)}\right)=F(\mathbf {0} ).$

Это можно сделать с помощью любого из множества алгоритмов поиска строк . Можно также просто догадаться $\gamma _{0}=0.001,$ что дает

$\mathbf {x} ^{(1)}={\begin{bmatrix}0.0075\\0.002\\-0.20944\\\end{bmatrix}}.$

Оценка целевой функции по этому значению дает

$F\left(\mathbf {x} ^{(1)}\right)=0.5\left((-2.48)^{2}+(-1.00)^{2}+(6.28)^{2}\right)=23.306.$

Снижение с $F(\mathbf {0} )=58.456$ к значению следующего шага

$F\left(\mathbf {x} ^{(1)}\right)=23.306$

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

Комментарии

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

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

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

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

методы, основанные на методе Ньютона и обращении гессиана с использованием методов сопряженных градиентов . Лучшими альтернативами могут быть Как правило, такие методы сходятся за меньшее количество итераций, но стоимость каждой итерации выше. Примером может служить метод BFGS , который заключается в вычислении на каждом шаге матрицы, на которую умножается вектор градиента, чтобы перейти в «лучшее» направление, в сочетании с более сложным алгоритмом поиска линии , чтобы найти «лучшее» значение $\gamma .$ Для чрезвычайно больших задач, где преобладают проблемы с памятью компьютера, метод ограниченной памяти, такой как L-BFGS вместо BFGS или метода наикрутейшего спуска следует использовать .

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

Градиентный спуск можно рассматривать как применение метода Эйлера для решения обыкновенных дифференциальных уравнений. $x'(t)=-\nabla f(x(t))$ к градиентному потоку . В свою очередь, это уравнение можно вывести как оптимальный регулятор для системы управления $x'(t)=u(t)$ с $u(t)$ предоставлено в форме обратной связи $u(t)=-\nabla f(x(t))$.

Модификации

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

Методы быстрого градиента

Юрий Нестеров был предложен простая модификация, которая обеспечивает более быструю сходимость для выпуклых задач и с тех пор получила дальнейшее обобщение. Для гладких задач без ограничений этот метод называется методом быстрого градиента (FGM) или методом ускоренного градиента (AGM). В частности, если дифференцируемая функция $F$ является выпуклым и $\nabla F$ является липшицевым , и не предполагается, что $F$ , сильно выпукло то ошибка в целевом значении, генерируемая на каждом шаге $k$ методом градиентного спуска будет ограничено ${\textstyle {\mathcal {O}}\left({\tfrac {1}{k}}\right)}$. При использовании метода ускорения Нестерова погрешность уменьшается при ${\textstyle {\mathcal {O}}\left({\tfrac {1}{k^{2}}}\right)}$. Известно, что ставка ${\mathcal {O}}\left({k^{-2}}\right)$ по убыванию функции стоимости оптимальна для методов оптимизации первого порядка. Тем не менее, есть возможность улучшить алгоритм за счет уменьшения постоянного коэффициента. Оптимизированный градиентный метод (OGM) уменьшает эту константу в два раза и является оптимальным методом первого порядка для крупномасштабных задач.

Для ограниченных или негладких задач FGM Нестерова называется методом быстрого проксимального градиента (FPGM), ускорением метода проксимального градиента .

или шара Метод

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

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

Расширения

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

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

Теоретические свойства

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

См. также

• Поиск строки с возвратом
• Метод сопряженных градиентов
• Стохастический градиентный спуск
• Рпроп
• Правило Дельты
• Условия Вульфа
• Предварительное кондиционирование
• Алгоритм Бройдена–Флетчера–Гольдфарба–Шенно
• Формула Дэвидона – Флетчера – Пауэлла
• Метод Нелдера-Мида
• Алгоритм Гаусса – Ньютона
• восхождение на холм
• Квантовый отжиг
• CLS (непрерывный локальный поиск)
• Нейроэволюция

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

• Бойд, Стивен ; Ванденберге, Ливен (2004). «Неограниченная минимизация» (PDF) . Выпуклая оптимизация . Нью-Йорк: Издательство Кембриджского университета. стр. 457–520. ISBN  0-521-83378-7 .
• Чонг, Эдвин КП; Жак, Станислав Х. (2013). «Градиентные методы» . Введение в оптимизацию (Четвертое изд.). Хобокен: Уайли. стр. 131–160. ISBN  978-1-118-27901-4 .
• Химмельблау, Дэвид М. (1972). «Процедуры неограниченной минимизации с использованием производных». Прикладное нелинейное программирование . Нью-Йорк: МакГроу-Хилл. стр. 63–132. ISBN  0-07-028921-2 .

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

• Использование градиентного спуска в C++, Boost, Ublas для линейной регрессии
• В серии видеороликов Академии Хана обсуждается градиентное восхождение.
• Онлайн-книга, обучающая градиентному спуску в контексте глубоких нейронных сетей
• Архивировано в Ghostarchive и Wayback Machine : «Градиентный спуск, как обучаются нейронные сети» . 3Синий1Коричневый . 16 октября 2017 г. — через YouTube .
• Справочник по теоремам сходимости для (стохастических) градиентных методов