Участница: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{ E }[/math] итераций обработки всей выборки (будем называть одну итерацию эпохой).

В начале каждой эпохи будем случайно перемешивать выборку, а затем последовательно выбирать порции данных по [math]\displaystyle{ n }[/math] объектов. Это обеспечит локальность расположения в памяти последовательно идущих мини-батчей и сохранит логику случайного выбора мини-батчей. Таким образом, процедура случайного выбора мини-батча заменяется на линейный проход по всем данным.

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

Основное время работы алгоритма приходится на вычисление градиента, которые повторяются, пока сходимость не будет достигнута.

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

[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{ O(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