Участник: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 Макроструктура алгоритма

На каждом шаге происходит вычисление точки, пока не выполнится критерий останова.

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].