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

Постановка задачи

Пусть мы имеем $m$ точек в $n$-мерном пространстве $\Bbb{R}^n$: $$ p_1, p_2, \dots, p_m \in \Bbb{R}^n. $$ Точки описывают объекты некоторых классов, координаты точек играют роль признаков (features). Множество объектов представляет собой обучающую выборку. На ней мы обучаем некоторую модель, которая описывается параметрами $$ w_1, w_2, \dots, w_k. $$ Набор этих параметров можно рассматривать как вектор $k$-мерного пространства $w\in \Bbb{R}^k$.

Для построения модели мы минимизируем некоторую функцию потерь $$ H(w, p_1, p_2, \dots, p_m) \to \min_w, $$ зависящую от параметров $w$ и вычисляемую на всем множестве объектов $p_1, p_2, \dots, p_m$. Функция потерь чаще всего представляется в виде суммы или среднего значения потери на отдельных элементах выборки: $$ H(w, p_1, p_2, \dots, p_m) = 1/m \cdot\sum_{i=1}^m L(w, p_i), $$ где $L(w, p_i)$ — функция потери на одном элементе $p_i$ из обучающей выборки. Часто к функции потери добавляется регуляризирующий член с коэффициентом регуляризации $\lambda$: $$ H(w, p_1, p_2, \dots, p_m) = 1/m \cdot\sum_{i=1}^m L(w, p_i) + \lambda R(w). $$ Регуляризирующий член может быть квадратом нормы $w$, $$ R(w) = ||w||^2, $$ либо просто нормой $||w||$, либо какой-нибудь еще функцией, принимающей неотрицательные значения и растущей при возрастании нормы $w$.

Для построения модели по обучающей выборке $p_1, p_2, \dots, p_m$ мы должны найти такой набор параметров $w$, при котором функция потерь принимает минимальное значение: $$ w = \text{argmin}_w H(w, p_1, \dots, p_m). $$

Две ранее рассмотренные нами задачи укладываются в эту схему.

Линейная (полиномиальная) регрессия

Пусть нам известно, что связь между переменной $x$ и зависящей от нее переменной $y$ выражается в виде полинома $f(w, x)$ степени $n$: $$ y = f(w, x) = w_0 x^n + w_1 x^{n-1} + \dots + w_n. $$ Мы имеем $m$ независимых измерений величины $y$ для разных значений $x$. Результаты этих измерений можно рассматривать как набор из $m$ точек на плоскости $\Bbb{R}^2$, где $i$-я точка задается значениями независимой переменной $x_i$ и зависящей от нее переменной $y_i$: $$ p_i = (x_i, y_i), \quad i = 1, 2, \dots m. $$ Функция потерь в данном случае равна сумме квадратов отклонений значений $y_i$ от значений полинома $f(w, x)$ в точках $x_i$: $$ H(w, p_1, p_2, \dots, p_m) = 1/m\cdot \sum_{i=1}^m (f(w,x_i) - y_i)^2, \\ p_i = (x_i, y_i), \quad i = 1, 2, \dots m. $$

Метод опорных векторов

Мы имеем набор из $m$ точек $t_i$ в $n$-мерном пространстве, каждая из которых представляет объект одного из двух классов: $$ t_1, t_2,\dots, t_m \in \Bbb{R}^n. $$ Объектам первого класса соответствует значение $y=1$ дополнительной переменной $y$, объектам второго класса соответствует значение $y=-1$. Таким образом, мы можем рассмотреть обучающую выборку $$ p_1, p_2,\dots, p_m \in \Bbb{R}^{n+1},\\ p_i = (t_i, y_i), \quad y_i = \pm 1. $$

В методе опорных векторов строится гиперплоскость в пространстве $\Bbb{R}^n$, разделяющая точки $t_i$ двух классов. Эта гиперплоскость задается уравнением $$ \langle w, t\rangle - b = 0, \quad w,t \in \Bbb{R}^n,\ b\in \Bbb{R}. $$ Здесь $w$ — вектор нормали к гиперплоскости. Линейный классификатор $f(t) = \langle w, t\rangle - b$ относит точку $t$ к первому классу, если его значение положительно, и ко второму, если отрицательно. Таким образом, строящаяся этим методом модель задается параметрами $(w, b)$, $w\in\Bbb{R}^n$, $b\in\Bbb{R}$.

Функция потери в методе опорных векторов записывается следующим образом: $$ H((w, b), p_1, p_2,\dots, p_m) = ||w||^2 + C\cdot 1/m\cdot\sum_{i=1}^m L(y_i(\langle w, t_i\rangle - b)) % \to \min_{w, b} ,\\ p_i = (t_i, y_i), i=1,\dots,m. $$ Здесь константа $С\in\Bbb{R}$ — гиперпараметр алгоритма. Для функции потери на одном элементе $L(x)$ обычно используется один из двух вариантов:
1) Hinge Loss $$ L_1(x) = \max(1 - x, 0), \quad x\in \Bbb{R}, $$ 2) Logistic Loss $$ \begin{array}{l} L_2(x) = \ln(1 + e^{-x}). \end{array} $$

Основная идея метода стохастического градиентного спуска

Задачу минимизации функции потери можно решать методом градиентного спуска или одним из его ускоренных вариантов. Однако в реальных задачах обучающая выборка может иметь довольно большой объем (например, десятки тысяч элементов), и вычисление градиента функции потери может потребовать довольно много процессорного времени и других ресурсов компьютера. Это может существенно замедлить обучение модели, учитывая то, что в градиентном спуске приходится выполнять большое число шагов. Основная идея стохастического градиентного спуска состоит в том, что мы на каждом шаге вычисляем градиент функции потери не по всей обучающей выборке, а только на ее небольшом подмножестве.

Классическая схема — на каждом шаге используем всего лишь один случайный элемент из обучающей выборки

В классической схеме мы выбираем из обучающего набора $p_1, p_2, \dots p_m$ всего один случайный элемент $p_j$. Функция потери вычисляется только на одном этом элементе $p_j$: $$ H_j(w) = L(w, p_j) $$ или $$ H_j(w) = L(w, p_j) + \lambda R(w), $$ когда используется регуляризация. Более точно, нам нужна не сама функция потери, а ее градиент по $w$: $$ g = \nabla H_j(w). $$ Этот вектор $g$ мы используем на очередном шаге стохастического градиентного спуска для вычисления следующего приближения $w_{k+1}$ параметров модели по очередному приближению $w_k$: $$ w_{k+1} = w_k - \alpha\cdot g. $$ Конечно, вектор $g$ будет отличаться от "настоящего" значения градиента функции потери, вычисленной по всему обучающему набору, и для достижения точки минимума потребуется большее количество шагов, Но мы выигрываем за счет того, что вычисление неточного вектора градиента происходит значительно быстрее.

Схема с мини-пакетом (Mini-Batch) — на каждом шаге используем пакет из фиксированного небольшого числа элементов обучающей выборки

Использование небольшого набора случайных элементов обучающей выборки для приближенного вычисления градиента функции потери позволяет уменьшить случайные вариации вектора градиента по сравнению с использованием только одного элемента. Такая схема носит название Mini-batch Gradient Descent, от англ. Mini-batch — мини-пакет. Мы фиксируем небольшой размер $s$ мини-пакета, например, $s=32$. Выбираем набор из $s$ элементов обучающей выборки, $s\le m$: $$ B = \{ p_{i_1}, p_{i_2}, \dots, p_{i_s} \} \subset \{ p_1, p_2, \dots, p_m \}. $$ Элементы $p_{i_j}$ можно выбирать либо совсем случайным образом, либо выбирать подряд идущие, начиная с некоторого индекса, задающего начало мини-пакета, в циклическом порядке. Для мини-пакета $B$ из $s$ элементов функция потери вычисляется следующим образом: $$ H_B(w) = 1/s \cdot\sum_{p \in B} L(w, p), $$ или $$ H_B(w) = 1/s \cdot\sum_{p \in B} L(w, p) + \lambda R(w), $$ когда используется регуляризация. Градиент этой функции $$ g = \nabla H_B(w) $$ используется на очередном шаге стохастического градиентного спуска. После выполнения очередного шага формируется новый мини-пакет, состоящий либо из $s$ случайно выбранных элементов обучающего набора, либо из следующих $s$ элементов в циклическом порядке после конца предыдущего пакета.

Сходимость метода стохастического градиентного спуска и размер шага

В целом метод стохастического градиентного спуска сходится хуже, чем обычный метод градиентного спуска. Пусть размер шага в градиентном спуске равен $\alpha$. Тогда сходимость к минимуму для выпуклой функции потери, градиент которой удовлетворяет условию Липшица с константой $L$, имеет место при условии $$ \alpha \lt 2/L. $$ Число шагов для достижения точки минимума с точностью $\varepsilon$ оценивается как $O(1/\varepsilon)$.

В реальных задачах определить величину константы Липшица $L$ бывает очень трудно. Поэтому чаще всего используют схему с убывающей величиной шага. Обозначим величину $i$-го шага через $\alpha_i$. Тогда для хороших функций потери (т.е. выпуклых и удовлетворяющих условию Липшица для градиента) имеет место следующее утверждение.

Метод стохастического градиентного спуска сходится к точке минимума при выполнении следующих двух условий на величины шагов $\alpha_i$: $$ \sum_{i=1}^\infty \alpha_i = \infty $$ (ряд, составленный из величин шагов, расходится); $$ \sum_{i=1}^\infty \alpha_i^2 \lt \infty $$ (ряд, составленный из квадратов величин шагов, сходится).

Отметим, что если использовать размер шага, пропорциональный $1/i$, где $i=1, 2, 3, \dots$ — номер шага, то оба сформулированных выше условия выполняются. Поэтому часто используется следующая формула для задания размера шага в зависимости от его номера $i$: $$ \alpha_i = {\alpha_0\over 1 + \eta \cdot i}. $$ Здесь $\alpha_0$ — начальный размер шага, $\eta$ — параметр, определяющий скорость убывания величины шага (чем он больше, тем быстрее шаг уменьшается). Часто используется также формула, в которой номер шага в знаменателе дроби возводится в степень $\beta \le 1$: $$ \alpha_i = {\alpha_0\over 1 + \eta \cdot i^\beta}. $$