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

Стохастический градиентный спуск (Stochastic Gradient Descent - SGD) - это простой, но очень эффективный подход для обучения линейных классификаторов и регрессоров под выпуклые функции потерь, такие как (линейные) Метод опорных векторов и Логистическая регрессия. Несмотря на то, что SGD существует в сообществе машинного обучения уже давно, значительное внимание к нему в контексте крупномасштабного обучения было привлечено совсем недавно.

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

Строго говоря, SGD - это всего лишь техника оптимизации и не соответствует определенному семейству моделей машинного обучения. Это лишь способ обучения модели. Часто экземпляр SGDClassifier или SGDRegressor будет иметь эквивалентную модель в scikit-learn API, потенциально использующий другую технику оптимизации. Например, использование SGDClassifier(loss='log_loss') приводит к логистической регрессии, то есть к модели, эквивалентной LogisticRegression, которая подгоняется с помощью SGD вместо того, чтобы подгоняться с помощью одного из других алгоритма в LogisticRegression. Аналогично, SGDRegressor(loss='squared_error', penalty='l2') и Ridge решают одну и ту же задачу оптимизации разными средствами.

Преимуществами стохастического градиентного спуска являются:

• Эффективность.

• Простота реализации (много возможностей для настройки кода).

К недостаткам стохастического градиентного спуска относятся:

• Для SGD требуется ряд гиперпараметров, таких как параметр регуляризации и количество итераций.

• SGD чувствителен к масштабированию признаков.

Предупреждение

Убедитесь, что вы перемешиваете (shuffle) ваши обучающие данные перед обучением модели или используйте shuffle=True для перестановки после каждой итерации (используется по умолчанию).

Также, в идеале, признаки должны быть стандартизированы с помощью, например, make_pipeline(StandardScaler(), SGDClassifier()) (см. Pipelines).

1.5.1. Классификация

Класс SGDClassifier реализует обычную стохастическую процедуру обучения методом градиентного спуска, которая поддерживает различные функции потерь и штрафы для классификации. Ниже показана граница принятия решения классификатора SGDClassifier, обученного с hinge loss, что эквивалентно линейному SVM.

Как и другие классификаторы, SGD должен быть оснащен двумя массивами: массивом X формы (n_samples, n_features), содержащим обучающие выборки, и массивом y формы (n_samples,), содержащим целевые значения (метки классов) для обучающих выборок:

>>> from sklearn.linear_model import SGDClassifier
>>> X = [[0., 0.], [1., 1.]]
>>> y = [0, 1]
>>> clf = SGDClassifier(loss="hinge", penalty="l2", max_iter=5)
>>> clf.fit(X, y)
SGDClassifier(max_iter=5)

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

>>> clf.predict([[2., 2.]])
array([1])

SGD подгоняет линейную модель к обучающим данным. Атрибут coef_ содержит параметры модели:

>>> clf.coef_
array([[9.9..., 9.9...]])

Атрибут intercept_ содержит перехват (он же смещение или отклонение):

>>> clf.intercept_
array([-9.9...])

Использует ли модель перехват, т.е. смещенную гиперплоскость, контролируется параметром fit_intercept.

Подписанное расстояние до гиперплоскости (вычисляемое как произведение точек между коэффициентами и входной выборкой плюс перехват) задается SGDClassifier.decision_function:

>>> clf.decision_function([[2., 2.]])
array([29.6...])

Конкретная функция потерь может быть задана с помощью параметра loss. SGDClassifier` поддерживает следующие функции потерь:

• loss="hinge": (soft-margin) линейный метод опорных векторов,

• loss="modified_huber": сглаженные hinge loss,

• loss="log_loss": логистическая регрессия,

• и все регрессионные потери ниже. В этом случае цель кодируется как -1 или 1, а задача рассматривается как задача регрессии. Предсказанный класс соответствует знаку предсказанной цели.

Формулы см. в математическом разделе ниже.

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

Использование loss="log_loss" или loss="modified_huber" включает метод predict_proba, который дает вектор вероятностных оценок \(P(y|x)`\) на выборку \(x\):

>>> clf = SGDClassifier(loss="log_loss", max_iter=5).fit(X, y)
>>> clf.predict_proba([[1., 1.]]) 
array([[0.00..., 0.99...]])

Конкретный штраф может быть задан с помощью параметра penalty. SGD поддерживает следующие штрафы:

• penalty="l2": L2 норма штрафа на coef_.

• penalty="l1": L1 норма штрафа на coef_.

• penalty="elasticnet": выпуклая комбинация штрафов L1 и L2; (1 - l1_ratio) * L2 + l1_ratio * L1.

По умолчанию задано penalty="l2". Штраф L1 приводит к разреженным решениям, обращая большинство коэффициентов в ноль. Эластичная сеть [11] решает некоторые недостатки штрафа L1 при наличии сильно коррелированных признаков. Параметр l1_ratio управляет выпуклой комбинацией штрафов L1 и L2.

SGDClassifier поддерживает многоклассовую классификацию, объединяя несколько бинарных классификаторов по схеме “один против всех” (OVA). Для каждого из классов \(K\) обучается бинарный классификатор, который различает этот и все остальные классы \(K-1\). Во время тестирования мы вычисляем показатель доверия (т.е. подписанные расстояния до гиперплоскости) для каждого классификатора и выбираем класс с наибольшим доверием. На рисунке ниже показан подход OVA на наборе данных Ирис. Пунктирные линии представляют три классификатора OVA; цвета фона показывают поверхность принятия решений, вызванную тремя классификаторами.

В случае многоклассовой классификации coef_ - это двумерный массив форм (n_classes, n_features), а intercept_ - одномерный массив форм (n_classes,). i-я строка coef_ содержит вектор веса OVA-классификатора для i-го класса; классы индексируются в порядке возрастания (см. атрибут classes_).

Обратите внимание, что в принципе, поскольку они позволяют создать вероятностную модель, loss="log_loss" и loss="modified_huber" больше подходят для классификации “один против всех”.

SGDClassifier поддерживает взвешенные классы и взвешенные экземпляры через параметры обучения class_weight и sample_weight. Дополнительную информацию см. в примерах ниже и в строке документации SGDClassifier.fit.

SGDClassifier поддерживает усредненный SGD (ASGD) [10]. Усреднение можно включить, установив average=True. ASGD выполняет те же обновления, что и обычный SGD (см. Математическая формулировка), но вместо использования последнего значения коэффициентов в качестве атрибута coef_ (т.е. значения последнего обновления), вместо coef_ устанавливается среднее значение коэффициентов по всем обновлениям. То же самое делается для атрибута intercept_. При использовании ASGD скорость обучения может быть больше и даже постоянной, что на некоторых наборах данных приводит к ускорению времени обучения.

Для классификации с логистическими потерями доступен другой вариант SGD со стратегией усреднения - алгоритм Stochastic Average Gradient (SAG), доступный в качестве алгоритма в LogisticRegression.

Примеры:

• SGD: Maximum margin separating hyperplane,

• Plot multi-class SGD on the iris dataset

• SGD: Weighted samples

• Comparing various online solvers

• SVM: Separating hyperplane for unbalanced classes (See the Note in the example)

1.5.2. Регрессия

Класс SGDRegressor реализует простую стохастическую процедуру обучения градиентного спуска, которая поддерживает различные функции потерь и штрафы для обучения моделей линейной регрессии. SGDRegressor хорошо подходит для задач регрессии с большим количеством обучающих выборок (> 10.000), для других задач мы рекомендуем Ridge, Lasso, или ElasticNet.

Конкретная функция потерь может быть задана через параметр loss. SGDRegressor` поддерживает следующие функции потерь:

• loss="squared_error": Обычные наименьшие квадраты,

• loss="huber": hinge loss для робастной регрессии,

• loss="epsilon_insensitive": линейная регрессия опорных вектора.

Формулы см. в математическом разделе ниже. Для робастной регрессии можно использовать функции hinge loss и epsilon_insensitive. Ширина области нечувствительности задается с помощью параметра epsilon. Этот параметр зависит от масштаба целевых переменных.

Параметр penalty определяет используемую регуляризацию (см. описание выше в разделе классификации).

SGDRegressor также поддерживает усредненный SGD [10] (здесь опять же см. описание выше в разделе классификации).

Для регрессии с квадратичными потерями и штрафом l2 доступен другой вариант SGD со стратегией усреднения - алгоритм Stochastic Average Gradient (SAG), доступный в качестве алгоритма в Ridge.

1.5.3. Онлайновая одноклассовая SVM

Класс sklearn.linear_model.SGDOneClassSVM реализует онлайн линейную версию одноклассовой SVM с использованием стохастического градиентного спуска. В сочетании с техникой аппроксимации ядрами, sklearn.linear_model.SGDOneClassSVM может быть использован для аппроксимации решения кернелизированной одноклассовой SVM, реализованной в sklearn.svm.OneClassSVM, с линейной сложностью по числу выборок. Обратите внимание, что сложность кернелизированной одноклассовой SVM в лучшем случае квадратична по числу выборок. sklearn.linear_model.SGDOneClassSVM, таким образом, хорошо подходит для наборов данных с большим числом обучающих выборок (> 10 000), для которых SGD-вариант может быть на несколько порядков быстрее.

Математические детали Click for more details

Его реализация основана на реализации стохастического градиентного спуска. Действительно, исходная задача оптимизации одноклассовой SVM имеет вид

\[\begin{split}\begin{aligned} \min_{w, \rho, \xi} & \quad \frac{1}{2}\Vert w \Vert^2 - \rho + \frac{1}{\nu n} \sum_{i=1}^n \xi_i \\ \text{s.t.} & \quad \langle w, x_i \rangle \geq \rho - \xi_i \quad 1 \leq i \leq n \\ & \quad \xi_i \geq 0 \quad 1 \leq i \leq n \end{aligned}\end{split}\]

где \(\nu \in (0, 1]\) - заданный пользователем параметр, управляющий долей промахов и долей опорных векторов. Избавившись от слабых переменных \(\xi_i\) эта задача эквивалентна

\[\min_{w, \rho} \frac{1}{2}\Vert w \Vert^2 - \rho + \frac{1}{\nu n} \sum_{i=1}^n \max(0, \rho - \langle w, x_i \rangle) \, .\]

Умножив на константу \(\nu\) и введя перехват \(b = 1 - \rho\), получим следующую эквивалентную задачу оптимизации

\[\min_{w, b} \frac{\nu}{2}\Vert w \Vert^2 + b\nu + \frac{1}{n} \sum_{i=1}^n \max(0, 1 - (\langle w, x_i \rangle + b)) \, .\]

Это похоже на задачи оптимизации, изученные в разделе Математическая формулировка с \(y_i = 1, 1 \leq i \leq n\) и \(\alpha = \nu/2\), \(L\) - функция потерь петли, а \(R\) - норма L2. Осталось добавить термин \(b\nu\) в цикл оптимизации.

Как SGDClassifier и SGDRegressor так и SGDOneClassSVM поддерживает усредненные SGD. Усреднение можно включить, установив average=True.

1.5.4. Стохастический градиентный спуск для разреженных данных

Примечание

Реализация с разреженными данными дает несколько иные результаты, чем реализация с плотными данными, из-за уменьшения скорости обучения для перехвата. См. Детали реализации.

Имеется встроенная поддержка разреженных данных, заданных в любой матрице в формате, поддерживаемом scipy.sparse. Однако для максимальной эффективности используйте формат матрицы CSR, определенный в scipy.sparse.csr_matrix.

Примеры:

• Классификация текстовых документов с использованием разряженынх признаков

1.5.5. Сложность

Основным преимуществом SGD является его эффективность, которая в основном линейно зависит от количества обучающих примеров. Если X - матрица размера (n, p), то стоимость обучения составляет \(O(k n \bar p)\), где k - количество итераций (эпох), а \(\bar p\) - среднее количество ненулевых признаков на выборку.

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

1.5.6. Критерий остановки

Классы SGDClassifier и SGDRegressor предоставляют два критерия для остановки алгоритма при достижении заданного уровня сходимости:

• При early_stopping=True входные данные разбиваются на обучающее и проверочное множества. Модель обучается на тренировочных данных, а критерий остановки основывается на оценке предсказания (с помощью метода score), вычисленной на валидационном множестве. Размер валидационного набора можно изменить с помощью параметра validation_fraction.

• При early_stopping=False модель обучается по всем входным данным, а критерий остановки основывается на объективной функции, вычисленной на обучающих данных.

В обоих случаях критерий оценивается один раз за эпоху, и алгоритм останавливается, если критерий не улучшается n_iter_no_change подряд. Улучшение оценивается с абсолютным допуском tol, и алгоритм останавливается в любом случае после максимального числа итераций max_iter.

1.5.7. Советы по практическому использованию

• Стохастический градиентный спуск чувствителен к масштабированию признаков, поэтому настоятельно рекомендуется масштабировать ваши данные. Например, масштабируйте каждый признак входного вектора X на [0,1] или [-1,+1], или стандартизируйте его так, чтобы среднее 0 и дисперсия 1. Обратите внимание, что такое же масштабирование должно быть применено к тестовым данных, чтобы получить значимые результаты. Это можно легко сделать с помощью StandardScaler:

  from sklearn.preprocessing import StandardScaler
  scaler = StandardScaler()
  scaler.fit(X_train)  # Don't cheat - fit only on training data
  X_train = scaler.transform(X_train)
  X_test = scaler.transform(X_test)  # apply same transformation to test data
  
  # Or better yet: use a pipeline!
  from sklearn.pipeline import make_pipeline
  est = make_pipeline(StandardScaler(), SGDClassifier())
  est.fit(X_train)
  est.predict(X_test)
  

  Если ваши атрибуты имеют внутреннюю шкалу (например, частота слов или индикаторные признаки), масштабирование не требуется.

• Для поиска разумного значения регуляризации \(\alpha\) лучше всего использовать автоматический поиск по гиперпараметрам, например, GridSearchCV или RandomizedSearchCV, обычно в диапазоне 10.0**-np.arange(1,7).

• Эмпирически мы обнаружили, что SGD сходится после наблюдения примерно 10^6 обучающих выборок. Таким образом, разумным первым предположением для количества итераций является max_iter = np.ceil(10**6 / n), где n - размер обучающего набора.

• Если вы применяете SGD к признакам, извлеченным с помощью PCA, мы обнаружили, что часто целесообразно масштабировать значения признаков на некоторую константу c, чтобы средняя норма L2 обучающих данных равнялась единице.

• Мы обнаружили, что усредненная SGD лучше всего работает при большом количестве признаков и более высоком eta0.

Ссылки:

• “Efficient BackProp” Y. LeCun, L. Bottou, G. Orr, K. Müller - In Neural Networks: Tricks of the Trade 1998.

1.5.8. Математическая формулировка

Здесь мы описываем математические детали процедуры SGD. Хороший обзор со скоростью сходимости можно найти в [12].

Дано множество обучающих примеров \((x_1, y_1), \ldots, (x_n, y_n)\), где \(x_i \in \mathbf{R}^m\) и \(y_i \in \mathcal{R}\) (\(y_i \in {-1, 1}\) для классификации), наша цель - выучить линейную оценочную функцию \(f(x) = w^T x + b\) с параметрами модели \(w \in \mathbf{R}^m\) и перехватом \(b \in \mathbf{R}\). Для того чтобы сделать предсказания для бинарной классификации, мы просто смотрим на знак \(f(x)\). Чтобы найти параметры модели, мы минимизируем регуляризованную ошибку обучения, которая задается следующим образом

\[E(w,b) = \frac{1}{n}\sum_{i=1}^{n} L(y_i, f(x_i)) + \alpha R(w)\]

где \(L\) - функция потерь, которая измеряет (неправильное) соответствие модели, а \(R\) - член регуляризации (он же штраф), который наказывает сложность модели; \(\alpha > 0\) - неотрицательный гиперпараметр, который управляет силой регуляризации.

Детали функций потерь. Click for more details

Различные варианты \(L\) влекут за собой различные классификаторы или регрессоры:

• Hinge (soft-margin): эквивалент классификации опорных векторов. \(L(y_i, f(x_i)) = \max(0, 1 - y_i f(x_i))\).

• Перцептрон: \(L(y_i, f(x_i)) = \max(0, - y_i f(x_i))\).

• Модифицированный Huber: \(L(y_i, f(x_i)) = \max(0, 1 - y_i f(x_i))^2\) if \(y_i f(x_i) > -1\), и \(L(y_i, f(x_i)) = -4 y_i f(x_i)\) в противном случае.

• Log Loss: эквивалент логистической регрессии. \(L(y_i, f(x_i)) = \log(1 + \exp (-y_i f(x_i)))\).

• Квадратная ошибка: линейная регрессия (гребень или лассо в зависимости от \(R\)). \(L(y_i, f(x_i)) = \frac{1}{2}(y_i - f(x_i))^2\).

• Huber: менее чувствителен к выбросам, чем метод наименьших квадратов. Он эквивалентен методу наименьших квадратов, если \(|y_i - f(x_i)| \leq \varepsilon\), и \(L(y_i, f(x_i)) = \varepsilon |y_i - f(x_i)| - \frac{1}{2} \varepsilon^2\) в противном случае.

• Epsilon-Insensitive: (soft-margin) эквивалент регрессии опорных векторов. \(L(y_i, f(x_i)) = \max(0, |y_i - f(x_i)| - \varepsilon)\).

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

Популярными вариантами регуляризации \(R\) (параметр penalty) являются:

• L2-норма: \(R(w) := \frac{1}{2} \sum_{j=1}^{m} w_j^2 = ||w||_2^2\),

• L1-норма: \(R(w) := \sum_{j=1}^{m} |w_j|\), что приводит к разреженным решениям.

• Elastic Net: \(R(w) := \frac{\rho}{2} \sum_{j=1}^{n} w_j^2 + (1-\rho) \sum_{j=1}^{m} |w_j|\), выпуклая комбинация L2 и L1, где \(\rho\) задается 1 - l1_ratio.

На рисунке ниже показаны контуры различных членов регуляризации в двумерном пространстве параметров (\(m=2\)), когда \(R(w) = 1\).

1.5.8.1. SGD

Стохастический градиентный спуск (Stochastic gradient descent - SGD) - это метод оптимизации для задач оптимизации без ограничений. В отличие от (пакетного) градиентного спуска, SGD аппроксимирует истинный градиент \(E(w,b)\), рассматривая один обучающий пример за раз.

Класс SGDClassifier реализует процедуру обучения SGD первого порядка. Алгоритм выполняет итерации по обучающим примерам и для каждого примера обновляет параметры модели в соответствии с правилом обновления, представленным в виде

\[w \leftarrow w - \eta \left[\alpha \frac{\partial R(w)}{\partial w} + \frac{\partial L(w^T x_i + b, y_i)}{\partial w}\right]\]

где \(\eta\) - скорость обучения, которая управляет размером шага в пространстве параметров. Перехват (intercept) \(b\) обновляется аналогично, но без регуляризации (и с дополнительным затуханием для разреженных матриц, как подробно описано в Детали реализации).

Скорость обучения \(\eta\) может быть либо постоянной, либо постепенно затухающей. Для классификации график скорости обучения по умолчанию (learning_rate='optimal') задается следующим образом

\[\eta^{(t)} = \frac {1}{\alpha (t_0 + t)}\]

где \(t\) - шаг по времени (всего имеется n_samples * n_iter шагов по времени), \(t_0\) определяется на основе эвристики, предложенной Леоном Ботту (Léon Bottou), так, чтобы ожидаемые начальные обновления были сопоставимы с ожидаемым размером весов (при этом предполагается, что норма обучающих выборок равна примерно 1). Точное определение можно найти в _init_t в BaseSGD.

Для регрессии график скорости обучения по умолчанию представляет собой обратное масштабирование (learning_rate='invscaling'), заданное следующим образом

\[\eta^{(t)} = \frac{eta_0}{t^{power\_t}}\]

где \(eta_0\) и \(power\_t\) - гиперпараметры, выбираемые пользователем через eta0 и power_t, соответственно.

Для постоянной скорости обучения используйте learning_rate='constant' и используйте eta0 для задания скорости обучения.

Для адаптивно уменьшающейся скорости обучения используйте learning_rate='adaptive' и eta0 для указания начальной скорости обучения. При достижении критерия остановки скорость обучения делится на 5, и алгоритм не останавливается. Алгоритм останавливается, когда скорость обучения становится меньше 1e-6.

Доступ к параметрам модели осуществляется через атрибуты coef_ и intercept_, coef_ содержит веса \(w\) и intercept_ содержит \(b\).

При использовании Averaged SGD (с параметром average), coef_ устанавливается на средний вес по всем обновлениям: coef_ \(= \frac{1}{T} \sum_{t=0}^{T-1} w^{(t)}\), где \(T\) - общее количество обновлений, найденное в атрибуте t_.

1.5.9. Детали реализации

На реализацию SGD влияет Stochastic Gradient SVM из [7].

Как и в SvmSGD, вектор веса представлен как произведение скаляра и вектора, что позволяет эффективно обновлять вес в случае L2 регуляризации.

В случае разреженных входных данных X, перехват обновляется с меньшей скоростью обучения (умноженной на 0.01), чтобы учесть тот факт, что он обновляется чаще. Обучающие примеры берутся последовательно, и скорость обучения снижается после каждого наблюдаемого примера. Мы взяли график скорости обучения из [8].

Для многоклассовой классификации используется подход “один против всех”.

Мы используем алгоритм усеченного градиента, предложенный в [9] для регуляризации L1 (и Elastic Net).

Код написан на языке Cython.

Ссылки:

[7]

“Stochastic Gradient Descent” L. Bottou - Website, 2010.

[8]

“Pegasos: Primal estimated sub-gradient solver for svm” S. Shalev-Shwartz, Y. Singer, N. Srebro - In Proceedings of ICML ‘07.

[9]

“Stochastic gradient descent training for l1-regularized log-linear models with cumulative penalty” Y. Tsuruoka, J. Tsujii, S. Ananiadou - In Proceedings of the AFNLP/ACL ‘09.

[10] (1,2)

“Towards Optimal One Pass Large Scale Learning with Averaged Stochastic Gradient Descent” Xu, Wei (2011)

[11]

“Regularization and variable selection via the elastic net” H. Zou, T. Hastie - Journal of the Royal Statistical Society Series B, 67 (2), 301-320.

[12]

“Solving large scale linear prediction problems using stochastic gradient descent algorithms” T. Zhang - In Proceedings of ICML ‘04.