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

Материал из MachineLearning.

(Различия между версиями)

Перейти к: навигация, поиск

Версия 22:44, 22 ноября 2008

Содержание

1 Постановка задачи
2 Метод градиентного спуска
3 Числовые примеры
4 Рекомендации программисту
5 Заключение
6 Ссылки
7 Список литературы

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

Рассмотрим задачу поиска минимума функции $f(x): \mathbb{R}^n \to \mathbb{R}$ , записываемую в виде:

(1)

$f(x) \to \min_{x \in \mathbb{R}^n}$

Пусть функция $f(x)$ такова, что можно вычислить ее градиент.

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

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

Идея метода

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

$x^{[k+1]}=x^{[k]}-\lambda^{[k]}\nabla f(x^{[k]})$

где $\lambda^{[k]}$ выбирается

постоянной, в этом случае метод может расходиться;
дробным шагом, т.е. длина шага в процессе спуска делится на некое число;
наискорейшим спуском: $\lambda^{[k]}=\arg\min_{\lambda} \,f(x^{[k]}-\lambda\nabla f(x^{[k]}))$

Алгоритм

Вход: функция $f: \mathbb{R}^n \to \mathbb{R}$

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

Повторять:
$x^{[k+1]}=x^{[k]}-\lambda^{[k]}\nabla f(x^{[k]})$ , где $\lambda^{[k]}$ выбирается одним из описанных выше способов
если выполен критерий останова, то возвращаем текущее значение $x^{[k+1]}$

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

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

$||x^{[k+1]}-x^{[k]}||\leq\eps$
$||f(x^{[k+1]})-f(x^{[k]})||\leq\eps$

Здеcь $x^{[k]} \in \mathbb{R}^n$ - значение, полученное после $k$ -го шага оптимизации. $\eps$ - наперед заданное положительное число.

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

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

Пусть $\lambda^{[k]}=\lambda=const$ , функция $f$ дифференцируема, ограничена снизу. Пусть выполняется условие Липшица для градиента $f'(x)$ : $||f'(x)-f'(y)|| \leq L ||x-y||$ . Пусть $0<\lambda<2/L$ .

Тогда $\lim_{k \to \infty}f'(x^{[k]}) = 0, \; f(x^{[k+1]})<f(x^{[k]})$ при любом выборе начального приближения.

В условиях теоремы градиентный метод обеспечивает сходимость $\{ x^{[k]} \}$ либо к точной нижней грани $\inf_x f(x)$ (если функция $f(x)$ не имеет минимума) либо к значению $f(x*): \;\lim_{k \to \infty}x^{[k]} = x*,\; f'(x*)=0.$ Существуют примеры, когда в точке $x*$ реализуется седло, а не минимум. Тем не менее, на практике методы градиентного спуска обычно обходят седловые точки и находят локальные минимумы целевой функции.

Определение. Дифференцируемая функция $f$ называется сильно выпуклой (с константой $\Lambda>0$ ), если для любых $x$ и $y$ из $\mathbb{R}^n$ справедливо

$f(x+y)\geq f(x)+ \langle f'(x) ,y \rangle + \Lambda||y||^2/2 .$

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

Пусть функция $f$ дифференцируема, сильно выпукла с константой $\Lambda$ . Пусть выполняется условие Липшица для градиента $f'(x)$ : $||f'(x)-f'(y)|| \leq L ||x-y||$ . Пусть $0<\lambda<2/L$ .

Тогда $\lim_{k \to \infty}x^{[k]} = x*, \; ||x^{[k]}-x*||\leq q^k ||x^{[0]}-x*||, \; q = \max\{|1-\lambda\Lambda|, |1-\lambda L |\}$ при любом выборе начального приближения.

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

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

Константа $q$ , фигурирующая в теореме 2 и характеризующая скорость сходимости метода, зависит от шага $\lambda$ . Нетрудно видеть, что величина $q=q(\lambda)=\max\{|1-\lambda\Lambda|, |1-\lambda L |\}$ минимальна, если шаг $\lambda$ выбирается из условия $|1-\lambda\Lambda| = |1-\lambda L |$ , т. е. если $\lambda = \lambda* = 2/(\Lambda + L)$ .

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

$q=q*=\frac{L-\Lambda}{L+\Lambda}$ .

В качестве $\Lambda$ и $L$ могут выступать равномерные по x оценки сверху и снизу собственных значений оператора $f''(x)$ . Если $\lambda << \Lambda$ , то $q*\approx 1$ и метод сходится очень медленно. Геометрически случай $\lambda << \Lambda$ соответствует функциям с сильно вытянутыми линиями уровня (см. рис. 2). Простейшим примером такой функции может служить функция на $\mathbb{R}^2$ , задаваемая формулой:

$f(x_1,x_2)=\Lambda x_1^2 + L x_2^2, \; \Lambda << L$ .

Поведение итераций градиентного метода для этой функции изображено на рис. 2 — они, быстро спустившись на "дно оврага", затем медленно "зигзагообразно" приближаются к точке минимума. Число $\mu = L/\Lambda$ (характеризующее, грубо говоря, разброс собственных значений оператора $f''(x)$ ) называют числом обусловленности функции $f$ . Если $\mu >> 1$ , то функции называют плохо обусловленными или овражными. Для таких функций градиентный метод сходится медленно.

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

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

В этом варианте градиентного метода величина шага $\lambda^{[k]}$ на каждой итерации выбирается из условия выполнения неравенства

(2)

$f(x^{[k+1]}) = f(x^{[k]}-\lambda^{[k]} f'(x^{[k]})) \leq f(x^{[k]})-\eps \lambda^{[k]}||f'(x^{[k]})||^2$ ,

где $\eps \in (0, 1)$ - некоторая заранее выбранная константа.

Процедуру нахождения такого $\lambda^{[k]}$ обычно оформляют так. Выбирается число $\delta \in (0, 1)$ и некоторый начальный шаг $\lambda^{[0]}$ . Теперь для каждого k полагают $\lambda^{[k]}=\lambda^{[0]}$ и делают шаг градиентного метода. Если с таким $\lambda^{[k]}$ условие (2) выполняется, то переходят к следующему k. Если же (2) не выполняется, то умножают $\lambda^{[k]}$ на $\delta$ ("дробят шаг") и повторяют эту процедуру до тех пор пока неравенство (2) не будет выполняться. В условиях теоремы 1 эта процедура для каждого k за конечное число шагов приводит к нужному $\lambda^{[k]}$ .

Можно показать, что в условиях теоремы 2 градиентный метод с дроблением шага линейно сходится. Описанный алгоритм избавляет нас от проблемы выбора $\lambda^{[k]}$ на каждом шаге, заменяя ее на проблему выбора параметров $\eps,\;\delta$ и $\lambda^{[0]}$ , к которым градиентный метод менее чувствителен. При этом, разумеется, объем вычислений возрастает (в связи с необходимостью процедуры дробления шага), впрочем, не очень сильно, поскольку в большинстве задач основные вычислительные затраты ложатся на вычисление градиента.

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

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

Рис.3 Геометрическая интерпретация метода наискорейшего спуска. На каждом шаге $\lambda^{[k]}$ выбирается так, чтобы следующая итерация была точкой минимума функции $f$ на луче L.

Этот вариант градиентного метода основывается на выборе шага из следующего соображения. Из точки $x^{[k]}$ будем двигаться в направлении антиградиента до тех пор пока не достигнем минимума функции f на этом направлении, т. е. на луче $L=\{x=x^{[k]}-\lambda f'(x^{[k]});\; \lambda \leq 0}$ :

$\lambda^{[k]} = \arg\min_{ \lambda\in [0, \infty)} f(x^{[k]}-\lambda f'(x^{[k]}))$ .

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

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

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

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

Заключение

Ссылки

Практикум ММП ВМК, 4й курс, осень 2008

Список литературы

Н.Н.Калиткин. Численные методы. Москва «Наука», 1978.
Н.И.Глебов, Ю.А.Кочетов, А.В.Плясунов. Методы оптимизации. 2000.
Р.Р.Ахмеров. Методы оптимизации гладких функций.

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

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B3%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D0%B3%D0%BE_%D1%81%D0%BF%D1%83%D1%81%D0%BA%D0%B0»

Категории: Незавершённые статьи | Учебные задачи

@@ Строка 7: / Строка 7: @@
 == Метод градиентного спуска ==
+[[Изображение:Grad1.PNG|thumb|500px|Рис.1 Геометрическая интерпретация метода градиентного спуска с постоянным шагом. На каждом шаге мы сдвигаемся по вектору антиградиента, "уменьшенному в <tex>\lambda</tex> раз".]]
 === Идея метода ===
@@ Строка 12: / Строка 13: @@
 Основная идея метода заключается в том, чтобы осуществлять оптимизацию в направлении наискорейшего спуска, а это направление задаётся антиградиентом <tex>-\nabla f</tex>:
-<tex>x^{[j+1]}=x^{[j]}-\lambda^{[j]}\nabla f(x^{[j]}) </tex>
+<tex>x^{[k+1]}=x^{[k]}-\lambda^{[k]}\nabla f(x^{[k]}) </tex>
-где <tex>\lambda^{[j]}</tex> выбирается
+где <tex>\lambda^{[k]}</tex> выбирается
 *постоянной, в этом случае метод может расходиться;
 *дробным шагом, т.е. длина шага в процессе спуска делится на некое число;
-*наискорейшим спуском: <tex>\lambda^{[j]}=\arg \min_{\lambda} \,f(x^{[j]}-\lambda\nabla f(x^{[j]})) </tex>
+*наискорейшим спуском: <tex>\lambda^{[k]}=\arg\min_{\lambda} \,f(x^{[k]}-\lambda\nabla f(x^{[k]})) </tex>
 === Алгоритм ===
@@ Строка 25: / Строка 26: @@
 # Повторять:
-# <tex>x^{[j+1]}=x^{[j]}-\lambda^{[j]}\nabla f(x^{[j]}) </tex>, где <tex>\lambda^{[j]}</tex> выбирается одним из описанных выше способов
+# <tex>x^{[k+1]}=x^{[k]}-\lambda^{[k]}\nabla f(x^{[k]}) </tex>, где <tex>\lambda^{[k]}</tex> выбирается одним из описанных выше способов
-# если выполен критерий останова, то возвращаем текущее значение <tex>x^{[j+1]}</tex>
+# если выполен критерий останова, то возвращаем текущее значение <tex>x^{[k+1]}</tex>
 ===Критерий останова===
@@ Строка 37: / Строка 38: @@
 <tex>\eps</tex> - наперед заданное положительное число.
-===Сходимость метода===
+===Сходимость градиентного спуска с постоянным шагом===
 '''Теорема 1 о сходимости метода градиентного спуска спуска с постоянным шагом.'''
@@ Строка 48: / Строка 50: @@
 В условиях теоремы градиентный метод обеспечивает сходимость <tex>\{ x^{[k]} \}</tex> либо к точной нижней грани <tex>\inf_x f(x)</tex> (если функция <tex>f(x)</tex> не имеет минимума) либо к значению <tex>f(x*): \;\lim_{k \to \infty}x^{[k]} = x*,\; f'(x*)=0.</tex>  Существуют примеры, когда в точке <tex>x*</tex> реализуется седло, а не минимум. Тем не менее, на практике методы градиентного спуска обычно обходят седловые точки и находят локальные минимумы целевой функции.
-'''Определение.''' Дифференцируемая функция <tex>f</tex> называется сильно выпуклой (с константой <tex>l>0</tex>), если для любых <tex>x</tex> и <tex>y</tex> из <tex>\mathbb{R}^n</tex> справедливо
+'''Определение.''' Дифференцируемая функция <tex>f</tex> называется сильно выпуклой (с константой <tex>\Lambda>0</tex>), если для любых <tex>x</tex> и <tex>y</tex> из <tex>\mathbb{R}^n</tex> справедливо
-::<tex>f(x+y)\geq f(x)+ \langle f'(x) ,y \rangle + l||y||^2/2 .</tex>
+::<tex>f(x+y)\geq f(x)+ \langle f'(x) ,y \rangle + \Lambda||y||^2/2 .</tex>
 '''Теорема 2 о сходимости метода градиентного спуска спуска с постоянным шагом.'''
-Пусть функция <tex>f</tex> дифференцируема, сильно выпукла. Пусть выполняется условие Липшица для градиента <tex>f'(x)</tex>:
+Пусть функция <tex>f</tex> дифференцируема, сильно выпукла с константой <tex>\Lambda</tex>. Пусть выполняется условие Липшица для градиента <tex>f'(x)</tex>:
 <tex>||f'(x)-f'(y)|| \leq L ||x-y||</tex>.
 Пусть <tex>0<\lambda<2/L</tex>.
-Тогда  <tex>\lim_{k \to \infty}x^{[k]} = x*, \; ||x^{[k]}-x*||\leq Cq^k, \; 0<q<1</tex> при любом выборе начального приближения.
+Тогда  <tex>\lim_{k \to \infty}x^{[k]} = x*, \; ||x^{[k]}-x*||\leq q^k ||x^{[0]}-x*||, \; q = \max\{|1-\lambda\Lambda|, |1-\lambda L |\}</tex> при любом выборе начального приближения.
+===Выбор оптимального шага===
+[[Изображение:Grad3.PNG|thumb|500px|Рис.2 Ситуация, когда метод гардиентного спуска сходится плохо.]]
+Константа <tex>q</tex>, фигурирующая в теореме 2 и характеризующая скорость сходимости метода, зависит от шага <tex>\lambda</tex>.
+Нетрудно видеть, что величина <tex>q=q(\lambda)=\max\{|1-\lambda\Lambda|, |1-\lambda L |\}</tex> минимальна, если шаг <tex>\lambda</tex> выбирается из условия <tex>|1-\lambda\Lambda| = |1-\lambda L |</tex>, т. е. если <tex> \lambda = \lambda* = 2/(\Lambda + L)</tex>.
+При таком выборе шага оценка сходимости будет наилучшей и будет характеризоваться величиной:
+::<tex>q=q*=\frac{L-\Lambda}{L+\Lambda}</tex>.
+В качестве <tex>\Lambda</tex> и <tex>L</tex> могут выступать равномерные по x оценки сверху и снизу собственных значений оператора <tex>f''(x)</tex>. Если <tex>\lambda << \Lambda</tex>, то <tex>q*\approx 1</tex> и метод сходится очень медленно. Геометрически случай <tex>\lambda << \Lambda</tex> соответствует функциям с сильно вытянутыми линиями уровня (см. рис. 2). Простейшим примером такой функции может служить функция на <tex> \mathbb{R}^2 </tex>, задаваемая формулой:
+::<tex>f(x_1,x_2)=\Lambda x_1^2 + L x_2^2, \; \Lambda << L</tex>.
+Поведение итераций градиентного метода для этой функции изображено на рис. 2 — они, быстро спустившись на "дно оврага", затем медленно "зигзагообразно" приближаются к точке минимума. Число <tex>\mu = L/\Lambda </tex> (характеризующее, грубо говоря, разброс собственных значений оператора <tex>f''(x)</tex>) называют числом обусловленности функции <tex>f</tex>. Если <tex>\mu >> 1</tex>, то функции называют плохо обусловленными или овражными. Для таких функций градиентный метод сходится медленно.
+Но даже для хорошо обусловленных функций проблема выбора шага нетривиальна в силу отсутствия априорной информации о минимизируемой функции. Если шаг выбирается малым (чтобы гарантировать сходимость), то метод сходится медленно. Увеличение же шага (с целью ускорения сходимости) может привести к расходимости метода. Далее будут описаны два алгоритма автоматического выбора шага, позволяющие частично обойти указанные трудности.
+===Градиентный метод с дроблением шага===
+В этом варианте градиентного метода величина шага <tex>\lambda^{[k]}</tex> на каждой итерации выбирается из условия выполнения неравенства
+{{eqno|2}}
+::<tex>f(x^{[k+1]}) = f(x^{[k]}-\lambda^{[k]} f'(x^{[k]})) \leq f(x^{[k]})-\eps \lambda^{[k]}||f'(x^{[k]})||^2 </tex>,
+где <tex>\eps \in (0, 1) </tex> - некоторая заранее выбранная константа.
+Процедуру нахождения такого <tex>\lambda^{[k]}</tex> обычно оформляют так. Выбирается число <tex>\delta \in (0, 1)</tex> и некоторый начальный шаг <tex>\lambda^{[0]}</tex>. Теперь для каждого k полагают <tex>\lambda^{[k]}=\lambda^{[0]}</tex> и делают шаг градиентного метода. Если с таким <tex>\lambda^{[k]}</tex> условие {{eqref|2}} выполняется, то переходят к следующему k. Если же {{eqref|2}} не выполняется, то умножают <tex>\lambda^{[k]}</tex> на <tex>\delta</tex> ("дробят шаг") и повторяют эту процедуру до тех пор пока неравенство {{eqref|2}} не будет выполняться. В условиях теоремы 1 эта процедура для каждого k за конечное число шагов приводит к нужному <tex>\lambda^{[k]}</tex>.
+Можно показать, что в условиях теоремы 2 градиентный метод с дроблением шага линейно сходится. Описанный алгоритм избавляет нас от проблемы выбора <tex>\lambda^{[k]}</tex>  на каждом шаге, заменяя ее на проблему выбора параметров <tex> \eps,\;\delta</tex> и <tex>\lambda^{[0]}</tex>, к которым градиентный метод менее чувствителен. При этом, разумеется, объем вычислений возрастает (в связи с необходимостью процедуры дробления шага), впрочем, не очень сильно, поскольку в большинстве задач основные вычислительные затраты ложатся на вычисление градиента.
+===Метод наискорейшего спуска===
+[[Изображение:Grad2.PNG|thumb|500px|Рис.3 Геометрическая интерпретация метода наискорейшего спуска. На каждом шаге <tex>\lambda^{[k]}</tex> выбирается так, чтобы следующая итерация была точкой минимума функции <tex>f</tex> на луче L.]]
+Этот вариант градиентного метода основывается на выборе шага из следующего соображения. Из точки  <tex>x^{[k]}</tex> будем двигаться в направлении антиградиента до тех пор пока не достигнем минимума функции f на этом направлении, т. е. на луче
+<tex>L=\{x=x^{[k]}-\lambda f'(x^{[k]});\; \lambda \leq 0} </tex>:
+::<tex>\lambda^{[k]} = \arg\min_{ \lambda\in [0, \infty)} f(x^{[k]}-\lambda f'(x^{[k]}))</tex>.
+Другими словами, <tex>\lambda^{[k]}</tex> выбирается так, чтобы следующая итерация была точкой минимума функции f на луче L (см. рис. 3). Такой вариант градиентного метода называется методом наискорейшего спуска. Заметим, кстати, что в этом методе направления соседних шагов ортогональны.
+Метод наискорейшего спуска требует решения на каждом шаге задачи одномерной оптимизации. Практика показывает, что этот метод часто требует меньшего числа операций, чем градиентный метод с постоянным шагом.
+В общей ситуации, тем не менее, теоретическая скорость сходимости метода наискорейшего спуска не выше скорости сходимости градиентного метода с постоянным (оптимальным) шагом.
 == Числовые примеры ==
 == Рекомендации программисту ==
@@ Строка 66: / Строка 114: @@
 == Список литературы ==
-* ''А.А.Самарский, А.В.Гулин.''&nbsp; Численные методы. Москва «Наука», 1989.
-* ''Н.С.Бахвалов, Н.П.Жидков, Г.М.Кобельков.''&nbsp; Численные методы. Лаборатория Базовых Знаний, 2003.
 * ''Н.Н.Калиткин.''&nbsp; Численные методы. Москва «Наука», 1978.
 * ''Н.И.Глебов, Ю.А.Кочетов, А.В.Плясунов.''&nbsp;Методы оптимизации.  2000.
+* ''Р.Р.Ахмеров.''&nbsp; Методы оптимизации гладких функций.

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

Материал из MachineLearning.

Версия 22:44, 22 ноября 2008

Содержание

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

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

Идея метода

Алгоритм

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

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

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

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

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

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

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

Заключение

Ссылки

Список литературы

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты