1.4. Метод опорных векторов (Support Vector Machines - SVM)

Метод опорных векторов (Support Vector Machines - SVM) - это набор методов контролируемого обучения, используемых для классификации, регрессии и выявления выбросов.

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

  • Эффективны в пространствах высокой размерности.

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

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

  • Универсальность: для функции принятия решений могут быть заданы различные Функциональные ядра. Предоставляются общие ядра, но можно указать и собственные.

К недостаткам Метода опорных векторов относятся:

  • Если число признаков намного больше числа выборок, то при выборе Функциональные ядра и термина регуляризации следует избегать переобучения.

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

Метод опорных векторов в scikit-learn поддерживает как плотные (numpy.ndarray и преобразуемые в них numpy.asarray), так и разреженные (любые scipy.sparse) векторы выборок в качестве входных. Однако, чтобы использовать SVM для прогнозирования по разреженным данным, она должна быть настроена на такие данные. Для оптимальной работы используйте C-упорядоченные numpy.ndarray (плотные) или scipy.sparse.csr_matrix (разреженные) с dtype=float64.

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

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

../_images/sphx_glr_plot_iris_svc_001.png

SVC и NuSVC являются похожими методами, но принимают немного разные наборы параметров и имеют разные математические формулировки (см. разделе Математическая формулировка). С другой стороны, LinearSVC - это другая (более быстрая) реализация Support Vector Classification для случая линейного ядра. Она также лишена некоторых атрибутов 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]...)

1.4.1.1. Многоклассовая классификация

SVC и NuSVC реализуют подход “один против одного” для многоклассовой классификации. Всего строится n_classes * (n_classes - 1) / 2 классификаторов, каждый из которых обучает данные из двух классов.

Для обеспечения согласованного интерфейса с другими классификаторами, опция decision_function_shape позволяет монотонно преобразовывать результаты классификаторов “один против одного” в функцию принятия решений “один против остальных” формы (n_samples, n_classes).

>>> 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] # 4 classes: 4*3/2 = 6
6
>>> clf.decision_function_shape = "ovr"
>>> dec = clf.decision_function([[1]])
>>> dec.shape[1] # 4 classes
4

С другой стороны, LinearSVC реализует “один против остальных” (“one-vs-the-rest”) мультиклассовую стратегию, обучая таким образом n_classes моделей.

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

Полное описание функции принятия решений см. в Математическая формулировка.

Детали о многоклассовых стратегиях. Click for more details

Обратите внимание, что LinearSVC также реализует альтернативную многоклассовую стратегию, так называемую многоклассовую SVM, сформулированную Краммером и Сингером [16], с помощью опции multi_class='crammer_singer'. На практике обычно предпочитают классификацию “один против остальных”, поскольку результаты в основном схожи, но время выполнения значительно меньше.

Для “один против остальных” LinearSVC атрибуты coef_ и intercept_ имеют форму (n_classes, n_features) и (n_classes,) соответственно. Каждая строка коэффициентов соответствует одному из классификаторов n_classes “один против остальных” и аналогично для интерцептов, в порядке убывания “первого” класса .

В случае “один против одного” SVC и NuSVC расположение атрибутов немного сложнее. В случае линейного ядра атрибуты coef_ и intercept_ имеют вид (n_classes * (n_classes - 1) / 2, n_features) и (n_classes * (n_classes - 1) / 2) соответственно. Это похоже на схему для LinearSVC, описанную выше, только теперь каждая строка соответствует бинарному классификатору. Порядок для классов от 0 до n следующий: “0 vs 1”, “0 vs 2”, … “0 vs n”, “1 vs 2”, “1 vs 3”, “1 vs n”, … “n-1 vs n”.

Форма dual_coef_ имеет вид (n_classes-1, n_SV) с несколько сложным для восприятия расположением.

Столбцы соответствуют опорным векторам, задействованным в любом из классификаторов n_classes * (n_classes - 1) / 2 “один против одного”.

Каждый опорный вектор v имеет двойной коэффициент в каждом из n_classes - 1 классификаторов, сравнивающих класс v с другим классом.

Обратите внимание, что некоторые, но не все, из этих двойственных коэффициентов могут быть нулевыми.

Записи n_classes - 1 в каждом столбце - это эти дуальные коэффициенты, упорядоченные по противоположному классу.

Это может быть понятнее на примере: рассмотрим задачу о трех классах, в которой класс 0 имеет три опорных вектора \(v^{0}_0, v^{1}_0, v^{2}_0\), а классы 1 и 2 имеют по два опорных вектора \(v^{0}_1, v^{1}_1\) и \(v^{0}_2, v^{1}_2\) соответственно. Для каждого опорного вектора \(v^{j}_i\) существуют два двойственных коэффициента. Назовем коэффициент опорного вектора \(v^{j}_i\) в классификаторе между классами \(i\) и \(k\) \(\alpha^{j}_{i,k}\). Тогда dual_coef_ выглядит следующим образом:

\(\alpha^{0}_{0,1}\)

\(\alpha^{1}_{0,1}\)

\(\alpha^{2}_{0,1}\)

\(\alpha^{0}_{1,0}\)

\(\alpha^{1}_{1,0}\)

\(\alpha^{0}_{2,0}\)

\(\alpha^{1}_{2,0}\)

\(\alpha^{0}_{0,2}\)

\(\alpha^{1}_{0,2}\)

\(\alpha^{2}_{0,2}\)

\(\alpha^{0}_{1,2}\)

\(\alpha^{1}_{1,2}\)

\(\alpha^{0}_{2,1}\)

\(\alpha^{1}_{2,1}\)

Coefficients for SVs of class 0

Coefficients for SVs of class 1

Coefficients for SVs of class 2

1.4.1.2. Оценки и вероятности

Метод decision_function в SVC и NuSVC` выдает оценки по классам для каждого образца (или одну оценку для образца в бинарном случае). Когда опция конструктора probability установлена в True, оценки вероятности принадлежности к классу (из методов predict_proba и predict_log_proba) включены. В бинарном случае вероятности калибруются с помощью шкалы Платта [9]: логистическая регрессия по оценкам SVM с дополнительной кросс-валидацией на обучающих данных. В многоклассовом случае это расширяется в соответствии с [10].

Примечание

Одна и та же процедура калибровки вероятностей доступна для всех моделей через CalibratedClassifierCV (см. Калибровка вероятности). В случае SVC и NuSVC эта процедура встроена в libsvm, которая используется под капотом, поэтому она не зависит от scikit-learn’овского CalibratedClassifierCV.

Кросс-валидация, задействованная в масштабировании по Платту, является дорогостоящей операцией для больших наборов данных.

Кроме того, оценки вероятности могут не совпадать с оценками:

  • “argmax” оценок может не совпадать с argmax вероятностей

  • при бинарной классификации образец может быть помечен predict как принадлежащий к положительному классу, даже если результат predict_proba меньше 0.5; и точно так же он может быть помечен как отрицательный, даже если результат predict_proba больше 0.5.

Известно, что метод Платта также имеет теоретические проблемы.

Если требуются доверительные оценки, но они не обязательно должны быть вероятностями, то рекомендуется установить probability=False и использовать decision_function вместо predict_proba.

Обратите внимание, что при decision_function_shape='ovr' и n_classes > 2, в отличие от decision_function, метод predict по умолчанию не пытается разрушить связи. Вы можете установить break_ties=True, чтобы вывод predict был таким же, как np.argmax(clf.decision_function(...), axis=1), иначе всегда будет возвращаться первый класс среди связанных классов; но имейте в виду, что это связано с вычислительными затратами. Пример разбиения на классы см. в SVM Tie Breaking Example.

1.4.1.3. Несбалансированные проблемы

В задачах, где необходимо придать большее значение определенным классам или отдельным выборкам, можно использовать параметры class_weight и sample_weight.

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

../_images/sphx_glr_plot_separating_hyperplane_unbalanced_001.png

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

../_images/sphx_glr_plot_weighted_samples_001.png

1.4.2. Регрессия

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

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

Существует три различных реализации опорных векторов регрессии: 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])

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 (floats двойной точности и int32 индексы ненулевых компонент). Если вы хотите настроить крупномасштабный линейный классификатор без копирования плотного массива numpy C-связной двойной точности в качестве входных данных, мы предлагаем использовать вместо него класс SGDClassifier. Объективная функция может быть настроена почти так же, как у модели LinearSVC.

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

  • Установка 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. Функциональные ядра

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

  • линейной linear: \(\langle x, x'\rangle\).

  • полиномиальной polynomial: \((\gamma \langle x, x'\rangle + r)^d\), где \(d\) задается параметром degree, \(r\) - coef0.

  • rbf: \(\exp(-\gamma \|x-x'\|^2)\), где \(\gamma\) задается параметром gamma, должно быть больше 0.

  • сигмоида sigmoid \(\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'

См. также Аппроксимация ядра (Kernel Approximation) для решения по использованию RBF-ядер, которое намного быстрее и более масштабируемо.

1.4.6.1. Параметры ядра RBF

При обучении SVM с ядром Radial Basis Function (RBF) необходимо учитывать два параметра: C и gamma. Параметр C, общий для всех ядер SVM, является компромиссом между неправильной классификацией обучающих примеров и простотой поверхности принятия решений. Низкое значение C делает поверхность принятия решений гладкой, в то время как высокое C стремится классифицировать все обучающие примеры правильно. gamma определяет, насколько сильно влияет один обучающий пример. Чем больше gamma, тем ближе должны быть другие примеры, чтобы на них повлиять.

Правильный выбор C и gamma имеет решающее значение для работы SVM. Рекомендуется использовать GridSearchCV с C и gamma, разнесенными на экспоненциальное расстояние, чтобы выбрать хорошие значения.

1.4.6.2. Пользовательские ядра

Вы можете определить свои собственные ядра, либо предоставив ядро в виде функции python, либо предварительно вычислив матрицу Грама.

Классификаторы с пользовательскими ядрами ведут себя так же, как и любые другие классификаторы, за исключением того, что:

  • Поле support_vectors_ теперь пустое, в support_` хранятся только индексы опорных векторов.

  • Ссылка (а не копия) первого аргумента метода fit() сохраняется для последующего использования. Если этот массив изменится между использованием fit() и predict(), вы получите неожиданные результаты.

Использование функций Python в качестве ядер. Click for more details

Вы можете использовать собственные определенные ядра, передавая функцию в параметре kernel.

Ваше ядро должно принимать в качестве аргументов две матрицы формы (n_samples_1, n_features), (n_samples_2, n_features) и возвращать матрицу ядра формы (n_samples_1, n_samples_2).

Следующий код определяет линейное ядро и создает экземпляр классификатора, который будет использовать это ядро:

>>> 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)

Использование матрицы Грама. Click for more details

Вы можете передать предварительно вычисленные ядра, используя опцию kernel='precomputed'. Тогда в методы fit и predict вместо X следует передать матрицу Грама. Необходимо указать значения ядра между всеми обучающими векторами и тестовыми векторами:

>>> 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. Математическая формулировка

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

../_images/sphx_glr_plot_separating_hyperplane_001.png

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

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

1.4.7.1. SVC

Даны обучающие векторы \(x_i \in \mathbb{R}^p\), i=1,… , n, в двух классах, и вектор \(y \in \{1, -1\}^n\), наша цель - найти \(w \in \mathbb{R}^p\) и \(b \in \mathbb{R}\) такие, чтобы предсказание, данное \(\text{sign} (w^T\phi(x) + b)\) было правильным для большинства образцов.

SVC решает следующую первичную задачу:

\[ \begin{align}\begin{aligned}\min_ {w, b, \zeta} \frac{1}{2} w^T w + C \sum_{i=1}^{n} \zeta_i\\\begin{split}\textrm {subject to } & y_i (w^T \phi (x_i) + b) \geq 1 - \zeta_i,\\ & \zeta_i \geq 0, i=1, ..., n\end{split}\end{aligned}\end{align} \]

Интуитивно мы пытаемся максимизировать маржу (минимизируя \(||w||^2 = w^Tw\)), получая при этом штраф, когда образец неправильно классифицирован или находится в пределах границы маржи. В идеале значение \(y_i (w^T \phi (x_i) + b)\) должно быть равно \(\geq 1\) для всех образцов, что означает идеальное предсказание. Но задачи обычно не всегда идеально разделяются гиперплоскостью, поэтому мы допускаем, что некоторые образцы могут находиться на расстоянии \(\zeta_i\) от правильной границы поля. Штрафной член C управляет силой этого штрафа и, как следствие, действует как обратный параметр регуляризации (см. примечание ниже).

Двойственная задача к первичной имеет вид

\[ \begin{align}\begin{aligned}\min_{\alpha} \frac{1}{2} \alpha^T Q \alpha - e^T \alpha\\\begin{split} \textrm {subject to } & y^T \alpha = 0\\ & 0 \leq \alpha_i \leq C, i=1, ..., n\end{split}\end{aligned}\end{align} \]

где \(e\) - вектор всех единиц, а \(Q\) - положительная полубесконечная матрица \(n\) by \(n\), \(Q_{ij} \equiv y_i y_j K(x_i, x_j)\), где \(K(x_i, x_j) = \phi (x_i)^T \phi (x_j)\) - ядро. Члены \(\alpha_i\) называются двойственными коэффициентами, и они ограничены сверху \(C\).

Это двойственное представление подчеркивает тот факт, что обучающие векторы неявно отображаются в пространство более высокой (возможно, бесконечной) размерности функцией \(\phi\): см. трюк с ядром.

После решения задачи оптимизации выход decision_function для заданной выборки \(x\) становится:

\[\sum_{i\in SV} y_i \alpha_i K(x_i, x) + b,\]

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

Доступ к этим параметрам можно получить через атрибуты dual_coef_, который содержит произведение \(y_i \alpha_i\), support_vectors_, который содержит опорные векторы, и intercept_, который содержит независимый член \(b`\).

Примечание

В то время как SVM-модели, полученные из libsvm и liblinear, используют C в качестве параметра регуляризации, большинство других оценочных средств используют alpha. Точная эквивалентность между величиной регуляризации двух моделей зависит от точной целевой функции, оптимизируемой моделью. Например, если в качестве модели используется Ridge регрессия, то соотношение между ними задается как \(C = \frac{1}{alpha}\).

LinearSVC Click for more details

Первичная задача может быть эквивалентно сформулирована как

\[\min_ {w, b} \frac{1}{2} w^T w + C \sum_{i=1}^{n}\max(0, 1 - y_i (w^T \phi(x_i) + b)),\]

где мы используем hinge loss. Это форма, которая непосредственно оптимизируется LinearSVC, но в отличие от двойственной формы, эта форма не включает внутренние произведения между выборками, поэтому знаменитый трюк с ядром не может быть применен. Поэтому LinearSVC поддерживает только линейное ядро (\(\phi\) - функция тождества).

NuSVC Click for more details

Формула \(\nu\)-SVC [15] является репараметризацией \(C\)-SVC и поэтому математически эквивалентна.

Мы вводим новый параметр \(\nu\) (вместо \(C\)), который управляет количеством опорных векторов и маргинальными ошибками: \(\nu \in (0, 1]\) - это верхняя граница доли маржинальных ошибок и нижняя граница доли опорных векторов. Маржинальная ошибка соответствует образцу, который лежит не по ту сторону своей маржинальной границы: он либо неправильно классифицирован, либо классифицирован правильно, но не лежит за пределами маржи.

1.4.7.2. SVR

Учитывая обучающие векторы \(x_i \in \mathbb{R}^p\), i=1,…, n, и вектор \(y \in \mathbb{R}^n\) \(\varepsilon\)-SVR решает следующую первичную задачу:

\[ \begin{align}\begin{aligned}\min_ {w, b, \zeta, \zeta^*} \frac{1}{2} w^T w + C \sum_{i=1}^{n} (\zeta_i + \zeta_i^*)\\\begin{split}\textrm {subject to } & y_i - w^T \phi (x_i) - b \leq \varepsilon + \zeta_i,\\ & w^T \phi (x_i) + b - y_i \leq \varepsilon + \zeta_i^*,\\ & \zeta_i, \zeta_i^* \geq 0, i=1, ..., n\end{split}\end{aligned}\end{align} \]

Здесь мы штрафуем выборки, чьи предсказания по крайней мере \(\varepsilon\) удалены от истинной цели. Эти образцы штрафуют цель на \(\zeta_i\) или \(\zeta_i^*\), в зависимости от того, лежат ли их предсказания выше или ниже трубки \(\varepsilon\).

Двойственная задача

\[ \begin{align}\begin{aligned}\min_{\alpha, \alpha^*} \frac{1}{2} (\alpha - \alpha^*)^T Q (\alpha - \alpha^*) + \varepsilon e^T (\alpha + \alpha^*) - y^T (\alpha - \alpha^*)\\\begin{split} \textrm {subject to } & e^T (\alpha - \alpha^*) = 0\\ & 0 \leq \alpha_i, \alpha_i^* \leq C, i=1, ..., n\end{split}\end{aligned}\end{align} \]

где \(e\) - вектор всех единиц, \(Q\) - положительная полубесконечная матрица \(n\) на \(n\), \(Q_{ij} \equiv K(x_i, x_j) = \phi (x_i)^T \phi (x_j)\) - ядро. Здесь обучающие векторы неявно отображаются в пространство более высокой (возможно, бесконечной) размерности с помощью функции \(\phi\).

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

\[\sum_{i \in SV}(\alpha_i - \alpha_i^*) K(x_i, x) + b\]

Доступ к этим параметрам осуществляется через атрибуты dual_coef_, который содержит разность \(\alpha_i - \alpha_i^*\), support_vectors_, который содержит опорные векторы, и intercept_, который содержит независимый член \(b`\).

LinearSVR Click for more details

Первичная задача может быть эквивалентно сформулирована как

\[\min_ {w, b} \frac{1}{2} w^T w + C \sum_{i=1}^{n}\max(0, |y_i - (w^T \phi(x_i) + b)| - \varepsilon),\]

где мы используем потери, нечувствительные к эпсилону, т.е. ошибки меньше, чем \(\varepsilon\), игнорируются. Именно эта форма непосредственно оптимизируется LinearSVR.

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

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

Описание реализации и детали используемых алгоритмов приведены в соответствующих статьях.