Участник: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>; | ||
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
Версия 00:14, 23 октября 2017
Содержание
- 1 Постановка задачи
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
1 Постановка задачи
Рассмотрим задачу поиска минимума функции [math]f(x)\colon \mathbb{R}^n \to \mathbb{R}[/math]
- [math] \begin{align} f(x) \rightarrow \min_{x \in \mathbb{R}^n} \end{align} [/math]
Будем считать, что у функции [math]f(x)[/math] существуют частные производные.
Если в задаче требуется найти максимум, вместо [math]f(x)[/math] следует брать [math]-f(x)[/math].
1.1 Общее описание алгоритма
Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.
Градиентный спуск является популярным методом в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путем минимизации функции цены.
1.2 Математическое описание алгоритма
Основная идея [1] метода состоит в том, чтобы идти в направлении [math]-\nabla f[/math], то есть в направлении, в котором функция быстрее всего убывает при бесконечно малом движении из данной точки:
- [math] \begin{align} x_{k+1} = x_{k} - \alpha_{k}\nabla f(x_{k}), \end{align} [/math]
где выбирается [math]\alpha_{k}[/math]по следующему правилу:
- постоянной, в таком случае метод может не сходиться;
- дробным шагом, то есть во время итерации длина шага делится на некоторое число;
- наискорейшим спуском[2], где [math]\alpha_{k} = \operatorname{arg}\min_{\alpha} f(x_{k} - \alpha_{k}\nabla f(x_{k}))[/math].
1.3 Вычислительное ядро алгоритма
1.4 Макроструктура алгоритма
1.5 Схема реализации последовательного алгоритма
Алгоритм:
- Выбираем начальную точку [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} \| \lt \varepsilon [/math];
- [math] \| f(x_{k+1}) - f(x_{k}) \| \lt \varepsilon [/math];
- [math] \| \nabla f(x_{k+1}) \| \lt \varepsilon [/math];
