Участник:Margarita/Градиентный спуск: различия между версиями
Перейти к навигации
Перейти к поиску
Margarita (обсуждение | вклад) Новая страница: «== Постановка задачи == Рассмотрим задачу поиска минимума функции <math>f(x)\colon \mathbb{R}^n \to \mathbb{R…» |
Margarita (обсуждение | вклад) Нет описания правки |
||
| Строка 6: | Строка 6: | ||
\end{align} | \end{align} | ||
</math> | </math> | ||
Будем считать, что | Будем считать, что у функции <math>f(x)</math> существуют частные производные. | ||
Если в задаче требуется найти максимум, вместо <math>f(x)</math> следует брать <math>-f(x)</math>. | |||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации. | |||
Градиентный спуск является популярным методом в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путем минимизации функции цены. | |||
===Математическое описание алгоритма === | ===Математическое описание алгоритма === | ||
Основная идея метода состоит в том, чтобы идти в направлении <math>-\nabla f</math>, то есть в направлении, в котором функция быстрее всего убывает при бесконечно малом движении из данной точки: | Основная идея <ref>, Н. Н. Калиткин “Численные методы.” Москва «Наука», 1978</ref> метода состоит в том, чтобы идти в направлении <math>-\nabla f</math>, то есть в направлении, в котором функция быстрее всего убывает при бесконечно малом движении из данной точки: | ||
:<math> | :<math> | ||
\begin{align} | \begin{align} | ||
x_{k+1} = x_{k} - \alpha_{k}\nabla f(x_{k}), | |||
\end{align} | \end{align} | ||
</math> | </math> | ||
где выбирается <math>\ | где выбирается <math>\alpha_{k}</math>по следующему правилу: | ||
* постоянной, в таком случае метод может не сходиться; | |||
* дробным шагом, то есть во время итерации длина шага делится на некоторое число; | |||
* наискорейшим спуском<ref>A. D. Belegundu and T. R. Chandrupatla. Optimization Concepts and Applications in Engineering, chapter 3. Prentice Hall, 1999</ref>, где <math>\alpha_{k} = \operatorname{arg}\min_{\alpha} f(x_{k} - \alpha_{k}\nabla f(x_{k}))</math>. | |||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
| Строка 25: | Строка 32: | ||
=== Схема реализации последовательного алгоритма === | === Схема реализации последовательного алгоритма === | ||
'''Алгоритм:''' | |||
# Выбираем начальную точку <math>x_{0}, \varepsilon</math>. | |||
# Вычисляем <math>x_{k+1} = x_{k} - \alpha_{k}\nabla f(x_{k})</math>, где <math>\alpha_{k}</math> выбирается одним из описанных выше способом. | |||
# Если выполнено условие останова, то возвращаем <math>x_{k+1}</math>, иначе переходим к шагу 2. | |||
Критерии останова могут различаться, исходя из различных соображений. Ниже приведены некоторые из них: | |||
*<math> \| x_{k+1} - x_{k} \| <\varepsilon </math>; | |||
*<math> \| f(x_{k+1}) - f(x_{k}) \| <\varepsilon </math>; | |||
*<math> \| \nabla f(x_{k+1}) \| <\varepsilon </math>; | |||
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
Версия от 21:14, 22 октября 2017
Постановка задачи
Рассмотрим задачу поиска минимума функции [math]\displaystyle{ f(x)\colon \mathbb{R}^n \to \mathbb{R} }[/math]
- [math]\displaystyle{ \begin{align} f(x) \rightarrow \min_{x \in \mathbb{R}^n} \end{align} }[/math]
Будем считать, что у функции [math]\displaystyle{ f(x) }[/math] существуют частные производные.
Если в задаче требуется найти максимум, вместо [math]\displaystyle{ f(x) }[/math] следует брать [math]\displaystyle{ -f(x) }[/math].
Общее описание алгоритма
Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.
Градиентный спуск является популярным методом в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путем минимизации функции цены.
Математическое описание алгоритма
Основная идея [1] метода состоит в том, чтобы идти в направлении [math]\displaystyle{ -\nabla f }[/math], то есть в направлении, в котором функция быстрее всего убывает при бесконечно малом движении из данной точки:
- [math]\displaystyle{ \begin{align} x_{k+1} = x_{k} - \alpha_{k}\nabla f(x_{k}), \end{align} }[/math]
где выбирается [math]\displaystyle{ \alpha_{k} }[/math]по следующему правилу:
- постоянной, в таком случае метод может не сходиться;
- дробным шагом, то есть во время итерации длина шага делится на некоторое число;
- наискорейшим спуском[2], где [math]\displaystyle{ \alpha_{k} = \operatorname{arg}\min_{\alpha} f(x_{k} - \alpha_{k}\nabla f(x_{k})) }[/math].
Вычислительное ядро алгоритма
Макроструктура алгоритма
Схема реализации последовательного алгоритма
Алгоритм:
- Выбираем начальную точку [math]\displaystyle{ x_{0}, \varepsilon }[/math].
- Вычисляем [math]\displaystyle{ x_{k+1} = x_{k} - \alpha_{k}\nabla f(x_{k}) }[/math], где [math]\displaystyle{ \alpha_{k} }[/math] выбирается одним из описанных выше способом.
- Если выполнено условие останова, то возвращаем [math]\displaystyle{ x_{k+1} }[/math], иначе переходим к шагу 2.
Критерии останова могут различаться, исходя из различных соображений. Ниже приведены некоторые из них:
- [math]\displaystyle{ \| x_{k+1} - x_{k} \| \lt \varepsilon }[/math];
- [math]\displaystyle{ \| f(x_{k+1}) - f(x_{k}) \| \lt \varepsilon }[/math];
- [math]\displaystyle{ \| \nabla f(x_{k+1}) \| \lt \varepsilon }[/math];