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

Материал из Алговики
Перейти к навигации Перейти к поиску
 
(не показаны 24 промежуточные версии этого же участника)
Строка 2: Строка 2:
  
 
== Постановка задачи ==
 
== Постановка задачи ==
 +
[[Файл:grad.png|thumb|250px|Последовательные приближения к точке экстремума (зел.) в направлении наискорейшего спуска (красн.). Синим отмечены линии уровня функции.]]
 +
 
Рассмотрим задачу поиска минимума функции <math>f(x)\colon \mathbb{R}^n \to \mathbb{R}</math>
 
Рассмотрим задачу поиска минимума функции <math>f(x)\colon \mathbb{R}^n \to \mathbb{R}</math>
 
:<math>
 
:<math>
Строка 15: Строка 17:
 
Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.
 
Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.
  
−
Градиентный спуск активно применяется в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путем минимизации функции цены.
+
Градиентный спуск активно применяется в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путём минимизации функции цены.
  
 
===Математическое описание алгоритма ===
 
===Математическое описание алгоритма ===
Строка 28: Строка 30:
 
* дробным шагом, то есть во время итерации длина шага делится на некоторое число;
 
* дробным шагом, то есть во время итерации длина шага делится на некоторое число;
 
* наискорейшим спуском<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\nabla f(x_{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\nabla f(x_{k}))</math>.
 +
Таким образом идём пока не выполнится некоторый критерий останова, определяемый конкретной задачей.
  
 
=== Вычислительное ядро алгоритма ===
 
=== Вычислительное ядро алгоритма ===
 +
 +
Наибольшая сложность алгоритма приходится на вычисление частных производных. Это особенно касается более общего случая, когда функция задана неявно и производную можно вычислить только с помощью численного дифференцирования.
  
 
=== Макроструктура алгоритма ===
 
=== Макроструктура алгоритма ===
 +
 +
Алгоритм представляет собой итерационный процесс, на каждом шаге которого происходит вычисление последующей точки  <math>x_{k+1}</math>. Для этого необходимо знать начальное приближение <math>x_{0}</math>, значение градиента в предыдущей точке <math>\nabla f(x_{k})</math> и правило определения параметра  <math>\alpha_{k}</math>, определяемое условием задачи. Кроме того, задачей определён и критерий останова, который проверяется на каждой итерации.
  
 
=== Схема реализации последовательного алгоритма ===
 
=== Схема реализации последовательного алгоритма ===
Строка 45: Строка 52:
  
 
=== Последовательная сложность алгоритма ===
 
=== Последовательная сложность алгоритма ===
 +
 +
Наибольшую вычислительную сложность из арифметических операций представляют деление и умножение чисел с плавающей точкой.
 +
На каждом шаге необходимо численно вычислять производную по формуле:
 +
:<math>
 +
\begin{align}
 +
f'(x_0) ≈ \frac{f(x_0 + \delta) - f(x_0))}{\delta},
 +
\end{align}
 +
</math>
 +
 +
для этого потребуется <math>n</math> делений, где <math>n</math> — размерность пространства.
 +
Пусть сложность вычисления коэффициента <math>\alpha_{k}</math> равна <math>p_{\alpha}</math>, а сложность вычисления функции <math>p_{f}</math>. Умножение <math>\alpha_{k} \nabla f(x_0)</math> даёт ещё <math>n</math> умножений. В итоге получаем:
 +
:<math>
 +
\begin{align}
 +
P(n, p_{\alpha},  p_{f}) = 2n + p_{\alpha} +2p_{f},
 +
\end{align}
 +
</math>
 +
где <math>f = f(n)</math>.
  
 
=== Информационный граф ===
 
=== Информационный граф ===
 +
 +
[[file: InfoGr.png|thumb|center|700px|Информационный граф.]]
 +
 +
Синие вершины графа — итерационное вычисление последовательности <math>x_{k-1}, x_k, x_{k+1}</math>.
 +
 +
Зелёные вершины графа — численное вычисление частных производных.
  
 
=== Ресурс параллелизма алгоритма ===
 
=== Ресурс параллелизма алгоритма ===
 +
 +
На каждой итерации алгоритма необходимо численно пересчитывать градиент функции. В случае пространства большой размерности, основная часть времени выполнения приходится на вычисление частных производных в точке, которые вычисляются независимо друг от друга.
  
 
=== Входные и выходные данные алгоритма ===
 
=== Входные и выходные данные алгоритма ===
 +
 +
'''Входные данные''':
 +
* функция <math>f(x)\colon \mathbb{R}^n \to \mathbb{R}</math>, которая может быть задана неявно;
 +
* начальная точка <math>x_{0}</math>;
 +
* правило вычисления <math>\alpha_{k}</math>;
 +
* критерий останова;
 +
* точность <math> \varepsilon</math>.
 +
 +
'''Выходные данные''':
 +
* минимальное значение функции.
  
 
=== Свойства алгоритма ===
 
=== Свойства алгоритма ===
Строка 62: Строка 104:
  
 
=== Масштабируемость алгоритма и его реализации ===
 
=== Масштабируемость алгоритма и его реализации ===
 +
 +
В качестве примера рассмотрим функцию <math>f(x) = \langle x,x \rangle</math>, где <math>x = (x_1, \ldots, x_n)</math>. Коэффициент <math>\alpha_k</math> будем вычислять по следующему правилу: <math>\alpha_k = \frac{1}{2}\alpha_{k-1}</math>.
 +
 +
Будем изменять размерность пространства от <math>2^{14}</math> до <math>2^{18}</math>, а число процессоров от <math>2</math> до <math>128</math>.
 +
 +
[[file:Gradscale.png|thumb|center|700px|Масштабируемость алгоритма]]
 +
 +
Из графика видно, что время работы программы обратно пропорционально числу процессоров, что согласуется с теоретическими результатами.
  
 
=== Динамические характеристики и эффективность реализации алгоритма ===
 
=== Динамические характеристики и эффективность реализации алгоритма ===
Строка 68: Строка 118:
  
 
=== Существующие реализации алгоритма ===
 
=== Существующие реализации алгоритма ===
 +
 +
 +
[https://github.com/dmitrime/gradient-descent/ GitHub] — реализация градиентного спуска на языке С++.
 +
 +
[https://gist.github.com/RichardWarburton/7390520/ GitHub] — реализация градиентного спуска на языке Java.
 +
 +
[https://github.com/schneems/Octave/blob/master/mlclass-ex1/gradientDescent.m/ GitHub] — реализация градиентного спуска на языке Octave.
 +
 +
[https://www.mathworks.com/matlabcentral/fileexchange/35535-simplified-gradient-descent-optimization/ MathWorks] — реализация градиентного спуска на языке MATLAB.
 +
 +
[https://www.pyimagesearch.com/2016/10/10/gradient-descent-with-python/ Gradient descent with Python] — реализация градиентного спуска на языке Python.
  
 
== Литература ==
 
== Литература ==
 
<references />
 
<references />

Текущая версия на 13:11, 30 ноября 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\nabla f(x_{k}))[/math].

Таким образом идём пока не выполнится некоторый критерий останова, определяемый конкретной задачей.

1.3 Вычислительное ядро алгоритма

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

1.4 Макроструктура алгоритма

Алгоритм представляет собой итерационный процесс, на каждом шаге которого происходит вычисление последующей точки [math]x_{k+1}[/math]. Для этого необходимо знать начальное приближение [math]x_{0}[/math], значение градиента в предыдущей точке [math]\nabla f(x_{k})[/math] и правило определения параметра [math]\alpha_{k}[/math], определяемое условием задачи. Кроме того, задачей определён и критерий останова, который проверяется на каждой итерации.

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 Последовательная сложность алгоритма

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

[math] \begin{align} f'(x_0) ≈ \frac{f(x_0 + \delta) - f(x_0))}{\delta}, \end{align} [/math]

для этого потребуется [math]n[/math] делений, где [math]n[/math] — размерность пространства. Пусть сложность вычисления коэффициента [math]\alpha_{k}[/math] равна [math]p_{\alpha}[/math], а сложность вычисления функции [math]p_{f}[/math]. Умножение [math]\alpha_{k} \nabla f(x_0)[/math] даёт ещё [math]n[/math] умножений. В итоге получаем:

[math] \begin{align} P(n, p_{\alpha}, p_{f}) = 2n + p_{\alpha} +2p_{f}, \end{align} [/math]

где [math]f = f(n)[/math].

1.7 Информационный граф

Информационный граф.

Синие вершины графа — итерационное вычисление последовательности [math]x_{k-1}, x_k, x_{k+1}[/math].

Зелёные вершины графа — численное вычисление частных производных.

1.8 Ресурс параллелизма алгоритма

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

1.9 Входные и выходные данные алгоритма

Входные данные:

  • функция [math]f(x)\colon \mathbb{R}^n \to \mathbb{R}[/math], которая может быть задана неявно;
  • начальная точка [math]x_{0}[/math];
  • правило вычисления [math]\alpha_{k}[/math];
  • критерий останова;
  • точность [math] \varepsilon[/math].

Выходные данные:

  • минимальное значение функции.

1.10 Свойства алгоритма

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

В качестве примера рассмотрим функцию [math]f(x) = \langle x,x \rangle[/math], где [math]x = (x_1, \ldots, x_n)[/math]. Коэффициент [math]\alpha_k[/math] будем вычислять по следующему правилу: [math]\alpha_k = \frac{1}{2}\alpha_{k-1}[/math].

Будем изменять размерность пространства от [math]2^{14}[/math] до [math]2^{18}[/math], а число процессоров от [math]2[/math] до [math]128[/math].

Масштабируемость алгоритма

Из графика видно, что время работы программы обратно пропорционально числу процессоров, что согласуется с теоретическими результатами.

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

GitHub — реализация градиентного спуска на языке С++.

GitHub — реализация градиентного спуска на языке Java.

GitHub — реализация градиентного спуска на языке Octave.

MathWorks — реализация градиентного спуска на языке MATLAB.

Gradient descent with Python — реализация градиентного спуска на языке Python.

3 Литература

  1. ↑ , Н. Н. Калиткин “Численные методы.” Москва «Наука», 1978
  2. ↑ A. D. Belegundu and T. R. Chandrupatla. Optimization Concepts and Applications in Engineering, chapter 3. Prentice Hall, 1999
Источник — https://algowiki-project.org/w/ru/index.php?title=Участник:Margarita/Градиентный_спуск&oldid=24619