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

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

Класс SGDClassifier реализует простую процедуру обучения стохастического градиентного спуска, которая поддерживает различные функции потерь и штрафы для классификации. Ниже приведена граница принятия решения для SGDClassifier, обученного с помощью функции потерь hinge, что эквивалентно линейной 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": (мягкий маржин) линейная машина опорных векторов,
• loss="modified_huber": сглаженная функция потерь hinge,
• 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": выпуклая комбинация L2 и L1; (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 поддерживает как взвешенные классы, так и взвешенные примеры через параметры метода fit class_weight и sample_weight. См. примеры ниже и документацию метода SGDClassifier.fit для получения дополнительной информации.

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

Для классификации с логистической функцией потерь доступен другой вариант SGD со стратегией усреднения — алгоритм стохастического усреднённого градиента (SAG), доступный в качестве решателя в LogisticRegression.

Примеры

• SGD: Гиперплоскость максимального разрыва
• Построение многоклассового SGD на наборе данных ирисов
• SGD: Взвешенные примеры
• Сравнение различных онлайн-решателей
• SVM: Гиперплоскость разделения для несбалансированных классов (см. примечание в примере)

1.5.2. Регрессия

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

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

• loss="squared_error": обычные наименьшие квадраты,
• loss="huber": функция потерь Хубера для устойчивой регрессии,
• 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 может быть быстрее на несколько порядков.

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

Примеры

• SVM для одного класса против SVM для одного класса, использующего стохастический градиентный спуск

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⁶ обучающих образцов. Таким образом, разумная первая оценка для числа итераций составляет 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 - В 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 \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) включают:

• 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.9. Детали реализации

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

Ссылки