Перейти к основному содержимому

Метод стохастического градиентного спуска

Идея метода​

Вспомним, что функция потерь в машинном обучении представляет собой эмпирический риск, то есть средние потери по объектам обучающей выборки:

L(w)=1N∑n=1NL(fw(xn), yn)L(\mathbf{w}) = \frac{1}{N}\sum_{n=1}^{N}\mathcal{L}(f_{\mathbf{w}}(\mathbf{x}_{n}),\,y_{n})

Рассмотрим детальнее метод градиентного спуска с учётом вида функции потерь:

инициализируем w0\mathbf{w}_0 случайно

пока не выполнено условие остановки:

             w:=w−ε∇wL(w)=w−ε1N∑n=1N∇wL(y^(xn),yn)\mathbf{w}:=\mathbf{w}-\varepsilon\nabla_{\mathbf{w}}L(\mathbf{w}) = \mathbf{w}-\varepsilon\frac{1}{N}\sum_{n=1}^N \nabla_{\mathbf{w}}\mathcal{L}(\hat{y}(\mathbf{x}_n),y_n)

Получается, что на каждом шаге алгоритма необходимо вычислять производные функции потерь на всех объектах обучающей выборки, которых может быть очень много!

Это приводит к медленной работе метода. При этом, поскольку алгоритм состоит из многих итераций с малым шагом ε\varepsilon, нам совсем не обязательно вычислять точное значение градиента L(w)L(\mathbf{w}), а достаточно сдвигаться лишь примерно в сторону уменьшения функции.

Идея метода стохастического градиентного спуска (stochastic gradient descent, SGD) заключается в использовании быстро вычислимой аппроксимации эмпирического риска для расчета градиента. Для этого используется приближение средними потерями на KK случайных объектах:

L(w)=1N∑n=1NL(xn,yn∣w)≈1K∑n∈IL(xn,yn∣w)=L~(w)L(\mathbf{w})=\frac{1}{N}\sum_{n=1}^{N}\mathcal{L}(\mathbf{x}_{n},y_{n}|\mathbf{w})\approx\frac{1}{K}\sum_{n\in I}\mathcal{L}(\mathbf{x}_{n},y_{n}|\mathbf{w})=\tilde{L}(\mathbf{w})

где I={n1,...nK}I=\{n_1,...n_K\} - индексы KK случайных объектов обучающей выборки, называемых минибатчом (minibatch). Используя эту аппроксимацию, получим метод стохастического градиентного спуска:

инициализируем настраиваемые веса w\mathbf{w} случайно

пока не выполнено условие остановки:

             случайно выбрать KK объектов I={n1,...nK}I=\{n_1,...n_K\} из {1,2,...N}\{1,2,...N\}

             w:=w−ε∇wL~(w)=w−εt1K∑n∈I∇wL(y^(xn),yn)\mathbf{w}:=\mathbf{w}-\varepsilon\nabla_{\mathbf{w}}\tilde{L}(\mathbf{w}) = \mathbf{w}-\varepsilon_t\frac{1}{K}\sum_{n\in I} \nabla_{\mathbf{w}}\mathcal{L}(\hat{y}(\mathbf{x}_n),y_n)

Как видим, одна итерация стохастического градиентного спуска выполняется за O(K)O(K) операций, а не за O(N)O(N), как в обычном методе градиентного спуска, причём KK мы выбираем сами, и он берётся намного меньше NN!

Поскольку по каждой итерации метода минибатч сэмплируется случайно, то, при достаточном числе итераций, алгоритм всё равно обойдет все объекты выборки.

На практике объекты обучающей выборки переставляются в случайном порядке, а затем извлекаются последовательно по KK штук за раз. Однократный проход по всем объектам обучающей выборки называют эпохой (epoch).

Онлайн-обучение

В режиме онлайн-обучения (online learning [1]) обучающие объекты поступают последовательно, а целевая зависимость часто динамически меняется со временем. Так происходит, например, при прогнозе цен на акции на бирже. В подобных сценариях вместо случайного сэмплирования объектов по всей истории наблюдений чаще сэмплируют недавние, более свежие наблюдения, лучше отражающие текущую зависимость в данных.

Выбор K​

Если KK велико, а объекты содержат повторяющуюся информацию, то точность аппроксимации будет высокой при более быстрой сходимости по сравнению с методом градиентного спуска.

Интересно, что метод будет сходиться даже при K=1K=1. Конечно, оценка эмпирического риска всего по одному объекту будет очень грубой. Однако, поскольку эта оценка является несмещённой (за счёт случайного выбора объекта), метод всё равно будет сходиться, надо лишь использовать более малый шаг обучения ε\varepsilon. Тогда за увеличенное количество итераций мы сможем обойти существенную часть объектов выборки и в итоге сместить веса в правильную сторону.

На практике KK выбирают таким, чтобы минибатч помещался в память и векторные операции, связанные с его обработкой, производились за один такт параллельных вычислений устройства.

Сходимость​

Для сходимости функция потерь должна быть непрерывно-дифференцируемой, выпуклой в окрестности оптимума и удовлетворять условию Липшица (иметь ограниченную производную [2]). Детальнее об условиях сходимости можно прочитать в учебнике ШАД [3]. Важным отличием условий сходимости стохастического градиентного спуска является то, что шаг сходимости должен быть не константой ε\varepsilon, а последовательностью εt\varepsilon_t, стремящейся к нулю в окрестности оптимума.

Действительно, при постоянном шаге, из-за того, что мы сдвигаемся не на точный градиент, а на его грубую аппроксимацию, даже дойдя до оптимума, метод будет совершать случайное блуждание в его окрестности. Для сходимости нужно постепенно уменьшать шаг, как показано ниже справа:

decreasing-step.png

Скорость уменьшения шага для сходимости

Формально метод сходится, если шаг удовлетворяет следующим двум условиям:

∑t=1+∞εt=+∞достигаем произвольной точки∑t=1+∞εt2<+∞εt сходится к нулю достаточно быстро\begin{aligned} \sum_{t=1}^{+\infty}\varepsilon_{t}=+\infty & \qquad\text{достигаем произвольной точки}\\ \sum_{t=1}^{+\infty}\varepsilon_{t}^{2}<+\infty & \qquad\varepsilon_{t}\text{ сходится к нулю достаточно быстро} \end{aligned}

Например, этому условию удовлетворяет последовательность

εt=a1+bt, где a,b>0 - гиперпараметры.\varepsilon_t=\frac{a}{1+bt}, \text{ где $a,b>0$ - гиперпараметры.}

На практике шаг часто берут небольшой константой, а потом её уменьшают, когда функция потерь перестаёт устойчиво уменьшаться, после чего продолжают обучение с уменьшенным шагом. Так делают несколько раз, и в библиотеках оптимизации, такой как PyTorch, такая стратегия уже реализована [4].

Далее в учебнике будет рассмотрено повышение скорости и устойчивости метода стохастического спуска за счёт внесения инерции, а также метод Ньютона оптимизации второго порядка. Также во второй части учебника по глубокому обучению будут описаны специализированные методы оптимизации для настройки нейросетей.

Вы также можете прочитать про метод градиентного и стохастического градиентного спуска у викиконспектах ИТМО [5] и учебнике ШАД [6]. В статье [7] детально разбираются различные алгоритмы оптимизации и анализируются их преимущества и недостатки.

Литература​

  1. Wikipedia: online machine learning.

  2. Wikipedia: Lipschitz continuity.

  3. Учебник ШАД: сходимость SGD.

  4. Документация PyTorch: ReduceLROnPlateau.

  5. Викиконспекты ИТМО: cтохастический градиентный спуск.

  6. Учебник ШАД: оптимизация в ML.

  7. Ruder S. An overview of gradient descent optimization algorithms //arXiv preprint arXiv:1609.04747. – 2016.