Оптимизаторы с постоянным шагом

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

Нейросети оптимизируют свои веса, минимизируя средние потери по обучающей выборке:

$$L(\mathbf{w})=\frac{1}{N}\sum_{n=1}^N \mathcal{L}_n(\mathbf{w}) \to \min_\mathbf{w},$$

где $\mathcal{L}_n(\mathbf{w})$ - потери на объекте $(\mathbf{x}_n,y_n)$.

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

Градиентные методы оптимизации основаны на линейной аппроксимации функции потерь:

$$L(\hat{\mathbf{w}}) \approx L(\mathbf{w})+\mathbf{w}^T \nabla L(\mathbf{w}),$$

согласно которому наибольшая локальная скорость убывания функции потерь достигается вдоль её антиградиента ($-\nabla L(\mathbf{w})$). На этой идее основан метод градиентного спуска (gradient descent):

инициализировать $\mathbf{w}$ случайно

ПОВТОРЯТЬ

    $\mathbf{w}:=\mathbf{w}-\eta \nabla L(\mathbf{w})=\mathbf{w}-\eta \frac{1}{N}\sum_{n=1}^N \nabla\mathcal{L}(\mathbf{w})$

ДО СХОДИМОСТИ

где $\eta>0$ - шаг обучения (learning rate), влияющий на скорость сходимости.

Выбор шага обучения

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

Инициализация весов

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

Обычно смещения инициализируют нулём, а прочие веса инициализируют

• из равномерного распределения $U[-\varepsilon,\varepsilon]$

• либо из нормального распределения $\mathcal{N}(0,\sigma^2)$.

Детали инициализации и формулы для расчётов $\varepsilon$ и $\sigma$ подробно рассмотрены в главе про инициализацию весов нейронных сетей.

Недостатком метода градиентного спуска является сложность вычисления градиента на каждом шаге (она пропорциональна числу объектов выборки $O(N)$).

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

Более быстрым является онлайновый метод стохастического градиентного спуска (online stochastic gradient descent, OSGD), в котором используется приближение

$$\nabla L(\mathbf{w})\approx \nabla\mathcal{L}_n(\mathbf{w}),$$

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

перемешать объекты выборки

инициализировать $\mathbf{w}$ случайно, $n:=1$

ПОВТОРЯТЬ

    $\mathbf{w}:=\mathbf{w}-\eta \nabla \mathcal{L}_n(\mathbf{w})$

    $n:=n+1$

    ЕСЛИ $n>N$:

        перемешать объекты выборки

        $n:=1$

ДО СХОДИМОСТИ

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

Недостатком OSGD является использование слишком зашумлённых версий исходного градиента $\nabla L(\mathbf{w})$, поскольку для оценки используется всего один объект. Это не препятствует сходимости метода при выборе достаточно малого (и убывающего с определённой скоростью) шага обучения $\eta$, но замедляет его, поскольку задействует лишь малое число вычислительных ресурсов за каждый такт оптимизации.

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

Чтобы ускорить метод OGD, рекомендуется использовать стохастический градиентный спуск по мини-батчам (mini-batch stochastic gradient descent, MSGD). Его также называют просто методом стохастического градиентного спуска (stochastic gradient descent, SGD). Его идея заключается в том, что для оценки градиента используется набор из $B$ объектов:

$$\nabla L(\mathbf{w}) \approx \frac{1}{B}\sum_{i=n}^{n+B-1}\nabla\mathcal{L}_n(\mathbf{w}) = \nabla\mathcal{L}_{n:n+B-1}(\mathbf{w}),$$

где $n:n+B-1$ обозначает, что усреднение происходит по объектам $n,n+1,...n+B-1$.

Псевдокод метода представлен ниже:

перемешать объекты выборки

инициализировать $\mathbf{w}$ случайно

$n:=1$

ПОВТОРЯТЬ

    $\mathbf{w}:=\mathbf{w}-\eta \nabla \mathcal{L}_{n:n+B-1}(\mathbf{w})$

    $n:=n+1$

    ЕСЛИ $n>N$:

        перемешать объекты выборки

        $n:=1$

ДО СХОДИМОСТИ

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

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

Дополнительное ускорение обеспечивает стохастический градиентный спуск с инерцией (GD+momentum). В этом методе обновление весов происходит не только на величину антиградиента, но и на величину обновления весов с предыдущей итерации:

$$\Delta \mathbf{w}_t = -\eta \nabla \mathcal{L}_{n:n+B-1}(\mathbf{w}_{t-1}) + \textcolor{red}{\mu \Delta \mathbf{w}_{t-1}} \tag{1}$$

Компонента, выделенная красным, называется инерцией (momentum), а $\mu\in [0,1)$ - гиперпараметр, который обычно полагают равным $\mu=0.9$.

Псевдокод метода представлен ниже:

перемешать объекты выборки

инициализировать $w$ случайно

$n:=1$

ПОВТОРЯТЬ

    $\Delta \mathbf{w} := -\eta \nabla \mathcal{L}_{n:n+B-1}(\mathbf{w})+\Delta \mathbf{w}$

    $\mathbf{w}:=\mathbf{w}+\Delta \mathbf{w}$

    $n:=n+1$

    ЕСЛИ $n>N$:

        перемешать объекты выборки

        $n:=1$

ДО СХОДИМОСТИ

Как видно в (1), если на предыдущей итерации осуществлялся сдвиг $\Delta \mathbf{w}_{t-1}$, то его часть будет осуществлена и на следующей итерации с весом $\mu$. Поскольку инерция сама содержит инерцию с предыдущей итерации, то итоговый сдвиг будет взвешенной комбинацией сдвигов со всех предыдущих итераций с экспоненциально убывающими весами:

$$\begin{aligned} \Delta \mathbf{w}_t &= -\eta \nabla \mathcal{L}_{n:n+B-1}(\mathbf{w}_{t-1}) + \mu \Delta \mathbf{w}_{t-1} \\ &=-\eta \nabla \mathcal{L}_{n:n+B-1}(\mathbf{w}_{t-1}) + \mu (-\eta \nabla \mathcal{L}_{n-B:n-1}(\mathbf{w}_{t-2}) + \mu \Delta \mathbf{w}_{t-2})\\ &=-\eta (\nabla \mathcal{L}_{n:n+B-1}(\mathbf{w}_{t-1})+\mu \nabla \mathcal{L}_{n-B:n-1}(\mathbf{w}_{t-2})+\mu^2 \nabla \mathcal{L}_{n-2B:n-B-1}(\mathbf{w}_{t-2})+...) \end{aligned}$$

В частности, когда градиент не меняется и равен общей константе $\nabla \mathcal{L}$, то

$$\Delta \mathbf{w}_t = -\eta \nabla \mathcal{L} (1+\mu+\mu^2+...)=-\frac{\eta}{1-\mu} \nabla \mathcal{L}$$

то есть вдоль направлений, где градиент не меняется, происходит ускорение сходимости в $1/(1-\mu)$ раз!

Если же функция меняется резко, то её градиент указывает то в одну сторону, то в другую, поэтому противоположные направления частично компенсируются в (1), и можно запускать оптимизатор с более высоким значением шага обучения $\eta$.

В обоих случаях достигается ускорение обучения нейросети.

Ускорение Нестерова

Дополнительное ускорение в методе SGD+momentum можно получить, если вычислять градиент не в текущей оценке весов $w_t$, а в более актуальной точке, которая ближе к значению весов на следующем шаге $\mathbf{w}_t+\mu \Delta \mathbf{w}_t$, т.е. по формуле:

$$\Delta \mathbf{w}_{t+1} = -\eta \nabla \mathcal{L}_{n:n+B-1}(\mathbf{w}_{t}+\textcolor{red}{\mu \Delta \mathbf{w}_{t}}) + \mu \Delta \mathbf{w}_{t}$$

Это ускорение называется инерцией Нестерова (Nesterov momentum, [1]).

Литература

1. Nesterov, Y. 2004. Introductory Lectures on Convex Optimization: A Basic Course. Kluwer.