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

Содержание

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

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

• Моменты

• Ускоренные градиенты Нестерова (Nesterov accelerated gradient)

• Adagrad

• Adadelta

• Adam (Adaptive Moment Estimation)

• Литература

---

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

Тренировка нейронной сети заключается в подборе параметров (весов) таким образом, чтобы минимизировать штрафную функцию на тренировочном наборе. Формализуя имеем:

1. Тренировочный набор:

   а) $X = \{x_i | i = 0,…,(N-1) \}$,

   б) $Y = \{y_i | i= 0,…,(N-1) \}$.

   Например, для задачи классификации: $y_i \in Y$ - метка класса для объекта $x_i \in X$.

2. Веса нейронной сети $w \in \Re^d$.

3. Штрафная функция:

\[L(w) = \sum_{i=0}^{N-1} L(w, x_i, y_i)\]

Мы хотим подобрать веса $w = w’$ таким образом, чтобы $L(w’)$ принимала минимальное значение.

Обычно такие задачи решаются при помощи метода градиентного спуска. Т.е. мы выбираем какое-то начальное значение весов $w_0$, вычисляем градиент функции в этой точке $\nabla L(w_0)$ и сдвигаем текущую точку $w_0$ в направлении обратном направлению градиента:

\[w_{p+1} = w_{p} - \eta \nabla L(w_{p})\]

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

Замечания

1. Какой должен быть параметр скорости обучения? Если взять скорость слишком большой, то алгоритм будет “скакать” вокруг точки минимума, а если слишком маленькой, то алгоритм будет сходиться слишком медленно.
2. Если у функции несколько локальных минимумов и мы “не угадали” с начальными значениями весов, то с маленьким параметром скорости обучения, алгоритм не имеет шансов выскочить из локального минимума.
3. Должен ли меняться и как параметр скорости обучения со временем?
4. Правильно ли иметь единую скорость обучения для всех параметров или есть смысл использовать разные?

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

При наличии достаточно большого тренировочного набора, вычислять функцию ошибки по всем элементам этого набора, задача весьма затратная по ресурсам. Поэтому разобьём набор на $K$ частей (minibatch) размера $M$:

\[X^{(k)} = \{x_i | i = Mk,...,(Mk+M-1) \},\] \[Y^{(k)} = \{y_i | i= Mk,...,(Mk+M-1) \},\] \[k=0,...,(K-1).\]

определим функции:

\[L^{(k)}(w) = \sum_{i=0}^{M-1} L(w, x_{Mk + i}, y_{Mk + i}), k=0,...,(K-1).\]

И вместо одной итерации градиентного спуска у нас появляется набор из $K$ миниитераций вида:

\[\begin{array}{l} w^{(k + 1)}_{p} = w^{(k)}_{p} - \eta \cdot \nabla L^{(k)}(w^{(k)}_{p}), k=0,...,(K-1), \\ w^{(0)}_{p+1} = w^{(K)}_p. \end{array}\]

Каждую “большую” итерацию ($p=0,1,2,…$), когда мы проходим весь набор, будем называть эпохой (epoch). Между эпохами тренировочный набор перемешивается, чтобы элементы попадали в разные минибатчи в разных эпохах. Т.о. $L^{(k)}(w)$ вообще говоря суммируются по разным поднаборам $X, Y$ для разных эпох (при фиксированном $k$).

Метод стохастического градиентного спуска, позволяет решить проблему требовательности к ресурсам обычного градиентного спуска, однако, ставит много новых вопросов, например, какого размера выбирать минибатчи?

Замечание

Избавимся от двойных индексов $k, p$ для упрощения формул. Будем использовать $L(w) = L^{(k)}(w)$, понимая, что в зависимости от итерации, мы выбираем, соответствующие поднаборы из тренировочного набора. Формула изменения весов на итерации $p$ перепишется тогда как: $w_{p + 1} = w_{p} - \eta \cdot \nabla L(w_{p})$

Моменты

Одна из проблем с SGD в том, что когда функция попадает в “овраг”, т.е. по одному из направлений имеем быстрый спуск, а по другому медленный, то SGD приводит к осциляции и крайне медленной сходимости к минимуму.

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

\[\begin{array}{l} \Delta_{p+1} = \gamma \cdot \Delta_{p} + \eta \cdot \nabla L(w_{p}), \\ w_{p+1} = w_{p} - \Delta_{p+1}. \end{array}\]

Скорость движения в направлении минимума увеличивается (т.к. это направление присутствует во всех градиентах), а осциляция гасится. Весовой параметр $\gamma$ обычно выбирается равным $0.9$ или близко к тому.

Ускоренные градиенты Нестерова (Nesterov accelerated gradient)

Следующее улучшение метода SGD, увеличивающие скорость сходимости было предложено в работе [2]. Вместо того чтобы высчитывать градиент в текущей точке, будем использовать градиент в точке “предсказанной” на основании сдвига, расчитанного на предыдущем шаге.

Для иллюстрации. Случай “чистых” моментов:

изменения для случая ускоренных градиентов Нестерова:

Формально это изменение запишется так:

\[\begin{array}{l} \Delta_{p+1} = \gamma \cdot \Delta_{p} + \eta \cdot \nabla L(w_{p} - \gamma \Delta_{p}), \\ w_{p+1} = w_{p} - \Delta_{p+1}. \end{array}\]

Здесь исходят из предположения, что основной вклад в вектор сдвига даёт первое слагаемое, а слагаемое с градиентом лишь “уточняет”. Логично поэтому уточняющий градиент расчитывать в окрестности новой точки, а не в текущей.

Параметр $\gamma$, как и ранее, выбирается около $0.9$.

Adagrad

Пока мы использовали единую скорость обучения $\eta$. Однако, когда мы обучаем нейронную сеть с миллионами параметров, это не очень хорошо. Какие-то параметры будут меняться чаще, какие-то реже. Интуитивно кажется, что параметры, которые меняются редко, надо менять с большей скоростью, чем те, которые меняются часто. В работе [3] предложен алгоритм, который подстраивает скорость обучения каждого из параметров в зависимости от того как сильно данные параметры менялись ранее.

Вместо единого скаляра $\eta$ в качестве скорости обучения, на каждой итерации будем определять вектор $\eta_p = (\eta^{(1)}_p,…, \eta^{(d)}_p)$. В данном случае $\eta$, которую мы использовали ранее будет просто начальной скоростью обучения. Для первой итерации мы положим $\eta^{(i)}_p = \eta, i=1,…,d$.

Итак, для каждой итерации $p$ у нас есть текущий вектор параметров:

\[w_p = (w^{(1)}_p,..., w^{(d)}_p),\]

и вектор градиента:

\[\nabla L(w_{p}) = (g^{(1)}_p,..., g^{(d)}_p).\]

Определим вспомогательный вектор:

\[G_p = (G^{(1)}_p,..., G^{(d)}_p)\]

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

\[G^{(i)}_p = \sum_{j=1}^{p} \left( g^{(i)}_j \right)^2, i=1,...,d\]

и, наконец, компоненты вектора скорости обучения $\eta_p$ определим как:

\[\eta^{(i)}_p = \frac \eta {\sqrt {G^{(i)}_p + \epsilon} }\]

$\epsilon$ - параметр страхующий от деления на нуль, обычно выбирается порядка $1e-8$. Изменение параметров осуществляем практически по той же формуле, что и раньше:

\[w_{p+1} = w_{p} - \eta_p \odot \nabla L(w_{p})\]

только вместо умножения скаляра на вектор, мы умножаем два вектора поэлементно (обозначая эту операцию $\odot$).

Adadelta

Основная проблема Adagrad заключается в том, что знаменатель в коэффициенте скорости обучения постоянно растёт, соответственно, через некоторое время для части параметров скорость обучения упадёт до нуля. Так же крайне важно подобрать “хорошие” начальные значения параметров, потому что если в начале обучения мы для некоторых параметров получим большие градиенты, то скорость обучения снизится и в дальнейшим уже не вырастет, не смотря на изменение параметров и их градиентов. Так же Adagrad не избавляет нас от необходимости выбирать начальное значение $\eta$. В статье [4] автор попытался избавиться от недостатков метода Adagrad.

Идея метода борьбы с непрерывным снижением скорости обучения следующая. Заменим сумму квадратов всех частных производных по некоторому параметру, на сумму только последних $W$ производных. Более точно заменим $\ell^2$ норму:

\[\sqrt {\sum_{j=1}^{p} \left( g^{(i)}_j \right)^2}\]

на среднее квадратичное последних $W$ производных:

\[RMS^{(i)}_p = \sqrt{\frac 1 W \sum_{j=p-W}^{p} \left( g^{(i)}_j \right)^2}, i=1,...,d\]

Кажется в этом случае мы избавляемся от проблемы как постоянного снижения скорости обучения, так и от того, что, при неудачном выборе начальных значений для каких-то параметров, частные производные окажутся слишком большими. Однако, применять идею непосредственно в таком виде неудобно чисто технически. Нам надо будет хранить $W$ последних градиентов, причем $W$ должно быть достаточно большим, чтобы всё это имело смысл. Поэтому в [4] среднее арифметическое квадратов частных производных предлагается приближать при помощи экспоненциально взвешенного скользящего среднего:

\[EG^{(i)}_{p+1} = \gamma \cdot EG^{(i)}_p + (1 - \gamma) \cdot \left( g^{(i)}_p \right)^2, i=1,...,d\]

при определенном подборе $\gamma$ можно считать:

\[RMS^{(i)}_p \approx \sqrt { EG^{(i)}_p }.\]

Таким образом, заменяя формулу изменения параметров из Adagrad на:

\[w_{p+1} = w_{p} - \frac \eta {\sqrt {EG_{p+1} + \epsilon} } \odot \nabla L(w_{p}),\]

мы избавляемся от постоянного снижения скорости обучения.

Остается проблема с выбором параметра $\eta$ - начальной скорости обучения. По этому поводу автор статьи [4] предлагает следующие. Обозначим изменение $i$-го параметра на $p$ шаге как $\Delta^{(i)}_p$ и, соответсвенно, изменение параметров как:

\[w_p = w_{p - 1} - \Delta_{p}.\]

кроме подсчета скользящего среднего квадратов градиентов, озаботимся еще подсчетом скользящего среднего $\Delta_p$:

\[E\Delta^{(i)}_p = \gamma \cdot E\Delta^{(i)}_{p-1} + (1 - \gamma) \cdot \left( \Delta^{(i)}_p \right)^2, i=1,...,d\]

и будем изменение параметров определять как:

\[\Delta_{p} = {\sqrt \frac {E\Delta_{p-1} + \epsilon} {EG_{p} + \epsilon} } \odot \nabla L(w_{p})\]

Замечание

1. Отметим, что скользящее среднее в числители вычислено для предыдущего шага, поскольку для текущего шага $p$ нам $\Delta_p$ еще не известно.

2. Не смотря на то, что $\epsilon$ в числителе и знаменателе одно и тоже, оно, имеет разную смысловую нагрузку. В знаменателе, мы при помощи $\epsilon$ избегаем проблемы деления на нуль, а в числителе - проблемы остановки обучения параметра, если скользящая средняя квадратов предыдущих сдвигов стала слишком мала (это как минимум происходит на самом первом шаге поскольку все скользящие среднии мы в алгоритме инициализируем нулями).

Adam (Adaptive Moment Estimation)

В статье [5] предлагают следить за скользящим средним градиентов и квадратов градиентов штрафной функции:

\[m_p = \beta_1 m_{p-1} + (1 - \beta_1) \cdot \nabla L\left(w_{p-1}\right)\] \[v_p = \beta_2 v_{p-1} + (1 - \beta_2) \cdot \left(\nabla L\left(w_{p-1}\right) \right)^2\]

Аналогично как это было в Adadelta эти скользящие среднии приближают первый и второй момент градиентов. $v_p$ предлагается использовать для изменения скорости обучения, а $m_p$ для замены обычного градиента вычисленного на текущем наборе параметров. Последнее базируется на идеи, которую уже применяли в методе Моментов, а именно сохранять инерцию сдвига параметров от предыдущих итераций.

Авторы статьи отмечают, что поскольку начальные значения $m_0, v_0$ инициализируются нулями, а коэффициенты $\beta_1, \beta_2$ выбираются близкими к единице, то “моменты” сохраняют сдвиг к нулю. Чтобы побороть эту проблему, предлагается для изменения параметров вместо непосредственно $m_p, v_p$ использовать:

\[\hat{m}_p = \frac {m_p} {1 - \beta_1^p}\] \[\hat{v}_p = \frac {v_p} {1 - \beta_2^p}\]

Формула изменения параметров запишется в виде:

\[w_{p} = w_{p - 1} - \frac {\eta \cdot \hat{m}_{p}} {\sqrt {\hat{v}_{p}} + \epsilon}\]

---

Литература

1. N. Qian, “On the momentum term in gradient descent learning algorithms.” Neural Networks : The Official Journal of the International Neural Network Society, 1999, 12(1), 145–151.

2. Y. Nesterov, “A method for unconstrained convex minimization problem with the rate of convergence $o(\frac 1 {k^2})$.” Doklady ANSSSR, 1983, vol. 269, pp. 543– 547.

3. J. Duchi, E. Hazan, Y. Singer, “Adaptive Subgradient Methods for Online Learning and Stochastic Optimization”. 2011, Journal of Machine Learning Research, 12, 2121–2159.

4. M. D. Zeiler, “ADADELTA: An Adaptive Learning Rate Method”. arXiv:1212.5701 2012

5. D. P. Kingma, J. L. Ba, “Adam: A Method for Stochastic Optimization”. arXiv:1412.6980 2014