1.4. Машины опорных векторов

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

SVC, NuSVC и LinearSVC — это классы, способные выполнять бинарную и многоклассовую классификацию набора данных.

SVC и NuSVC — похожие методы, но они принимают несколько разные наборы параметров и имеют разные математические формулировки (см. раздел Математическая формулировка). С другой стороны, LinearSVC — это другая (более быстрая) реализация классификации с помощью машин опорных векторов для случая линейного ядра. В ней также отсутствуют некоторые атрибуты SVC и NuSVC, например support_. В LinearSVC используется функция потерь squared_hinge, а из-за реализации на liblinear регуляризуется также свободный член, если он учитывается. Однако этот эффект можно уменьшить, тщательно настроив параметр intercept_scaling, который позволяет применять к свободному члену режим регуляризации, отличный от режима для остальных признаков. Поэтому результаты классификации и оценка могут отличаться от результатов двух других классификаторов.

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

>>> from sklearn import svm
>>> X = [[0, 0], [1, 1]]
>>> y = [0, 1]
>>> clf = svm.SVC()
>>> clf.fit(X, y)
SVC()

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

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

Функция принятия решений SVM (подробно описанная в разделе Математическая формулировка) зависит от некоторого подмножества обучающих данных, называемого опорными векторами. Некоторые свойства этих опорных векторов доступны в атрибутах support_vectors_, support_ и n_support_:

>>> # get support vectors
>>> clf.support_vectors_
array([[0., 0.],
       [1., 1.]])
>>> # get indices of support vectors
>>> clf.support_
array([0, 1]...)
>>> # get number of support vectors for each class
>>> clf.n_support_
array([1, 1]...)

Примеры

• SVM: разделяющая гиперплоскость с максимальным отступом
• SVM-Anova: SVM с одномерным отбором признаков
• График вероятностей классификации

>>> X = [[0], [1], [2], [3]]
>>> Y = [0, 1, 2, 3]
>>> clf = svm.SVC(decision_function_shape='ovo')
>>> clf.fit(X, Y)
SVC(decision_function_shape='ovo')
>>> dec = clf.decision_function([[1]])
>>> dec.shape[1] # 6 classes: 4*3/2 = 6
6
>>> clf.decision_function_shape = "ovr"
>>> dec = clf.decision_function([[1]])
>>> dec.shape[1] # 4 classes
4

>>> lin_clf = svm.LinearSVC()
>>> lin_clf.fit(X, Y)
LinearSVC()
>>> dec = lin_clf.decision_function([[1]])
>>> dec.shape[1]
4

1.4.1.3. Несбалансированные задачи

Если в задаче требуется придавать большее значение определённым классам или отдельным образцам, можно использовать параметры class_weight и sample_weight.

SVC (но не NuSVC) реализует параметр class_weight в методе fit. Это словарь вида {class_label : value}, где value — число с плавающей точкой > 0, задающее параметр C для класса class_label равным C * value. На рисунке ниже показана граница принятия решений для несбалансированной задачи с коррекцией весов и без неё.

SVC, NuSVC, SVR, NuSVR, LinearSVC, LinearSVR и OneClassSVM также поддерживают веса отдельных образцов в методе fit через параметр sample_weight. Как и class_weight, этот параметр задаёт значение C для i-го примера равным C * sample_weight[i], что побуждает классификатор правильно классифицировать эти образцы. На рисунке ниже показано влияние весов образцов на границу принятия решений. Размер окружностей пропорционален весам образцов:

Примеры

• SVM: разделяющая гиперплоскость для несбалансированных классов
• SVM: взвешенные образцы

1.4.2. Регрессия

Метод классификации с помощью машин опорных векторов можно расширить для решения задач регрессии. Этот метод называется регрессией с помощью машин опорных векторов.

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

Существует три реализации регрессии на основе опорных векторов: SVR, NuSVR и LinearSVR. LinearSVR работает быстрее, чем SVR, но поддерживает только линейное ядро, а NuSVR реализует несколько иную формулировку, чем SVR и LinearSVR. Из-за реализации на liblinear в LinearSVR также регуляризуется свободный член, если он учитывается. Однако этот эффект можно уменьшить, тщательно настроив параметр intercept_scaling, который позволяет применять к свободному члену режим регуляризации, отличный от режима для остальных признаков. Поэтому результаты классификации и оценка могут отличаться от результатов двух других классификаторов. Дополнительные сведения см. в разделе Особенности реализации.

Как и в случае классов классификации, метод fit принимает в качестве аргументов векторы X и y, но в данном случае ожидается, что y содержит значения с плавающей точкой, а не целые числа:

>>> from sklearn import svm
>>> X = [[0, 0], [2, 2]]
>>> y = [0.5, 2.5]
>>> regr = svm.SVR()
>>> regr.fit(X, y)
SVR()
>>> regr.predict([[1, 1]])
array([1.5])

Примеры

• Регрессия с помощью машин опорных векторов (SVR) с линейными и нелинейными ядрами

1.4.3. Оценка плотности, обнаружение новых объектов

Класс OneClassSVM реализует одноклассовую SVM, используемую для обнаружения выбросов.

Описание и сведения об использовании OneClassSVM см. в разделе Обнаружение новых объектов и выбросов.

1.4.4. Сложность

Машины опорных векторов — мощные инструменты, однако требования к вычислительным ресурсам и памяти быстро возрастают с увеличением числа обучающих векторов. В основе SVM лежит задача квадратичного программирования (QP), отделяющая опорные векторы от остальных обучающих данных. Решатель QP, используемый в реализации на основе libsvm, имеет сложность от \(O(n_{features} \times n_{samples}^2)\) до \(O(n_{features} \times n_{samples}^3)\) в зависимости от того, насколько эффективно на практике используется кэш libsvm (зависит от набора данных). Для очень разреженных данных вместо \(n_{features}\) следует использовать среднее число ненулевых признаков в векторе образца.

Для линейного случая алгоритм, используемый в LinearSVC при реализации на основе liblinear, значительно эффективнее аналога SVC на основе libsvm и масштабируется почти линейно до миллионов образцов и/или признаков.

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

• Избегайте копирования данных: для SVC, SVR, NuSVC и NuSVR, если данные, переданные некоторым методам, не являются непрерывными массивами в порядке C и не используют двойную точность, перед вызовом базовой реализации на C они будут скопированы. Проверить, является ли заданный массив numpy непрерывным в порядке C, можно, изучив его атрибут flags.

  Для LinearSVC (и LogisticRegression) любой входной массив numpy будет скопирован и преобразован во внутреннее разреженное представление данных liblinear (числа с плавающей точкой двойной точности и индексы ненулевых компонент типа int32). Если вы хотите обучить линейный классификатор для больших наборов данных, не копируя в качестве входных данных плотный непрерывный в порядке C массив numpy двойной точности, рекомендуем вместо этого использовать класс SGDClassifier. Целевую функцию можно настроить так, чтобы она была почти такой же, как у модели LinearSVC.

• Размер кэша ядра: для SVC, SVR, NuSVC и NuSVR размер кэша ядра существенно влияет на время выполнения при решении задач большого размера. Если у вас достаточно оперативной памяти, рекомендуется установить для cache_size значение выше заданного по умолчанию (200 МБ), например 500 МБ или 1000 МБ.

• Настройка C: по умолчанию C равно 1, и это разумный выбор по умолчанию. Если у вас много зашумлённых наблюдений, следует уменьшить это значение: уменьшение C соответствует усилению регуляризации.

  LinearSVC и LinearSVR менее чувствительны к C при больших значениях, и после достижения определённого порога качество предсказаний перестаёт улучшаться. При этом для обучения с большими значениями C требуется больше времени — иногда до 10 раз больше, как показано в [11].

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

  >>> from sklearn.pipeline import make_pipeline
  >>> from sklearn.preprocessing import StandardScaler
  >>> from sklearn.svm import SVC
  
  >>> clf = make_pipeline(StandardScaler(), SVC())
  

  Дополнительные сведения о масштабировании и нормализации см. в разделе Предварительная обработка данных.

• О параметре shrinking, цитата из [12]: Мы обнаружили, что при большом числе итераций сокращение может уменьшить время обучения. Однако если решить задачу оптимизации с невысокой точностью (например, задав большой порог остановки), версия кода без сокращения может работать значительно быстрее
• Параметр nu в NuSVC/OneClassSVM/NuSVR приближённо задаёт долю ошибок на обучающей выборке и опорных векторов.
• В SVC, если данные несбалансированы (например, положительных объектов много, а отрицательных мало), задайте class_weight='balanced' и/или попробуйте разные значения параметра штрафа C.

• Случайность базовых реализаций: базовые реализации SVC и NuSVC используют генератор случайных чисел только для перемешивания данных при оценке вероятностей (когда probability установлено в True). Эту случайность можно контролировать с помощью параметра random_state. Если probability установлено в False, эти оцениватели не используют случайность, и random_state не влияет на результаты. Базовая реализация OneClassSVM похожа на реализации SVC и NuSVC. Поскольку для OneClassSVM оценка вероятностей не предоставляется, он не использует случайность.

  Базовая реализация LinearSVC использует генератор случайных чисел для выбора признаков при обучении модели методом двойственного координатного спуска (то есть когда dual установлено в True). Поэтому для одних и тех же входных данных результаты могут немного различаться. Если это происходит, попробуйте уменьшить значение параметра tol. Эту случайность также можно контролировать с помощью параметра random_state. Если dual установлено в False, базовая реализация LinearSVC не использует случайность, и random_state не влияет на результаты.

• Использование L1-штрафа, обеспечиваемого LinearSVC(penalty='l1', dual=False), даёт разреженное решение: ненулевыми и влияющими на функцию принятия решения оказываются веса лишь для части признаков. Увеличение C приводит к усложнению модели (выбирается больше признаков). Значение C, при котором получается «нулевая» модель (все веса равны нулю), можно вычислить с помощью l1_min_c.

1.4.6. Функции ядра

Функция ядра может быть одной из следующих:

• линейное: \(\langle x, x'\rangle\).
• полиномиальное: \((\gamma \langle x, x'\rangle + r)^d\), где \(d\) задаётся параметром degree, а \(r\) — параметром coef0.
• rbf: \(\exp(-\gamma \|x-x'\|^2)\), где \(\gamma\) задаётся параметром gamma и должен быть больше 0.
• сигмоидальное \(\tanh(\gamma \langle x,x'\rangle + r)\), где \(r\) задаётся параметром coef0.

Различные ядра задаются параметром kernel:

>>> linear_svc = svm.SVC(kernel='linear')
>>> linear_svc.kernel
'linear'
>>> rbf_svc = svm.SVC(kernel='rbf')
>>> rbf_svc.kernel
'rbf'

См. также раздел Аппроксимация ядра, где описан более быстрый и лучше масштабируемый способ использования ядер RBF.

>>> import numpy as np
>>> from sklearn import svm
>>> def my_kernel(X, Y):
...     return np.dot(X, Y.T)
...
>>> clf = svm.SVC(kernel=my_kernel)

>>> import numpy as np
>>> from sklearn.datasets import make_classification
>>> from sklearn.model_selection import train_test_split
>>> from sklearn import svm
>>> X, y = make_classification(n_samples=10, random_state=0)
>>> X_train , X_test , y_train, y_test = train_test_split(X, y, random_state=0)
>>> clf = svm.SVC(kernel='precomputed')
>>> # linear kernel computation
>>> gram_train = np.dot(X_train, X_train.T)
>>> clf.fit(gram_train, y_train)
SVC(kernel='precomputed')
>>> # predict on training examples
>>> gram_test = np.dot(X_test, X_train.T)
>>> clf.predict(gram_test)
array([0, 1, 0])

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

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

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

В качестве полезных источников по теории и практическому применению SVM рекомендуем [13] и [14].

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

Внутри мы используем libsvm [12] и liblinear [11] для выполнения всех вычислений. Эти библиотеки имеют оболочки на C и Cython. Описание реализации и подробности используемых алгоритмов приведены в соответствующих научных статьях.

Литература