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

Метод опорных векторов (support vector machine, SVM [1]) является одним из самых популярных метод классификации. Его популярности способствует:

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

• Возможность выразить формулу построения прогноза через скалярные произведения одних объектов на другие. Заменяя скалярные произведения на другие функции (из определённого класса) можно обобщить метод, превратив его из линейного классификатора в нелинейный.

Далее мы рассмотрим геометрическое обоснование метода опорных векторов в случае, когда классы линейно разделимы. Потом обобщим метод на случай линейно неразделимых классов. В конце рассмотрим обобщение метода опорных векторов на многоклассовый случай и приведём пример запуска метода в python, используя библиотеку sklearn.

Бинарная классификация

Линейно разделимый случай

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

Как видно на рисунке ниже, в линейно разделимом случае решение будет неоднозначным - существует много гиперплоскостей, разделяющих объекты разных классов:

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

Действительно, при предположении, что объекты одного класса похожи друг на друга, новые объекты красного класса будут появляться рядом с известными представителями красного класса. То же справедливо и для новых представителей зелёного класса. Если гиперплоскость проведена таким образом, чтобы быть максимально удалённой от представителей каждого класса, то вероятность ошибки на новых данных будет ниже!

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

Гиперплоскость $\mathbf{x}^T\mathbf{ w}+w_0=0$ разделяет классы $y\in\{+1,-1\}$, если выполнены следующие условия:

$$\begin{cases} \mathbf{x}_{n}^{T}\mathbf{w}+w_{0}\ge b, & \text{если } y_{n}=+1; \\ \mathbf{x}_{n}^{T}\mathbf{w}+w_{0}\le-b, & \text{если }y_{n}=-1; \\ n=1,2,...N; \end{cases}$$

где $b>0$ - некоторый параметр. Это проиллюстрировано ниже:

Параметры $\mathbf{w},w_0,b$ определены с точностью до общего положительного множителя, поэтому, не ограничивая общности, условие разделимости можно записать в виде:

$$\begin{cases} \mathbf{x}_{n}^{T}\mathbf{w}+w_{0}\ge 1, & y_{n}=+1; \\ \mathbf{x}_{n}^{T}\mathbf{w}+w_{0}\le-1, & y_{n}=-1; \\ n=1,2,...N; \end{cases}$$

где мы разделили неравенства на $b>1$. Это равнозначно выбору $b=1$.

Условие разделимости классов можно эквивалентно записать одной строкой:

$$y_n (\mathbf{x}_n^\top \mathbf{w} + w_0) \geq 1, \quad n = 1, 2, \ldots, N$$

Теперь среди всех гиперплоскостей, разделяющих классы, мы бы хотели выбрать ту, которая будет максимизировать пограничную полосу между классами, называемую зазором (margin). Для этого нужно, чтобы расстояние от ближайших объектов обучающей выборки $\mathbf{x}$ до гиперплоскости $H=\{\mathbf{x}:\mathbf{x}^{T}\mathbf{w}+w_{0}=0\}$ оказалось наибольшим.

Как показывалось ранее, это расстояние равно:

$$\rho(\mathbf{x},H)=\frac{|\mathbf{x}^{T}\mathbf{w}+w_{0}|}{||\mathbf{w}||}$$

Поскольку ближайшие объекты будут лежать на гиперплоскостях $\mathbf{x}_{n}^{T}\mathbf{w}+w_{0}=\pm b$, а $b$ взят равным единице, то расстояние от гиперплоскости до ближайших объектов будет $1/||\mathbf{w}||$, а зазор будет равен $2/||\mathbf{w}||$.

Отсюда получаем оптимизационную задачу для нахождения безошибочного линейного классификатора, обеспечивающего максимизацию зазора:

$$\begin{cases} \frac{2}{\left\lVert \mathbf{w}\right\rVert }\to\underset{\mathbf{w},w_{0}}{\max},\\ y_{n}(\mathbf{x}_{n}^{T}\mathbf{w}+w_{0})\ge 1, \\ n=1,2,...N. \end{cases}$$

Используя свойство

$$\argmax\frac{2}{\left\lVert \mathbf{w}\right\rVert }=\argmin\frac{\left\lVert \mathbf{w}\right\rVert }{2}=\argmin\frac{\left\lVert \mathbf{w}\right\rVert ^{2}}{2},$$

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

$$\begin{cases} \frac{1}{2}\mathbf{w}^{T}\mathbf{w}\to\underset{\mathbf{w},w_{0}}{\min},\\ y_{n}(\mathbf{x}_{n}^{T}\mathbf{w}+w_{0})=M(\mathbf{x}_{n},y_{n})\ge 1, \\ n=1,2,...N. \end{cases} \tag{1}$$

Интуиция оптимизационной задачи

Оптимизационную задачу выше можно проинтерпретировать как нахождение такого линейного классификатора, который:

1. обеспечивает уверенную классификацию всех объектов (с отступом не ниже единицы)

2. является максимально простым за счёт минимизации L2-нормы весов.

Заметим, что решение будет зависеть только от объектов, имеющих отступ $y_{n}(\mathbf{x}_{n}^{T}\mathbf{w}+w_{0})=M(\mathbf{x}_{n},y_{n})= 1$, которые лежат на гиперплоскостях

$$y_n (\mathbf{x}_n^\top \mathbf{w} + w_0) = \pm 1$$

и называются опорными векторами (support vectors).

Включение/исключение других объектов с отступом $M(\mathbf{x}_{n},y_{n})>1$ не будет оказывать влияния на решение, поэтому такие объекты называются неинформативными (non-informative).

Линейно неразделимый случай

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

Синими векторами помечены объекты, нарушающие условия разделимости:

$$y_n (\mathbf{x}_n^\top \mathbf{w} + w_0) \geq 1, \quad n = 1, 2, \ldots, N.$$

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

Чтобы находить решение и для случая линейно неразделимых данных, каждому объекту разрешается отклоняться от требования

$$y_{n}(\mathbf{x}_{n}^{T}\mathbf{w}+w_{0})=M(\mathbf{x}_{n},y_{n}) \ge 1$$

на величину нарушения $\xi_n \ge 0$. При этом, чтобы минимизировать возможные нарушения, суммарная величина всех нарушений штрафуется в оптимизационном критерии, что даёт оптимизационную задачу метода опорных векторов в линейно неразделимом случае:

$$\begin{cases} \frac{1}{2}\mathbf{w}^{T}\mathbf{w}+{\color{red}C\sum_{n=1}^{N}\xi_{n}}\to\min_{\mathbf{w},w_{0},{\color{red}\bm{\xi}}}\\ y_{n}(\mathbf{w}^{T}\mathbf{x}_{n}+w_{0})=M(\mathbf{x}_{n},y_{n})\ge1{\color{red}-\xi_{n}},\\ {\color{red}\xi_{n}\ge0,\,n=1,2,...N} \end{cases} \tag{2}$$

Эта задача для любых данных всегда имеет решение при достаточно больших нарушениях $\xi_n$ и представляет собой итоговую оптимизационную задачу по умолчанию для метода опорных векторов.

Гиперпараметр $C\ge 0$ управляет противоречием между точностью модели и её простотой. Подумайте как именно.

В отличие от задачи (1), в (2) оптимизация дополнительно производится по величинам нарушений $\bm{\xi}=[\xi_1,\xi_2,...\xi_N]$, оптимальные значения для которых легко найти:

$$\xi^*_n=\max\{0,1-M_{n}(\mathbf{w},w_{0})\}, \tag{3}$$

поскольку

• $\xi^*_n\ge 0$;

• при $M_{n}(\mathbf{w},w_{0})\ge 1$ неравенство на отступ в (2) не нарушено, и $\xi^*_n=0$;

• при $M_{n}(\mathbf{w},w_{0})<1$ $\xi^*_n$ должно выбираться минимально возможным, чтобы удовлетворить неравенству, то есть равным $1-M_{n}(\mathbf{w},w_{0})$.

Подставляя оптимальные значения $\bm{\xi}^*$ из (3) в (2), получим эквивалентную безусловную задачу оптимизации:

$$\frac{1}{2C}\left\lVert \mathbf{w}\right\rVert _{2}^{2}+\sum_{n=1}^{N}\max\{0,1-M_{n}(\mathbf{w},w_{0})\}\to\min_{\mathbf{w},w_{0}} \tag{4}$$

что соответствует оценке линейного бинарного классификатора

• с функцией потерь hinge;

• и L2-регуляризацией.

L1-SVM

В качестве популярной вариации метода опорных векторов используется метод L1-SVM [2], в котором веса штрафуются не по квадрату L2-нормы, а по L1-норме, что даёт следующую задачу условной оптимизации:

$$\begin{cases} ||\mathbf{w}||_1+C\sum_{n=1}^{N}\xi_{n}\to\min_{\mathbf{w},w_{0},\bm{\xi}}\\ y_{n}(\mathbf{w}^{T}\mathbf{x}_{n}+w_{0})=M_{n}(\mathbf{w},w_{0})\ge1-\xi_{n},\\ \xi_{n}\ge 0,\,n=1,2,...N, \end{cases}$$

которая эквивалентная безусловной оптимизации:

$$\frac{1}{C}\left\lVert \mathbf{w}\right\rVert_1 +\sum_{n=1}^{N}\max\{0,1-M_{n}(\mathbf{w},w_{0})\}\to\min_{\mathbf{w},w_{0}}$$

Штраф весов по L1-норме способен в точности занулять веса при оптимизации, что делает прогноз зависимым лишь от части наиболее информативных признаков. Такая возможность полезна, когда заранее известно, что используется много слабо информативных и нерелевантных признаков.

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

Рассмотрим многоклассовую классификацию, в которой $y\in\{1,2,...C\}$. Решить эту задачу можно набором бинарных классификаторов, как описано в следующей главе.

Однако для метода опорных векторов существует модификация, позволяющая производить многоклассовую классификацию напрямую (multiclass support vector machines [3]).

В предложенном подходе настраиваются коэффициенты многоклассового классификатора с функциями рейтинга для каждого класса:

$$g_{c}(\mathbf{x})=(\mathbf{w}^{c})^{T}\mathbf{x}+w_{0}^{c},\qquad c=1,2,...C$$

Прогноз строится, назначая класс, обладающий максимальным рейтингом.

Линейно разделимый случай

В линейно разделимом случае веса предлагается находить из следующей оптимизационной задачи:

$$\begin{cases} \sum_{c=1}^{C}(\mathbf{w}^{c})^{T}\mathbf{w}^{c}\to\min_{\{ \mathbf{w}^{c},w^{c}_0\}_{c}}\\ (\mathbf{w}^{y_{n}})^{T}\mathbf{x}_{n}+w_{0}^{y_{n}}-(\mathbf{w}^{c})^{T}\mathbf{x}-w_{0}^{c}\ge1\quad\forall c\ne y_{n},\\ n=1,2,...N \end{cases}$$

По сути требуется найти найти максимально простой классификатор (по L2-норме весов), выдающий рейтинги для верных классов, которые хотя бы на единицу превосходят рейтинги для неправильных классов.

Линейно неразделимый случай

В более общем линейно неразделимом случае (по умолчанию) объектам разрешается отклоняться от ограничения на рейтинги на величины нарушений $\bm{\xi}=[\xi_1,\xi_2,...\xi_N]$, которые штрафуются по величине:

$$\begin{cases} \sum_{c=1}^{C}(\mathbf{w}^{c})^{T}\mathbf{w}^{c}{\color{red}+C\sum_{n=1}^{N}\xi_{n}}\to\min_{\{ \mathbf{w}^{c},w^{c}_0\}_{c},\bm{\xi}} \\ (\mathbf{w}^{y_{n}})^{T}\mathbf{x}_{n}+w_{0}^{y_{n}}-(\mathbf{w}^{c})^{T}\mathbf{x}_{n}-w_{0}^{c}\ge1-{\color{red}\xi_{n}}\quad\forall c\ne y_{n},\\ {\color{red}\xi_{n}\ge 0},\quad n=1,2,...N \end{cases} \tag{5}$$

Последнюю задачу можно эквивалентно переписать в виде безусловной оптимизации, как показано ниже.

Переход к безусловной оптимизации

Из второго ограничения (5):

$$\xi_n \ge 1 - \big[ (\mathbf{w}^{y_n})^{T} \mathbf{x}_{n} + w_{0}^{y_{n}} - (\mathbf{w}^{c})^{T} \mathbf{x}_{n} - w_{0}^c \big], \quad \forall c \ne y_n$$

Следовательно, чтобы удовлетворить всем условиям, $\xi_n$ должно быть не меньше максимального нарушения по всем $c \ne y_n$:

$$\xi_n \ge \max_{c \ne y_n} \left[ 1 - (\mathbf{w}^{y_n})^{T} \mathbf{x}_{n} - w_{0}^{y_{n}} + (\mathbf{w}^{c})^{T} \mathbf{x}_{n} + w_{0}^c \right]$$

С учётом $\xi_n \ge 0$ получаем:

$$\xi_n = \max\Big\{0, \; \max_{c \ne y_n} \big[ 1 - (\mathbf{w}^{y_n})^{T} \mathbf{x}_{n} - w_{0}^{y_{n}} + (\mathbf{w}^{c})^{T} \mathbf{x}_{n} + w_{0}^c \big] \Big\}$$

Это обобщение функции потерь hinge на многоклассовый случай:

$$\mathcal{L}(y_n, f(\mathbf{x}_n)) = \max\Big\{0, \; \max_{c \ne y_n} \big[ 1 - (\mathbf{w}^{y_n})^{T} \mathbf{x}_{n} - w_{0}^{y_{n}} + (\mathbf{w}^{c})^{T} \mathbf{x}_{n} + w_{0}^c \big] \Big\},$$

где $f(\mathbf{x}_n)$ — вектор оценок рейтингов для всех классов.

Подставив $\xi_n = \mathcal{L}(y_n, f(\mathbf{x}_n))$ в функционал, получим:

$$\sum_{c=1}^C (\mathbf{w}^c)^T \mathbf{w}^c \;+\; C \sum_{n=1}^N \mathcal{L}\big(y_n, f(\mathbf{x}_n)\big) \to\min_{\{ \mathbf{w}^{c},w^{c}_0\}_{c}}$$

В [4] приводится эмпирическое сравнение различных вариантов многоклассового метода опорных векторов.

Обобщение метода через ядра

Решение условных задач оптимизации (2) и (5), используя условия Каруша-Куна-Таккера [5], можно свести к двойственной задаче оптимизации, из которой формулу построения прогноза можно выразить как зависимость не от самих признаковых описаний объектов, а от попарных скалярных произведений между объектами:

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

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

$$\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,$$

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

Дополнительно ознакомиться с методом опорных векторов можно [8].

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

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

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. Zhu J. et al. 1-norm support vector machines //Advances in neural information processing systems. – 2003. – Т. 16.

3. Crammer K., Singer Y. On the algorithmic implementation of multiclass kernel-based vector machines //Journal of machine learning research. – 2001. – Т. 2. – №. Dec. – С. 265-292.

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. Wikipedia: Условия Каруша — Куна — Таккера.

6. Wikipedia: kernel method.

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

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