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

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

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

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

ОписаниеПравить

 

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

Пусть целевая функция имеет вид:

$F(\stackrel{\to <!--\; \to \; -->}{x}):\mathbb{X}\to <!--\; \to \; -->\mathbb{R}$$F({\vec {x}}):\;\mathbb {X} \to \mathbb {R}$ .

И задача оптимизации задана следующим образом:

$F(\stackrel{\to <!--\; \to \; -->}{x})\to <!--\; \to \; -->\underset{\stackrel{\to <!--\; \to \; -->}{x}\in <!--\; \in \; -->\mathbb{X}}{min}$$F({\vec {x}})\to \min _{{\vec {x}}\in \mathbb {X} }$ 

В случае, когда требуется найти максимум, вместо $F(\stackrel{\to <!--\; \to \; -->}{x})$$F({\vec {x}})$  используется $-<!--\; -\; -->F(\stackrel{\to <!--\; \to \; -->}{x})$$-F({\vec {x}})$ 

Основная идея метода заключается в том, чтобы идти в направлении наискорейшего спуска, а это направление задаётся антиградиентом $-<!--\; -\; -->\mathrm{\nabla <!--\; \nabla \; -->}F$$-\nabla F$ :

${\stackrel{\to <!--\; \to \; -->}{x}}^{[j+1]}={\stackrel{\to <!--\; \to \; -->}{x}}^{[j]}-<!--\; -\; -->{\mathrm{\lambda <!--\; \lambda \; -->}}^{[j]}\mathrm{\nabla <!--\; \nabla \; -->}F\left({\stackrel{\to <!--\; \to \; -->}{x}}^{[j]}\right)$${\vec {x}}^{[j+1]}={\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F\left({\vec {x}}^{[j]}\right)$ 

где ${\mathrm{\lambda <!--\; \lambda \; -->}}^{[j]}$$\lambda ^{[j]}$ задает скорость градиентного спуска и может быть выбрана

• постоянной (в этом случае метод может расходиться);
• убывающей в процессе градиентного спуска;
• гарантирующей наискорейший спуск:
  1. Для поиска минимума $F\left(\stackrel{\to <!--\; \to \; -->}{x}\right)$$F\left({\vec {x}}\right)$  получаем ${\mathrm{\lambda <!--\; \lambda \; -->}}^{[j]}={\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}_{\mathrm{\lambda <!--\; \lambda \; -->}}F\left({\stackrel{\to <!--\; \to \; -->}{x}}^{[j+1]}\right)={\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}_{\mathrm{\lambda <!--\; \lambda \; -->}}F\left({\stackrel{\to <!--\; \to \; -->}{x}}^{[j]}-<!--\; -\; -->\mathrm{\lambda <!--\; \lambda \; -->}\mathrm{\nabla <!--\; \nabla \; -->}F\left({\stackrel{\to <!--\; \to \; -->}{x}}^{[j]}\right)\right)$$\lambda ^{[j]}=\mathrm {argmin} _{\lambda }F\left({\vec {x}}^{[j+1]}\right)=\mathrm {argmin} _{\lambda }\,F\left({\vec {x}}^{[j]}-\lambda \nabla F\left({\vec {x}}^{[j]}\right)\right)$ 
  2. Для поиска максимума $F\left(\stackrel{\to <!--\; \to \; -->}{x}\right)$$F\left({\vec {x}}\right)$  получаем ${\mathrm{\lambda <!--\; \lambda \; -->}}^{[j]}={\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}\mathrm{x}}_{\mathrm{\lambda <!--\; \lambda \; -->}}F\left({\stackrel{\to <!--\; \to \; -->}{x}}^{[j+1]}\right)={\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}\mathrm{x}}_{\mathrm{\lambda <!--\; \lambda \; -->}}F\left({\stackrel{\to <!--\; \to \; -->}{x}}^{[j]}+\mathrm{\lambda <!--\; \lambda \; -->}\mathrm{\nabla <!--\; \nabla \; -->}F\left({\stackrel{\to <!--\; \to \; -->}{x}}^{[j]}\right)\right)$$\lambda ^{[j]}=\mathrm {argmax} _{\lambda }F\left({\vec {x}}^{[j+1]}\right)=\mathrm {argmax} _{\lambda }\,F\left({\vec {x}}^{[j]}+\lambda \nabla F\left({\vec {x}}^{[j]}\right)\right)$ 

АлгоритмПравить

1. Задают начальное приближение и точность расчёта ${\stackrel{\to <!--\; \to \; -->}{x}}^0,\mathrm{\epsilon <!--\; \epsilon \; -->}$${\vec {x}}^{0},\varepsilon$ 
2. Рассчитывают ${\stackrel{\to <!--\; \to \; -->}{x}}^{[j+1]}={\stackrel{\to <!--\; \to \; -->}{x}}^{[j]}-<!--\; -\; -->{\mathrm{\lambda <!--\; \lambda \; -->}}^{[j]}\mathrm{\nabla <!--\; \nabla \; -->}F\left({\stackrel{\to <!--\; \to \; -->}{x}}^{[j]}\right)$${\vec {x}}^{[j+1]}={\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F\left({\vec {x}}^{[j]}\right)$ , где ${\mathrm{\lambda <!--\; \lambda \; -->}}^{[j]}={\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}_{\mathrm{\lambda <!--\; \lambda \; -->}}F\left({\stackrel{\to <!--\; \to \; -->}{x}}^{[j]}-<!--\; -\; -->\mathrm{\lambda <!--\; \lambda \; -->}\mathrm{\nabla <!--\; \nabla \; -->}F\left({\stackrel{\to <!--\; \to \; -->}{x}}^{[j]}\right)\right)$$\lambda ^{[j]}=\mathrm {argmin} _{\lambda }\,F\left({\vec {x}}^{[j]}-\lambda \nabla F\left({\vec {x}}^{[j]}\right)\right)$ 
3. Проверяют условие остановки:
   • Если $\left|{\stackrel{\to <!--\; \to \; -->}{x}}^{[j+1]}-<!--\; -\; -->{\stackrel{\to <!--\; \to \; -->}{x}}^{[j]}\right|>\mathrm{\epsilon <!--\; \epsilon \; -->}$$\left|{\vec {x}}^{[j+1]}-{\vec {x}}^{[j]}\right|>\varepsilon$ , $\left|F\left({\stackrel{\to <!--\; \to \; -->}{x}}^{[j+1]}\right)-<!--\; -\; -->F\left({\stackrel{\to <!--\; \to \; -->}{x}}^{[j]}\right)\right|>\mathrm{\epsilon <!--\; \epsilon \; -->}$$\left|F\left({\vec {x}}^{[j+1]}\right)-F\left({\vec {x}}^{[j]}\right)\right|>\varepsilon$  или $\Vert \mathrm{\nabla <!--\; \nabla \; -->}F\left({\stackrel{\to <!--\; \to \; -->}{x}}^{[j+1]}\right)\Vert >\mathrm{\epsilon <!--\; \epsilon \; -->}$$\left\|\nabla F\left({\vec {x}}^{[j+1]}\right)\right\|>\varepsilon$  (выбирают одно из условий), то $j=j+1$$j=j+1$  и переход к шагу 2.
   • Иначе $\stackrel{\to <!--\; \to \; -->}{x}={\stackrel{\to <!--\; \to \; -->}{x}}^{[j+1]}$${\vec {x}}={\vec {x}}^{[j+1]}$  и останов.

Соотношение КанторовичаПравить

Для квадратичной функции вида $\frac{x^T\mathrm{\Gamma <!--\; \Gamma \; -->}x}{2}+c^{T}x,{\mathrm{\Gamma <!--\; \Gamma \; -->}}^T=\mathrm{\Gamma <!--\; \Gamma \; -->}$${\frac {x^{T}\Gamma x}{2}}+c^{T}x,\Gamma ^{T}=\Gamma$  метод наискорейшего градиентного поиска сходится из любой начальной точки $x_0$$x_{0}$  со скоростью геометрической прогрессии (линейно) со знаменателем, не превосходящим значение $q$$q$ . При этом справедливы следующие оценки:

$\mathrm{\exists <!--\; \exists \; -->}a=a(x_0),T>0:0\le <!--\; \le \; -->a\le <!--\; \le \; -->q=\frac{{\left({\mathrm{\lambda <!--\; \lambda \; -->}}_{min}/{\mathrm{\lambda <!--\; \lambda \; -->}}_{max}-<!--\; -\; -->1\right)}^2}{{\left({\mathrm{\lambda <!--\; \lambda \; -->}}_{min}/{\mathrm{\lambda <!--\; \lambda \; -->}}_{max}+1\right)}^2}$$\exists a=a(x_{0}),T>0:0\leq a\leq q={\frac {\left(\lambda _{min}/\lambda _{max}-1\right)^{2}}{\left(\lambda _{min}/\lambda _{max}+1\right)^{2}}}$ ,

$f(x_k)-<!--\; -\; -->f(x^{\ast <!--\; \ast \; -->})\le <!--\; \le \; -->a^k(f(x_0)-<!--\; -\; -->f(x^{\ast <!--\; \ast \; -->}))$$f(x_{k})-f(x^{*})\leq a^{k}(f(x_{0})-f(x^{*}))$ ,

$\Vert <!--\; \Vert \; -->x_k-<!--\; -\; -->x^{\ast <!--\; \ast \; -->}\Vert <!--\; \Vert \; -->\le <!--\; \le \; -->T{a}^{k/2}\Vert <!--\; \Vert \; -->x_0-<!--\; -\; -->x^{\ast <!--\; \ast \; -->}\Vert <!--\; \Vert \; -->$$\|x_{k}-x^{*}\|\leq Ta^{k/2}\|x_{0}-x^{*}\|$ ,

где ${\mathrm{\lambda <!--\; \lambda \; -->}}_{min}$$\lambda _{min}$  и ${\mathrm{\lambda <!--\; \lambda \; -->}}_{max}$$\lambda _{max}$  — минимальное и максимальное собственные числа матрицы вторых производных ${\mathrm{\nabla <!--\; \nabla \; -->}}^{2}f(x)=\mathrm{\Gamma <!--\; \Gamma \; -->}$$\nabla ^{2}f(x)=\Gamma$ .

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

ПримерПравить

Применим градиентный метод к функции $F(x,y)=\sin <!--\; \; -->\left(\frac{1}{2}{x}^2-<!--\; -\; -->\frac{1}{4}{y}^2+3\right)\cos <!--\; \; -->(2x+1-<!--\; -\; -->e^y)$$F(x,y)=\sin \left({\frac {1}{2}}x^{2}-{\frac {1}{4}}y^{2}+3\right)\cos(2x+1-e^{y})$ . Тогда последовательные приближения будут выглядеть так:

  

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

Усовершенствования, модификацииПравить

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

Метод градиентного спуска наиболее простой в реализации из всех методов локальной оптимизации. Имеет довольно слабые условия сходимости, но при этом скорость сходимости достаточно мала (линейна). Шаг градиентного метода часто используется как часть других методов оптимизации, например, метод Флетчера — Ривса.

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

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

Применение в искусственных нейронных сетяхПравить

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

СсылкиПравить

• J. Mathews. Module for Steepest Descent or Gradient Method.
• Метафорическая интерактивная демонстрация метода Наискорейший Пью

ЛитератураПравить

• Поляк Б. Т. Введение в оптимизацию. — М.: Наука. Главная редакция физико-математической литературы, 1983. — 384 с.
• Нестеров Ю. Е. Методы выпуклой оптимизации. — М.: Издательство МЦНМО, 2010. — 281 с.
• Гасников А. В. Современные численные методы оптимизации. Метод универсального градиентного спуска : учебное пособие. — М.: МФТИ, 2018. — 291 с. — ISBN 978-5-7417-0667-1.
• Акулич И. Л. Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. — С. 298-310.
• Гилл Ф., Мюррей У., Райт М. Практическая оптимизация = Practical Optimization. — М.: Мир, 1985.
• Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.
• Максимов Ю. А., Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
• Максимов Ю. А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.
• Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.
• Городецкий С. Ю., Гришагин В. А. Нелинейное программирование и многоэкстремальная оптимизация. — Нижний Новгород: Издательство Нижегородского Университета, 2007. — С. 357-363.