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

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

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

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

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

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

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

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

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

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

ПОВТОРЯТЬ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ПОВТОРЯТЬ

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

    $n:=n+1$

    ЕСЛИ $n>N$:

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

        $n:=1$

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

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

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

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

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

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

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

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

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

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

$n:=1$

ПОВТОРЯТЬ

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

    $n:=n+1$

    ЕСЛИ $n>N$:

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

        $n:=1$

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

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

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

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

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

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

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

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

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

$n:=1$

ПОВТОРЯТЬ

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

    $w:=w+\Delta w$

    $n:=n+1$

    ЕСЛИ $n>N$:

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

        $n:=1$

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

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

$$\begin{align*} \Delta w_t &= -\eta \nabla \mathcal{L}_{n:n+B-1}(w_{t-1}) + \mu \Delta w_{t-1} \\ &=-\eta \nabla \mathcal{L}_{n:n+B-1}(w_{t-1}) + \mu (-\eta \nabla \mathcal{L}_{n-B:n-1}(w_{t-2}) + \mu \Delta w_{t-2})\\ &=-\eta (\nabla \mathcal{L}_{n:n+B-1}(w_{t-1})+\mu \nabla \mathcal{L}_{n-B:n-1}(w_{t-2})+\mu^2 \nabla \mathcal{L}_{n-2B:n-B-1}(w_{t-2})+...) \end{align*}$$

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

$$\Delta 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$, а в более актуальной точке, которая ближе к значению весов на следующем шаге $w_t+\mu \Delta w_t$, т.е. по формуле:

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

Это ускорение называется инерция Нестерова [1].

Литература

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