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

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

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

Как и другие классификаторы, 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": линейная машина опорных векторов с мягким зазором;
• loss="modified_huber": сглаженная шарнирная функция потерь;
• loss="log_loss": логистическая регрессия;
• а также все приведённые ниже функции потерь для регрессии. В этом случае целевая переменная кодируется значением \(-1\) или \(1\), а задача рассматривается как задача регрессии. Предсказанный класс соответствует знаку предсказанного целевого значения.

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

Использование 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": штраф на норму \(L_2\) для coef_.
• penalty="l1": штраф на норму \(L_1\) для coef_.
• penalty="elasticnet": выпуклая комбинация \(L_2\) и \(L_1\); (1 - l1_ratio) * L2 + l1_ratio * L1.

По умолчанию используется penalty="l2". Штраф \(L_1\) приводит к разреженным решениям, обнуляя большинство коэффициентов. Elastic Net [11] устраняет некоторые недостатки штрафа \(L_1\) при наличии сильно коррелированных признаков. Параметр l1_ratio задаёт выпуклую комбинацию штрафов \(L_1\) и \(L_2\).

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

В случае многоклассовой классификации coef_ — это двумерный массив формы (n_classes, n_features), а intercept_ — одномерный массив формы (n_classes,). Строка coef_ с индексом \(i\) содержит вектор весов классификатора 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: разделяющая гиперплоскость с максимальным зазором
• Визуализация многоклассового SGD на наборе данных iris
• SGD: взвешенные образцы
• SVM: разделяющая гиперплоскость для несбалансированных классов (см. примечание в примере)

1.5.2. Регрессия

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

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

• loss="squared_error": обычный метод наименьших квадратов;
• loss="huber": функция потерь Хьюбера для робастной регрессии;
• loss="epsilon_insensitive": линейная регрессия на опорных векторах.

Формулы приведены в разделе с математическим описанием ниже. Функции потерь Хьюбера и с нечувствительной областью epsilon можно использовать для робастной регрессии. Ширину нечувствительной области необходимо задать с помощью параметра epsilon. Значение этого параметра зависит от масштаба целевых переменных.

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

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

Для регрессии с квадратичной функцией потерь и штрафом \(L_2\) доступен ещё один вариант 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 может работать на несколько порядков быстрее.

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

Примеры

• Одноклассовая SVM и одноклассовая SVM с использованием стохастического градиентного спуска

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

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

Примеры

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

1.5.5. Сложность

Главное преимущество SGD — его эффективность: затраты времени в основном линейно зависят от числа обучающих примеров. Если \(X\) — матрица размера \(n \times p\) (с \(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 так, чтобы средняя норма \(L_2\) обучающих данных равнялась единице.
• Мы обнаружили, что усреднённый SGD лучше всего работает при большом числе признаков и более высоком значении eta0.

Литература

• «Эффективное обратное распространение ошибки» Y. LeCun, L. Bottou, G. Orr, K. Müller — в сборнике «Нейронные сети: приёмы и рекомендации», 1998.

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

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

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

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

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

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

• норма \(L_2\): \(R(w) := \frac{1}{2} \sum_{j=1}^{m} w_j^2 = \frac{1}{2} ||w||_2^2\),
• норма \(L_1\): \(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|\) — выпуклая комбинация \(L_2\) и \(L_1\), где \(\rho\) задаётся параметром 1 - l1_ratio.

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

1.5.9. Подробности реализации

На реализацию SGD повлияла работа Stochastic Gradient SVM [7]. Как и в SvmSGD, вектор весов представлен в виде произведения скаляра и вектора, что позволяет эффективно обновлять веса при регуляризации \(L_2\). При разреженном входе X свободный член обновляется с меньшей скоростью обучения (умноженной на 0.01), поскольку он обновляется чаще. Обучающие примеры выбираются последовательно, а скорость обучения снижается после обработки каждого примера. Мы использовали расписание скорости обучения из работы [8]. Для многоклассовой классификации используется подход «один против всех». Для регуляризации \(L_1\) (и Elastic Net) мы используем алгоритм усечённого градиента, предложенный в работе [9]. Код написан на Cython.

Литература