Алговики - Вклад [ru]

Участник:Margarita/Градиентный спуск

2017-11-30T10:11:17Z

Margarita: /* Масштабируемость алгоритма и его реализации */

автор: [[Участник:Margarita|М.В.Зайцева]]

== Постановка задачи ==
[[Файл:grad.png|thumb|250px|Последовательные приближения к точке экстремума (зел.) в направлении наискорейшего спуска (красн.). Синим отмечены линии уровня функции.]]

Рассмотрим задачу поиска минимума функции <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>.

=== Общее описание алгоритма ===
Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.

Градиентный спуск активно применяется в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путём минимизации функции цены.

===Математическое описание алгоритма ===
Основная идея <ref>, Н. Н. Калиткин “Численные методы.” Москва «Наука», 1978</ref> метода состоит в том, чтобы идти в направлении антиградиента <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> выбирается по одному из следующих правил:
* постоянной, в таком случае метод может не сходиться;
* дробным шагом, то есть во время итерации длина шага делится на некоторое число;
* наискорейшим спуском<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>, определяемое условием задачи. Кроме того, задачей определён и критерий останова, который проверяется на каждой итерации.

=== Схема реализации последовательного алгоритма ===
'''Алгоритм:'''
# Выбираем начальную точку <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>.

=== Последовательная сложность алгоритма ===

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

'''Выходные данные''':
* минимальное значение функции.

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

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

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

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

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

В качестве примера рассмотрим функцию <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|Масштабируемость алгоритма]]

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

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

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

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

[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 />

Участник:Margarita/Градиентный спуск

2017-11-30T09:27:25Z

Margarita: /* Масштабируемость алгоритма и его реализации */

автор: [[Участник:Margarita|М.В.Зайцева]]

== Постановка задачи ==
[[Файл:grad.png|thumb|250px|Последовательные приближения к точке экстремума (зел.) в направлении наискорейшего спуска (красн.). Синим отмечены линии уровня функции.]]

Рассмотрим задачу поиска минимума функции <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>.

=== Общее описание алгоритма ===
Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.

Градиентный спуск активно применяется в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путём минимизации функции цены.

===Математическое описание алгоритма ===
Основная идея <ref>, Н. Н. Калиткин “Численные методы.” Москва «Наука», 1978</ref> метода состоит в том, чтобы идти в направлении антиградиента <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> выбирается по одному из следующих правил:
* постоянной, в таком случае метод может не сходиться;
* дробным шагом, то есть во время итерации длина шага делится на некоторое число;
* наискорейшим спуском<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>, определяемое условием задачи. Кроме того, задачей определён и критерий останова, который проверяется на каждой итерации.

=== Схема реализации последовательного алгоритма ===
'''Алгоритм:'''
# Выбираем начальную точку <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>.

=== Последовательная сложность алгоритма ===

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

'''Выходные данные''':
* минимальное значение функции.

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

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

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

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

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

В качестве примера рассмотрим функцию <math>f(x) = \langle x,x \rangle</math>, где <math>x = (x_1, \ldots, x_n)</math>. Будем изменять размерность пространства от <math>2^{14}</math> до <math>2^{18}</math>, а число процессоров от <math>2</math> до <math>128</math>.

[[file:Gradscale.png|thumb|center|700px|Масштабируемость алгоритма]]

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

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

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

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

[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 />

Участник:Margarita/Градиентный спуск

2017-11-30T09:01:21Z

Margarita: /* Последовательная сложность алгоритма */

автор: [[Участник:Margarita|М.В.Зайцева]]

== Постановка задачи ==
[[Файл:grad.png|thumb|250px|Последовательные приближения к точке экстремума (зел.) в направлении наискорейшего спуска (красн.). Синим отмечены линии уровня функции.]]

Рассмотрим задачу поиска минимума функции <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>.

=== Общее описание алгоритма ===
Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.

Градиентный спуск активно применяется в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путём минимизации функции цены.

===Математическое описание алгоритма ===
Основная идея <ref>, Н. Н. Калиткин “Численные методы.” Москва «Наука», 1978</ref> метода состоит в том, чтобы идти в направлении антиградиента <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> выбирается по одному из следующих правил:
* постоянной, в таком случае метод может не сходиться;
* дробным шагом, то есть во время итерации длина шага делится на некоторое число;
* наискорейшим спуском<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>, определяемое условием задачи. Кроме того, задачей определён и критерий останова, который проверяется на каждой итерации.

=== Схема реализации последовательного алгоритма ===
'''Алгоритм:'''
# Выбираем начальную точку <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>.

=== Последовательная сложность алгоритма ===

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

'''Выходные данные''':
* минимальное значение функции.

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

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

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

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

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

[[file:Gradscale.png|thumb|center|700px|Масштабируемость алгоритма]]

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

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

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

[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 />

Участник:Margarita/Градиентный спуск

2017-11-30T08:45:07Z

Margarita: /* Масштабируемость алгоритма и его реализации */

автор: [[Участник:Margarita|М.В.Зайцева]]

== Постановка задачи ==
[[Файл:grad.png|thumb|250px|Последовательные приближения к точке экстремума (зел.) в направлении наискорейшего спуска (красн.). Синим отмечены линии уровня функции.]]

Рассмотрим задачу поиска минимума функции <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>.

=== Общее описание алгоритма ===
Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.

Градиентный спуск активно применяется в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путём минимизации функции цены.

===Математическое описание алгоритма ===
Основная идея <ref>, Н. Н. Калиткин “Численные методы.” Москва «Наука», 1978</ref> метода состоит в том, чтобы идти в направлении антиградиента <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> выбирается по одному из следующих правил:
* постоянной, в таком случае метод может не сходиться;
* дробным шагом, то есть во время итерации длина шага делится на некоторое число;
* наискорейшим спуском<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>, определяемое условием задачи. Кроме того, задачей определён и критерий останова, который проверяется на каждой итерации.

=== Схема реализации последовательного алгоритма ===
'''Алгоритм:'''
# Выбираем начальную точку <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>.

=== Последовательная сложность алгоритма ===

Наибольшую вычислительную сложность из арифметических операций представляют деление и умножение чисел с плавающей точкой.
На каждом шаге необходимо численно вычислять производную по формуле:
:<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>\alpha_{k} \nabla f(x_0)</math> даёт ещё <math>n</math> умножений. В итоге получаем:
:<math>
\begin{align}
P(n, p_{\alpha}) = 2n + p_{\alpha}.
\end{align}
</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>.

'''Выходные данные''':
* минимальное значение функции.

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

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

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

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

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

[[file:Gradscale.png|thumb|center|700px|Масштабируемость алгоритма]]

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

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

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

[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 />

Участник:Margarita/Градиентный спуск

2017-11-30T08:44:56Z

Margarita: /* Информационный граф */

автор: [[Участник:Margarita|М.В.Зайцева]]

== Постановка задачи ==
[[Файл:grad.png|thumb|250px|Последовательные приближения к точке экстремума (зел.) в направлении наискорейшего спуска (красн.). Синим отмечены линии уровня функции.]]

Рассмотрим задачу поиска минимума функции <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>.

=== Общее описание алгоритма ===
Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.

Градиентный спуск активно применяется в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путём минимизации функции цены.

===Математическое описание алгоритма ===
Основная идея <ref>, Н. Н. Калиткин “Численные методы.” Москва «Наука», 1978</ref> метода состоит в том, чтобы идти в направлении антиградиента <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> выбирается по одному из следующих правил:
* постоянной, в таком случае метод может не сходиться;
* дробным шагом, то есть во время итерации длина шага делится на некоторое число;
* наискорейшим спуском<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>, определяемое условием задачи. Кроме того, задачей определён и критерий останова, который проверяется на каждой итерации.

=== Схема реализации последовательного алгоритма ===
'''Алгоритм:'''
# Выбираем начальную точку <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>.

=== Последовательная сложность алгоритма ===

Наибольшую вычислительную сложность из арифметических операций представляют деление и умножение чисел с плавающей точкой.
На каждом шаге необходимо численно вычислять производную по формуле:
:<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>\alpha_{k} \nabla f(x_0)</math> даёт ещё <math>n</math> умножений. В итоге получаем:
:<math>
\begin{align}
P(n, p_{\alpha}) = 2n + p_{\alpha}.
\end{align}
</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>.

'''Выходные данные''':
* минимальное значение функции.

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

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

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

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

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

[[file:Gradscale.png|thumb|center|700px|Рисунок 2. Масштабируемость алгоритма]]

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

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

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

[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 />

Участник:Margarita/Градиентный спуск

2017-11-30T08:44:37Z

Margarita: /* Информационный граф */

автор: [[Участник:Margarita|М.В.Зайцева]]

== Постановка задачи ==
[[Файл:grad.png|thumb|250px|Последовательные приближения к точке экстремума (зел.) в направлении наискорейшего спуска (красн.). Синим отмечены линии уровня функции.]]

Рассмотрим задачу поиска минимума функции <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>.

=== Общее описание алгоритма ===
Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.

Градиентный спуск активно применяется в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путём минимизации функции цены.

===Математическое описание алгоритма ===
Основная идея <ref>, Н. Н. Калиткин “Численные методы.” Москва «Наука», 1978</ref> метода состоит в том, чтобы идти в направлении антиградиента <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> выбирается по одному из следующих правил:
* постоянной, в таком случае метод может не сходиться;
* дробным шагом, то есть во время итерации длина шага делится на некоторое число;
* наискорейшим спуском<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>, определяемое условием задачи. Кроме того, задачей определён и критерий останова, который проверяется на каждой итерации.

=== Схема реализации последовательного алгоритма ===
'''Алгоритм:'''
# Выбираем начальную точку <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>.

=== Последовательная сложность алгоритма ===

Наибольшую вычислительную сложность из арифметических операций представляют деление и умножение чисел с плавающей точкой.
На каждом шаге необходимо численно вычислять производную по формуле:
:<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>\alpha_{k} \nabla f(x_0)</math> даёт ещё <math>n</math> умножений. В итоге получаем:
:<math>
\begin{align}
P(n, p_{\alpha}) = 2n + p_{\alpha}.
\end{align}
</math>

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

[[file: InfoGr.png|thumb|center|700px|Рисунок 1. Информационный граф.]]

Синие вершины графа — итерационное вычисление последовательности <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>.

'''Выходные данные''':
* минимальное значение функции.

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

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

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

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

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

[[file:Gradscale.png|thumb|center|700px|Рисунок 2. Масштабируемость алгоритма]]

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

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

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

[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 />

Участник:Margarita/Градиентный спуск

2017-11-30T08:43:56Z

Margarita: /* Масштабируемость алгоритма и его реализации */

автор: [[Участник:Margarita|М.В.Зайцева]]

== Постановка задачи ==
[[Файл:grad.png|thumb|250px|Последовательные приближения к точке экстремума (зел.) в направлении наискорейшего спуска (красн.). Синим отмечены линии уровня функции.]]

Рассмотрим задачу поиска минимума функции <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>.

=== Общее описание алгоритма ===
Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.

Градиентный спуск активно применяется в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путём минимизации функции цены.

===Математическое описание алгоритма ===
Основная идея <ref>, Н. Н. Калиткин “Численные методы.” Москва «Наука», 1978</ref> метода состоит в том, чтобы идти в направлении антиградиента <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> выбирается по одному из следующих правил:
* постоянной, в таком случае метод может не сходиться;
* дробным шагом, то есть во время итерации длина шага делится на некоторое число;
* наискорейшим спуском<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>, определяемое условием задачи. Кроме того, задачей определён и критерий останова, который проверяется на каждой итерации.

=== Схема реализации последовательного алгоритма ===
'''Алгоритм:'''
# Выбираем начальную точку <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>.

=== Последовательная сложность алгоритма ===

Наибольшую вычислительную сложность из арифметических операций представляют деление и умножение чисел с плавающей точкой.
На каждом шаге необходимо численно вычислять производную по формуле:
:<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>\alpha_{k} \nabla f(x_0)</math> даёт ещё <math>n</math> умножений. В итоге получаем:
:<math>
\begin{align}
P(n, p_{\alpha}) = 2n + p_{\alpha}.
\end{align}
</math>

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

[[file: InfoGr.png|400px]]

Синие вершины графа — итерационное вычисление последовательности <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>.

'''Выходные данные''':
* минимальное значение функции.

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

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

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

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

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

[[file:Gradscale.png|thumb|center|700px|Рисунок 2. Масштабируемость алгоритма]]

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

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

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

[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 />

Участник:Margarita/Градиентный спуск

2017-11-29T18:55:54Z

Margarita: /* Общее описание алгоритма */

автор: [[Участник:Margarita|М.В.Зайцева]]

== Постановка задачи ==
[[Файл:grad.png|thumb|250px|Последовательные приближения к точке экстремума (зел.) в направлении наискорейшего спуска (красн.). Синим отмечены линии уровня функции.]]

Рассмотрим задачу поиска минимума функции <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>.

=== Общее описание алгоритма ===
Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.

Градиентный спуск активно применяется в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путём минимизации функции цены.

===Математическое описание алгоритма ===
Основная идея <ref>, Н. Н. Калиткин “Численные методы.” Москва «Наука», 1978</ref> метода состоит в том, чтобы идти в направлении антиградиента <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> выбирается по одному из следующих правил:
* постоянной, в таком случае метод может не сходиться;
* дробным шагом, то есть во время итерации длина шага делится на некоторое число;
* наискорейшим спуском<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>, определяемое условием задачи. Кроме того, задачей определён и критерий останова, который проверяется на каждой итерации.

=== Схема реализации последовательного алгоритма ===
'''Алгоритм:'''
# Выбираем начальную точку <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>.

=== Последовательная сложность алгоритма ===

Наибольшую вычислительную сложность из арифметических операций представляют деление и умножение чисел с плавающей точкой.
На каждом шаге необходимо численно вычислять производную по формуле:
:<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>\alpha_{k} \nabla f(x_0)</math> даёт ещё <math>n</math> умножений. В итоге получаем:
:<math>
\begin{align}
P(n, p_{\alpha}) = 2n + p_{\alpha}.
\end{align}
</math>

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

[[file: InfoGr.png|400px]]

Синие вершины графа — итерационное вычисление последовательности <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>.

'''Выходные данные''':
* минимальное значение функции.

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

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

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

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

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

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

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

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

[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 />

Участник:Margarita/Градиентный спуск

2017-11-29T18:21:07Z

Margarita: /* Последовательная сложность алгоритма */

автор: [[Участник:Margarita|М.В.Зайцева]]

== Постановка задачи ==
[[Файл:grad.png|thumb|250px|Последовательные приближения к точке экстремума (зел.) в направлении наискорейшего спуска (красн.). Синим отмечены линии уровня функции.]]

Рассмотрим задачу поиска минимума функции <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>.

=== Общее описание алгоритма ===
Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.

Градиентный спуск активно применяется в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путем минимизации функции цены.

===Математическое описание алгоритма ===
Основная идея <ref>, Н. Н. Калиткин “Численные методы.” Москва «Наука», 1978</ref> метода состоит в том, чтобы идти в направлении антиградиента <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> выбирается по одному из следующих правил:
* постоянной, в таком случае метод может не сходиться;
* дробным шагом, то есть во время итерации длина шага делится на некоторое число;
* наискорейшим спуском<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>, определяемое условием задачи. Кроме того, задачей определён и критерий останова, который проверяется на каждой итерации.

=== Схема реализации последовательного алгоритма ===
'''Алгоритм:'''
# Выбираем начальную точку <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>.

=== Последовательная сложность алгоритма ===

Наибольшую вычислительную сложность из арифметических операций представляют деление и умножение чисел с плавающей точкой.
На каждом шаге необходимо численно вычислять производную по формуле:
:<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>\alpha_{k} \nabla f(x_0)</math> даёт ещё <math>n</math> умножений. В итоге получаем:
:<math>
\begin{align}
P(n, p_{\alpha}) = 2n + p_{\alpha}.
\end{align}
</math>

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

[[file: InfoGr.png|400px]]

Синие вершины графа — итерационное вычисление последовательности <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>.

'''Выходные данные''':
* минимальное значение функции.

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

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

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

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

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

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

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

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

[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 />

Участник:Margarita/Градиентный спуск

2017-11-29T18:20:15Z

Margarita: /* Информационный граф */

автор: [[Участник:Margarita|М.В.Зайцева]]

== Постановка задачи ==
[[Файл:grad.png|thumb|250px|Последовательные приближения к точке экстремума (зел.) в направлении наискорейшего спуска (красн.). Синим отмечены линии уровня функции.]]

Рассмотрим задачу поиска минимума функции <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>.

=== Общее описание алгоритма ===
Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.

Градиентный спуск активно применяется в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путем минимизации функции цены.

===Математическое описание алгоритма ===
Основная идея <ref>, Н. Н. Калиткин “Численные методы.” Москва «Наука», 1978</ref> метода состоит в том, чтобы идти в направлении антиградиента <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> выбирается по одному из следующих правил:
* постоянной, в таком случае метод может не сходиться;
* дробным шагом, то есть во время итерации длина шага делится на некоторое число;
* наискорейшим спуском<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>, определяемое условием задачи. Кроме того, задачей определён и критерий останова, который проверяется на каждой итерации.

=== Схема реализации последовательного алгоритма ===
'''Алгоритм:'''
# Выбираем начальную точку <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>.

=== Последовательная сложность алгоритма ===

Наибольшую вычислительную сложность из арифметических операций представляют деление и умножение чисел с плавающей точкой.
На каждом шаге необходимо численно вычислять производную по формуле:
:<math>
\begin{align}
f'(x_0) ≈ \frac{f(x_0) - f(x_0 + \delta) )}{\delta},
\end{align}
</math>

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

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

[[file: InfoGr.png|400px]]

Синие вершины графа — итерационное вычисление последовательности <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>.

'''Выходные данные''':
* минимальное значение функции.

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

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

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

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

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

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

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

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

[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 />

Файл:InfoGr.png

2017-11-29T10:41:06Z

Margarita:

Участник:Margarita/Градиентный спуск

2017-11-29T10:40:31Z

Margarita: /* Информационный граф */

автор: [[Участник:Margarita|М.В.Зайцева]]

== Постановка задачи ==
[[Файл:grad.png|thumb|250px|Последовательные приближения к точке экстремума (зел.) в направлении наискорейшего спуска (красн.). Синим отмечены линии уровня функции.]]

Рассмотрим задачу поиска минимума функции <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>.

=== Общее описание алгоритма ===
Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.

Градиентный спуск активно применяется в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путем минимизации функции цены.

===Математическое описание алгоритма ===
Основная идея <ref>, Н. Н. Калиткин “Численные методы.” Москва «Наука», 1978</ref> метода состоит в том, чтобы идти в направлении антиградиента <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> выбирается по одному из следующих правил:
* постоянной, в таком случае метод может не сходиться;
* дробным шагом, то есть во время итерации длина шага делится на некоторое число;
* наискорейшим спуском<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>, определяемое условием задачи. Кроме того, задачей определён и критерий останова, который проверяется на каждой итерации.

=== Схема реализации последовательного алгоритма ===
'''Алгоритм:'''
# Выбираем начальную точку <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>.

=== Последовательная сложность алгоритма ===

Наибольшую вычислительную сложность из арифметических операций представляют деление и умножение чисел с плавающей точкой.
На каждом шаге необходимо численно вычислять производную по формуле:
:<math>
\begin{align}
f'(x_0) ≈ \frac{f(x_0) - f(x_0 + \delta) )}{\delta},
\end{align}
</math>

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

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

[[file: InfoGr.png|400px]]

Синие вершины графа — последовательные значения <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>.

'''Выходные данные''':
* минимальное значение функции.

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

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

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

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

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

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

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

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

[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 />

Участник:Margarita/Градиентный спуск

2017-11-28T12:18:06Z

Margarita: /* Постановка задачи */

автор: [[Участник:Margarita|М.В.Зайцева]]

== Постановка задачи ==
[[Файл:grad.png|thumb|250px|Последовательные приближения к точке экстремума (зел.) в направлении наискорейшего спуска (красн.). Синим отмечены линии уровня функции.]]

Рассмотрим задачу поиска минимума функции <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>.

=== Общее описание алгоритма ===
Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.

Градиентный спуск активно применяется в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путем минимизации функции цены.

===Математическое описание алгоритма ===
Основная идея <ref>, Н. Н. Калиткин “Численные методы.” Москва «Наука», 1978</ref> метода состоит в том, чтобы идти в направлении антиградиента <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> выбирается по одному из следующих правил:
* постоянной, в таком случае метод может не сходиться;
* дробным шагом, то есть во время итерации длина шага делится на некоторое число;
* наискорейшим спуском<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>, определяемое условием задачи. Кроме того, задачей определён и критерий останова, который проверяется на каждой итерации.

=== Схема реализации последовательного алгоритма ===
'''Алгоритм:'''
# Выбираем начальную точку <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>.

=== Последовательная сложность алгоритма ===

Наибольшую вычислительную сложность из арифметических операций представляют деление и умножение чисел с плавающей точкой.
На каждом шаге необходимо численно вычислять производную по формуле:
:<math>
\begin{align}
f'(x_0) ≈ \frac{f(x_0) - f(x_0 + \delta) )}{\delta},
\end{align}
</math>

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

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

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

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

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

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

'''Выходные данные''':
* минимальное значение функции.

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

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

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

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

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

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

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

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

[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 />

Участник:Margarita/Градиентный спуск

2017-11-28T10:10:44Z

Margarita: /* Существующие реализации алгоритма */

автор: [[Участник:Margarita|М.В.Зайцева]]

== Постановка задачи ==
[[Файл:grad.png|thumb|250px|Последовательные приближения к точке экстремума (зел.) в направлении наискорейшего спуска (красн.). Синим отмечены линии уровня функции.]]

Рассмотрим задачу поиска минимума функции <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>.

=== Общее описание алгоритма ===
Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.

Градиентный спуск активно применяется в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путем минимизации функции цены.

===Математическое описание алгоритма ===
Основная идея <ref>, Н. Н. Калиткин “Численные методы.” Москва «Наука», 1978</ref> метода состоит в том, чтобы идти в направлении антиградиента <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> выбирается по одному из следующих правил:
* постоянной, в таком случае метод может не сходиться;
* дробным шагом, то есть во время итерации длина шага делится на некоторое число;
* наискорейшим спуском<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>, определяемое условием задачи. Кроме того, задачей определён и критерий останова, который проверяется на каждой итерации.

=== Схема реализации последовательного алгоритма ===
'''Алгоритм:'''
# Выбираем начальную точку <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>.

=== Последовательная сложность алгоритма ===

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

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

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

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

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

'''Выходные данные''':
* минимальное значение функции.

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

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

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

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

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

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

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

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

[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 />

Участник:Margarita/Градиентный спуск

2017-11-28T09:27:35Z

Margarita: /* Постановка задачи */

автор: [[Участник:Margarita|М.В.Зайцева]]

== Постановка задачи ==
[[Файл:grad.png|thumb|250px|Последовательные приближения к точке экстремума (зел.) в направлении наискорейшего спуска (красн.). Синим отмечены линии уровня функции.]]

Рассмотрим задачу поиска минимума функции <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>.

=== Общее описание алгоритма ===
Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.

Градиентный спуск активно применяется в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путем минимизации функции цены.

===Математическое описание алгоритма ===
Основная идея <ref>, Н. Н. Калиткин “Численные методы.” Москва «Наука», 1978</ref> метода состоит в том, чтобы идти в направлении антиградиента <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> выбирается по одному из следующих правил:
* постоянной, в таком случае метод может не сходиться;
* дробным шагом, то есть во время итерации длина шага делится на некоторое число;
* наискорейшим спуском<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>, определяемое условием задачи. Кроме того, задачей определён и критерий останова, который проверяется на каждой итерации.

=== Схема реализации последовательного алгоритма ===
'''Алгоритм:'''
# Выбираем начальную точку <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>.

=== Последовательная сложность алгоритма ===

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

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

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

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

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

'''Выходные данные''':
* минимальное значение функции.

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

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

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

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

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

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

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

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

== Литература ==
<references />

Участник:Margarita/Градиентный спуск

2017-11-27T21:13:46Z

Margarita: /* Макроструктура алгоритма */

Участник:Margarita/Градиентный спуск

2017-11-27T21:13:18Z

Margarita: /* Макроструктура алгоритма */

Участник:Margarita/Градиентный спуск

2017-11-27T21:13:00Z

Margarita: /* Макроструктура алгоритма */

Участник:Margarita/Градиентный спуск

2017-11-27T21:10:20Z

Margarita: /* Постановка задачи */

Участник:Margarita/Градиентный спуск

2017-11-27T20:16:58Z

Margarita: /* Ресурс параллелизма алгоритма */

Участник:Margarita/Градиентный спуск

2017-11-27T20:09:53Z

Margarita: /* Макроструктура алгоритма */

Участник:Margarita/Градиентный спуск

2017-11-27T19:45:55Z

Margarita: /* Вычислительное ядро алгоритма */

Участник:Margarita/Градиентный спуск

2017-11-27T19:45:18Z

Margarita: /* Вычислительное ядро алгоритма */

Участник:Margarita/Градиентный спуск

2017-11-26T20:15:11Z

Margarita: /* Постановка задачи */

Участник:Margarita/Градиентный спуск

2017-11-26T20:03:12Z

Margarita: /* Постановка задачи */

автор: [[Участник:Margarita|М.В.Зайцева]]

== Постановка задачи ==
[[Файл:grad.png|thumb|250px|Последовательные приближения к точке экстремума в направлении наискорейшего спуска (красн.). Синим отмечены линии уровня функции.]]

Рассмотрим задачу поиска минимума функции <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>.

=== Общее описание алгоритма ===
Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.

Градиентный спуск активно применяется в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путем минимизации функции цены.

===Математическое описание алгоритма ===
Основная идея <ref>, Н. Н. Калиткин “Численные методы.” Москва «Наука», 1978</ref> метода состоит в том, чтобы идти в направлении антиградиента <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> выбирается по одному из следующих правил:
* постоянной, в таком случае метод может не сходиться;
* дробным шагом, то есть во время итерации длина шага делится на некоторое число;
* наискорейшим спуском<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_{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>.

=== Последовательная сложность алгоритма ===

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

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

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

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

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

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

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

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

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

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

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

== Литература ==
<references />

Файл:Grad.png

2017-11-26T20:01:21Z

Margarita:

Участник:Margarita/Градиентный спуск

2017-11-04T19:25:53Z

Margarita: /* Математическое описание алгоритма */

автор: [[Участник:Margarita|М.В.Зайцева]]

== Постановка задачи ==
Рассмотрим задачу поиска минимума функции <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>.

=== Общее описание алгоритма ===
Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.

Градиентный спуск активно применяется в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путем минимизации функции цены.

===Математическое описание алгоритма ===
Основная идея <ref>, Н. Н. Калиткин “Численные методы.” Москва «Наука», 1978</ref> метода состоит в том, чтобы идти в направлении антиградиента <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> выбирается по одному из следующих правил:
* постоянной, в таком случае метод может не сходиться;
* дробным шагом, то есть во время итерации длина шага делится на некоторое число;
* наискорейшим спуском<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_{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>.

=== Последовательная сложность алгоритма ===

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

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

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

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

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

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

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

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

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

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

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

== Литература ==
<references />

Участник:Margarita/Градиентный спуск

2017-11-04T18:10:25Z

Margarita: /* Схема реализации последовательного алгоритма */

автор: [[Участник:Margarita|М.В.Зайцева]]

== Постановка задачи ==
Рассмотрим задачу поиска минимума функции <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>.

=== Общее описание алгоритма ===
Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.

Градиентный спуск активно применяется в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путем минимизации функции цены.

===Математическое описание алгоритма ===
Основная идея <ref>, Н. Н. Калиткин “Численные методы.” Москва «Наука», 1978</ref> метода состоит в том, чтобы идти в направлении антиградиента <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> выбирается по одному из следующих правил:
* постоянной, в таком случае метод может не сходиться;
* дробным шагом, то есть во время итерации длина шага делится на некоторое число;
* наискорейшим спуском<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_{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>.

=== Последовательная сложность алгоритма ===

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

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

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

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

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

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

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

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

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

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

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

== Литература ==
<references />

Участник:Margarita/Градиентный спуск

2017-11-04T18:00:49Z

Margarita:

автор: [[Участник:Margarita|М.В.Зайцева]]

== Постановка задачи ==
Рассмотрим задачу поиска минимума функции <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>.

=== Общее описание алгоритма ===
Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.

Градиентный спуск активно применяется в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путем минимизации функции цены.

===Математическое описание алгоритма ===
Основная идея <ref>, Н. Н. Калиткин “Численные методы.” Москва «Наука», 1978</ref> метода состоит в том, чтобы идти в направлении антиградиента <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> выбирается по одному из следующих правил:
* постоянной, в таком случае метод может не сходиться;
* дробным шагом, то есть во время итерации длина шага делится на некоторое число;
* наискорейшим спуском<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_{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>;

=== Последовательная сложность алгоритма ===

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

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

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

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

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

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

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

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

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

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

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

== Литература ==
<references />

Участник:Margarita/Градиентный спуск

2017-11-04T18:00:21Z

Margarita:

автор: [[Участник:Margarita|М.В. Зайцева]]

== Постановка задачи ==
Рассмотрим задачу поиска минимума функции <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>.

=== Общее описание алгоритма ===
Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.

Градиентный спуск активно применяется в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путем минимизации функции цены.

===Математическое описание алгоритма ===
Основная идея <ref>, Н. Н. Калиткин “Численные методы.” Москва «Наука», 1978</ref> метода состоит в том, чтобы идти в направлении антиградиента <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> выбирается по одному из следующих правил:
* постоянной, в таком случае метод может не сходиться;
* дробным шагом, то есть во время итерации длина шага делится на некоторое число;
* наискорейшим спуском<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_{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>;

=== Последовательная сложность алгоритма ===

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

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

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

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

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

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

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

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

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

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

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

== Литература ==
<references />

Участник:Margarita

2017-11-04T17:52:35Z

Margarita: Новая страница: «Зайцева Маргарита Владимировна, ВМК МГУ, 415 группа 2017/2018. Статьи:<br> Участник:Margarita/Гради…»

Зайцева Маргарита Владимировна, ВМК МГУ, 415 группа 2017/2018.

Статьи:<br>
[[Участник:Margarita/Градиентный спуск|Градиентный спуск]].

Участник:Margarita/Градиентный спуск

2017-11-04T17:49:25Z

Margarita:

автор: [[Участник:Margarita|М.В.Зайцева]]

== Постановка задачи ==
Рассмотрим задачу поиска минимума функции <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>.

=== Общее описание алгоритма ===
Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.

Градиентный спуск активно применяется в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путем минимизации функции цены.

===Математическое описание алгоритма ===
Основная идея <ref>, Н. Н. Калиткин “Численные методы.” Москва «Наука», 1978</ref> метода состоит в том, чтобы идти в направлении антиградиента <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> выбирается по одному из следующих правил:
* постоянной, в таком случае метод может не сходиться;
* дробным шагом, то есть во время итерации длина шага делится на некоторое число;
* наискорейшим спуском<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_{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>;

=== Последовательная сложность алгоритма ===

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

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

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

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

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

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

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

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

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

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

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

== Литература ==
<references />

Участник:Margarita/Градиентный спуск

2017-10-23T16:36:19Z

Margarita: /* Математическое описание алгоритма */

== Постановка задачи ==
Рассмотрим задачу поиска минимума функции <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>.

=== Общее описание алгоритма ===
Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.

Градиентный спуск активно применяется в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путем минимизации функции цены.

===Математическое описание алгоритма ===
Основная идея <ref>, Н. Н. Калиткин “Численные методы.” Москва «Наука», 1978</ref> метода состоит в том, чтобы идти в направлении антиградиента <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> выбирается по одному из следующих правил:
* постоянной, в таком случае метод может не сходиться;
* дробным шагом, то есть во время итерации длина шага делится на некоторое число;
* наискорейшим спуском<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_{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>;

=== Последовательная сложность алгоритма ===

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

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

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

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

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

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

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

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

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

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

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

== Литература ==
<references />

Участник:Margarita/Градиентный спуск

2017-10-23T15:38:02Z

Margarita:

== Постановка задачи ==
Рассмотрим задачу поиска минимума функции <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>.

=== Общее описание алгоритма ===
Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.

Градиентный спуск активно применяется в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путем минимизации функции цены.

===Математическое описание алгоритма ===
Основная идея <ref>, Н. Н. Калиткин “Численные методы.” Москва «Наука», 1978</ref> метода состоит в том, чтобы идти в направлении антиградиента <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> выбирается по одному из следующих правил:
* постоянной, в таком случае метод может не сходиться;
* дробным шагом, то есть во время итерации длина шага делится на некоторое число;
* наискорейшим спуском<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>.

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

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

=== Схема реализации последовательного алгоритма ===
'''Алгоритм:'''
# Выбираем начальную точку <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>;

=== Последовательная сложность алгоритма ===

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

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

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

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

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

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

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

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

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

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

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

== Литература ==
<references />

Участник:Margarita/Градиентный спуск

2017-10-23T15:31:58Z

Margarita: /* Общее описание алгоритма */

== Постановка задачи ==
Рассмотрим задачу поиска минимума функции <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>.

=== Общее описание алгоритма ===
Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.

Градиентный спуск активно применяется в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путем минимизации функции цены.

===Математическое описание алгоритма ===
Основная идея <ref>, Н. Н. Калиткин “Численные методы.” Москва «Наука», 1978</ref> метода состоит в том, чтобы идти в направлении <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>по следующему правилу:
* постоянной, в таком случае метод может не сходиться;
* дробным шагом, то есть во время итерации длина шага делится на некоторое число;
* наискорейшим спуском<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>.

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

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

=== Схема реализации последовательного алгоритма ===
'''Алгоритм:'''
# Выбираем начальную точку <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>;

=== Последовательная сложность алгоритма ===

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

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

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

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

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

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

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

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

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

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

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

== Литература ==
<references />

Участник:Margarita/Градиентный спуск

2017-10-22T21:14:58Z

Margarita:

== Постановка задачи ==
Рассмотрим задачу поиска минимума функции <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>.

=== Общее описание алгоритма ===
Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.

Градиентный спуск является популярным методом в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путем минимизации функции цены.

===Математическое описание алгоритма ===
Основная идея <ref>, Н. Н. Калиткин “Численные методы.” Москва «Наука», 1978</ref> метода состоит в том, чтобы идти в направлении <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>по следующему правилу:
* постоянной, в таком случае метод может не сходиться;
* дробным шагом, то есть во время итерации длина шага делится на некоторое число;
* наискорейшим спуском<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>.

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

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

=== Схема реализации последовательного алгоритма ===
'''Алгоритм:'''
# Выбираем начальную точку <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>;

=== Последовательная сложность алгоритма ===

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

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

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

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

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

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

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

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

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

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

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

== Литература ==
<references />

Наискорейший спуск

2017-10-22T16:08:37Z

Margarita: Полностью удалено содержимое страницы

Участник:Margarita/Градиентный спуск

2017-10-22T16:07:57Z

Margarita: Новая страница: «== Постановка задачи == Рассмотрим задачу поиска минимума функции <math>f(x)\colon \mathbb{R}^n \to \mathbb{R…»

Наискорейший спуск

2017-10-22T15:57:41Z

Margarita: Новая страница: « == Постановка задачи == Рассмотрим задачу поиска минимума функции <math>f(x)\colon \mathbb{R}^n \to \mathbb{…»