Участница:OvsyannikovaSA/Стохастический градиентный спуск
Свойства и структура алгоритмов
Общее описание алгоритма
Стохастический градиентный спуск (Stochastic Gradient Descent, SGD) представляет собой один из базовых и наиболее распространённых алгоритмов оптимизации, применяемых для обучения моделей машинного обучения и нейронных сетей. Он относится к классу итерационных методов минимизации функций.
Математическое описание алгоритма
Пусть даны [math]\displaystyle{ \{x_i, y_i\}_{i=1}^N, x_i \in \mathbb{R}^m }[/math] - вектор признаков [math]\displaystyle{ i }[/math]-го объекта, [math]\displaystyle{ y_i \in \mathbb{R} }[/math] - значение целевой переменной; класс моделей [math]\displaystyle{ a_\omega: \mathbb{R}^m \rightarrow \mathbb{R} }[/math]; функция потерь [math]\displaystyle{ f: \mathbb{R}\times \mathbb{R} \rightarrow \mathbb{R} }[/math]. Задача: найти вектор параметров модели (весов) [math]\displaystyle{ \omega \in \mathbb{R}^d }[/math], т.ч. [math]\displaystyle{ \omega = argmin_{\omega\in \mathbb{R}^d}\;L(\omega),\;L(\omega)=\sum_{i=1}^N f(a_{\omega}(x_i), y_i) }[/math].
Алгоритм классического градиентного спуска (batch gradient descent) можно сформулировать следующим образом:
вход: функция потерь L(ω), шаг обучения α
выбрать начальное приближение ω0
пока не достигнута сходимость:
вычислить градиент g <- grad L(ω);
обновить веса ω <- ω - αg;
вернуть ω |
Здесь и далее шаг обучения (learning rate) [math]\displaystyle{ \alpha }[/math] является гиперпараметром, т.е. параметром, который не оптимизируется в ходе работы алгоритма и который необходимо выбрать заранее. Начальное приближение [math]\displaystyle{ \omega_0 }[/math] также необходимо выбрать заранее исходя из некоторых соображений. Условие достижения сходимости на практике обычно заменяется повторением процедуры некоторое количество раз, после чего можно считать, что алгоритм сошелся в требуемом приближении. В данном подходе для того, чтобы совершить одно обновление весов, необходимо вычислить функцию потерь для всех элементов выборки. Этот метод может оказаться неподходящим в некоторых случаях, например, при использовании больших датасетов, не помещающихся в памяти, или в случае, когда новые данные поступают в реальном времени.
Модернизацией этого алгоритма является стохастический градиентный спуск (stochastic gradient descent):
вход: функция потерь L(ω), шаг обучения α
выбрать начальное приближение ω0
пока не достигнута сходимость:
случайно выбрать (xi, yi)
вычислить градиент g <- grad f(ω; xi, yi);
обновить веса ω <- ω - αg;
вернуть ω |
Алгоритм отличается от предыдущего тем, что обновление весов происходит после обработки одного объекта выборки. Компромиссом между двумя этими подходами служит стохастический градиентный спуск на мини-батчах (mini-batch gradient descent). Для него требуется выбрать размер батча (batch_size). Обозначим [math]\displaystyle{ L(\omega)=\sum_{i=1}^{batch\_size} f(a_{\omega}(x_i), y_i) }[/math]
вход: функция потерь L(ω), шаг обучения α, размер батча batch_size
выбрать начальное приближение ω0
пока не достигнута сходимость:
случайно выбрать (xik, yik), 1<=k<=batch_size
вычислить градиент g <- grad L(ω; (xik, yik), 1<=k<=batch_size);
обновить веса ω <- ω - αg;
вернуть ω |
Часто случайный выбор батча заменяют на линейный проход по всем данным. Преимущество алгоритма заключается в частом обновлении градиента и возможности использовать эффективные матричные вычисления. В этой работе мы сосредоточимся на реализации градиентного спуска с мини-батчами.
Вычислительное ядро алгоритма
Основное время работы алгоритма приходится на выбор мини-батча и вычисление градиента, которые повторяются, пока сходимость не будет достигнута.
Макроструктура алгоритма
Схема реализации последовательного алгоритма
Последовательная сложность алгоритма
[math]\displaystyle{ N }[/math] - размер выборки,
[math]\displaystyle{ n }[/math] - размер батча ([math]\displaystyle{ batch\_size }[/math]),
[math]\displaystyle{ C }[/math] - сложность вычисления производной функции потерь на одном примере.
Будем считать, что сходимость достигается за [math]\displaystyle{ E }[/math] итераций обработки всей выборки (будем называть одну итерацию эпохой). В начале каждой эпохи будем случайно перемешивать выборку, а затем последовательно выбирать порции данных по [math]\displaystyle{ n }[/math] объектов. Это обеспечит локальность расположения в памяти последовательно идущих мини-батчей и сохранит логику случайного выбора мини-батчей. Сложность случайного перемешивания выборки объема [math]\displaystyle{ N }[/math] алгоритмом Фишера-Йетса - [math]\displaystyle{ O(N) }[/math].
Сложность обработки одного батча - [math]\displaystyle{ O(n \cdot C) }[/math].
Будем считать, что количество батчей [math]\displaystyle{ N/n }[/math] - целое число; тогда сложность вычисления градиентов в течение одной эпохи - [math]\displaystyle{ O(N/n \cdot n \cdot C) = O(N\cdot C) }[/math].
Сложность одной эпохи с учетом перемешивания выборки - [math]\displaystyle{ O(N)+O(N\cdot C)=O(N\cdot C) }[/math].
Сложность всего алгоритма с [math]\displaystyle{ E }[/math] эпохами - [math]\displaystyle{ O(E\cdot N\cdot C) }[/math]
Литература
Yujing Ma, Florin Rusu, Martin Torres. Stochastic Gradient Descent on Highly-Parallel Architectures [Электронный ресурс] // arXiv:1802.08800 [math.ST]. – 2018. – Режим доступа: https://arxiv.org/abs/1802.08800
Sebastian Ruder. An overview of gradient descent optimization algorithms [Электронный ресурс] // arXiv:1609.04747 [math.ST]. – 2016. – Режим доступа: https://arxiv.org/abs/1609.04747