Участница: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] объектов. Это обеспечит локальность расположения в памяти последовательно идущих мини-батчей и сохранит логику случайного выбора мини-батчей. Таким образом, процедура случайного выбора мини-батча заменяется на линейный проход по всем данным.
Вычислительное ядро алгоритма
Основное время работы алгоритма приходится на вычисление градиента, которые повторяются, пока сходимость не будет достигнута.
Макроструктура алгоритма
Алгоритм стохастического градиентного спуска с мини-батчами представляется повторением следующих макроопераций:
1. Инициализация параметров: задание начального приближения вектора параметров модели [math]\displaystyle{ w_0 }[/math]. Может быть случайной инициализацией, загрузкой предварительно обученной модели и т.п.
w ← ИнициализацияПараметров(описание_модели, стратегия_инициализации)
2. Перемешивание обучающей выборки: получение случайной перестановки обучающей выборки в начале эпохи. Можно выполнять, например, алгоритмом Фишера-Йетса.
Входные данные: [math]\displaystyle{ D=\{(x_i, y_i)\}_{i=1}^N }[/math] - обучающая выборка.
Выходные данные: [math]\displaystyle{ D_{perm} }[/math] - перемешанная выборка.
D_perm ← ПеремешиваниеОбучающейВыборки(D, генератор_случайных_чисел)
3. Формирование мини-батчей: разбиение переставленной выборки на последовательность мини-батчей.
Входные данные: [math]\displaystyle{ D_{perm} }[/math]
Выходные данные: последовательность подмножеств [math]\displaystyle{ B_k\subset D, \; k=1,..., K, \; \cup_k B_k=D, B_k \cap B_j = \emptyset, k\neq j }[/math].
СписокБатчей ← ФормированиеМиниБатчей((X,y)_perm, размер_батча)
4. Вычисление градиента на батче. Может включать вычисление значений модели на батче, матрично-векторные умножения, суммирование по объектам батча.
Входные данные: текущие параметры [math]\displaystyle{ w }[/math], мини-батч [math]\displaystyle{ B=\{(x_i, y_i)\}_{i\in I_B} }[/math]
Выходные данные: [math]\displaystyle{ g_B }[/math] - градиент по параметрам на этом батче.
g_B ← ВычислениеГрадиентаНаБатче(w, B)
5. Обновление параметров: осуществление одного шага метода по вычисленному градиенту на батче.
Входные данные: текущие параметры [math]\displaystyle{ w }[/math], градиент на батче [math]\displaystyle{ g_B }[/math].
Выходные данные: новые параметры [math]\displaystyle{ w_{new}=w-\alpha g_B }[/math].
w ← ОбновлениеПараметров(w, g_B, гиперпараметры_шага)
6. Проверка критерия останова: проверка условий завершения итерационного процесса. Может быть проверкой номера эпохи, проверкой изменения функции потерь и т.п.
флаг_стоп ← ПроверкаКритерияОстановки(номер_эпохи, номер_шага, значение_критерия, история)
На макроуровне алгоритм можно описать так:
w ← ИнициализацияПараметров(описание_модели, стратегия_инициализации)
номер_эпохи ← 0
повторять
номер_эпохи ← номер_эпохи + 1
D_perm ← ПеремешиваниеОбучающейВыборки(D, генератор_случайных_чисел)
СписокБатчей ← ФормированиеМиниБатчей(D_perm, размер_батча)
Для каждого B из СписокБатчей:
g_B ← ВычислениеГрадиентаНаБатче(w, B)
w ← ОбновлениеПараметров(w, g_B, гиперпараметры_шага)
флаг_стоп ← ПроверкаКритерияОстановки(номер_эпохи, значение_критерия, история)
Пока флаг_стоп = ЛОЖЬ |
Схема реализации последовательного алгоритма
Последовательная сложность алгоритма
[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].
Информационный граф
На схеме изображен информационный граф стохастического градиентного спуска с мини-батчами.
Здесь приводится схема выполнения одной эпохи. Стрелки, изображающие обработку остальных объектов данного батча, опущены для улучшения читаемости схемы. После обработки одного батча с весами [math]\displaystyle{ w_i }[/math] производится шаг градиентного спуска, и следующий батч обрабатывается уже с весами [math]\displaystyle{ w_{i+1} }[/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