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

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

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

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

L(w)=1N∑n=1NLn(w)→min⁡w,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)+wT∇L(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−η1N∑n=1N∇L(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)≈1B∑i=nn+B−1∇Ln(w)=∇Ln:n+B−1(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+B−1n:n+B-1 обозначает, что усреднение происходит по объектам n,n+1,...n+B−1n,n+1,...n+B-1.

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

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

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

n:=1n:=1

ПОВТОРЯТЬ

    w:=w−η∇Ln:n+B−1(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+B−1(wt−1)+μΔwt−1(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+B−1(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), если на предыдущей итерации осуществлялся сдвиг Δwt−1\Delta \mathbf{w}_{t-1}, то его часть будет осуществлена и на следующей итерации с весом μ\mu. Поскольку инерция сама содержит инерцию с предыдущей итерации, то итоговый сдвиг будет взвешенной комбинацией сдвигов со всех предыдущих итераций с экспоненциально убывающими весами:

Δwt=−η∇Ln:n+B−1(wt−1)+μΔwt−1=−η∇Ln:n+B−1(wt−1)+μ(−η∇Ln−B:n−1(wt−2)+μΔwt−2)=−η(∇Ln:n+B−1(wt−1)+μ∇Ln−B:n−1(wt−2)+μ2∇Ln−2B:n−B−1(wt−2)+...)\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+B−1(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.