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

автор: М.В.Зайцева

1 Постановка задачи

Последовательные приближения к точке экстремума (зел.) в направлении наискорейшего спуска (красн.). Синим отмечены линии уровня функции.

Рассмотрим задачу поиска минимума функции [math]f(x)\colon \mathbb{R}^n \to \mathbb{R}[/math]

[math] \begin{align} f(x) \rightarrow \min_{x \in \mathbb{R}^n} \end{align} [/math]

Будем считать, что у функции [math]f(x)[/math] существуют частные производные.

Если в задаче требуется найти максимум, вместо [math]f(x)[/math] следует брать [math]-f(x)[/math].

1.1 Общее описание алгоритма

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

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

1.2 Математическое описание алгоритма

Основная идея метода состоит в том, чтобы идти в направлении антиградиента [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] выбирается по одному из следующих правил:

• постоянной, в таком случае метод может не сходиться;
• дробным шагом, то есть во время итерации длина шага делится на некоторое число;
• наискорейшим спуском, где [math]\alpha_{k} = \operatorname{arg}\min_{\alpha} f(x_{k} - \alpha\nabla f(x_{k}))[/math].

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

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

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

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

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

1.5 Схема реализации последовательного алгоритма

Алгоритм:

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

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

• [math] \| x_{k+1} - x_{k} \| \lt \varepsilon [/math];
• [math] \| f(x_{k+1}) - f(x_{k}) \| \lt \varepsilon [/math];
• [math] \| \nabla f(x_{k+1}) \| \lt \varepsilon [/math].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рисунок 2. Масштабируемость алгоритма

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

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

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

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

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

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