Участник:Anton/Песочница

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 6: Строка 6:
== Метод градиентного спуска ==
== Метод градиентного спуска ==
-
===Алгоритм===
+
=== Идея метода ===
 +
Основная идея метода заключается в том, чтобы идти в направлении наискорейшего спуска, а это направление задаётся антиградиентом <tex>-\nabla f</tex>:
 +
 +
<tex>x^{[j+1]}=x^{[j]}-\lambda^{[j]}\nabla f(x^{[j]}) </tex>
 +
 +
где <tex>\lambda^{[j]}</tex> выбирается
 +
*постоянной, в этом случае метод может расходиться;
 +
*дробным шагом, т.е. длина шага в процессе спуска делится на некое число;
 +
*наискорейшим спуском: <tex>\lambda^{[j]}=\arg \min_{\lambda} \,f(x^{[j]}-\lambda\nabla f(x^{[j]})) \!</tex>
 +
 +
=== Алгоритм ===
'''Вход:''' функция <tex>f: \mathbb{R}^n \to \mathbb{R}</tex>
'''Вход:''' функция <tex>f: \mathbb{R}^n \to \mathbb{R}</tex>
'''Выход:''' найденная точка оптимума <tex>x</tex>
'''Выход:''' найденная точка оптимума <tex>x</tex>
-
# Инициализация некоторым значением <tex>x_0 \in \mathbb{R}^n</tex>
+
# Повторять:
-
# повторять:
+
# <tex>x^{[j+1]}=x^{[j]}-\lambda^{[j]}\nabla f(x^{[j]}) </tex>, где <tex>\lambda^{[j]}=\arg\min_{\lambda} \,f(x^{[j]}-\lambda \nabla f(x^{[j]})) </tex>
-
#* для <tex>i=1\dots n</tex>
+
# если выполен критерий останова, то возвращаем текущее значение <tex>x^{[j+1]}</tex>
-
#*# фиксируем значения всех переменных кроме <tex>x_i</tex>, получая одномерную функцию <tex>f(x_i)</tex>
+
 
-
#*# проводим одномерную оптимизацию по переменной <tex>x_i</tex>, любым методом одномерной оптимизации
+
-
#*# если выполен критерий останова, то возвращаем текущее значение <tex>x=(x_1,\dots,x_n)</tex>
+
-
+
===Критерий останова===
===Критерий останова===
Критерии остановки процесса приближенного нахождения минимума могут быть основаны на различных соображениях.
Критерии остановки процесса приближенного нахождения минимума могут быть основаны на различных соображениях.
Некоторые из них:
Некоторые из них:
-
# <tex>||x_{k+1}-x_{k}||\leq\eps</tex>
+
# <tex>||x^{[k+1]}-x^{[k]}||\leq\eps</tex>
-
# <tex>||f(x_{k+1})-f(x_{k})||\leq\eps</tex>
+
# <tex>||f(x^{[k+1]})-f(x^{[k]})||\leq\eps</tex>
-
Здечь <tex>x_k \in \mathbb{R}^n</tex> --- значение, полученное после <tex>k</tex>-го шага оптимизации.
+
Здеcь <tex>x^{[k]} \in \mathbb{R}^n</tex> - значение, полученное после <tex>k</tex>-го шага оптимизации.
 +
<tex>\eps</tex> - наперед заданное положительное число.
===Сходимость метода===
===Сходимость метода===
-
 
-
Легко убедится, что существуют функции, когда метод координатного спуска не приводит даже в локальный оптимум.
 
-
 
-
Пусть линии уровня образуют истинный овраг (рис.1), когда спуск по любой координате приводит на <<дно>> оврага, а любое движение по следующей координате (пунктирная линия) ведет на подъем. Никакой дальнейший спуск по координатам в данном случае невозможен, хотя минимум еще не достигнут.
 
-
 
-
'''Теорема о сходимости метода покоординатного спуска.'''
 
-
 
-
Для простоты рассмотрим функцию двух переменных <tex>f(x,y)</tex>. Выберем некоторое началное приближение <tex>(x_0,y_0)</tex> и проведем линию уровня через эту точку. Пусть в области <tex>G</tex>, ограниченной этой линией уровня, выполняются неравенства, означающий положительную определенность квадратичной формы:
 
-
::<tex>f_{xx}''\geq a>0,\; f_{yy}''\geq b>0,\; |f_{xy}''|\leq c,\; ab>c^2.</tex>
 
-
Тогда спуск по координатам сходится к минимуму из данного начального приближения, причем линейно.
 
== Числовые примеры ==
== Числовые примеры ==

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

Содержание

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

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

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

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

Идея метода

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

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

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

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

Алгоритм

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

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

  1. Повторять:
  2. x^{[j+1]}=x^{[j]}-\lambda^{[j]}\nabla f(x^{[j]}) , где \lambda^{[j]}=\arg\min_{\lambda} \,f(x^{[j]}-\lambda \nabla f(x^{[j]}))
  3. если выполен критерий останова, то возвращаем текущее значение x^{[j+1]}

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

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

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

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

Сходимость метода

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

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

Заключение

Ссылки

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

  • А.А.Самарский, А.В.Гулин.  Численные методы. Москва «Наука», 1989.
  • Н.С.Бахвалов, Н.П.Жидков, Г.М.Кобельков.  Численные методы. Лаборатория Базовых Знаний, 2003.
  • Н.Н.Калиткин.  Численные методы. Москва «Наука», 1978.
Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Anton/%D0%9F%D0%B5%D1%81%D0%BE%D1%87%D0%BD%D0%B8%D1%86%D0%B0»
Личные инструменты