Метод опорных векторов

Идея метода

Метод опорных векторов (support vector machine, SVM, предложен в [1]) - частный случай линейного бинарного классификатора, когда веса находятся, используя функцию потерь hinge в сочетании с L2-регуляризацией.

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

Ниже приведён процесс настройки метода опорных векторов от начальной инициализации (слева) к окончательному решению (справа):

При этом решение будет зависеть только от опорных векторов (support vectors), имеющих отступ $M(\mathbf{x},y)\le 1$ при настроенных весах. Опорные вектора на рисунке выделены более тёмным цветом.

От неинформативных объектов (non-informative objects) с отступом $M(\mathbf{x},y)>1$ решение зависеть не будет: их добавление или удаление из выборки никак не изменит решение.

Достоинством метода опорных векторов является то, что формула построения прогноза при решении двойственной задачи оптимизации будет зависеть только от попарных скалярных произведений между объектами (а не от самих объектов):

$$\hat{y}(\mathbf{x})=F(\langle \mathbf{x},\mathbf{x}_1 \rangle, \langle \mathbf{x},\mathbf{x}_2 \rangle,...)$$

Это позволяет применить ядерное обобщение метода (kernel trick, [2]) заменяя операции стандартного скалярного произведения специальными функциями $K(\cdot,\cdot)$, называемыми ядрами Мерсера (Mercer kernel [3]):

$$\hat{y}(\mathbf{x})=F(K(\mathbf{x},\mathbf{x}_1), K(\mathbf{x},\mathbf{x}_2),...)$$

Ядра Мерсера соответствуют обычному скалярному произведению, но не в исходном пространстве признаков $\mathbf{x}$, а в нелинейно преобразованном $\phi(\mathbf{x})$:

$$K(\mathbf{x},\mathbf{x}')=\langle \phi(\mathbf{x}), \phi(\mathbf{x}') \rangle,$$

что соответствует превращению линейного метода опорных векторов в нелинейный метод классификации.

Многоклассовый случай

Метод опорных векторов допускает более общую постановку для решения задачи многоклассовой классификации, см. [4].

Детальнее с алгоритмом опорных векторов вы можете ознакомиться в викиконспектах ИТМО [5].

Пример запуска в Python

Пример запуска метода опорных векторов для 2-х классов:

from sklearn.svm import SVC   
from sklearn.metrics import accuracy_score

X_train, X_test, Y_train, Y_test = get_demo_classification_data()  
model = SVC(C=1)                # инициализация модели, (1/C) - вес при регуляризаторе
model.fit(X_train, Y_train)     # обучение модели   
Y_hat = model.predict(X_test)   # построение прогнозов
print(f'Точность прогнозов: {100*accuracy_score(Y_test, Y_hat):.1f}%')  

# Можно считать информацию по опорным векторам:
print(f'Число опорных векторов к каждом классе: {model.n_support_}')
print(model.support_vectors_[:5])   # выводим первые 5 опорных векторов

model = SVC(kernel='rbf', gamma=1)   # инициализация модели с использованием Гауссова ядра
model.fit(X_train, Y_train)          # обучение модели   
Y_hat = model.predict(X_test)        # построение прогнозов
print(f'Точность прогнозов: {100*accuracy_score(Y_test, Y_hat):.1f}%')    

Больше информации. Полный код.

Литература

1. Cortes C., Vapnik V. Support-vector networks //Machine learning. – 1995. – Т. 20. – С. 273-297.

2. Wikipedia: kernel method.

3. Викиконспекты ИТМО: ядра.

4. Hsu C. W., Lin C. J. A comparison of methods for multiclass support vector machines //IEEE transactions on Neural Networks. – 2002. – Т. 13. – №. 2. – С. 415-425.

5. Викиконспекты ИТМО: метод опорных векторов.