Участник:Margarita/Градиентный спуск
автор: М.В.Зайцева
Содержание
- 1 Постановка задачи
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
1 Постановка задачи
Рассмотрим задачу поиска минимума функции [math]f(x)\colon \mathbb{R}^n \to \mathbb{R}[/math]
- [math] \begin{align} f(x) \rightarrow \min_{x \in \mathbb{R}^n} \end{align} [/math]
Будем считать, что у функции [math]f(x)[/math] существуют частные производные.
Если в задаче требуется найти максимум, вместо [math]f(x)[/math] следует брать [math]-f(x)[/math].
1.1 Общее описание алгоритма
Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.
Градиентный спуск активно применяется в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путем минимизации функции цены.
1.2 Математическое описание алгоритма
Основная идея [1] метода состоит в том, чтобы идти в направлении антиградиента [math]-\nabla f[/math] (отсюда название метода), то есть в направлении, в котором функция быстрее всего убывает при бесконечно малом движении из данной точки:
- [math] \begin{align} x_{k+1} = x_{k} - \alpha_{k}\nabla f(x_{k}), \end{align} [/math]
где [math]\alpha_{k}[/math] выбирается по одному из следующих правил:
- постоянной, в таком случае метод может не сходиться;
- дробным шагом, то есть во время итерации длина шага делится на некоторое число;
- наискорейшим спуском[2], где [math]\alpha_{k} = \operatorname{arg}\min_{\alpha} f(x_{k} - \alpha\nabla f(x_{k}))[/math].
Таким образом идём пока не выполнится некоторый критерий останова, определяемый конкретной задачей.
1.3 Вычислительное ядро алгоритма
1.4 Макроструктура алгоритма
1.5 Схема реализации последовательного алгоритма
Алгоритм:
- Выбираем начальную точку [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} \| \lt \varepsilon [/math];
- [math] \| f(x_{k+1}) - f(x_{k}) \| \lt \varepsilon [/math];
- [math] \| \nabla f(x_{k+1}) \| \lt \varepsilon [/math].