Градиентный спуск - численный способ минимизации Loss-a. Простейший случай

Напомним, что градиент функции нескольких переменных - это вектор направления наибольшего роста функции.

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

Продемонстрируем на примере решении задачи линейной регрессии с MSE Loss и регуляризатором ElasticNet. Она не решается аналитически, и необходимо численно минимизировать

\[ \mathcal{L}(w)=\frac{1}{N} \sum_{i=1}^{N}\left( X_{i \alpha} w_\alpha-y_i\right)^2+\tau \sum_{i=1}^N w_i^2+\mu \sum_{i=1}^N\left|w_i\right| \]

\[ \mathcal{L}(w) \longrightarrow \min _w \]

Общий алгоритм градиентного спуска будет следующим образом:

0. Фиксируем малый \(\varepsilon\) - условие остановки алгоритма.

1. Выберем начальное приближение \(w^{(0)} \in \mathbb{R}^m\). Как правило, инициализируют случайным образом.

2. Каждую последующую точку выбираем в направлении обратном градиенту \(\mathcal{L}\) - таким образом мы двигаемся в направлении минимизации \(\mathcal{L}\).

\[w^{(n+1)}_k=w^{(n)}_k-\alpha \cdot \left.\frac{\partial \mathcal{L}(w)}{\partial w_{k}}\right|_{w^{(n)}} \]

Здесь \(\alpha\) - так называемый шаг градиентного спуска (или learning rate). Если он будет слишком большим, мы не упадём в минимум и будем туда-сюда скакать около него. Если он будет слишком маленьким, мы рискуем так и не дойти до минимума. Таким образом, он является подбираемым гиперпараметром.

3. Если на каком-то шаге получилось, что

\[|\mathcal{L}(w^{(n+1)}) - \mathcal{L}(w^{(n)})| < \varepsilon\]

То алгоритм останавливается и последнее получившееся \(w_{final}=w^{(n+1)}\) принимается за окончательный ответ. Иначе на шаг 2.

Стоит отметить, что по хорошему, надо строить зависимость \(\mathcal{L}(n)\). Т.к. для произвольной функции или для данных гиперпараметров алгоритм может и не сойтись. В идеальном случае, это будет монотонно стремящаяся к нулю функция. В плохом - сильно осциллирующая краказябра.

Естественно, это самая простая реализация градиентного спуска. Её можно существенно улучшить различными приёмчиками. В частности, learning rate можно сделать зависимым от \(n\). К примеру,

\[ \alpha(n) = \frac{1}{n} \]

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

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

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

Решить эту проблему помогает стохастический градиентный спуск. Его идея - вычислять градиент функции потерь на каждом шаге алгоритма не по всей выборке, а по некоторой подвыборке (batch), которая будет меняться каждый шаг.

Если старый градиент рассчитывался по всей выборке

\[ \nabla \mathcal{L}=\frac{1}{N} \sum_{i=1}^N\left(\nabla \mathcal{L}_i\right) \]

то на batch-е размером \(B \ll N\) градиент не должен сильно поменяться

\[ \nabla \mathcal{L} \approx \frac{1}{B} \sum_{i=1}^B\left(\nabla \mathcal{L}_i\right) \]

Иными словами, мы «нарезаем» нашу обучающую выборку из \(N\) элементов на \(N/B\) кусков, на каждом из которых вычисляем градиент поочередно. Таким образом вся обучающая выборка используется, но нам нет необходимости суммировать огромное количество слагаемых для одного шага алгоритма.

Один проход по всей выборке называется эпохой. После окончания эпохи (прохода по всей выборке) можно опять «нарезать» выборку на \(N/B\) частей случайным образом (чтобы исключить какие-либо корреляции) и повторять процесс. В таком случае, как правило, строят зависимость \(\mathcal{L}\) от \(k\)-ой эпохи.

Понятно, что процесс будет стохастическим, и на каждом шаге алгоритма мы будем чутка отклоняться от направления на минимум. Тем не менее, этот шум даже полезен, т.к. он помогает не проваливаться в узкие локальные минимумы - эмпирический факт :).

# Реализация градиентного спуска
# Ищем минимум следующей функции

import numpy as np
import matplotlib.pyplot as plt

def f(x1, x2):
    return 0.5*x1**2 + (5/2)*x2**2 - x1*x2 - 2*(x1 + x2)

def gradient(x1, x2):
    return np.array([-2 + x1 - x2, -2 - x1 + 5*x2])

def norm(matrice_1x2):
    n_line = matrice_1x2.shape[0]
    N = 0
    for i in range(n_line):
        N += matrice_1x2[i]**2
    return np.sqrt(N)

x1, x2 = -25, -35
alpha = 0.1
epsilon = pow(10,-6)

grad_f = gradient(x1, x2)
n_grad = norm(grad_f)

i = 1
evolution_X1_X2 = [[x1, x2]]
while n_grad > epsilon:

    direction = -grad_f
    x1, x2 = x1 + alpha*direction[0], x2 + alpha*direction[1]
    evolution_X1_X2 = np.vstack((evolution_X1_X2, [x1, x2]))
    grad_f = gradient(x1, x2)
    n_grad = norm(grad_f)
    i += 1

evolution_X1 = evolution_X1_X2[:, 0]
evolution_X2 = evolution_X1_X2[:, 1]


x1 = np.linspace(-30, 25, 150)
x2 = np.linspace(-40, 20, 150)
X1, X2 = np.meshgrid(x1, x2)
Z = f(X1, X2)

fig = plt.figure(figsize = (10,7))
plt.grid(False)
plt.imshow(Z, extent = [-30,25,-40,20], origin = 'lower', cmap = 'jet', alpha = 1)
plt.title("Evolution of the cost function during gradient descent with level circles", fontsize=15)
plt.plot(evolution_X1, evolution_X2)
plt.plot(evolution_X1, evolution_X2, '*', label = "Cost function")
plt.xlabel('x1', fontsize=11)
plt.ylabel('x2', fontsize=11)
plt.colorbar()
plt.legend(loc = "upper right")
plt.show()