Участница: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{ B }[/math]). Обозначим [math]\displaystyle{ L(\omega)=\sum_{i=1}^{B} f(a_{\omega}(x_i), y_i) }[/math]

Стохастический градиентный спуск с мини-батчами

вход: функция потерь L(ω), шаг обучения α, размер батча B выбрать начальное приближение ω0 пока не достигнута сходимость: случайно выбрать (xik, yik), 1<=k<=B вычислить градиент g <- grad L(ω; (xik, yik), 1<=k<=B); обновить веса ω <- ω - αg; вернуть ω

Преимущество алгоритма заключается в частом обновлении градиента и возможности использовать эффективные матричные вычисления. В этой работе мы сосредоточимся на реализации градиентного спуска с мини-батчами.

Необходимо некоторым способом определить условия, при которых будет считаться, что алгоритм сошелся. Будем считать, что сходимость достигается за [math]\displaystyle{ E }[/math] итераций обработки всей выборки (будем называть одну итерацию эпохой).

В начале каждой эпохи будем случайно перемешивать выборку, а затем последовательно выбирать порции данных по [math]\displaystyle{ B }[/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{ B }[/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{ B }[/math] случайных элементов - [math]\displaystyle{ O(B) }[/math]. Такая оценка будет верна, если в системе реализован произвольный доступ к памяти. Однако для больших выборок, не помещающихся целиком в памяти, произвольный доступ к элементам выборки не будет возможен.

Сложность обработки одного батча - [math]\displaystyle{ O(B \cdot C) }[/math].

Будем считать, что количество батчей [math]\displaystyle{ N/B }[/math] - целое число; тогда сложность вычисления градиентов в течение одной эпохи - [math]\displaystyle{ O(N/B \cdot B \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 L_i(w) }[/math].

Этот этап демонстрирует координатный параллелизм (независимость итераций цикла по примерам в батче).

• Обновление весов: операция [math]\displaystyle{ w_{k+1} = w_k - \alpha g_k }[/math] представляет собой векторные операции (вычитание и скалярное умножение), которые также могут быть распараллелены по координатам вектора весов ([math]\displaystyle{ w }[/math]).

Параллельная сложность и высота ярусно-параллельной формы

Оценка параллельной сложности алгоритма (высота канонической ярусно-параллельной формы) дается в терминах числа операций умножения/деления и сложения (которые доминируют).

Пусть [math]\displaystyle{ d }[/math] — размерность вектора весов, [math]\displaystyle{ B }[/math] — размер мини-батча.

Основной вычислительный шаг SGD состоит из трех этапов:

Параллельная сложность одного шага Стохастического Градиентного Спуска (SGD)

Этап	Параллельная сложность (Высота ЯПФ, H)	Ширина ЯПФ (W - Сбалансированность)	Описание Ресурса Параллелизма
Вычисление градиентов	[math]\displaystyle{ O(\log_2 B + 1) }[/math]	[math]\displaystyle{ O(d \times B) }[/math]	Массовый параллелизм (Координатный параллелизм) по примерам в мини-батче. Требуется редукция/суммирование.
Усреднение и масштабирование	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(d) }[/math]	Конечный параллелизм (Координатный параллелизм) по координатам вектора весов.
Обновление весов	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(d) }[/math]	Конечный параллелизм (Координатный параллелизм) по координатам вектора весов.

Таким образом, параллельная сложность (высота) одного шага SGD составляет [math]\displaystyle{ H = O(\log_2 B) }[/math].

Сбалансированность параллельных шагов (ширина ярусов)

Ширина ярусов отражает сбалансированность параллельных шагов по числу операций:

• Ширина этапа градиентов: на этапе вычисления градиентов ширина ярусов максимальна, достигает [math]\displaystyle{ W = O(d \times B) }[/math]. Этот этап сбалансирован при [math]\displaystyle{ P }[/math] процессорах, где [math]\displaystyle{ P \le B }[/math], поскольку каждому процессу можно поручить обработку [math]\displaystyle{ \lceil B/P \rceil }[/math] примеров.
• Ширина этапов обновления: на этапах усреднения и обновления весов ширина ярусов составляет [math]\displaystyle{ W = O(d) }[/math]. Этот этап также сбалансирован, если [math]\displaystyle{ P \le d }[/math], поскольку операции могут быть распределены по [math]\displaystyle{ P }[/math] процессорам.

Алгоритм SGD обладает хорошей сбалансированностью на каждом шаге, что позволяет эффективно использовать большое число процессоров (ядер), особенно когда произведение [math]\displaystyle{ d \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{ d \times 1 }[/math] (или матрица [math]\displaystyle{ d \times C }[/math], если модель содержит скрытые слои или многоклассовый вывод).

Является плотной структурой данных. Диапазон значений зависит от функции потерь и регуляризации, но обычно это числа, близкие к нулю, или числа малого/среднего диапазона.

• История потерь (loss history, опционально): вектор, содержащий значение функции потерь, вычисленное после каждого шага SGD. Объем равен [math]\displaystyle{ (E \times N) / B }[/math]. Используется для анализа сходимости и отладки алгоритма.

Свойства алгоритма

Соотношение последовательной и параллельной сложности

Алгоритм SGD является последовательным по отношению к шагам обновления весов. Однако в рамках одного шага обновления (одного мини-батча) он обладает высоким ресурсом параллелизма.

• Последовательная сложность одного шага SGD: [math]\displaystyle{ T_{seq} = O(B \cdot d) }[/math], где [math]\displaystyle{ B }[/math] - размер батча, [math]\displaystyle{ d }[/math] - размерность весов.
• Параллельная сложность одного шага SGD (высота ЯПФ): [math]\displaystyle{ H = O(\log_2 B + 1) }[/math].

Теоретический выигрыш от параллельной реализации (ускорение) составляет:

[math]\displaystyle{ S = \frac{T_{seq}}{H} = \frac{O(B \cdot d)}{O(\log_2 B + 1)} }[/math]

Теоретически, параллельная реализация обеспечивает значительное ускорение [math]\displaystyle{ O(B \cdot d) }[/math], которое растет линейно с размером батча и размерностью задачи, если есть достаточное количество процессоров [math]\displaystyle{ P }[/math].

• Сложности параллелизации: главная сложность заключается в информационной зависимости между последовательными шагами обновления. Параллельная реализация дает выигрыш только внутри одного шага (градиент и обновление), но не может ускорить последовательность шагов, что является фундаментальным ограничением SGD.

Вычислительная Мощность

• Общее число операций (за одну эпоху): [math]\displaystyle{ O(N \cdot d) }[/math], где [math]\displaystyle{ N }[/math] — общее число объектов.
• Объем входных данных (матрица [math]\displaystyle{ X }[/math]): [math]\displaystyle{ O(N \cdot d) }[/math].
• Объем выходных данных (вектор весов [math]\displaystyle{ w }[/math]): [math]\displaystyle{ O(d) }[/math].

[math]\displaystyle{ W_{comp} = \frac{\text{Число операций}}{\text{Объем входных данных}} = \frac{O(N \cdot d)}{O(N \cdot d + d)} }[/math]

При больших [math]\displaystyle{ N }[/math] [math]\displaystyle{ N \cdot d }[/math] доминирует в знаменателе. Таким образом, вычислительная мощность SGD составляет:

[math]\displaystyle{ W_{comp} \approx O(1) }[/math]

Вычислительная мощность SGD близка к константе ([math]\displaystyle{ O(1) }[/math]). Это означает, что число операций примерно равно объему исходных данных. Это значение относительно невысокое. Это свойство требует, чтобы алгоритм выполнялся "близко" к памяти с данными (например, на том же узле кластера), чтобы минимизировать накладные расходы на перемещение данных.

Устойчивость Алгоритма

Алгоритм SGD является стохастическим и неустойчивым в смысле получения одного и того же результата при каждом запуске.

• Неустойчивость к входным данным: поскольку SGD использует только часть данных (мини-батч) для каждого шага, дисперсия в оценке градиента высокая. Это приводит к флуктуациям в траектории сходимости.
• Ошибка округления: при использовании массового параллелизма (например, при суммировании градиентов от [math]\displaystyle{ B }[/math] примеров) на системах с массовым параллелизмом порядок выполнения ассоциативных операций (сложение) может меняться от запуска к запуску. Это приводит к неповторяемости результатов работы параллельных программ, что является серьезной проблемой на практике.

Сбалансированность вычислительного процесса

Алгоритм обладает хорошей сбалансированностью с точки зрения распределения нагрузки.

На каждой итерации преобладают арифметические операции при вычислении градиента. Соотношение между арифметическими операциями и обращениями к памяти (чтение/запись) определяется параметром [math]\displaystyle{ B \cdot d }[/math], который обычно достаточно велик, что обеспечивает эффективную работу процессоров.

Распределение нагрузки по [math]\displaystyle{ P }[/math] процессам на этапе вычисления градиента достигается просто: каждый процессор обрабатывает [math]\displaystyle{ \lceil B/P \rceil }[/math] примеров. Это обеспечивает высокую балансировку нагрузки.

Детерминированность

Алгоритм SGD является недетерминированным по следующим причинам:

1. Порядок обработки мини-батчей: в классическом SGD набор мини-батчей на каждой эпохе случаен, что меняет структуру вычислительного процесса и итоговый результат. 2. Изменение порядка ассоциативных операций: как было описано выше, изменение порядка суммирования градиентов в параллельной среде приводит к непостоянству ошибок округления, что является причиной недетерминированности конечного результата в параллельной реализации.

Дополнительные свойства

• Степень исхода вершины: высока для вектора весов [math]\displaystyle{ w }[/math]. На каждом шаге [math]\displaystyle{ w }[/math] используется для вычисления градиента для всех [math]\displaystyle{ B }[/math] примеров. На этапе реализации это требует эффективной рассылки вектора [math]\displaystyle{ w }[/math] всем параллельным процессам/потокам, работающим над батчем, и эффективного доступа к нему.
• "Длинные" дуги: возникают в информационном графе SGD при рассылке величин (таких как learning rate [math]\displaystyle{ \alpha }[/math] или текущие веса [math]\displaystyle{ w }[/math]) по всем итерациям цикла мини-батчей. В случае вектора весов ([math]\displaystyle{ w }[/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