1. Пятьдесят оттенков градиентного спуска

Маша Нестерова, хозяйка машин лёрнинга, собрала два наблюдения: \(x_1 = 1, x_2 = 2\), \(y_1 = 2, y_2 = 3\). Она собирается обучить линейную регрессию \(y = w \cdot x\). В качестве функции потерь она использует квадратичную функцию потерь, \(MSE\).

а) Найдите теоретическую оценку неизвестного параметра \(w\). Для этого выпишите функцию потерь, по-честному возьмите от неё производную, приравняйте её к нулю и решите получившееся уравнение.

Решение

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

\[ MSE = \frac{1}{2} \cdot ((2 - w)^2 + (3 - 2 w)^2) \to \min_{w} \]

Берём производную, решаем уравнение и получаем ответ:

\[ MSE_w^{'} = - (2 - w) - 2 (3 - 2 w) = 0 \Rightarrow \hat w = \frac{8}{5} = 1.6 \]

Убедимся в том, что это точка минимума. Для этого возьмём вторую производную и посмотрим на её знак

\[ MSE_w^{''} = w + 4 w = 5w > 0. \]

Видно, что мы действительно в точке минимума.

б) Сделайте три шага градиентного спуска. В качестве стартовой точки используйте \(w_0 = 0\). В качестве скорости обучения возьмите \(\eta = 0.1\).

Решение

Чтобы сделать три шага градиентного спуска, нужно найти градиент. Наша функция потерь выглядит как

\[ L(w) = (y - w x)^2. \]

Мы подбираем один параметр, значит градиентом в данном случае будет просто одно число — производная по этому параметру.

\[ \nabla_w L(w, x, y) = \frac{\partial L}{\partial w} = -2 x (y - w x). \]

Градиент – направление наискорейшего роста функции. Чтобы минимизировать функцию, будем идти в направлении антиградиента с какой-то скоростью обучения \(\eta.\) Стартовая точка \(w_0 = 0\). Мы хотим сделать шаг

\[ w_1 = w_0 - \eta \cdot \nabla_w L(w_0) \]

Посчитаем градиент в точке \(w_0\) по всей выборке:

\[ \nabla_w L(w_0) = \frac{1}{n} \cdot \sum_{i = 1}^n \nabla_w L(w_0, x_i, y_i) = \frac{1}{2} \cdot (-2(2- w_0) - 2\cdot 2(3 - 2 w_0)) = -8 \]

Делаем первый шаг:

\[ w_1 = 0 + 0.1 \cdot 8 = 0.8 \]

По аналогии, второй шаг:

\[\begin{equation*} \begin{aligned} & \nabla_w L(w_1) = \frac{1}{2} \cdot (-2(2 - w_1) - 2\cdot 2(3 - 2 w_1)) = -4 \\ & w_2 = w_1 - \eta \cdot \nabla_w L(w_1) = 0.8 + 0.1 \cdot 4 = 1.2 \end{aligned} \end{equation*}\]

По аналогии, третий шаг:

\[\begin{equation*} \begin{aligned} & \nabla_w L(w_2) = \frac{1}{2} \cdot (-2(2 - w_2) - 2\cdot 2(3 - 2 w_2)) = -2 \\ & w_3 = w_2 - \eta \cdot \nabla_w L(w_2) = 1.2 + 0.1 \cdot 2 = 1.4 \end{aligned} \end{equation*}\]

Почти добежали до оптимальной точки. Чем ближе мы к точке оптимума, тем меньше значение градиента и тем меньше наши шаги. Тем не менее, если не аккуратно выбрать скорость обучения \(\eta\), можно случайно перепрыгнуть оптимум либо вообще не дойти до него за обозримое число итераций.

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

Решение

Теперь то же самое, но градиентный спуск стохастический. Считать градиент по всей выборке – дорого. Нужно найти его для каждого наблюдения, а затем посчитать среднее. На каждой итерации сложность по времени такого алгоритма будет \(O(n).\)

Стохастический градиентный спуск, SGD, предлагает считать градиент в случайной точке и делать шаг. Тогда на каждой итерации сложность по времени будет \(O(1).\) Нам придётся сделать больше шагов, траектория будет более шумной. Однако практика показывает, что такой алгоритм сойдётся быстрее. Обычно градиент оценивают не по одному наблюдению, а по небольшой случайной подвыборке, батчу.

Первый шаг:

\[\begin{equation*} \begin{aligned} & \nabla_w L(w_0) = -2(2 - w_0 \cdot 1) = -4 \\ & w_1 = w_0 - \eta \cdot \nabla_w L(w_0) = 0 + 0.1 \cdot 4 = 0.4 \end{aligned} \end{equation*}\]

Второй шаг:

\[\begin{equation*} \begin{aligned} & \nabla_w L(w_1) = -2 \cdot 2 \cdot (3 - w_1 \cdot 2) = - 8.8 \\ & w_2 = w_1 - \eta \cdot \nabla_w L(w_1) = 0.4 + 0.1 \cdot 8.8 = 1.28 \end{aligned} \end{equation*}\]

Третий шаг:

\[\begin{equation*} \begin{aligned} & \nabla_w L(w_2) = -2(2 - w_1 \cdot 1) = -1.44 \\ & w_3 = w_2 - \eta \cdot \nabla_w L(w_2) = 1.28 + 0.144 = 1.424 \end{aligned} \end{equation*}\]

Четвёртый шаг:

\[\begin{equation*} \begin{aligned} & \nabla_w L(w_3) = -2 \cdot 2(3 - w_3 \cdot 2) \\ & w_4 = w_3 - \eta \cdot \nabla_w L(w_4) = 1.424 + 0.1 \cdot 0.608 = 1.4848 \end{aligned} \end{equation*}\]

г) Если вы добрались до этого пункта, вы поняли градиентный спуск. Маша довольна. Начинаем заниматься тупой технической бессмыслицей. Сделайте два шага Momentum SGD. Возьмите \(\alpha = 0.9, \eta = 0.1\)

Решение

Momentum SGD[1] — то же самое, но с учётом инерции. В переменной \(h_t\) мы будем копить свои знания о градиенте, а затем делать шаг на накопленную величину. Параметр \(\alpha\) тут отвечает за забывание накопленной инерции.

\[\begin{equation*} \begin{aligned} & h_t = \alpha \cdot h_{t-1} + \eta \cdot \nabla_w L(w_{t-1}) \\ & w_t = w_{t-1} - h_t \end{aligned} \end{equation*}\]

На первом шаге инерция нулевая, мы только начинаем её копить:

\[\begin{equation*} \begin{aligned} & \nabla_w L(w_0) = -2 \cdot 1\cdot (2 - w_0 \cdot 1) = -4 \\ & h_1 = 0.9 \cdot 0 + 0.1 \cdot (-4) = -0.4 \\ & w_1 = 0 + 0.4 = 0.4 \end{aligned} \end{equation*}\]

На втором шаге появляется накопленная инерция \(\alpha \cdot h_{t-1}\):

\[\begin{equation*} \begin{aligned} & \nabla_w L(w_1) = -2 \cdot 2 \cdot (3 - w_1 \cdot 2) = -8.8 \\ & h_2 = 0.9 \cdot (-0.4) + 0.1 \cdot (-8.8) = -1.24 \\ & w_2 = 0.4 + 1.24 = 1.64 \end{aligned} \end{equation*}\]

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

д) Сделайте два шага Momentum SGD с коррекцией Нестерова.

Решение

Nesterov SGD работает как momentum, но мы при этом пытаемся смотреть себе под ноги. Мы всё-равно сделаем шаг на величину инерции. Имеет смысл сразу же считать градиент в той точке, где мы окажемся после этого шага.

\[\begin{equation*} \begin{aligned} & h_t = \alpha \cdot h_{t-1} + \eta \cdot \nabla_w L(w_{t-1} - \alpha \cdot h_{t-1}) \\ & w_t = w_{t-1} - h_t \end{aligned} \end{equation*}\]

Раньше мы ходили по красной траектории. Мы искали градиент в той точке, где мы стоим, ходили по нему и по инерции. Теперь мы будем ходить по синей траектории. Сначала делаем шаг по инерции, а затем находим градиент и делаем ход по нему. Благодаря этому алгоритм будет сходиться быстрее.

Первый шаг никак не изменится, на втором шаге мы должны посчитать значение градиента немного в другой точке

\[\begin{equation*} \begin{aligned} & \nabla_w L(w_1 - \alpha h_1) = -2 \cdot 2 \cdot (3 - (w_1 - \alpha \cdot h_1) \cdot 2) \\ & \nabla_w L(w_1 - \alpha h_1) = -4(3 - (0.4 + 0.9 \cdot 0.4) \cdot 2) = -5.92 \\ & h_t = 0.9 \cdot (-0.4) + 0.1 \cdot (-5.92) = -0.952 \\ & w_2 = 0.4 + 1.256 = 1.352 \end{aligned} \end{equation*}\]

Видно, что мы движемся более аккуратно по сравнению с momentum и не перелетаем точку оптимума на втором шаге.

е) Сделайте два шага RMSprop. Возьмите \(\alpha = 0.9, \eta = 0.1\)

Решение

Смысл RMSprop заключается в том, чтобы для каждого параметра ввести свою, индивидуальную скорость обучения. В формулах появляется индекс \(j,\) который отвечает за конкретный параметр. Здесь \(g_{j,t} = \nabla_{w_j} L(w_{t}).\)

\[\begin{equation*} \begin{aligned} & v_{j,t} = \alpha \cdot v_{j,t-1} + (1 - \alpha) \cdot (g_{j,t-1})^2 \\ & w_{j,t}= w_{j,t-1} - \frac{\eta_t}{\sqrt{v_{j,t} + \epsilon}} \cdot g_{j,t-1} \end{aligned} \end{equation*}\]

Если у нас есть случайная величина \(X\) и мы хотим посчитать для неё дисперсию, мы можем это сделать по формуле \(Var(X) = \mathbb{E}(X^2) - \mathbb{E}^2(X).\) Величина \(g_{j,t} = \nabla_{w_j} L(w_{t})\) — это оценка градиента, то есть оценка для \(\mathbb{E}(\nabla_{w_j} L(w_t)).\) Величина \(g^2_{j,t}\) будет оценкой для второго момента, а это почти дисперсия. Отметчу, что это ни в коем случае не формальное доказательство, а «показательство».

Получается, что в первой формуле мы для каждого параметра оцениваем, насколько большой разброс у его градиента в текущей точке. Если разброс большой, мы делаем шаги медленно, так как величина \(v_{j,t}\) в знаменателе оказывается высокой и скорость обучения для параметра \(w_j\) оказывается низкой. По аналогии, если разброс не такой большой, мы движемся более широкими шагами.

Первый шаг:

\[\begin{equation*} \begin{aligned} & \nabla L(w_0) = -2(2 - w_0 \cdot 1) = -4 \\ & v_1 = 0 + 0.1 \cdot (-4)^2 = 1.6 \\ & w_1 = 0 + \frac{0.1}{\sqrt{1.6}} \cdot 4 = 0.31 \end{aligned} \end{equation*}\]

Второй шаг:

\[\begin{equation*} \begin{aligned} & \nabla L(w_1) = -2 \cdot 2 \cdot (3 - w_1 \cdot 2) = -9.47 \\ & v_2 = 0.9 \cdot 1.6 + 0.1 \cdot (-9.47)^2 = 10.41 \\ & w_2 = 0.31 + \frac{0.1}{\sqrt{10.41}} \cdot 9.41 = 0.61 \end{aligned} \end{equation*}\]

ж) Сделайте два шага Adam. Возьмём \(\beta_1 = \beta_2 = 0.9, \eta = 0.1\)

Решение

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

\[\begin{equation*} \begin{aligned} &h_{j,t} = \frac{\beta_1 \cdot h_{j,t-1} + (1 - \beta_1) \cdot g_{j,t}}{1 - \beta_1^t} \\ &v_{j,t} = \frac{\beta_2 \cdot v_{j,t-1} + (1 - \beta_2) \cdot g_{j,t}^2}{1 - \beta_2^t} \\ &w_{j,t} = w_{j,t-1} - \frac{\eta_t}{\sqrt{v_{j,t} + \varepsilon}} \cdot h_{j,t} \end{aligned} \end{equation*}\]

Первый шаг:

\[\begin{equation*} \begin{aligned} & g_1 = \nabla_w L(w_0) = -2(2 - w_0 \cdot 1) = -4 \\ & h_1 = \frac{0.9 \cdot 0 + 0.1 \cdot -4}{0.1} = -4 \\ & v_1 = \frac{0.9 \cdot 0 + 0.1 \cdot (-4)^2}{0.1} = 4^2 \\ & w_1 = 0 + \frac{0.1}{\sqrt{4^2}} \cdot 4 = 0.1 \end{aligned} \end{equation*}\]

Второй шаг:

\[\begin{equation*} \begin{aligned} & g_2 = \nabla_w L(w_0) = -4(3 - w_1 \cdot 2) = --3.2 \\ & h_2 = \frac{0.9 \cdot (-4) + 0.1 \cdot (-3.2)}{0.19} = -3.58 \\ & v_2 = \frac{0.9 \cdot (-4)^2 + 0.1 \cdot (-3.2)^2}{0.19} = 81.15 \\ & w_2 = 0.1 + \frac{0.1}{\sqrt{81.15}} \cdot 3.58 = 0.14 \end{aligned} \end{equation*}\]

з) В Rmsprop и Adam мы находим индивидуальные скорости обучения для всех параметров, корректируя их на второй момент градиента. Кажется, что хорошо было бы корректировать их на настоящую дисперсию, а не на второй момент.

Придумайте, как внести в Adam корректировку скорости обучения именно на дисперсию. Выпишите соотвествующие уравнения и получите метод AdaBelief.

Решение

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

\[\begin{equation*} \begin{aligned} &h_{j,t} = \frac{\beta_1 \cdot h_{j,t-1} + (1 - \beta_1) \cdot g_{j,t}}{1 - \beta_1^t} \\ &v_{j,t} = \frac{\beta_2 \cdot v_{j,t-1} + (1 - \beta_2) \cdot (g_{j,t} - h_{jt})^2}{1 - \beta_2^t} \\ &w_{j,t} = w_{j,t-1} - \frac{\eta_t}{\sqrt{v_{j,t} + \varepsilon}} \cdot h_{j,t} \end{aligned} \end{equation*}\]

На картинке ниже сравнивается сходимость разных градиентных спусков между собой. На ней нет Adam, но зато есть несколько других вариаций градиентного спуска, которые мы не разобрали в задачках выше. Они являются вариациями адаптивного градиентного спуска и почитать про них подробнее можно в статье, из которой взята анимация[2].

На картинке видно, что SGD движется в сторону оптимума очень медленно. Momentum у него довольно сильно выигрывает в скорости, однако из-за накопленной инерции, поначалу, momentum уходит куда-то не туда и делает большой зиг-заг. Momentum с поправкой Нестерова делает зиг-заг поменьше и добирается до оптимума быстрее.

В таких методах как Adagrad, Adadelta и Rmsprop скорость обучения подбирается индивидуально для каждого параметра. Мы видим, что эти алгоритмы добегают до точки оптимума быстрее всего.

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

Adam – это база. Тем не менее, методы оптимизации не стоят на месте и каждый год появляются более новые модернизации градиентного спуска.

---

[1]

Красивый визуал про momentum SGD

[2]

Как работают разные градиентные спуски