Участница: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;
вернуть ω |
Часто случайный выбор батча заменяют на линейный проход по всем данным. Преимущество алгоритма заключается в частом обновлении градиента и возможности использовать эффективные матричные вычисления. В этой работе мы сосредоточимся на реализации градиентного спуска с мини-батчами.
Литература
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