Участница: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].
Ресурс параллелизма алгоритма
Ресурс параллелизма алгоритма стохастического градиентного спуска (SGD) определяется зависимостями данных между его основными шагами: вычислением градиента и обновлением весов.
Иерархическая Структура Параллелизма
Параллелизм в SGD имеет двухуровневую (иерархическую) структуру, которая напрямую связана с циклическим профилем последовательной реализации.
1. Внешний уровень: конечный параллелизм
Внешний уровень параллелизма определяется последовательностью итераций по эпохам и по батчам:
- цикл по эпохам: итерации по эпохам зависимы, поскольку веса, полученные на одной эпохе, используются на следующей. Этот цикл не имеет параллельного ресурса.
- цикл по батчам (мини-батчам): обновления весов на основе последовательных мини-батчей информационно зависимы. Обновление [math]\displaystyle{ w_{k+1} }[/math] зависит от [math]\displaystyle{ w_k }[/math] и градиента [math]\displaystyle{ g_k }[/math]. Это создает ресурс конечного параллелизма, то есть высокая параллельность внутри каждого шага, но последовательность между шагами.
2. Внутренний уровень: массовый параллелизм
Внутренний уровень связан с обработкой данных внутри одного шага SGD (одного мини-батча).
Это ресурс массового параллелизма, который может быть реализован двумя способами:
- Вычисление градиента: вычисление частных градиентов для каждого примера ([math]\displaystyle{ x_i }[/math]) в мини-батче полностью независимо: [math]\displaystyle{ \frac{1}{|B|} \sum_{x_i \in B} \nabla Q_i(W) }[/math].
Этот этап демонстрирует координатный параллелизм (независимость итераций цикла по примерам в батче).
- Обновление весов: операция [math]\displaystyle{ w_{k+1} = w_k - \eta g_k }[/math] представляет собой векторные операции (вычитание и скалярное умножение), которые также могут быть распараллелены по координатам вектора весов ($w$).
Параллельная Сложность и Высота Ярусно-Параллельной Формы
Оценка параллельной сложности алгоритма (высота канонической ярусно-параллельной формы) дается в терминах числа операций умножения/деления и сложения (которые доминируют).
Пусть [math]\displaystyle{ m }[/math] — размерность вектора весов (число признаков), [math]\displaystyle{ B }[/math] — размер мини-батча.
Основной вычислительный шаг SGD состоит из трех этапов:
| Этап | Параллельная сложность (Высота ЯПФ, H) |
Ширина ЯПФ (W - Сбалансированность) |
Описание Ресурса Параллелизма |
|---|---|---|---|
| Вычисление градиентов | [math]\displaystyle{ O(\log_2 B + 1) }[/math] | [math]\displaystyle{ O(m \times B) }[/math] | Массовый параллелизм (Координатный параллелизм) по примерам в мини-батче. Требуется редукция/суммирование. |
| Усреднение и масштабирование | [math]\displaystyle{ O(1) }[/math] | [math]\displaystyle{ O(m) }[/math] | Конечный параллелизм (Координатный параллелизм) по координатам вектора весов. |
| Обновление весов | [math]\displaystyle{ O(1) }[/math] | [math]\displaystyle{ O(m) }[/math] | Конечный параллелизм (Координатный параллелизм) по координатам вектора весов. |
Таким образом, параллельная сложность (высота) одного шага SGD составляет [math]\displaystyle{ H = O(\log_2 B) }[/math].
Сбалансированность параллельных шагов (ширина ярусов)
Ширина ярусов отражает сбалансированность параллельных шагов по числу операций:
- Ширина этапа градиентов: на этапе вычисления градиентов ширина ярусов максимальна, достигая [math]\displaystyle{ W = O(m \times B) }[/math]. Этот этап сбалансирован при [math]\displaystyle{ P }[/math] процессорах, где [math]\displaystyle{ P \le B }[/math], поскольку каждому процессу можно поручить обработку [math]\displaystyle{ \lceil B/P \rceil }[/math] примеров.
- Ширина этапов обновления: на этапах усреднения и обновления весов ширина ярусов составляет [math]\displaystyle{ W = O(m) }[/math]. Этот этап также сбалансирован, если [math]\displaystyle{ P \le m }[/math], поскольку операции могут быть распределены по [math]\displaystyle{ P }[/math] процессорам.
Алгоритм SGD обладает хорошей сбалансированностью на каждом шаге, что позволяет эффективно использовать большое число процессоров (ядер), особенно когда произведение [math]\displaystyle{ m \times B }[/math] велико.
Входные и выходные данные алгоритма
Входные данные
Обучающая выборка ([math]\displaystyle{ D }[/math]) обычно представляется в виде двух плотных структур данных:
1. Матрица Признаков ([math]\displaystyle{ X\in\mathbb{R}^{N \times m} }[/math]), [math]\displaystyle{ N }[/math] — общее число обучающих примеров, а [math]\displaystyle{ m }[/math] — число признаков (размерность векторов весов).
В задачах машинного обучения [math]\displaystyle{ N }[/math] часто значительно больше, чем [math]\displaystyle{ m }[/math] (много примеров, но относительно небольшое число признаков), или же [math]\displaystyle{ m }[/math] может быть очень большим (например, при использовании One-Hot-Encoding).
В зависимости от задачи, матрица [math]\displaystyle{ X }[/math] может быть:
- плотной (dense): каждая ячейка содержит значащее числовое значение.
- разреженной (sparse): если большая часть элементов равна нулю.
2. Вектор целевых значений ([math]\displaystyle{ y }[/math]) - вектор размера [math]\displaystyle{ N \times 1 }[/math] или [math]\displaystyle{ N \times C }[/math] (для многоклассовой классификации, где [math]\displaystyle{ C }[/math] — число классов).
Обычно плотный, содержит действительные числа (для регрессии) или целочисленные метки/векторы (для классификации).
3. Параметры обучения
- Скорость обучения ([math]\displaystyle{ \alpha\in\mathbb{R} }[/math], learning rate): его значение обычно мало (например, [math]\displaystyle{ 10^{-2} }[/math] или [math]\displaystyle{ 10^{-3} }[/math]) и оказывает критическое влияние на сходимость.
- Размер мини-батча ([math]\displaystyle{ B\in\mathbb{R} }[/math], batch size): определяет число примеров, используемых для одного шага. Обычно является степенью двойки ([math]\displaystyle{ 32, 64, 128, \dots }[/math]).
- Число эпох ([math]\displaystyle{ E\in\mathbb{N} }[/math], epochs): число полных проходов по всему набору данных.
Выходные Данные
- Вектор весов модели ([math]\displaystyle{ w }[/math]): вектор размера [math]\displaystyle{ m \times 1 }[/math] (или матрица [math]\displaystyle{ m \times C }[/math], если модель содержит скрытые слои или многоклассовый вывод).
Является плотной структурой данных. Диапазон значений зависит от функции потерь и регуляризации, но обычно это числа, близкие к нулю, или числа малого/среднего диапазона.
- История потерь (loss history, опционально): вектор, содержащий значение функции потерь, вычисленное после каждого шага SGD. Объем равен [math]\displaystyle{ (E \times N) / B }[/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