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

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

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

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

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

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

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

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

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

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

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

ПОВТОРЯТЬ

    w:=wηL(w)=wη1Nn=1NL(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})

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

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

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

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

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

Важность случайной инициализации весов

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

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

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

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

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

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

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

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

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

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

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

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

ПОВТОРЯТЬ

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

    n:=n+1n:=n+1

    ЕСЛИ n>Nn>N:

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

        n:=1n:=1

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

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

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

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

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

L(w)1Bi=nn+B1Ln(w)=Ln:n+B1(w),\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+B1n:n+B-1 обозначает, что усреднение происходит по объектам n,n+1,...n+B1n,n+1,...n+B-1.

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

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

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

n:=1n:=1

ПОВТОРЯТЬ

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

    n:=n+1n:=n+1

    ЕСЛИ n>Nn>N:

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

        n:=1n:=1

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

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

Влияние настроек на найденное решение

Стоит отметить, что размер мини-батча BB и характер уменьшения шага обучения η\eta могут влиять на найденный локальный оптимум, поскольку в общем случае функция потерь не является выпуклой функцией от весов нейросети!

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

Стохастическая оптимизация по случайным объектам была впервые предложена в работах [1] и [2], а в [3] она была впервые применена к настройке простейшей нейросети.

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

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

Δwt=ηLn:n+B1(wt1)+μΔwt1(1)\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), а μ[0,1)\mu\in [0,1) - гиперпараметр, который обычно полагают равным μ=0.9\mu=0.9.

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

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

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

n:=1n:=1

ПОВТОРЯТЬ

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

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

    n:=n+1n:=n+1

    ЕСЛИ n>Nn>N:

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

        n:=1n:=1

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

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

Δwt=ηLn:n+B1(wt1)+μΔwt1=ηLn:n+B1(wt1)+μ(ηLnB:n1(wt2)+μΔwt2)=η(Ln:n+B1(wt1)+μLnB:n1(wt2)+μ2Ln2B:nB1(wt2)+...)\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}

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

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

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

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

Таким образом, и для плавно, и для резко меняющейся функции потерь внесение инерции способно ускорить сходимость. Однако инерция способна и замедлить её, если взять μ\mu слишком большим: в этом случае направление изменения весов будет слишком полагаться на устаревшие значения градиента.

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

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

Δwt+1=ηLn:n+B1(wt+μΔwt)+μΔwt\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, [5], [6]).

Литература

  1. Robbins H., Monro S. A stochastic approximation method //The annals of mathematical statistics. – 1951. – С. 400-407.
  2. Kiefer J., Wolfowitz J. Stochastic estimation of the maximum of a regression function //The Annals of Mathematical Statistics. – 1952. – С. 462-466.
  3. Rosenblatt F. The perceptron: a probabilistic model for information storage and organization in the brain //Psychological review. – 1958. – Т. 65. – №. 6. – С. 386.
  4. Поляк Б. Т. О некоторых способах ускорения сходимости итерационных методов //Журнал вычислительной математики и математической физики. – 1964. – Т. 4. – №. 5. – С. 791-803.
  5. Нестеров Ю. Е. Метод минимизации выпуклых функций со скоростью сходимости O(1/k2) // Доклады АН СССР. 1983. Т. 269, № 3. С. 543–547.
  6. Nesterov, Y. 2004. Introductory Lectures on Convex Optimization: A Basic Course. Kluwer.