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

Проблема предыдущего алгоритма заключается в том, что чтобы определить новое приближение вектора весов необходимо вычислить градиент от каждого элемента выборки, что может сильно замедлять алгоритм. Идея ускорения алгоритма заключается в использовании только одного элемента, либо некоторой подвыборки для подсчета нового приближения весов. То есть теперь новое приближение будет вычисляться как ${\bf w}^{(t+1)}={\bf w}^{(t)} - h\nabla \mathscr{L}_i({\bf w}^{(t)})$, где $i$ $-$ случайно выбранный индекс. Так как теперь направление изменения $\bf w$ будет определяться за $O(1)$, подсчет $Q$ на каждом шаге будет слишком дорогостоящим. Для того, чтобы ускорить оценку $Q$, будем использовать приближенную рекуррентную формулу. Можно выбрать одну из следующих формул:

среднее арифметическое: $\overline{Q}_m = \dfrac{1}{m}\varepsilon_m + \dfrac{1}{m}\varepsilon_{m - 1} + \dfrac{1}{m}\varepsilon_{m - 2} + \dots = \dfrac{1}{m}\varepsilon_m + (1 - \dfrac{1}{m})\overline{Q}_{m-1}$;
экспоненциальное скользящее среднее: $\overline{Q}_m = \lambda\varepsilon_m + (1 - \lambda)\varepsilon_{m - 1} + (1 - \lambda)^2\varepsilon_{m - 2} + \dots = \lambda\varepsilon_m + (1-\lambda)\overline{Q}_{m - 1},$ где $\lambda$ $-$ темп забывания предыстории ряда.

Псевдокод

def SGD(X, h, $\lambda$):  # где X $-$ выборка, h $-$ градиентный шаг, а $\lambda$ $-$ темп забывания 
   ${\bf w} =$ initialize_weights()  # инициализировать веса 
   $\overline{Q} = \frac{1}{l} \sum_{i=1}^{l}\mathscr{L}_i({\bf w})$ # инициализировать оценку функционала 
   while $Q$ not converges or ${\bf w}$ not converges:
       $i =$ rand() % $l$  # случайно выбрать элемент, по которому будет считаться градиент 
       $\varepsilon = \mathscr{L}_i({\bf w})$  # вычислить потерю 
       ${\bf w} = {\bf w} - h \nabla \mathscr{L}_i({\bf w})$ # обновить вектор весов в направлении антиградиента
       $\overline{Q} = \lambda\varepsilon + (1 - \lambda)\overline{Q}$ # оценить функционал
   return w

Эвристики

Существует несколько способов инициализировать веса:

${\bf w} = {\bf 0}$;
$w_j = random(-\dfrac{1}{2n}, \dfrac{1}{2n})$. Стоит брать небольшие случайные веса, так как если выбрать их слишком большими, в некоторых случаях (к примеру в случае нейрона с функцией активациии равной арктангенсу) большие начальные значения веса могут привести в область с малыми по модулю производными, в связи с чем из такой области будет трудно выбраться;
$w_j = \dfrac{\langle y, f_j \rangle}{\langle f_j, f_j \rangle}$, где $f_j = (f_j(x_i))_{i=1}^l$. Оценка оптимальная в случае, если функция потерь квадратична и признаки нескоррелированы, то есть $\langle f_j, f_k \rangle = 0, j \neq k$.

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

При выборе случайного элемента можно использовать следующие эвристики:

брать объекты из разных классов;
брать объекты, на которых ошибка больше, то есть чем меньше отступ (в метрических классификаторах расстояние от разделяющей поверхности до объекта) i-го объекта $M_i$, тем больше вероятность взять этот объект;
брать объекты, на которых уверенность меньше, то есть чем меньше $|M_i|$, тем больше вероятность взять этот объект;
не брать объекты, на которых уже высокая уверенность ($M_i > \mu_+$) либо не брать объекты-выбросы ($M_i<\mu_i$);

Выбирать величину градиентного шага можно следующими способами:

$h_t = \dfrac{1}{t}$;
метод скорейшего градиентного спуска: $\mathscr{L}_i({\bf w} - h\nabla \mathscr{L}_i({\bf w})) \rightarrow \min\limits_h$;
при квадратичной функции потерь можно использовать $h = ||x_i||^2$;
иногда можно выполнять пробные шаги, а именно увеличивать $h$ для выбивания процесса из локальных минимумов;
метод Левенберга-Марквардта;

Регуляризация

Основным способом уменьшить переобучение является регуляризация, т.е. сокращение весов. Будем штрафовать за увеличение нормы вектора весов, для этого перепишем функцию потерь $\tilde{\mathscr{L}}_i({\bf w}) = \mathscr{L}_i({\bf w}) + \dfrac{\tau}{2}||w||^2 = \mathscr{L}_i({\bf w}) + \dfrac{\tau}{2} \sum\limits_{j=1}^nw_j^2 \rightarrow \min\limits_w$, где $\tau$ $-$ коэффициент регуляризации.

Тогда градиент будет следующим: $\nabla \tilde{\mathscr{L}}_i({\bf w}) = \nabla \mathscr{L}_i({\bf w}) + \tau {\bf w}$, а градиентный шаг будет выглядеть так: ${\bf w} = {\bf w}(1 - h\tau) - h\nabla \mathscr{L}_i({\bf w})$.

Достоинства и недостатки

Достониства:

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

Недостатки

нет универсального набора эвристик, их нужно выбирать для конкретной задачи отдельно;

Пример кода scikit-learn

Классификатор sklearn.linear_model.SGDClassifier имеет несколько параметров, например:

loss $-$ функция потерь. По умолчанию используется "hinge", дающая алгоритм линейного SVM;

penalty $-$ метод регуляризации. По умолчанию "l2";

alpha $-$ $\tau$, коэффициент регуляризации;

learning_rate $-$ алгоритм изменения градиентного шага;

eta0 $-$ начальный градиентный шаг;

shuffle перемешивать тренировочную выборку после каждой итерации;

Импортируем нужные библиотеки:

from sklearn.linear_model import SGDClassifier
from sklearn import datasets
from sklearn.model_selection import train_test_split

Выберем тренировочное и тестовое множества:

iris = datasets.load_iris()

X = iris.data
y = iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3)

Обучение:

clf = SGDClassifier(shuffle = True)
model = clf.fit(X_train, y_train)

Предсказание:

y_pred = model.predict(X_test)
model.score(X_test, y_test)

См. также

Источники информации

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

Содержание

Обычный градиентный спуск