Участник:Margarita/Градиентный спуск: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
(Новая страница: «== Постановка задачи == Рассмотрим задачу поиска минимума функции <math>f(x)\colon \mathbb{R}^n \to \mathbb{R…»)
 
Строка 6: Строка 6:
 
\end{align}
 
\end{align}
 
</math>
 
</math>
Будем считать, что функция <math>f(x)</math> такова, что можно вычислить её градиент.
+
Будем считать, что у функции <math>f(x)</math> существуют частные производные.
 +
 
 +
Если в задаче требуется найти максимум, вместо <math>f(x)</math> следует брать <math>-f(x)</math>.
  
 
=== Общее описание алгоритма ===
 
=== Общее описание алгоритма ===
Наискорейший спуск<ref>, Н. Н. Калиткин “Численные методы.” Москва <<Наука>>, 1978</ref> — это вариант градиентного спуска: метода нахождения локального экстремума функции с помощью движения вдоль направления градиента.
+
Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.
 +
 
 +
Градиентный спуск является популярным методом в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путем минимизации функции цены.
  
 
===Математическое описание алгоритма ===
 
===Математическое описание алгоритма ===
Основная идея метода состоит в том, чтобы идти в направлении <math>-\nabla f</math>, то есть в направлении, в котором функция быстрее всего убывает при бесконечно малом движении из данной точки:
+
Основная идея <ref>, Н. Н. Калиткин “Численные методы.” Москва «Наука», 1978</ref> метода состоит в том, чтобы идти в направлении <math>-\nabla f</math>, то есть в направлении, в котором функция быстрее всего убывает при бесконечно малом движении из данной точки:
 
:<math>
 
:<math>
 
\begin{align}
 
\begin{align}
x^{k+1} = x^{k} - \lambda^{k}(\nabla f),
+
x_{k+1} = x_{k} - \alpha_{k}\nabla f(x_{k}),
 
\end{align}
 
\end{align}
 
</math>
 
</math>
где выбирается  <math>\lambda^{k} </math>по следующему правилу: <math>\lambda^{k} = \operatorname{arg}\min_{\lambda}  f(x^{k} - \lambda^{k}(\nabla f))</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 Постановка задачи

Рассмотрим задачу поиска минимума функции [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 Схема реализации последовательного алгоритма

Алгоритм:

  1. Выбираем начальную точку [math]x_{0}, \varepsilon[/math].
  2. Вычисляем [math]x_{k+1} = x_{k} - \alpha_{k}\nabla f(x_{k})[/math], где [math]\alpha_{k}[/math] выбирается одним из описанных выше способом.
  3. Если выполнено условие останова, то возвращаем [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];

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. , Н. Н. Калиткин “Численные методы.” Москва «Наука», 1978
  2. A. D. Belegundu and T. R. Chandrupatla. Optimization Concepts and Applications in Engineering, chapter 3. Prentice Hall, 1999